Оптимизация запросов

Оптимизация запросов

# Обзор обработки запросов
шаги:
 компилирует и преобразует инструкцию SQL в выражение, состоящее из логических операций высокого уровня, называемое логический план;
 оптимизирует логический план и превращает его в план выполнения;
 выполняет (интерпретирует) план и возвращает результаты

Вывод компилятора запросов – это выражение, состоящее из высокоуровневых операций, которые остаются декларативными – они не дают 
никаких инструкций о том, как получить требуемый результат. 

Оптимизатор выполняет два вида преобразований: заменяет логические операции на алгоритмы выполнения и, возможно, 
изменяет структуру логического выражения, меняя порядок выполнения логических операций. 

Наконец, план выполнения запроса интерпретируется движком выполнения запроса, который в сообществе PostgreSQL часто называют 
исполнителем, и вывод возвращается в клиентское приложение. 

# Реляционные операции
Центральная концепция реляционной теории – отношение. Для наших целей мы рассматриваем отношение в виде таблицы. 

Любая реляционная операция принимает одно или несколько отношений в качестве аргументов и порождает еще одно отношение в качестве 
результата. Это результирующее отношение можно использовать как аргумент другой реляционной операции, порождая следующее отношение, 
которое, в свою очередь, тоже может стать аргументом. Таким образом, мы можем создавать сложные выражения и представлять сложные запросы. 

Фильтрация, проекция и произведение:
 Фильтрацию часто называют селекцией, а в реляционной теории – ограничением. Результат представляет собой множество записей, то есть 
тоже отношение. 
 Проекция также принимает одно отношение в качестве аргумента и удаляет некоторые атрибуты (столбцы). Реляционная проекция удаляет из 
результата все дубликаты, но проекция SQL этого не делает.
 Произведение (также называемое декартовым произведением) порождает множество всех пар строк из первого и второго аргументов. 

 Соединение можно выразить как произведение, за которым следует фильтрация. 
 К реляционным операциям также относятся группировка, объединение, пересечение и разность множеств. 

