EnFirebird: методы доступа к данным
Дмитрий Еманов, (с) 2005-2006, v1.0
Содержание
Введение1. Первичные методы доступа 2. Фильтры 3. Методы слияния Заключение
Введение
В данной статье пойдет речь о выполнении сервером Firebird операций выборки данных, являющихся основой для почти всех поддерживаемых DML команд. Мы детально рассмотрим, какие существуют источники данных, какие трансформации могут осуществляться над потоками данных, как выполняются конкретные SQL команды на низком уровне. Также будет дана привязка к работе оптимизатора по выбору методов доступа с примерами планов.Набор операций над данными, выполняемых сервером для получения результата заданной выборки, называется путем доступа. Путь доступа можно представить в виде дерева с корнем, представляющим собой конечный результат. Каждый узел этого дерева называется методом доступа или источником данных. Объектами операций в методах доступа являются потоки данных. Каждый метод доступа либо формирует поток данных, либо трансформирует его по определенным правилам. Листовые узлы дерева называются первичными методами доступа. Их единственная задача – формирование потоков данных.
С точки зрения видов выполняемых операций существует три класса источников данных:
- первичный метод доступа – выполняет чтение из таблицы или хранимой процедуры
- фильтр – трансформирует один входной поток данных в один выходной поток
- слияние – преобразует два или более входных потоков данных в один выходной поток
Источники данных могут быть конвейерными и буферизированными. Конвейерный источник данных выдает записи в процессе чтения своих входных потоков, в то время как буферизированный источник сначала должен прочитать все записи из своих входных потоков и только потом сможет выдать первую запись на свой выход.
С точки зрения оценки производительности, каждый метод доступа имеет два обязательных атрибута – кардинальность (cardinality) и стоимость (cost). Первый отражает, сколько записей будет выбрано из источника данных. Второй оценивает стоимость выполнения метода доступа. Величина стоимости напрямую зависит от кардинальности и механизма выборки или трансформации потока данных. В текущих версиях сервера стоимость определяется количеством логических чтений (страничных фетчей, page fetches), необходимых для возврата всех записей методом доступа. Таким образом, более "высокие" методы всегда имеют большую стоимость, чем низкоуровневые.
1. Первичные методы доступа
Группа этих методов доступа выполняет создание потока данных на основе низкоуровневых источников, таких как таблицы (внутренние и внешние) и процедуры. Далее мы рассмотрим каждый из первичных источников данных отдельно.1.1. Чтение таблицы
Является самым распространенным первичным методом доступа. Стоит отметить, что здесь мы ведем речь только о "внутренних" таблицах, то есть тех, данные которых расположены в файлах базы данных. Доступ к внешним таблицам (external tables), а также выборка из хранимых процедур (stored procedures) осуществляются другими способами и будут описаны отдельно.
1.1.1. Полное сканирование
Этот метод также известен как естественный или последовательный перебор (full table scan, natural scan, sequential scan).
В данном методе доступа сервер осуществляет последовательное чтение всех страниц, выделенных для данной таблицы, в порядке их физического расположения на диске. Очевидно, что этот метод обеспечивает наиболее высокую производительность с точки зрения пропускной способности, то есть количества отфетченных записей в единицу времени. Также достаточно очевидно, что прочитаны будут все записи данной таблицы независимо от того, нужны они нам или нет.
Так как ожидаемый объем данных довольно велик, то в процессе чтения страниц таблицы с диска существует проблема вытеснения читаемыми страницами других, потенциально нужных конкурирующим сессиям. Для этого логика работы страничного кеша меняется – текущая страница скана помечается как MRU (most recently used) в течение чтения всех записей с данной страницы. Как только на странице нет больше данных и надо фетчить следующую, то текущая страница освобождается с признаком LRU (least recently used), уходя в "хвост" очереди и будучи таким образом первым кандидатом на удаление из кеша.
Записи читаются из таблицы по одной, сразу выдаваясь на выход. Следует отметить, что пре-фетча записей (хотя бы в пределах страницы) с их буферизацией в сервере нет. То есть полная выборка из таблицы со 100К записями, занимающими 1000 страниц, приведет к 100К страничным фетчам (page fetch), а не к 1000, как можно было бы предположить. Также нет и пакетного чтения (multi-block reads), при котором соседние страницы можно было бы выделить в группы и читать с диска "пачками" по несколько штук, уменьшая этим объем физического ввода/вывода.Здесь и далее при упоминании поведения оптимизатора будут приводиться: пример SELECT-запроса, план его выполнения и схематическое представление полного пути доступа (в текстовом виде). В плане выполнения полное сканирование таблицы обозначается словом "NATURAL".
SELECT *
FROM RDB$RELATIONS
PLAN (RDB$RELATIONS NATURAL)
STATEMENT (SELECT)
[cardinality=500, cost=500.000]
=> TABLE (RDB$RELATIONS) SEQUENTIAL ACCESS
[cardinality=500, cost=500.000]
В статистике выполнения запроса записи, прочитанные полным сканированием, отражаются как неиндексированные чтения (non indexed reads).
1.1.2. Доступ через идентификатор записи
В этом случае подсистема выполнения получает идентификатор (физический номер) записи, которую надо прочитать. Этот номер записи может быть получен из разных источников, каждый из которых будет описан далее.
Несколько упрощенно, физический номер записи содержит информацию о странице, на которой расположена данная запись, и о смещении внутри этой страницы. Таким образом этой информации достаточно, чтобы выполнить фетч необходимой страницы и найти на ней искомую запись.
Этот метод доступа является низкоуровневым и используется только как реализация выборки на основе битовой карты (как индексного скана, так и доступа через RDB$DB_KEY) и индексной навигации. Более подробно об этих методах доступа будет рассказано далее.
Стоимость данного вида доступа всегда равна единице. Чтения записей отражаются в статистике как индексированные.
1.1.3. Позиционированный доступ
Здесь идет речь о позиционированных командах UPDATE и DELETE (синтаксис WHERE CURRENT OF
1.2. Индексный доступ
Идея индексного доступа проста – помимо таблицы с данными у нас есть еще структура, содержащая пары "ключ – номер записи" в виде, позволяющем выполнять быстрый поиск по значению ключа. В Firebird индекс представляет собой страничное B+ дерево с префиксной компрессией ключей.
Индексы могут быть простыми (односегментными) и составными (многосегментными или композитными). Следует отметить, что совокупность полей композитного индекса представляет собой единый ключ. Поиск в индексе может осуществляться как по ключу целиком, так и по его подстроке (подключу). Очевидно, что поиск по подключу допустим только для начальной части ключа (например, starting with или использование не всех сегментов композита). Если поиск осуществляется по всем сегментам индекса, то это называется полным совпадением (full match) ключа, иначе это частичное совпадение (partial match) ключа. Отсюда для композитного индекса по полям (A, B, C) следует, что:
- он может быть использовать для предикатов (A = 0) или (A = 0 and B = 0) или (A = 0 and B = 0 and C = 0), но не может быть использован для предикатов (B = 0) или (C = 0) или (B = 0 and C = 0);
- предикат (A = 0 and B > 0 and C = 0) приведет к частичному совпадению по двум сегментам, а предикат (A > 0 and B = 0) – к частичному совпадению всего по одному сегменту.
Очевидно, что индексный доступ требует от нас чтения как страниц индекса для поиска, так и страниц данных для чтения записей. Другие СУБД в некоторых случаях способны ограничиваться только страницами индекса – например, если все поля выборки входят в индекс. Но такая схема невозможна в Firebird в связи с его архитектурой – ключ индекса содержит только номер записи без информации о ее версии – следовательно, сервер в любом случае должен прочитать страницу данных для определения, видна ли хоть одна из версий с данным ключом для текущей транзакции. Часто возникает вопрос: а если включить информацию о версиях (то есть номера транзакций) в ключ индекса? Ведь тогда можно будет реализовать чистое индексное покрытие (index only scan). Но тут есть два проблематичных момента. Во-первых, увеличится длина ключа, следовательно индекс будет занимать больше страниц, что приведет к большему объему ввода/вывода на ту же самую операцию сканирования. Во-вторых, каждое изменение записи приведет к модификации ключа индекса, даже если изменялись неключевые поля. В то время как сейчас индекс модифицируется только в случае изменения ключевых полей записи. Если первая из проблем приведет лишь к относительно небольшому (единицы процентов) ухудшению производительности, то вторая как минимум утраивает количество модифицированных страниц на каждую команду изменения данных по сравнению с текущей ситуацией. До сих пор разработчики сервера считают это слишком большой ценой за реализацию чистого индексного покрытия.
По сравнению с другими СУБД у индексов в Firebird есть еще одна особенность – сканирование индекса всегда однонаправленное, от меньших ключей к большим. Часто из-за этого индекс называют однонаправленным и говорят, что в его узле есть указатели только на следующий узел и нет указателя на предыдущий. На самом деле, проблема не в этом. Все структуры сервера Firebird спроектированы как свободные от взаимных блокировок (deadlock free), причем гарантируется минимальная возможная гранулярность блокировок, равная одной странице. Помимо этого, действует также правило "аккуратной" записи (careful write) страниц, служащее мгновенному восстановлению после сбоя. Проблема в двунаправленных индексах заключается в том, что они нарушают это правило при расщеплении страницы. На текущий момент неизвестен способ безблокировочной работы с двунаправленными указателями в случае, если одна из страниц должна быть записана строго перед другой.
Основным параметром, влияющим на оптимизацию индексного доступа, является селективность индекса. Это величина, обратная количеству уникальных значений ключа. В расчетах кардинальности и стоимости предполагается равномерное распределение значений ключа в индексе.
1.2.1. Битовые карты
Основная стандартная проблема индексного доступа это случайный ввод/вывод по отношению к страницам данных. Ведь действительно порядок ключей в индексе весьма нечасто совпадает с порядком соответствующих записей в таблице. Таким образом, выборка значительного числа записей через индекс наверняка приведет к многократному фетчу каждой соответствующей страницы данных. Эта проблема решается в других СУБД с помощью кластерных индексов (термин MSSQL) или таблиц, упорядоченных по индексу (термин Oracle), в которых данные расположены прямо в индексе в порядке возрастания кластерного ключа.
В Firebird эта проблема решена другим путем. Сканирование индекса не является конвейерной операцией, а выполняется для всего диапазона поиска, включая полученные номера записей в специальную битовую карту. Эта карта представляет собой разреженный битовый массив, где каждый бит соответствует конкретной записи и наличие единицы в нем является указанием для выборки данной записи. Особенность данного решения состоит в том, что битовая карта по определению отсортирована по номерам записей. После окончания скана данный массив служит основой для последовательного доступа через идентификатор записи. Достоинство очевидно – чтение из таблицы идет в физическим порядке расположения страниц, как и при полном сканировании, то есть каждая страница будет прочитана только один раз. Таким образом простота реализации индекса тут сочетается с максимально эффективным доступом к записям. Цена – некоторое увеличение времени отклика на запросах со стратегией FIRST_ROWS, когда нужно очень быстро получить первые записи.
Разумеется, для доступа на основе битовой карты страничный кеш также переводится в режим, описанный в пункте 1.1.1.
Над битовыми картами допустимы операции пересечения (bit and) и объединения (bit or), таким образом сервер может использовать несколько индексов для одной таблицы. При пересечении битовых карт результирующая кардинальность не увеличивается. Например, для выражения (F = 0 and ? = 0) его вторая часть не индексируема и, следовательно, проверяется уже после индексной выборки, не оказывая этим влияния на конечный результат. Но объединение битовых карт приводит к увеличению результирующей кардинальности, поэтому объединяться могут только части полностью индексированного предиката. То есть при выносе второй части выражения (F = 0 or ? = 0) на уровень выше может оказаться, что надо было сканировать все записи. Поэтому индекс для поля F не будет использован в таком выражении.
Селективность пересечения двух битовых карт вычисляется по формуле:
(bestSel + (((worstSel - bestSel) / (1 - bestSel)) * bestSel)) / 2
Селективность объединения двух битовых карт вычисляется по формуле:
bestSel + worstSel
Так как стоимость доступа через идентификатор записи равна единице, то итоговая стоимость доступа через битовую карту будет равна суммарной стоимости индексного поиска (для всех индексов, формирующих битовую карту) плюс результирующей кардинальности битовой карты.
1.2.2. Сканирование диапазона
Поиск под индексу осуществляется с использованием верхней и нижней границы. То есть, если указана нижняя граница сканирования, то сначала находится соответствующий ей ключ и только потом начинается последовательный перебор ключей с занесением номеров записей в битовую карту. Если указана верхняя граница, то каждый ключ сравнивается с ней и при ее достижении сканирование прекращается. Такой механизм называется сканированием диапазона (range scan). В случае, когда нижняя граница равна верхней, говорят о сканировании на равенство (equality scan). Если сканирование на равенство выполняется для уникального индекса, то это называется уникальным сканированием (unique scan). Данный вид сканирования имеет особое значение, так как может вернуть не более одной записи и, следовательно, по определению является самым дешевым. Если у нас не задана ни одна из границ, то мы имеем дело с полным сканированием (full scan). Этот метод применяется исключительно для индексной навигации, описанной ниже.
Неприятной особенностью текущей реализации сканирования является тот факт, что верхняя и нижняя границы являются строгими. То есть для обоих предикатов (F > 0) и (F >= 0) нижней границей будет нуль, что приведет к одинаковому числу индексированных чтений, хотя очевидно, что для первого предиката часть из них избыточна.
При выборе индексов для сканирования оптимизатор использует стратегию на основе стоимости (cost based). Стоимость сканирования диапазона оценивается на основании селективности индекса, количества записей в таблице, среднего количества ключей на индексной странице и высоты B+ дерева. В плане выполнения сканирование диапазона индекса обозначается словом "INDEX", за которым в скобках следуют наименования всех индексов, образующих итоговую битовую карту.
SELECT *
FROM RDB$RELATIONS
WHERE RDB$RELATION_NAME = ?
PLAN (RDB$RELATIONS INDEX (RDB$INDEX_0))
STATEMENT (SELECT)
[cardinality=1, cost=4.000]
=> TABLE (RDB$RELATIONS) ACCESS BY DB_KEY
[cardinality=1, cost=4.000]
=> BITMAP
[cardinality=1, cost=3.000]
=> INDEX (RDB$INDEX_0) UNIQUE SCAN
[cardinality=1, cost=3.000]
SELECT *
FROM RDB$RELATIONS
WHERE RDB$RELATION_NAME > ?
PLAN (RDB$RELATIONS INDEX (RDB$INDEX_0))
STATEMENT (SELECT)
[cardinality=250, cost=255.000]
=> TABLE (RDB$RELATIONS) ACCESS BY DB_KEY
[cardinality=250, cost=255.000]
=> BITMAP
[cardinality=250, cost=5.000]
=> INDEX (RDB$INDEX_0) RANGE SCAN
[cardinality=250, cost=5.000]
SELECT *
FROM RDB$RELATION_FIELDS
WHERE RDB$RELATION_NAME = ?
PLAN (RDB$RELATION_FIELDS INDEX (RDB$INDEX_4))
STATEMENT (SELECT)
[cardinality=5, cost=9.000]
=> TABLE (RDB$RELATION_FIELDS) ACCESS BY DB_KEY
[cardinality=5, cost=9.000]
=> BITMAP
[cardinality=5, cost=4.000]
=> INDEX (RDB$INDEX_4) RANGE SCAN
[cardinality=5, cost=4.000]
SELECT *
FROM RDB$INDICES
WHERE RDB$RELATION_NAME = ? AND RDB$FOREIGN_KEY = ?
PLAN (RDB$INDICES INDEX (RDB$INDEX_31, RDB$INDEX_41))
STATEMENT (SELECT)
[cardinality=2, cost=9.000]
=> TABLE (RDB$INDICES) ACCESS BY DB_KEY
[cardinality=2, cost=9.000]
=> BITMAP AND
[cardinality=2, cost=7.000]
=> INDEX (RDB$INDEX_31) RANGE SCAN
[cardinality=5, cost=4.000]
=> INDEX (RDB$INDEX_41) RANGE SCAN
[cardinality=2, cost=3.000]
1.2.3. Навигация по индексу
Индексная навигация есть ни что иное, как последовательное сканирование ключей индекса. А так как для каждой записи серверу надо выполнить фетч записи и проверить ее видимость для нашей транзакции, то данная операция выходит достаточно дорогой. Именно поэтому данный метод доступа не применяется для обычных выборок (в отличие от Oracle, например), а используется только в случаях, когда это оправдано.Основное отличие индексной навигации от сканирования (описанного в пункте 1.2.2) заключается в отсутствии битовой карты между сканированием индекса и доступом к записи через ее идентификатор. Причина понятна – сортировка записей по физическим номерам в данном случае противопоказана. Из этого можно сделать вывод, что при индекс сканируется по мере фетча с клиента, а не "за раз" (как в случае использования битовой карты).
Стоимость навигации оценить достаточно сложно. Для вычисления MIN/MAX в подавляющем большинстве случаев она будет равна высоте B+ дерева (поиск первого ключа) плюс единица (фетч страницы). Стоимость такого доступа считается принебрежительно малой величиной, так как на практике описанное вычисление MIN/MAX всегда будет быстрее альтернативных вариантов. Для оценки же стоимости индексной сортировки надо учесть как количество и среднюю ширину ключей индекса, так и кардинальность битовой карты (если таковая есть), а также иметь представление о факторе кластеризации (clustering factor) индекса – коэффициенте соответствия расположения ключей физическим номерам записей. В настоящий момент в сервере отсутствует вычисление стоимости навигации, то есть снова используется стратегия на основе правил (rule based). В будущем планируется использовать данных подход только для MIN/MAX и FIRST, а в остальных случаях опираться на стоимость.
SELECT RDB$PROCEDURE_NAME
FROM RDB$PROCEDURES
ORDER BY RDB$PROCEDURE_NAME
PLAN (RDB$PROCEDURES ORDER RDB$INDEX_21)
STATEMENT (SELECT)
[cardinality=200, cost=205.000]
=> TABLE (RDB$PROCEDURES) ACCESS BY DB_KEY
[cardinality=200, cost=205.000]
=> INDEX (RDB$INDEX_21) FULL SCAN
[cardinality=200, cost=5.000]
SELECT MIN(RDB$PROCEDURE_NAME)
FROM RDB$PROCEDURES
WHERE RDB$PROCEDURE_NAME > ?
PLAN (RDB$PROCEDURES ORDER RDB$INDEX_21)
STATEMENT (SELECT)
[cardinality=100, cost=103.000]
=> TABLE (RDB$PROCEDURES) ACCESS BY DB_KEY
[cardinality=100, cost=103.000]
=> INDEX (RDB$INDEX_21) RANGE SCAN
[cardinality=100, cost=3.000]
SELECT MIN(RDB$PROCEDURE_NAME)
FROM RDB$PROCEDURES
WHERE RDB$PROCEDURE_ID > ?
PLAN (RDB$PROCEDURES ORDER RDB$INDEX_21 INDEX (RDB$INDEX_22))
STATEMENT (SELECT)
[cardinality=100, cost=303.000]
=> TABLE (RDB$PROCEDURES) ACCESS BY DB_KEY
[cardinality=100, cost=303.000]
=> INDEX (RDB$INDEX_21) FULL SCAN
[cardinality=100, cost=203.000]
=> BITMAP
[cardinality=100, cost=3.000]
=> INDEX (RDB$INDEX_22) RANGE SCAN
[cardinality=100, cost=3.000]
1.3. Доступ посредством RDB$DB_KEY
Механизм работы с RDB$DB_KEY практически недокументирован. Читателям, интересующимся данным вопросом, можно порекомендовать статьи на сайте Клаудио Валдеррамы (Claudio Valderrama): "The mystery of RDB$DB_KEY" и "Practical use of RDB$DB_KEY".
С точки зрения методов доступа тут все просто – создается битовая карта и в нее помещается единственной номер записи – значение RDB$DB_KEY. После чего выполняется чтение записи посредством описанного выше доступа через идентификатор записи. Очевидно, что стоимость такого доступа равна единице. То есть получаем что-то вроде псевдо-индексного доступа, что и отражается в плане выполнения запроса.
SELECT *
FROM RDB$RELATIONS
WHERE RDB$DB_KEY = ?
PLAN (RDB$RELATIONS INDEX ())
STATEMENT (SELECT)
[cardinality=1, cost=1.000]
=> TABLE (RDB$RELATIONS) ACCESS BY DB_KEY
[cardinality=1, cost=1.000]
=> BITMAP
[cardinality=1, cost=0.000]
=> DB_KEY
[cardinality=1, cost=0.000]
Чтения через RDB$DB_KEY отражаются в статистике как индексированные. Причина этого понятна из описания выше – все, что читается посредством доступа через идентификатор записи, считается сервером индексированным доступом. Не совсем корректное, но достаточно безобидное допущение.
1.4. Внешняя таблица
Данный вид доступа используется только при работе с внешними таблицами. По сути он представляет собой аналог полного сканирования таблицы. Записи читаются из внешнего файла поштучно, посредством текущего указателя (смещения). Кеширование отсутствует. Индексирование внешних таблиц не поддерживается.
По причине отсутствия альтернативных методов доступа к внешним данным, стоимость не вычисляется и не используется. Кардинальность выборки из внешней таблицы принимается равной 10000. В плане выполнения отображается словом "NATURAL".
SELECT *
FROM EXT_TABLE
WHERE EXT_FIELD = ?
PLAN (EXT_TABLE NATURAL)
STATEMENT (SELECT)
[cardinality=10000, cost=?.???]
=> TABLE (EXT_TABLE) SEQUENTIAL ACCESS
[cardinality=10000, cost=?.???]
1.5. Процедурный доступ
Данный метод доступа используется при выборке из хранимых процедур, использующих предложение SUSPEND для возврата результата. В Firebird хранимая процедура всегда представляет собой черный ящик, о внутренностях и деталях реализации которого сервер не делает никаких предположений. Процедура всегда считается недетерминированным источником данных, то есть может возвращать разные данные при двух последующих вызовах, выполненных в равных условиях. В свете этого очевидно, что любого вида индексация результатов процедуры невозможна. Процедурный метод доступа также представляет собой аналог полного сканирования таблицы. При каждом фетче из процедуры она выполняется с момента предыдущего останова (начала процедуры для первого фетча) до следующего предложения SUSPEND, после чего ее выходные параметры формируют строку данных, которая и возвращается из данного метода доступа.
Аналогично доступу для внешних таблиц, стоимость процедурного доступа также не рассчитывается и не учитывается, так как нет альтернативных вариантов. Однако для процедур кардинальность устанавливается равной нулю. О причинах этого и побочных эффектах будет рассказано в части, посвященной соединениям.
В плане выполнения процедурный доступ может отображаться по разному, в зависимости от версии сервера. Наиболее правильным является отображение "NATURAL", хотя в некоторых версиях может выводиться детализация (планы) выборок внутри процедуры. Это позволяет оценить план выполнения запроса в целом, с учетом "внутренностей" всех участвующих процедур, но формально это является неверным.
SELECT *
FROM PROC_TABLE
WHERE PROC_FIELD = ?
PLAN (PROC_TABLE NATURAL)
STATEMENT (SELECT)
[cardinality=0, cost=?.???]
=> TABLE (PROC_TABLE) SEQUENTIAL ACCESS
[cardinality=0, cost=?.???]
2. Фильтры
Данная группа методов доступа является преобразователем полученных данных. Главное отличие этой группы от прочих заключается в том, что у всех фильтров присутствует только один вход. Они не изменяют ширину входного потока, а лишь уменьшают его кардинальность по правилам, определяемым своей функцией. На вход фильтру может поступать поток данных как из первичного, так и из любого другого источника данных.
С точки зрения реализации, у фильтров есть еще одна общая черта – для них не оценивается кардинальность и стоимость. То есть считается, что все фильтры не изменяют кардинальность входных данных и выполняются за нулевое время.
Далее будут описаны существующие в Firebird реализации методов-фильтров и решаемые ими задачи.
2.1. Проверка предикатов
Наверное, это наиболее часто используемый случай, и заодно самый простой для понимания. Данный фильтр проверяет некоторое логическое условие для каждой записи, переданной ему на вход. Если это условие выполняется, то запись без изменений пропускается на выход, иначе игнорируется. В зависимости от входных данных и логического условия, фетч одной записи из данного фильтра может привести к одному или более фетчей из входного потока. Вырожденными случаями проверочных фильтров являются предопределенные условия вида (1 = 1) или (1 <> 1), которые либо просто пропускают входные данные через себя, либо удаляют их.
Как можно понять из названия, данные фильтры применяются для выполнения предикатов WHERE, HAVING, ON и других. С целью уменьшения результирующей кардинальности выборки, проверка предикатов всегда ставится как можно "ниже" ("глубже") в дерево выполнения запроса. В случае проверки на поле таблицы, проверка предиката будет выполнена сразу после фетча записи из этой таблицы.
В плане выполнения проверка предикатов не отображается.
SELECT *
FROM RDB$RELATIONS
WHERE RDB$SYSTEM_FLAG = ?
PLAN (RDB$RELATIONS NATURAL)
STATEMENT (SELECT)
[cardinality=500, cost=500.000]
=> BOOLEAN
[cardinality=500, cost=500.000]
=> TABLE (RDB$RELATIONS) SEQUENTIAL ACCESS
[cardinality=500, cost=500.000]
SELECT *
FROM RDB$RELATIONS
WHERE RDB$RELATION_NAME = ?
PLAN (RDB$RELATIONS INDEX (RDB$INDEX_0))
STATEMENT (SELECT)
[cardinality=1, cost=4.000]
=> BOOLEAN
[cardinality=1, cost=4.000]
=> TABLE (RDB$RELATIONS) ACCESS BY DB_KEY
[cardinality=1, cost=4.000]
=> BITMAP
[cardinality=1, cost=3.000]
=> INDEX (RDB$INDEX_0) UNIQUE SCAN
[cardinality=1, cost=3.000]
По последнему примеру может возникнуть вопрос: зачем использован BOOLEAN, если предикат реализуется через INDEX UNIQUE SCAN? Дело в том, что Firebird реализует нечеткий поиск в индексе. То есть индексное сканирование является лишь оптимизацией вычисления предиката и в ряде случаев может вернуть больше записей, чем требуется. Именно поэтому сервер не полагается лишь на результат индексного сканирования и проверяет предикат еще раз, после фетча записи. Отмечу, что в подавляющем большинстве случаев это не несет заметных накладных расходов с точки зрения производительности.
2.2. Сортировка
Также известна как внешняя сортировка (external sort). Данный фильтр применяется оптимизатором при необходимости упорядочить входной поток в случае невозможности применения индексной навигации (см. пункт 1.2.3). Примеры его использования: сортировка или группировка (в случае, когда нет подходящих индексов или индексы неприменимы для входного потока), построение B+ дерева индекса, выполнение операции DISTINCT, подготовка данных для однопроходного слияния (см. ниже) и другие.
Так как входные данные по определению неупорядочены, то очевидно, что фильтр сортировки должен выполнить фетч всех записей из своего входного потока прежде чем он сможет выдать хоть одну из них на выход. Таким образом, данный фильтр можно считать буферизируемым источником данных.
Алгоритм сортировки представляет собой многоуровневую быструю сортировку (quick sort). Набор входных записей помещается во внутренний буфер, после чего он сортируется и блок перемещается во внешнюю память. Далее таким же образом заполняется следующий блок и процесс продолжается до окончания записей во входном потоке. После чего заполненные блоки вычитываются и по ним строится бинарное дерево слияния. При чтении из фильтра сортировки происходит разбор дерева и слияние записей в один проход. Внешней памятью может выступать как виртуальная память, так и дисковое пространство, в зависимости от настроек файла конфигурации сервера.
Из всего вышесказанного можно сделать вывод, что записи читаются и сортируются целиком (а не только ключи). Сервер не производит повторного чтения записей с диска, вместо этого они читаются из буфера сортировки.
У сортировки существует два режима работы: "нормальный" и "усекающий". Первый из них сохраняет записи с дублирующимися ключами сортировки, в то время как второй приводит к тому, что дубликаты удаляются. Именно "усекающий"режим реализует операцию DISTINCT, например.
В плане выполнения сортировка обозначается словом "SORT", за которым в скобках следует описание входного потока.
SELECT *
FROM RDB$RELATIONS
ORDER BY RDB$SYSTEM_FLAG
PLAN SORT (RDB$RELATIONS NATURAL)
STATEMENT (SELECT)
[cardinality=500, cost=500.000]
=> SORT
[cardinality=500, cost=500.000]
=> TABLE (RDB$RELATIONS) SEQUENTIAL ACCESS
[cardinality=500, cost=500.000]
SELECT *
FROM RDB$RELATIONS
WHERE RDB$RELATION_NAME > ?
ORDER BY RDB$SYSTEM_FLAG
PLAN SORT (RDB$RELATIONS INDEX (RDB$INDEX_0))
STATEMENT (SELECT)
[cardinality=100, cost=105.000]
=> SORT
[cardinality=100, cost=105.000]
=> BOOLEAN
[cardinality=100, cost=105.000]
=> TABLE (RDB$RELATIONS) ACCESS BY DB_KEY
[cardinality=100, cost=105.000]
=> BITMAP
[cardinality=100, cost=5.000]
=> INDEX (RDB$INDEX_0) RANGE SCAN
[cardinality=100, cost=5.000]
Возможные варианты избыточной сортировки (например, DISTINCT и ORDER BY по одному и тому же полю) устраняются оптимизатором и приводятся лишь к минимально необходимому числу сортировок.
2.3. Агрегация
Данный фильтр используется исключительно для вычисления агрегирующих функций (MIN, MAX, AVG, SUM, COUNT), включая случаи их использования в группировках.
Реализация довольна тривиальна. Все перечисленные функции требуют единственного временного регистра для хранения текущего граничного (MIN/MAX) или аккумулированного (прочие функции) значения. Далее для каждой записи из входного потока мы проверяем или суммируем этот регистр. В случае группировки алгоритм несколько усложняется. Для корректного вычисления функции для каждой группы должны быть четко определены границы между этими группами. Самым простым решением является гарантия упорядоченности входного потока. В данном случае мы выполняем агрегирование для одного и того же ключа группировки, а после его изменения выдаем результат на выход и продолжаем уже со следующим ключом. Данный подход как раз и использован в Firebird – агрегация по группам строго зависит от наличия сортировки на входе.
Существует альтернативный способ вычисления агрегатов – хеширование. В этом случае сортировка входного потока не требуется, однако к каждому ключу группировки применяется хеш-функция и регистр хранится для каждого ключа (точнее, для каждой коллизии ключа) в хеш-таблице. Плюс данного алгоритма – нет необходимости в дополнительной сортировке. Минус – больший расход памяти для хранения хеш-таблицы. Данный метод обычно выигрывает у сортировки при низкой селективности ключей группировки (мало уникальных значений, следовательно небольшая хеш-таблица). Агрегация хешированием в Firebird отсутствует.
В плане выполнения агрегация не показывается.
SELECT MIN(RDB$RELATION_ID)
FROM RDB$RELATIONS
PLAN (RDB$RELATIONS NATURAL)
STATEMENT (SELECT)
[cardinality=500, cost=500.000]
=> AGGREGATE
[cardinality=500, cost=500.000]
=> TABLE (RDB$RELATIONS) SEQUENTIAL ACCESS
[cardinality=500, cost=500.000]
SELECT RDB$SYSTEM_FLAG, COUNT(*)
FROM RDB$RELATIONS
WHERE RDB$RELATION_NAME > ?
GROUP BY RDB$SYSTEM_FLAG
PLAN SORT (RDB$RELATIONS INDEX (RDB$INDEX_0))
STATEMENT (SELECT)
[cardinality=100, cost=105.000]
=> AGGREGATE
[cardinality=100, cost=105.000]
=> SORT
[cardinality=100, cost=105.000]
=> BOOLEAN
[cardinality=100, cost=105.000]
=> TABLE (RDB$RELATIONS) ACCESS BY DB_KEY
[cardinality=100, cost=105.000]
=> BITMAP
[cardinality=100, cost=5.000]
=> INDEX (RDB$INDEX_0) RANGE SCAN
[cardinality=100, cost=5.000]
В случае вычисления функций SUM/AVG/COUNT в режиме DISTINCT для каждой группы значений перед аккумулированием производится их сортировка в режиме устранения дубликатов. При этом в плане не отображается слово SORT.
2.4. Счетчики
Данный вид фильтра также очень прост. Его цель – выдать только часть записей входного потока, основываясь на некотором значении N внутреннего счетчика. Есть две разновидности данного фильтра, применяемые для реализаций предложений FIRST/SKIP/ROWS запроса. Первая разновидность (FIRST-счетчик) выдает на выход только первые N записей своего входного потока, после чего выдает признак EOF. Вторая разновидность (SKIP-счетчик) игнорирует первые N записей своего входного потока и начинает выдавать их на выход, начиная с записи N+1. Очевидно, что при наличии в запросе ограничения выборки вида (FIRST 100 SKIP 100), сначала должен быть применен SKIP-счетчик, и только после него – FIRST-счетчик. Оптимизатор гарантирует правильное применение счетчиков при выполнении запроса.
В плане выполнения счетчики не показываются.
SELECT FIRST 1 *
FROM RDB$RELATIONS
PLAN (RDB$RELATIONS NATURAL)
STATEMENT (SELECT)
[cardinality=500, cost=500.000]
=> FIRST
[cardinality=500, cost=500.000]
=> TABLE (RDB$RELATIONS) SEQUENTIAL ACCESS
[cardinality=500, cost=500.000]
SELECT FIRST 1 SKIP 1 *
FROM RDB$RELATIONS
WHERE RDB$RELATION_NAME > ?
PLAN (RDB$RELATIONS INDEX (RDB$INDEX_0))
STATEMENT (SELECT)
[cardinality=100, cost=105.000]
=> FIRST
[cardinality=100, cost=105.000]
=> SKIP
[cardinality=100, cost=105.000]
=> BOOLEAN
[cardinality=100, cost=105.000]
=> TABLE (RDB$RELATIONS) ACCESS BY DB_KEY
[cardinality=100, cost=105.000]
=> BITMAP
[cardinality=100, cost=5.000]
=> INDEX (RDB$INDEX_0) RANGE SCAN
[cardinality=100, cost=5.000]
2.5. Проверка сингулярности
Этот фильтр используется для гарантированности возврата из метода только одной записи. Он применяется в случае использовании в тексте запроса сингулярных подзапросов (singleton subqueries).
Для выполнения своей функции, фильтр проверки сингулярности производит два чтения из входного потока. Если второе чтение вернуло EOF, то выдаем первую запись на выход. Иначе инициируем ошибку isc_sing_select_err (multiple rows in singleton select).
В плане выполнения проверка сингулярности не показывается.
SELECT *
FROM RDB$RELATIONS
WHERE RDB$RELATION_ID = ( SELECT RDB$RELATION_ID FROM RDB$DATABASE )
PLAN (RDB$DATABASE NATURAL)
PLAN (RDB$RELATIONS INDEX (RDB$INDEX_1))
STATEMENT (SELECT)
[cardinality=1, cost=1.000]
=> SINGULAR
[cardinality=1, cost=1.000]
=> TABLE (RDB$DATABASE) SEQUENTIAL ACCESS
[cardinality=1, cost=1.000]
STATEMENT (SELECT)
[cardinality=1, cost=4.000]
=> BOOLEAN
[cardinality=1, cost=4.000]
=> TABLE (RDB$RELATIONS) ACCESS BY DB_KEY
[cardinality=1, cost=4.000]
=> BITMAP
[cardinality=1, cost=3.000]
=> INDEX (RDB$INDEX_1) RANGE SCAN
[cardinality=1, cost=3.000]
2.6. Блокировка записи
Данный фильтр реализует пессимистическую блокировку записи. Она применяется только в случае присутствия в тексте запроса предложения "WITH LOCK". Каждая запись, прочитанная из входного потока фильтра, возвращается на выход уже заблокированной текущей транзакцией. Для блокировки используется создание новой версии записи, помеченной идентификатором текущей транзакции. В случае, если текущая транзакция уже изменяла данную запись, то блокировка не выполняется.
В текущих версиях фильтр блокировки работает только для первичных методов доступа. В плане выполнения блокировка не показывается.
SELECT *
FROM RDB$RELATIONS
WITH LOCK
PLAN (RDB$RELATIONS NATURAL)
STATEMENT (SELECT)
[cardinality=100, cost=100.000]
=> LOCK
[cardinality=100, cost=100.000]
=> TABLE (RDB$RELATIONS) SEQUENTIAL ACCESS
[cardinality=100, cost=100.000]
3. Методы слияния
Эта категория методов доступа во многом напоминает фильтры. Методы слияния тоже преобразуют входные данные по определенному алгоритму. Формальная разница только в том, что данная группа методов всегда оперирует с несколькими входными потоками. Кроме того, обычным результатом их работы является либо расширение выборки по полям, либо увеличение ее кардинальности.Существует два класса методов слияния – соединение (join) и объединение (union), выполняющие разные функции. Ниже мы познакомимся с их описанием и возможными алгоритмами реализации.
3.1. Соединение
Как можно догадаться по названию, данная группа методов реализует SQL-соединения (joins). Стандарт SQL определяет два вида соединений: внутренние (inner) и внешние (outer). Кроме того, внешние соединения делятся на односторонние (left или right) и полные (full). У любого вида соединений есть два входных потока – левый и правый. Для внутреннего и полного внешнего соединений эти потоки семантически равноценны. В случае же одностороннего внешнего соединения один из потоков является ведущим (обязательным), а второй – ведомым (необязательным). Часто также ведущий поток называют внешним, а ведомый – внутренним. Для левого внешнего соединения ведущим (внешним) потоком является левый, а ведомым (внутренним) – правый. Для правого внешнего соединения – наоборот.
Сразу отмечу, что формально левое внешнее соединение эквивалентно инвертированному правому внешнему соединению. Под инверсией в данном контексте я понимаю замену внешнего потока на внутренний или наоборот. Так что достаточно реализовать только один вид одностороннего внешнего соединения (обычно это левое). Так и сделано в Firebird. Однако, решение о преобразовании правого соединения в левое (базовое) и его последующей оптимизации принимал оптимизатор, что зачастую приводило к некорректной оптимизации правых соединений. Начиная с версии 1.5, сервер превращает правые соединения в левые на уровне разбора BLR, что устраняет возможные конфликты в оптимизаторе.
У каждого соединения помимо входных потоков существует еще один атрибут – условие связи. Именно это условие и определяет результат, то есть как именно будут поставлены в соответствие данные входных потоков. При отсутствии данного условия получаем вырожденный случай – декартово произведение (cross join) входных потоков.
Вернемся к односторонним внешним соединениям. Их потоки не зря называются ведущим и ведомым. В данном случае внешний (ведущий) поток всегда должен быть прочитан перед внутренним (ведомым), иначе невозможно будет выполнить требуемую стандартом подстановку NULL-значений в случае отсутствия соответствий внутреннего потока внешнему. Отсюда можно сделать вывод, что оптимизатор не имеет возможности выбирать порядок выполнения одностороннего внешнего соединения и он всегда будет определяться текстом запроса. В то время как для внутренних и полных внешних соединений входные потоки независимы и могут читаться в произвольном порядке, следовательно алгоритм выполнения таких соединений определяется исключительно оптимизатором и никак не зависит от текста запроса.
3.1.1. Рекурсивный перебор
Данный метод является наиболее распространенным в Firebird. В других СУБД этот алгоритм также называется соединением посредством вложенных циклов (nested loops join).
Суть его проста. Открывается один из входных потоков (внешний) и из него читается одна запись. После чего открывается второй поток (внутренний) и из него тоже читается одна запись. Затем проверяется условие связи. Если условие выполнено, эти две записи сливаются в одну и выдаются на выход. Далее читается вторая запись из внутреннего потока и процесс повторяется до выдачи из него EOF. Если внутренний поток не содержит ни одной соответствующей внешнему потоку записи, то возможны два варианта развития событий. В случае внутреннего соединения запись не возвращается на выход. В случае же внешнего соединения мы соединяем запись из внешнего потока с необходимым количеством NULL-значений и выдаем ее на выход. Далее, независимо от вида соединения, мы читаем вторую запись из внешнего потока и начинаем процесс итерации по внутреннему потоку заново. А так как входным потоком может выступать точно такое же соединение, в итоге получаем бинарное дерево, обрабатываемое рекурсивно. Отсюда и название метода. Очевиден факт, что данный алгоритм работает по конвейерному принципу и соединение потоков выполняется прямо в процессе клиентского фетча.
Ключевой особенностью этого метода соединения является "вложенная" выборка из внутреннего потока. Очевидно, что читать весь внутренний поток для каждой записи внешнего потока очень накладно. Поэтому данный рекурсивный алгоритм работает эффективно только в случае наличия индекса, применимого к условию связи. В этом случае на каждой итерации из внутреннего потока будет выбрано подмножество записей, удовлетворяющих текущей записи внешнего потока. Стоит обратить внимание, что не каждый индекс подходит для эффективного выполнения данного алгоритма, а только соответствующий условию связи. Например, при связи вида (ON SLAVE.F = 0) даже при использовании индекса по полю "F" внутренней таблицы все равно из нее будут читаться одни и те же записи на каждой итерации, что есть напрасная трата ресурсов. В данной ситуации, соединение слиянием было бы более эффективным (см. ниже).
Можно ввести определение "зависимости потоков" как наличие полей обоих потоков в условии связи и сделать вывод, что рекурсивный алгоритм эффективен только при зависимости потоков друг от друга. Начиная с версии 2.0, данный алгоритм выбирается исключительно при наличии зависимости между потоками. В предыдущих версиях, были возможны неоптимальные варианты соединений.
Если вспомнить пункт 2.1, где описан принцип максимально "глубокого" помещения предикативных фильтров оптимизатором, то становится понятен один момент: индивидуальные табличные фильтры уйдут "ниже" методов соединения. Соответственно, в случае предиката вида (WHERE MASTER.F = 0) и отсутствии в таблице "MASTER" записей с полем "F", равным нулю, обращений к внутреннему потоку соединения вообще не будет, так как в данном случае нет итерации по внешнему потоку (в нем нет записей).
Так как логические связки AND и OR оптимизируются через битовые карты, то рекурсивный алгоритм может быть использован для всех видов условий связи, причем обычно достаточно эффективно.
Рекурсивный перебор выбирается оптимизатором всегда, когда есть подходящие индексы (снова стратегия выбора на основе правил). Однако в случае внутреннего соединения оптимизатор выбирает наиболее эффективный порядок связи потоков. Главные критерии выбора: кардинальности обоих потоков и селективность условия связи. Используется следующие формулы для оценки стоимости определенного порядка соединения:
cost = cardinality(outer) + (cardinality(outer) * (indexScanCost + cardinality(inner) * selectivity(link)))
cardinality = cardinality(outer) * (cardinality(inner) * selectivity(link))
Последняя часть формулы определяет стоимость выборки из внутреннего потока на каждой итерации. Умножив ее на количество итераций, получаем общую стоимость выборки из внутреннего потока. Общая стоимость получается путем добавления стоимости выборки из внешнего потока. Из всех возможных перестановок выбирается вариант с наименьшей стоимостью. В процессе перебора вариантов отбрасываются заведомо худшие (на основании уже имеющейся стоимостной информации).
В плане выполнения рекурсивное соединение отображается словом "JOIN", за которым в скобках через запятую описываются входные потоки.
SELECT *
FROM RDB$RELATIONS R
LEFT JOIN RDB$RELATION_FIELDS RF ON R.RDB$RELATION_NAME = RF.RDB$RELATION_NAME
PLAN JOIN (R NATURAL, RF INDEX (RDB$INDEX_4))
STATEMENT (SELECT)
[cardinality=2500, cost=4500.000]
=> LOOP (LEFT)
[cardinality=2500, cost=4500.000]
=> TABLE (RDB$RELATIONS) SEQUENTIAL ACCESS
[cardinality=500, cost=500.000]
=> TABLE (RDB$RELATION_FIELDS) ACCESS BY DB_KEY
[cardinality=5, cost=8.000]
=> BITMAP
[cardinality=5, cost=3.000]
=> INDEX (RDB$INDEX_4) RANGE SCAN
[cardinality=5, cost=3.000]
SELECT *
FROM RDB$RELATIONS R
JOIN RDB$RELATION_FIELDS RF ON R.RDB$RELATION_NAME = RF.RDB$RELATION_NAME
JOIN RDB$FIELDS F ON RF.RDB$BASE_FIELD = F.RDB$FIELD_NAME
PLAN JOIN (RF NATURAL, F INDEX (RDB$INDEX_2), R INDEX (RDB$INDEX_0))
STATEMENT (SELECT)
[cardinality=2500, cost=17500.000]
=> LOOP (INNER)
[cardinality=2500, cost=17500.000]
=> TABLE (RDB$RELATION_FIELDS) SEQUENTIAL ACCESS
[cardinality=2500, cost=2500.000]
=> TABLE (RDB$FIELDS) ACCESS BY DB_KEY
[cardinality=1, cost=3.000]
=> BITMAP
[cardinality=1, cost=2.000]
=> INDEX (RDB$INDEX_4) RANGE SCAN
[cardinality=1, cost=2.000]
=> TABLE (RDB$RELATIONS) ACCESS BY DB_KEY
[cardinality=1, cost=3.000]
=> BITMAP
[cardinality=1, cost=2.000]
=> INDEX (RDB$INDEX_0) UNIQUE SCAN
[cardinality=1, cost=2.000]
Отметим один момент. Так как для внутреннего соединения все потоки равнозначны, оптимизатор в случае более чем двух потоков преобразует бинарное дерево в "плоский" вид. Выходит, что де-факто внутреннее соединение оперирует с более чем двумя входными потоками. На алгоритм это никак не влияет, однако объясняет разницу в синтаксисе планов для внутренних и внешних соединений.
Есть еще одна особенность рекурсивного алгоритма. Он никогда не использует индексы в случае полного внешнего соединения. Естественно, это приводит к крайне неэффективному выполнению этой операции. К слову, увидеть явную проблематичность рекурсивного алгоритма в каком-либо случае очень просто: если в плане выполнения любой входной поток для JOIN (кроме первого) описан как NATURAL, значит это будет выполняться очень медленно.
Теперь вернемся ненадолго к пункту 1.5, где мы говорили о процедурном доступе. Там было сказано, что кардинальность процедуры всегда принимается равной нулю. Что это нам дает? А это автоматически ставит процедуру в начало соединения. Таким образом, она всегда будет выполнена один раз вместо того, чтобы выполняться заново на каждой итерации (ведь индекс мы к ней применить не можем). Однако, тут есть неприятная особенность. Дело в том, что оптимизатор не в состоянии определить зависимость входных параметров процедуры от прочих потоков:
SELECT *
FROM MY_TAB, MY_PROC(MY_TAB.F)
или
SELECT *
FROM MY_TAB
JOIN MY_PROC(MY_TAB.F) ON 1 = 1
В данном случае процедура будет поставлена вперед, когда из таблицы MY_TAB еще не выбрана ни одна запись. Соответственно, на этапе исполнения будет выдана ошибка isc_no_cur_rec (no current record for fetch operation). Обходится данная проблема через явное указание порядка соединения синтаксисом:
SELECT *
FROM MY_TAB
LEFT JOIN MY_PROC(MY_TAB.F) ON 1 = 1
Теперь таблица всегда будет прочитана перед процедурой и все будет работать корректно.
Примечание: эта ошибка оптимизатора будет исправлена в следующих версиях сервера.
3.1.2. Однопроходное слияние
Слияние является альтернативным алгоритмом реализации соединения. В этом случае входные потоки полностью независимы. Для корректного выполнения операции потоки должны быть предварительно упорядочены по ключу соединения, после чего строится бинарное дерево слияния. Далее при фетче читаются записи из обоих потоков и их ключи связи сравниваются на равенство. При совпадении ключей запись возвращается на выход. Затем читаются новые записи из входных потоков и процесс повторяется. В отличии от предыдущего метода, слияние всегда выполняется в один проход, то есть каждый входной поток читается только один раз. Это возможно благодаря последовательному расположению ключей связи во входных потоках.
Однако, данный алгоритм не может быть использован для всех видов соединения. Как было отмечено выше, требуется сравнение ключей на строгое равенство. Таким образом, соединение с условием связи вида (ON MASTER.F > SLAVE.F) не может быть выполнено посредством однопроходного слияния. Справедливости ради стоит отметить, что соединения такого вида не могут быть эффективно выполнены никаким способом, так как даже в случае рекурсивного алгоритма на каждой итерации будут повторяющиеся чтения из внутреннего потока.
Тем не менее, у данного метода есть одно достоинство по сравнению с рекурсивным алгоритмом - допускается слияние на основе выражений. Например, соединение с условием связи вида (ON MASTER.F + 1 = SLAVE.F + 2) легко выполняется методом слияния. Причина понятна: нет зависимости между потоками и, следовательно, нет требования использования индексов.
Примечание: поддержка алгоритмом внешних соединений планируется в следующих версиях сервера.
Данный алгоритм способен обработать нескольких условий связи, объединенных через AND. При этом входные потоки просто сортируются по нескольким полям. Однако, в случае объединения условий связи через OR, метод слияния не может быть применен.
Оптимизатор выбирает данный алгоритм соединения только в случае невозможности или неоптимальности использования рекурсивного алгоритма, то есть в первую очередь при отсутствии индексов по условию связи или их неприменимости, а также при отсутствии зависимости между входными потоками. В планы выполнения однопроходное слияние отображается словом "MERGE", за которым в скобках через запятую описываются входные потоки.
SELECT *
FROM RDB$RELATIONS R
JOIN RDB$RELATION_FIELDS RF ON UPPER(R.RDB$RELATION_NAME) = UPPER(RF.RDB$RELATION_NAME)
WHERE R.RDB$SYSTEM_FLAG = 1
PLAN MERGE (SORT (RF NATURAL), SORT (R NATURAL))
STATEMENT (SELECT)
[cardinality=2500, cost=3000.000]
=> MERGE
[cardinality=2500, cost=3000.000]
=> SORT
[cardinality=500, cost=500.000]
=> BOOLEAN
[cardinality=500, cost=500.000]
=> TABLE (RDB$RELATIONS) SEQUENTIAL ACCESS
[cardinality=500, cost=500.000]
=> SORT
[cardinality=2500, cost=2500.000]
=> TABLE (RDB$RELATION_FIELDS) SEQUENTIAL ACCESS
[cardinality=2500, cost=2500.000]
Из вышесказанного можно сделать один важный вывод. Так как алгоритм слияния не поддерживается для внешних соединений, то всегда будет выбран рекурсивный алгоритм. Однако, он крайне неэффективен в случае отсутствия индексов по полю связи. Вывод: всегда индексируйте поля, по которым производится одностороннее внешнее соединение. Впрочем, эта рекомендация никак не поможет в случае полного внешнего соединения, которое в текущих версиях сервера всегда выполняются неоптимально. В данном случае можно рекомендовать замену FULL OUTER JOIN на две отдельных выборки из входных потоков, объединенных через UNION ALL (см. ниже).
3.1.3. Хеширование
Это еще один альтернативный метод выполнения соединения. В данном случае входные потоки всегда делятся на ведущий и ведомый, при этом ведомым обычно выбирается поток с наименьшей кардинальностью. Сначала меньший (ведомый) поток целиком вычитывается во внутренний буфер. В процессе чтения к каждому ключу связи применяется хеш-функция и пара {хеш, указатель в буфере} записывается в хеш-таблицу. После чего читается ведущий поток и его ключ связи опробуется в хеш-таблице. Если соответствие найдено, то записи обоих потоков соединяются и выдаются на выход. В случае нескольких дубликатов данного ключа в ведомой таблице на выход будут выданы несколько записей. Если вхождения ключа в хеш-таблицу нет, переходим к следующей записи ведущего потока и так далее.
Очевидно, что данный метод имеет все преимущества и недостатки однопроходного слияния: индексы для соединения не используются, возможна работа с выражениями, допустимо только соединение по строгому равенству ключей.
Данный алгоритм максимально эффективен при небольшом размере хеш-таблицы, именно поэтому почти всегда ведомым выбирается меньший из двух поток. В этом случае соединение хешированием всегда выигрывает у слияния, которое требует дополнительной сортировки входных потоков. Однако в случаях, когда обе таблицы слишком большие или когда используется односторонее внешнее соединение с большой ведомой таблицей, данный метод неэффективен и обычно уступает вышеописанным алгоритмам.
Соединение хешированием в Firebird отсутствует.
3.2. Объединение
Опять же, название говорит само за себя. Этот метод доступа выполняет операцию SQL-объединения (union). Существует два режима выполнения этой операции: ALL и DISTINCT. В первом случае реализация тривиальна: данный метод просто читает первый входной поток и выдает его на выход, по получении из него EOF начинает читать второй входной поток и так далее. То есть объединение только увеличивает итоговую кардинальность выборки. В случае же DISTINCT требуется устранить полные дубликаты записей, присутствующие в результате объединения. Для этого на выходе метода объединения размещается фильтр сортировки, работающий в "усекающем" режиме по всем полям.Стоимость выполнения объединения равна суммарной стоимости всех входных потоков, кардинальность также получается суммированием. В плане выполнения объединение отображается отдельными планами на каждый из входных потоков.
SELECT RDB$RELATION_ID
FROM RDB$RELATIONS
WHERE RDB$SYSTEM_FLAG = 1
UNION
SELECT RDB$PROCEDURE_ID
FROM RDB$PROCEDURES
WHERE RDB$SYSTEM_FLAG = 1
PLAN (RDB$RELATIONS NATURAL)
PLAN (RDB$PROCEDURES NATURAL)
STATEMENT (SELECT)
[cardinality=1500, cost=1500.000]
=> SORT
[cardinality=1500, cost=1500.000]
=> UNION
[cardinality=1500, cost=1500.000]
=> BOOLEAN
[cardinality=500, cost=500.000]
=> TABLE (RDB$RELATIONS) SEQUENTIAL ACCESS
[cardinality=500, cost=500.000]
=> BOOLEAN
[cardinality=1000, cost=1000.000]
=> TABLE (RDB$PROCEDURES) SEQUENTIAL ACCESS
[cardinality=1000, cost=1000.000]
Заключение
Выше мы рассмотрели все виды операций, которые участвуют в выполнении SQL-запросов. Для каждого алгоритма приведено подробное описание и примеры, включая детализацию дерева выполнения запроса. Имеет смысл отметить, что Firebird реализует не так и много методов доступа по сравнению с конкурентами, однако зачастую это объясняется либо особенностями архитектуры, либо сравнительно большей эффективностью имеющихся методов.Важным для понимания является также факт, что большинство операций выполняется сервером по мере фетча, а не сразу с последующей буферизацией результатов. Это обычно приводит к очень быстрой выдаче первых записей запроса. Исключениями из этого правила являются внешняя сортировка и использующие ее операции (например, GROUP BY или UNION DISTINCT).
Автор приветствует любые замечания и дополнения по приведенным материалам. Для связи с автором используйте адрес электронной почты, указанный в начале статьи.