К настоящему времени внимательным читателям, не пропустившим ни одной статьи, возможно, не терпится. Мы уже перешли к третьей статье - и до сих пор говорим о теории! Когда же мы будем писать SQL код?
Очень скоро! В этой статье рассматривается последняя часть обработки запросов, и в конце у нас будет все необходимое для понимания планов выполнения.
Во второй статье рассказывается о реляционных операциях, и в ней говорится, что для выполнения запросов нужны физические операции, или алгоритмы. Сопоставить эти алгоритмы с логическими операциями непросто; иногда сложная логическая операция заменяется несколькими физическими операциями, или несколько логических операций объединяются в одну физическую.
В этой главе мы описываем эти алгоритмы, начиная с алгоритмов извлечения данных, а затем переходим к алгоритмам для более сложных операций.
Понимание этих алгоритмов позволит нам вернуться к планам выполнения и лучше понять их компоненты. Таким образом, мы будем всего в одном шаге от нашей цели, которая состоит в том, чтобы научиться настраивать запросы.
стоимостные модели алгоритмов
В первой статье упоминалось несколько способов измерения производительности системы, включая время отклика, стоимость и удовлетворенность пользователей. Эти показатели являются внешними по отношению к базе данных, и хотя внешние показатели наиболее ценны, они не доступны оптимизатору запросов.
Вместо этого оптимизатор использует внутренние показатели, основанные на объеме вычислительных ресурсов, необходимых для выполнения запроса или отдельной физической операции в рамках плана. Наиболее важными ресурсами являются те, что влияют на время выполнения, а именно циклы процессора и количество операций ввода-вывода (чтение и запись дисковых блоков). Другие ресурсы, такие как память или дисковое пространство, тоже косвенно влияют на время выполнения; например, количество доступной памяти будет влиять на соотношение циклов процессора и количество операций ввода-вывода. Распределение памяти контролируется параметрами сервера и здесь не рассматривается.
Эти два основных показателя, циклы процессора и количество операций ввода-вывода, напрямую не сопоставимы. Однако для сравнения планов выполнения запросов оптимизатор объединяет их в одну функцию стоимости: чем ниже стоимость, тем лучше план.
В течение нескольких десятилетий количество операций ввода-вывода было доминирующим компонентом стоимости, потому что вращающиеся жесткие диски работают на порядки медленнее, чем процессор. Но для современного оборудования это не обязательно так, поэтому оптимизатор должен быть настроен на использование правильного соотношения. Это также контролируется параметрами сервера.
Стоимостная модель физической операции оценивает ресурсы, необходимые для выполнения операции. Как правило, стоимость зависит от таблиц, указанных в качестве аргументов операции. Для представления стоимостных моделей мы будем использовать простые формулы со следующими обозначениями: для любой таблицы или отношения R символы TR и BR обозначают количество строк в таблице и количество дисковых блоков, занимаемых таблицей, соответственно. Дополнительные обозначения будут вводиться по мере необходимости.
В следующем разделе обсуждаются физические операции и рассматриваются алгоритмы и стоимостные модели для каждой из них. Поскольку относительная скорость процессора и внешнего хранилища может варьироваться в широких пределах, затраты на процессор и ввод-вывод рассматриваются отдельно. Мы не будем говорить про логические операции проекции и фильтрации, которые обсуждали в предыдущей статье. Обычно они объединяются с предшествующей им операцией, потому что могут применяться независимо к каждой строке, не завися от других строк в таблице аргумента.
алгоритмы достуПа к данным
Чтобы начать выполнение запроса, движок должен извлечь сохраненные данные. Этот раздел касается алгоритмов, используемых для чтения данных из объектов базы данных. На практике эти операции часто сочетаются с последующей операцией в плане выполнения запроса. Это выгодно в тех случаях, когда можно сэкономить время выполнения, избегая чтения, которое впоследствии будет отфильтровано.
Эффективность таких операций зависит от соотношения количества строк, составляющих результат операции, к общему количеству строк в сохраненной таблице. Такое соотношение называется селективностью (избирательностью). Выбор алгоритма для определенной операции чтения зависит от селективности фильтров, которые могут применяться одновременно.
Представление данных
Неудивительно, что данные хранятся в файлах на жестких дисках. Любой файл, используемый для объектов базы данных, делится на блоки одинаковой длины; по умолчанию PostgreSQL использует блоки по 8192 байта каждый. Блок - это единица, которая передается между жестким диском и оперативной памятью, а количество операций ввода-вывода, необходимое для выполнения любого доступа к данным, равно количеству блоков, которые читаются или записываются.
Объекты базы данных состоят из логических элементов (строк таблиц, индексных записей и т. д.). PostgreSQL выделяет место для этих элементов блоками. Несколько мелких элементов могут находиться в одном блоке; более крупные элементы могут быть распределены между несколькими блоками. Общая структура блока показана на рис. 3.1.
Рис. 3.1 ❖ Общая структура блока в PostgreSOL
Распределение элементов по блокам также зависит от типа объекта базы данных. Строки таблицы хранятся с использованием структуры данных, называемой кучей (heap): строка может быть вставлена в любой блок, в котором достаточно свободного места, без специального упорядочивания. Другие объекты (например, индексы) могут использовать блоки иначе.
Полное (последовательное) сканирование
При полном сканировании движок базы данных последовательно считывает все строки в таблице и для каждой строки проверяет условие фильтрации. Чтобы оценить стоимость этого алгоритма, требуется более подробное описание, показанное псевдокодом в листинге 3.1.
Листинг 3.1 ❖ Псевдокод алгоритма доступа к данным полным сканированием
FOR each block IN a_table LOOP
read block
FOR each row IN block LOOP
IF filter_condition (row)
THEN output (row)
END IF
END LOOP
END LOOP
Количество операций ввода-вывода равно BR; общее количество итераций внутреннего цикла равно TR. Нам также необходимо оценить стоимость операций, порождающих выходные строки. Она зависит от селективности (которая обозначается S) и равняется S * TR. Собрав все эти части воедино, мы можем вычислить стоимость полного сканирования:
c1 * BR + c2 * TR + c3 * S * TR,
где константы c1, c2 и c3 представляют характеристики аппаратного обеспечения.
Полностью просканировать можно любую таблицу; для этого не нужны дополнительные структуры данных. Остальные алгоритмы зависят от наличия индексов в таблице, как описано ниже.
Доступ к таблицам на основе индексов
Обратите внимание, что пока мы не перешли к физическим операциям, мы даже не упоминали алгоритмы доступа к данным. Нам не нужно «читать» отношения - это абстрактные объекты. Если следовать идее того, что отношения отображаются в таблицы, нет другого способа получить данные, кроме как прочитать всю таблицу в оперативную память. Как еще мы узнаем, какие значения содержатся в каких строках? Но реляционные базы данных не были бы таким мощным инструментом обработки данных, если бы на этом мы и остановились. Все реляционные базы данных, включая PostgreSQL, позволяют создавать дополнительные, избыточные структуры, значительно ускоряя доступ к данным по сравнению с простым последовательным чтением.
Эти дополнительные структуры называются индексами.
Как создаются индексы, мы рассмотрим позже; пока нам нужно знать два факта, касающихся индексов. Во-первых, индексы - «избыточные» объекты базы данных; они не хранят никакой дополнительной информации, которую нельзя найти в исходной таблице.
Во-вторых, индексы предоставляют дополнительные пути доступа к данным; они позволяют определить, какие значения хранятся в строках таблицы, без необходимости чтения самой таблицы - так работает доступ на основе индексов. И как упоминалось ранее, это происходит полностью прозрачно для приложения.
Если условие (или условия) фильтрации поддерживается индексом в таблице, индекс можно использовать для доступа к данным из этой таблицы. Алгоритм извлекает список указателей на блоки, содержащие строки со значениями, удовлетворяющими условию фильтрации, и только эти блоки читаются из таблицы.
Чтобы получить строку таблицы по указателю, необходимо прочитать блок, содержащий эту строку. Основная структура данных таблицы - это куча, то есть строки хранятся неупорядоченно. Их порядок не гарантирован и не соответствует свойствам данных. Есть две отдельные физические операции, используемые PostgreSQL для получения строк с помощью индексов: индексное сканирование (index scan) и сканирование по битовой карте (bitmap heap scan). При индексном сканировании движок базы данных считывает одну за другой все записи индекса, которые удовлетворяют условию фильтрации, и в этом же порядке извлекает блоки. Поскольку базовая таблица представляет собой кучу, несколько записей индекса могут указывать на один и тот же блок. Чтобы избежать многократного чтения одного и того же блока, в PostgreSQL реализована операция сканирования по битовой карте, которая создает битовую карту блоков, содержащих необходимые строки. Потом все строки в этих блоках фильтруются. Преимущество реализации PostgreSQL состоит в том, что она упрощает использование нескольких индексов в одной и той же таблице в одном запросе, применяя логические операторы «и» и «или» к битовым картам блоков, порождаемым каждым индексом.
Стоимостная модель этого алгоритма намного сложнее. Неформально ее можно описать так: при малых значениях селективности, скорее всего, все строки, удовлетворяющие условиям фильтрации, будут располагаться в разных блоках, и, следовательно, стоимость будет пропорциональна количеству возвращаемых строк. Для больших значений селективности количество обрабатываемых блоков приближается к общему количеству блоков. В последнем случае стоимость становится выше, чем стоимость полного сканирования, поскольку для доступа к индексу необходимы ресурсы.
Сканирование только индекса
Операции доступа к данным не обязательно возвращают полные строки. Если некоторые столбцы не нужны для запроса, их можно опустить, как только строка пройдет условия фильтрации (если таковые имеются). Говоря более формально, это означает, что логическая проекция сочетается с доступом к данным. Такое сочетание особенно полезно, если индекс, используемый для фильтрации, содержит все столбцы, необходимые для запроса.
Алгоритм считывает данные из индекса и применяет оставшиеся условия фильтрации, если это необходимо. Обычно не нужно обращаться к табличным данным, но иногда необходимы дополнительные проверки - мы подробно рассмотрим эту тему в главе 5.
Стоимостная модель сканирования только индекса аналогична модели для доступа к таблице на основе индекса, за исключением того, что не нужно обращаться к данным таблицы. Для малых значений селективности стоимость примерно пропорциональна количеству возвращаемых строк. При больших значениях селективности алгоритм выполняет (почти) полный просмотр индекса. Стоимость просмотра индекса обычно ниже, чем стоимость полного просмотра таблицы, потому что индекс содержит меньше данных.
Сравнение алгоритмов доступа к данным
Выбор лучшего алгоритма доступа к данным в основном зависит от селективности запроса. Отношение стоимости к селективности для различных алгоритмов доступа к данным показано на рис. 3.2. Мы намеренно ограничиваемся качественным сравнением; все числа на этом графике опущены, поскольку они зависят от аппаратного обеспечения и размера таблицы.
Рис. 3.2 ❖ Связь стоимости и селективности запросов для разных алгоритмов доступа к данным
Линия, соответствующая полному сканированию, прямая и почти горизонтальная: ее рост происходит из-за генерации выходных строк. Как правило, стоимость генерации незначительна по сравнению с другими затратами для этого алгоритма.
Линия, обозначающая стоимость доступа к таблице на основе индекса, начинается (почти) с нуля и быстро растет с ростом селективности. Рост замедляется при больших значениях селективности, где стоимость этого алгоритма значительно выше, чем стоимость полного сканирования.
Самым интересным моментом является пересечение двух линий: для меньших значений селективности предпочтительнее доступ на основе индексов, а полное сканирование лучше подходит для больших значений селективности. Точное положение пересечения зависит от аппаратного обеспечения и может зависеть от размера таблицы. Для относительно медленных вращающихся дисков доступ на основе индексов предпочтительнее, только если селективность не превышает 2-5 %. Для твердотельных накопителей или виртуального окружения это значение может быть выше. На старых вращающихся дисках произвольный доступ к блокам может быть на порядок медленнее последовательного доступа, поэтому дополнительные накладные расходы на индексы при той же пропорции строк получаются выше.
Линия, соответствующая сканированию только индекса, располагается в самой нижней части графика, а это означает, что предпочтительно использовать этот алгоритм, если он применим (то есть все необходимые столбцы находятся в индексе).
Оптимизатор запросов оценивает селективность запроса и селективность, соответствующую точке пересечения для данной таблицы и данного индекса. Условие фильтрации запроса, показанного в листинге 3.2, выбирает значительную часть таблицы.
Листинг 3.2 ❖ Фильтрация по диапазону, выполняемая полным сканированием таблицы
SELECT flight_no, departure_airport, arrival_airport
FROM flight
WHERE scheduled_departure BETWEEN '2020-05-15' AND '2020-08-31';
В данном случае оптимизатор выбирает полное сканирование (см. рис. 3.3).
Рис. 3.3 ❖ Последовательное сканирование
Однако меньший диапазон в том же запросе приводит к доступу к таблице на основе индекса. Запрос показан в листинге 3.3, а его план выполнения - на рис. 3.4.
Листинг 3.3 ❖ Фильтрация по диапазону с доступом к таблице на основе индекса
SELECT flight_no, departure_airport, arrival_airport
FROM flight
WHERE scheduled_departure BETWEEN '2020-08-12' AND '2020-08-13';
На самом деле работа оптимизатора запросов намного сложнее: условия фильтрации могут поддерживаться несколькими индексами с разными значениями селективности. Несколько индексов могут быть объединены для создания битовой карты, уменьшая число блоков, которые нужно просканировать. В результате количество вариантов, доступных оптимизатору, значительно превышает выбор из трех алгоритмов.
Рис. 3.4 ❖ Сканирование по битовой карте (доступ на основе индекса)
Таким образом, среди алгоритмов доступа к данным нет победителей и проигравших. Любой алгоритм может выиграть при определенных условиях. Далее, выбор алгоритма зависит от структур хранения и статистических свойств данных. База данных поддерживает для таблиц метаданные, называемые статистикой: информация о кардинальности столбца, разреженности и т. д. Обычно эта статистика неизвестна во время разработки приложения и может изменяться на протяжении жизненного цикла приложения. Следовательно, декларативный характер языка запросов важен для производительности системы. В частности, при изменении статистики таблицы или при корректировке других факторов стоимости для одного и того же запроса может быть выбран другой план выполнения.
индексные структуры
Этот раздел начинается с абстрактного определения того, какую структуру хранения можно назвать индексом; кратко рассматриваются наиболее распространенные индексные структуры, такие как деревья и хеш-индексы, и затрагиваются некоторые особенности PostgreSQL.
Мы покажем, как оценить масштаб улучшений для разных типов индексов и как распознать случаи, когда использование индекса не дает никаких преимуществ в смысле производительности.
Что такое индекс?
Можно предположить, что любой человек, работающий с базами данных, знает, что такое индекс. Увы, удивительно много людей - разработчиков баз данных и составителей отчетов, а в некоторых случаях даже администраторов баз данных - используют индексы и даже создают их, лишь поверхностно представляя, что это за объекты и какова их структура. Во избежание недоразумений мы начнем с определения того, что мы подразумеваем под индексом.
Существует множество типов индексов, поэтому мы ориентируемся не на структурные свойства, а определяем индекс по способу его использования. Структура данных называется индексом, если:
- это избыточная структура данных;
- она невидима для приложения;
- она предназначена для ускорения выбора данных по определенным критериям.
Избыточность означает, что индекс можно удалить без потери данных и восстановить по информации, хранящейся где-то еще (конечно, в таблицах). Невидимость означает, что приложение не может узнать о наличии индекса или о его отсутствии. Иначе говоря, любой запрос дает те же результаты как с индексом, так и без него. И наконец, индекс создается в надежде (или с уверенностью), что это улучшит производительность конкретного запроса или (что еще лучше!) нескольких запросов.
Улучшение производительности не происходит бесплатно. Поскольку индекс избыточен, он должен обновляться при обновлении данных таблицы. Это приводит к накладным расходам для операций обновления, которыми иногда нельзя пренебречь. В частности, индексы PostgreSQL могут оказывать большое влияние на операцию очистки (VACUUM). Однако многие учебники по базам данных переоценивают эти расходы. Современные высокопроизводительные СУБД используют алгоритмы, которые снижают стоимость обновлений индексов, поэтому несколько индексов в таблице - обычное дело.
Хотя индексные структуры могут значительно различаться для разных типов индексов, ускорение всегда достигается за счет быстрой проверки некоторых условий фильтрации, указанных в запросе. Такие условия фильтрации устанавливают определенные ограничения на атрибуты таблицы. На рис. 3.5 показана структура наиболее распространенных индексов.
В правой части рисунка показана таблица, а в левой - индекс, который можно рассматривать как особый вид таблицы. Каждая строка индекса состоит из индексного ключа и указателя на строку таблицы. Значение ключа обычно совпадает со значением атрибута таблицы. В примере на рис. 3.5 в качестве значения используется код аэропорта; следовательно, данный индекс поддерживает поиск по коду аэропорта.
У столбца может быть одно и то же значение в нескольких строках таблицы. Если этот столбец индексирован, индекс должен содержать указатели на все строки, содержащие это значение индексного ключа. В PostgreSQL индекс содержит несколько записей, то есть ключ индекса повторяется для каждого указателя на строку таблицы.
Рисунок 3.5 объясняет, как добраться до соответствующей строки таблицы при обнаружении записи индекса; однако он не объясняет, почему строку индекса можно найти намного быстрее, чем строку таблицы. Действительно, это зависит от того, как структурирован индекс, и именно это мы обсуждаем в следующих подразделах.
Рис. 3.5 ❖ Индексная структура
B-деревья
Самая распространенная индексная структура - это B-дерево. Структура B-дерева показана на рис. 3.6; коды аэропортов являются индексными ключами. Дерево состоит из иерархически организованных узлов, связанных с блоками, хранящимися на диске.
Листовые узлы (показанные на рис. 3.6 в нижней строке) содержат точно такие же записи индекса, как на рис. 3.5; эти записи состоят из индексного ключа и указателя на строку таблицы.
Нелистовые узлы (расположенные на всех уровнях, кроме нижнего) содержат записи, состоящие из наименьшего ключа (на рис. 3.5 это наименьшее буквенно-цифровое значение) в блоке, расположенном на следующем уровне, и указателя на этот блок. Все записи во всех блоках упорядочены, и в каждом блоке используется не менее половины доступного объема.
Любой поиск ключа K начинается с корневого узла B-дерева. Во время поиска по блоку будет найден самый большой ключ P, не превышающий K, и затем поиск продолжается в блоке, на который ссылается указатель, связанный с P. Поиск продолжается, пока мы не дойдем до листового узла, где указатели ссылаются на строки таблицы. Количество просмотренных при поиске узлов равно глубине дерева. Конечно, ключ K не обязательно хранится в индексе, но при поиске обнаруживается либо ключ, либо то место, где он мог быть расположен.
Рис. 3.6 ❖ Пример В-дерева
B-деревья также поддерживают поиск по диапазону (представляемый операцией between в SQL). Как только будет найдена нижняя граница диапазона, все индексные ключи диапазона можно получить последовательным сканированием листовых узлов до тех пор, пока не будет достигнута верхняя граница диапазона. Сканирование листовых узлов необходимо также для получения всех указателей, если индекс не является уникальным (то есть значение индексного ключа может соответствовать более чем одной строке).
Почему так часто используются B-деревья?
Из информатики мы знаем, что ни один алгоритм поиска не может найти индексный ключ среди N различных ключей быстрее, чем за время log N (выраженное в инструкциях процессора). Такая производительность достигается с помощью двоичного поиска по упорядоченному списку или с помощью двоичных деревьев. Однако стоимость обновлений (например, вставки новых ключей) может быть очень высока как для упорядоченных списков, так и для двоичных деревьев: вставка одной записи может привести к полной реструктуризации. Это делает обе структуры непригодными для хранения на диске.
Напротив, B-деревья можно изменять без значительных накладных расходов. Когда вы вставляете запись, реструктуризация ограничена одним блоком. Если емкость блока превышена, то он расщепляется на два блока, и обновление распространяется на верхние уровни. Даже в худшем случае количество измененных блоков не будет превышать глубины дерева.
Чтобы оценить стоимость поиска в B-дереве, нужно вычислить его глубину. Если каждый блок содержит f указателей, то количество блоков на каждом уровне в f раз больше, чем в предыдущем. Следовательно, глубина дерева, содержащего N записей, равна log N / log f. Эта формула дает количество обращений к диску, необходимое для поиска по одному ключу. Количество инструкций процессора для каждого блока ограничено, и обычно внутри блока используется двоичный поиск. Следовательно, стоимость ресурсов процессора лишь ненамного хуже теоретически возможного лучшего варианта. Размер блока в PostgreSQL составляет 8 Кбайт. В такой блок помещаются десятки индексных записей; следовательно, индекс с шестью-семью уровнями может вместить миллиарды записей.
В PostgreSOL индекс на основе B-дерева можно создать для любого порядкового типа данных; то есть такого, что из любых двух различных значений этого типа одно значение меньше другого. В эту категорию входят и пользовательские типы.
Битовые карты
Битовая карта - это вспомогательная структура данных, которая используется внутри PostgreSQL с разными целями. Битовые карты можно рассматривать как своего рода индекс: они созданы для облегчения доступа к другим структурам данных, содержащим несколько блоков. Обычно битовые карты используются для компактного представления свойств табличных данных.
Чаще всего битовая карта содержит по одному биту для каждого блока (8192 байта). Значение бита равно 1, если блок обладает нужным свойством, и 0, если нет. На рис. 3.7 показано, как битовые карты используются для доступа к данным по нескольким индексам.
Рис. 3.7 ❖ Использование битовых карт для доступа к таблицам по нескольким индексам
Движок базы данных начинает со сканирования двух индексов и построения для каждого из них битовой карты, которая указывает на блоки с подходящими табличными строками. Эти битовые карты показаны на рисунке в строках, обозначенных «Индекс 1» и «Индекс 2». Как только битовые карты будут созданы, движок выполняет побитовую операцию «и», чтобы найти блоки, содержащие подходящие значения для обоих критериев отбора. Наконец, сканируются блоки данных, соответствующие единицам в полученной битовой карте. Таким образом, к блокам, которые удовлетворяют только одному из двух критериев, не придется обращаться.
Обратите внимание, что подходящие значения могут находиться в разных строках одного блока. Битовая карта гарантирует, что соответствующие строки не будут пропущены, но не гарантирует, что все просканированные блоки содержат подходящие строки.
Битовые карты очень компактны; однако для очень больших таблиц они могут занимать много блоков.
Другие виды индексов
PostgreSQL предлагает множество индексных структур, поддерживающих разные типы данных и разные классы условий поиска.
Хеш-индекс использует хеш-функцию для вычисления адреса индексного блока, содержащего индексный ключ. Для условия равенства этот тип индекса работает быстрее B-дерева, однако он совершенно бесполезен для запросов по диапазону. Стоимостная оценка поиска по хеш-индексу не зависит от размера индекса (в отличие от логарифмической зависимости для B-деревьев).
R-дерево поддерживает поиск по пространственным данным. Индексный ключ для R-дерева всегда представляет собой прямоугольник в многомерном пространстве. Поиск возвращает все объекты, имеющие непустое пересечение с прямоугольником запроса. Структура R-дерева похожа на структуру B-дерева; однако расщепление переполненных узлов устроено намного сложнее. R-деревья эффективны для небольшого числа измерений (обычно от двух до трех).
Другие типы индексов, доступные в PostgreSQL, полезны для полнотекстового поиска, поиска в очень больших таблицах и многого другого. Дополнительная информация по этим темам представлена в главе 14. Любой из этих индексов можно относительно легко настроить для пользовательских типов данных. Однако в этой книге мы не обсуждаем индексы по пользовательским типам.
сочетание отношений
Настоящая мощь реляционной теории и баз данных SQL основана на сочетании данных из нескольких таблиц.
В этом разделе описываются алгоритмы операций, сочетающие данные, в том числе декартово произведение, соединение, объединение, пересечение и даже группировка. Удивительно, но большинство этих операций можно реализовать с помощью практически идентичных алгоритмов. По этой причине мы обсуждаем алгоритмы, а не операции, которые они реализуют. Мы будем использовать имена R и S для входных таблиц при описании этих алгоритмов.
Вложенные циклы
Первый алгоритм предназначен для получения декартова произведения, то есть множества всех пар строк из входных таблиц. Самый простой способ вычислить произведение - перебрать строки таблицы R и для каждой строки из R перебрать строки таблицы S. Псевдокод этого простого алгоритма представлен в листинге 3.4, а графическое представление алгоритма показано на рис. 3.8.
Листинг 3.4 ❖ Псевдокод для вложенных циклов
FOR row1 IN table1 LOOP
FOR row2 IN table2 LOOP
output (row)
END LOOP
END LOOP
Время, необходимое для этого простого алгоритма, пропорционально произведению размеров таблиц ввода: rows(R)*rows(S).
Интересный теоретический факт состоит в том, что любой алгоритм, вычисляющий декартово произведение, не может работать лучше; то есть стоимость любого алгоритма будет пропорциональна произведению размеров его входов или выше. Конечно, некоторые вариации этого алгоритма могут работать лучше, чем другие, но стоимость остается пропорциональной произведению.
Небольшие модификации алгоритма вложенного цикла позволяют вычислить практически любую логическую операцию, сочетающую данные из двух таблиц. Псевдокод из листинга 3.5 реализует соединение.
Листинг 3.5 ❖ Алгоритм вложенного цикла для соединения
FOR row1 IN table1 LOOP
FOR row2 IN table2 LOOP
IF match(row1,row2) THEN
output (row)
END IF
END LOOP
END LOOP
Обратите внимание, что соединение вложенными циклами является простой реализацией абстрактного определения соединения как декартова произведения, за которым следует фильтр. Поскольку вложенный цикл обрабатывает все пары входных строк, стоимость остается той же, хотя количество выходных строк меньше, чем в случае декартова произведения.
На практике одна или обе входные таблицы являются хранимыми таблицами, а не результатом предыдущей операции. В таком случае алгоритм соединения можно комбинировать с алгоритмом доступа к данным.
Хотя стоимость обработки остается прежней, варианты алгоритма вложенного цикла в сочетании с полным сканированием выполняют вложенные циклы по блокам входных таблиц и еще один уровень вложенных циклов по строкам, содержащимся в этих блоках. Более сложные алгоритмы минимизируют количество обращений к диску, загружая несколько блоков первой таблицы (внешний цикл) и обрабатывая все строки этих блоков за один проход по таблице S .
Рис. 3.8 ❖ Алгоритм вложенного цикла
Вышеупомянутые алгоритмы могут работать с любыми условиями соединения. Тем не менее большинство соединений, которые нужны на практике, являются естественными (natural): их условие соединения требует, чтобы некоторые атрибуты таблицы R были равны соответствующим атрибутам таблицы S.
Алгоритм соединения вложенными циклами также можно комбинировать с индексным доступом к данным, если в таблице S есть индекс по атрибутам, используемым в условии соединения. Для естественных соединений внутренний цикл такого алгоритма сокращается до нескольких строк таблицы S для каждой строки таблицы R. Внутренний цикл может даже полностью исчезнуть, если индекс по таблице S уникален, например атрибут соединения таблицы S является его первичным ключом.
Алгоритм вложенного цикла с индексным доступом обычно предпочтителен, если количество строк в таблице R тоже мало. Однако доступ на основе индекса становится неэффективным, когда количество строк, подлежащих обработке, увеличивается, как описано в этой статье.
Можно формально доказать, что для декартова произведения и соединений с произвольными условиями не существует более производительного алгоритма, чем вложенные циклы. Однако важный вопрос заключается в том, имеется ли более подходящий алгоритм для каждого конкретного типа условий соединения. В следующем разделе показано, что для естественных соединений такой алгоритм есть.
Алгоритмы на основе хеширования
Результат естественного соединения состоит из пар строк из таблиц R и S, которые имеют равные значения атрибутов, по которым выполняется соединение. Идея алгоритма соединения хешированием проста: если значения равны, то и хеш-значения тоже равны.
Алгоритм разбивает обе входные таблицы по корзинам в соответствии со значениями хеш-функции, а затем независимо соединяет строки в каждой корзине. Схема этого алгоритма показана на рис. 3.9.
Рис. 3.9 ❖ Алгоритм соединения хешированием
Базовая версия алгоритма соединения хешированием включает две фазы: 1) на этапе построения все кортежи таблицы R сохраняются в корзинах согласно значениям хеш-функции;
2) на этапе проверки каждая строка таблицы S направляется в соответствующую ей корзину. Если подходящие строки таблицы R находятся в этой корзине, порождаются выходные строки.
Самый простой способ найти подходящие строки в корзине - использовать вложенные циклы (фактически нужно перебирать все строки в корзине для каждой строки таблицы S).
Две фазы алгоритма на основе хеширования показаны как отдельные физические операции в плане выполнения.
Стоимость соединения хешированием приблизительно можно оценить по следующей формуле, где JA - атрибут, по которому выполняется соединение:
cost(hash,R,S) = size(R) + size(S) + size(R)*size(S)/size(JA)
Первое и второе слагаемые в этой формуле приблизительно равны стоимости одного прохода по всем строкам таблиц R и S. Последнее слагаемое обозначает размер порождаемого результата соединения. Конечно, стоимость вывода одинакова для всех алгоритмов соединения, но нам не нужно было включать его в оценку стоимости алгоритма вложенного цикла, потому что она меньше, чем стоимость вложенных циклов.
Эта формула показывает, что алгоритм на основе хеширования значительно лучше вложенных циклов подходит для больших таблиц и большого количества различных значений атрибута соединения. Например, если атрибут соединения в одной из входных таблиц уникален, то последнее слагаемое всего лишь будет равно размеру другой таблицы.
Базовый алгоритм соединения хешированием работает, если все корзины, созданные на этапе построения хеш-таблицы, помещаются в оперативную память. Другой вариант, называемый гибридным соединением хешированием, соединяет таблицы, которые не могут поместиться в оперативную память. Гибридное соединение хешированием разделяет обе таблицы так, чтобы отдельные разделы помещались в память, а затем выполняет базовый алгоритм для каждой пары соответствующих разделов. Стоимость гибридного соединения хешированием выше, потому что разделы временно хранятся на жестком диске и обе таблицы сканируются дважды. Однако стоимость по- прежнему пропорциональна сумме размеров таблиц, а не их произведению.
Сортировка слиянием
Еще один алгоритм для естественных соединений, который называют сортировкой слиянием, показан на рис. 3.10.
Рис. 3.10 ❖ Алгоритм сортировки слиянием
На первом этапе алгоритма обе входные таблицы сортируются в порядке возрастания по атрибутам соединения.
После того как таблицы правильно упорядочены, на этапе слияния обе таблицы сканируются один раз и для каждого значения атрибута соединения вычисляется декартово произведение строк, содержащих это значение. Обратите внимание, что это произведение является необходимой частью результата соединения. Новые строки с таким же значением атрибута не могут появиться в оставшейся части входных данных, потому что таблицы упорядочены.
Стоимость фазы слияния можно выразить той же формулой, что и для соединения хешированием, то есть она пропорциональна сумме размеров входных и выходных данных. Фактическая стоимость несколько ниже, потому что нет необходимости в этапе построения хеш-таблицы.
Стоимость сортировки можно оценить следующей формулой:
size(R)*log(size(R)) + size(S)*log(size(S))
Алгоритм сортировки слиянием особенно эффективен, если одна или обе входные таблицы уже отсортированы. Это может произойти в серии соединений по одним и тем же атрибутам.
Сравнение алгоритмов
Как и в случае с алгоритмами доступа к данным, здесь нет заведомых победителей или проигравших. Любой из алгоритмов может оказаться лучше в зависимости от обстоятельств. Алгоритм вложенного цикла более универсален и лучше всего подходит для небольших соединений с использованием индексов; сортировка слиянием и хеширование более эффективны для больших таблиц, если они применимы.
выводы
Рассмотрев стоимостные модели алгоритмов, алгоритмы доступа к данным, назначение и структуру индексов и алгоритмы для более сложных операций вроде соединения, мы наконец-то набрали достаточно строительных блоков, чтобы взяться за результат работы планировщика запросов - план выполнения.
В следующей статье рассказывается, как читать и понимать планы выполнения и улучшать их.