Последний элемент реляционной теории, который нужен для оптимизации, – правила эквивалентности. 
 коммутативность – JOIN(R,S) = JOIN (S,R). 
 ассоциативность – JOIN(R, JOIN(S,T) = JOIN(JOIN(R,S), T). 
 дистрибутивность – JOIN(R, UNION(S, T)) = UNION(JOIN(R,S), JOIN(R, T)). 

# Логические операции
Набор логических операций, необходимых для представления SQL-запросов, включает в  себя все реляционные операции, но с другой 
семантикой. Как отмечалось ранее, проекция SQL не удаляет дубликаты; для удаления дубликатов включена отдельная операция. 
Другие дополнительные операции необходимы для представления конструкций SQL, которые нельзя выразить в реляционной теории, например 
левое, правое и полное внешние соединения дают результат, который не является отношением (но является таблицей SQL). 
Многие правила эквивалентности также действительны и для логических операций. 

# Операции и алгоритмы
Чтобы сделать запрос исполняемым, логические операции необходимо заменить физическими (которые также называют алгоритмами). Когда мы 
переходим с логического уровня на физический, математические отношения превращаются в таблицы, которые хранятся в базе данных, и нам 
нужно определить способы получения данных из этих таблиц. 

----------------------------------------------------------------------------------------------------------------------------------------

# Алгоритмы доступа к данным
Любой файл, используемый для объектов базы данных, делится на блоки одинаковой длины; 
по умолчанию PostgreSQL использует блоки по 8192 байта каждый.

Объекты базы данных состоят из логических элементов (строк таблиц, индексных записей и т. д.).
PostgreSQL выделяет место для этих элементов блоками. Несколько мелких элементов могут находиться в одном блоке;
более крупные элементы могут быть распределены между несколькими блоками.

Распределение элементов по блокам также зависит от типа объекта базы данных.
Строки таблицы хранятся с использованием структуры данных, называемой кучей (heap):
строка может быть вставлена в любой блок, в котором достаточно свободного места, без специального упорядочивания.

# Полное (последовательное) сканирование
При полном сканировании движок базы данных последовательно считывает все строки в таблице и для каждой строки проверяет условие фильтрации. 
Полностью просканировать можно любую таблицу; для этого не нужны дополнительные структуры данных. Остальные алгоритмы зависят от наличия 
индексов в таблице, как описано ниже. 

# Доступ к таблицам на основе индексов
Все реляционные базы данных, включая PostgreSQL, позволяют создавать дополнительные, избыточные структуры, 
значительно ускоряя доступ к данным по сравнению с простым последовательным чтением. 
Эти дополнительные структуры называются индексами. 

Во-первых, индексы – «избыточные» объекты базы данных; они не хранят никакой дополнительной информации, которую 
нельзя найти в исходной таблице. 
Во-вторых, индексы предоставляют дополнительные пути доступа к данным; они позволяют определить, 
какие значения хранятся в строках таблицы, без необходимости чтения самой таблицы – так работает доступ на основе индексов. 

Если условие (или условия) фильтрации поддерживается индексом в таблице, индекс можно использовать для доступа к данным из этой таблицы. 
Алгоритм извлекает список указателей на блоки, содержащие строки со значениями, удовлетворяющими условию фильтрации, 
и только эти блоки читаются из таблицы. 

Основная структура данных таблицы – это куча, то есть строки хранятся неупорядоченно. 
Есть две отдельные физические операции, используемые PostgreSQL для получения строк с помощью индексов: 
индексное сканирование (index scan) и сканирование по битовой карте (bitmap heapscan). 

При индексном сканировании движок базы данных считывает одну за другой все записи индекса, которые удовлетворяют условию фильтрации, 
и в этом же порядке извлекает блоки. 

Поскольку базовая таблица представляет собой кучу, несколько записей индекса могут указывать на один и тот же блок. 
Чтобы избежать многократного чтения одного и того же блока, в PostgreSQL реализована операция сканирования по битовой карте, 
которая создает битовую карту блоков, содержащих необходимые строки. Потом все строки в этих блоках фильтруются. 

Стоимостная модель этого алгоритма: при малых значениях селективности, скорее всего, все строки, удовлетворяющие условиям фильтрации, 
будут располагаться в разных блоках, и, следовательно, стоимость будет пропорциональна количеству возвращаемых строк. 
Для больших значений селективности количество обрабатываемых блоков приближается к общему количеству блоков. 
В последнем случае стоимость становится выше, чем стоимость полного сканирования, поскольку для доступа к индексу необходимы ресурсы. 

# Сканирование только индекса
Операции доступа к  данным не обязательно возвращают полные строки. Если некоторые столбцы не нужны для запроса, их можно опустить, 
как только строка пройдет условия фильтрации (если таковые имеются). Говоря более формально, это означает, 
что логическая проекция сочетается с доступом к данным. Такое сочетание особенно полезно, если индекс, используемый для фильтрации, 
содержит все столбцы, необходимые для запроса. 

Алгоритм считывает данные из индекса и применяет оставшиеся условия фильтрации, если это необходимо. 
Для малых значений селективности стоимость примерно пропорциональна количеству возвращаемых строк. 
При больших значениях селективности алгоритм выполняет (почти) полный просмотр индекса. 
Стоимость просмотра индекса обычно ниже, чем стоимость полного просмотра таблицы, потому что индекс содержит меньше данных. 

# Индексные структуры
Этот раздел начинается с абстрактного определения того, какую структуру хранения можно назвать индексом; 
кратко рассматриваются наиболее распространенные индексные структуры, такие как деревья и хеш-индексы.
Поскольку индекс избыточен, он должен обновляться при обновлении данных таблицы. 

# B-деревья
Дерево состоит из иерархически организованных узлов, связанных с блоками, хранящимися на диске. 
Любой поиск ключа K начинается с корневого узла B-дерева. Во время поиска по блоку будет найден самый большой ключ P, не превышающий K, 
и затем поиск продолжается в блоке, на который ссылается указатель, связанный с P. Поиск продолжается, пока мы не дойдем до листового 
узла, где указатели ссылаются на строки таблицы. Количество просмотренных при поиске узлов равно глубине дерева.

B-деревья также поддерживают поиск по диапазону (представляемый операцией between в SQL). Как только будет найдена нижняя граница 
диапазона, все индексные ключи диапазона можно получить последовательным сканированием листовых узлов до тех пор, пока не будет 
достигнута верхняя граница диапазона. Сканирование листовых узлов необходимо также для получения всех указателей, если индекс не 
является уникальным (то есть значение индексного ключа может соответствовать более чем одной строке). 

B-деревья можно изменять без значительных накладных расходов. Когда вы вставляете запись, реструктуризация ограничена одним блоком. 
Если емкость блока превышена, то он расщепляется на два блока, и обновление распространяется на верхние уровни. Даже в худшем случае 
количество измененных блоков не будет превышать глубины дерева. Индекс с шестью-семью уровнями может вместить миллиарды записей.

# Битовые карты
Битовая карта – это вспомогательная структура данных, которая используется внутри PostgreSQL с разными целями. 
Битовые карты можно рассматривать как своего рода индекс: они созданы для облегчения доступа к другим структурам данных, 
содержащим несколько блоков. Обычно битовые карты используются для компактного представления свойств табличных данных. 
Чаще всего битовая карта содержит по одному биту для каждого блока (8192 байта). 
Значение бита равно 1, если блок обладает нужным свойством, и 0, если нет. 

Движок базы данных начинает со сканирования (как пример двух) индексов и построения для каждого из них битовой карты, 
которая указывает на блоки с подходящими табличными строками. 

Как только битовые карты будут созданы, движок выполняет побитовую операцию «и»/«или», чтобы найти блоки, содержащие подходящие 
значения для обоих критериев отбора. Наконец, сканируются блоки данных, соответствующие единицам в полученной битовой карте. 

Битовые карты очень компактны; однако для очень больших таблиц они могут занимать много блоков. 

# Хеш-индекс
Хеш-индекс использует хеш-функцию для вычисления адреса индексного блока, содержащего индексный ключ. Для условия равенства этот тип 
индекса работает быстрее B-дерева, однако он совершенно бесполезен для запросов по диапазону. 
Стоимостная оценка поиска по хеш-индексу не зависит от размера индекса (в отличие от логарифмической зависимости для B-деревьев). 

# R-дерево
R-дерево поддерживает поиск по пространственным данным. Индексный ключ для R-дерева всегда представляет собой прямоугольник в 
многомерном пространстве. Поиск возвращает все объекты, имеющие непустое пересечение с прямоугольником запроса. 
Структура R-дерева похожа на структуру B-дерева; однако расщепление переполненных узлов устроено намного сложнее. R-деревья 
эффективны для небольшого числа измерений (обычно от двух до трех). 

# Другие типы индексов
Другие типы индексов, доступные в PostgreSQL, полезны для полнотекстового поиска, поиска в очень больших таблицах и многого другого. 

# Алгоритмы
## Вложенные циклы
Алгоритм вложенного цикла с индексным доступом обычно предпочтителен, если количество строк в таблице R тоже мало. 
Однако доступ на основе индекса становится неэффективным, когда количество строк, подлежащих обработке, увеличивается.

##Алгоритмы на основе хеширования
Алгоритм на основе хеширования значительно лучше вложенных циклов подходит для больших таблиц и большого количества различных значений 
атрибута соединения. Например, если атрибут соединения в одной из входных таблиц уникален, то последнее слагаемое всего лишь будет 
равно размеру другой таблицы. 

## Сортировка слиянием
Алгоритм сортировки слиянием особенно эффективен, если одна или обе входные таблицы уже отсортированы. 
Это может произойти в серии соединений по одним и тем же атрибутам.

----------------------------------------------------------------------------------------------------------------------------------------