Введение в оптимизацию запросов

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

Компонента SQL СУБД, которая определяет, как осуществлять навигацию по физическим структурам данных для доступа к требуемым данным, называется оптимизатором запросов (query optimizer).

Навигационная логика (вариант алгоритма) для доступа к требуемым данным называется путем или методом доступа (access path).

Последовательность выполняемых оптимизатором действий, которые обеспечивают выбранные пути доступа, называется планом выполнения (execution plan).

Процесс, используемый оптимизатором запросов для определения пути доступа, называется оптимизацией запросов (query optimization).

Во время процесса оптимизации запросов определяются пути доступа для всех типов команд SQL DML. Однако команда SQL SELECT представляет наибольшую сложность в решении задачи выбора пути доступа. Поэтому этот процесс обычно называют оптимизацией запроса, а не оптимизацией путей доступа к данным. Далее следует отметить, что термин оптимизация запросов является не совсем точным в том смысле, что нет гарантии, что в процессе оптимизации запроса будет действительно получен оптимальный путь доступа. Более подходящим термином мог бы быть термин "улучшение запроса" (query improvement). Например, наилучший возможный путь доступа, имеющий заданную стоимость (в смысле вычислительной сложности). Далее всюду используется стандартный общепринятый термин "оптимизация запросов" во избежание недоразумений.

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

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

Синтаксическая оптимизация

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

Пример. Рассмотрим следующий запрос, который делает выборку данных из таблиц PRODUCT (ПРОДУКЦИЯ) и VENDOR (ПРОИЗВОДИТЕЛЬ):

SELECT VENDOR_CODE, PRODUCT_CODE, PRODUCT_DESC
FROM VENDOR, PRODUCT
WHERE VENDOR.VENDOR_CODE = PRODUCT.VENDOR_CODE
AND VENDOR.VENDOR_CODE = "100";

Наиболее очевидный путь обработки этого запроса состоит в следующем:

Оценим стоимость процесса обработки этого запроса в терминах операций ввода/вывода. Пусть для определенности таблица VENDOR содержит 50 строк, а таблица PRODUCT - 1000 строк. Тогда формирование декартова произведения потребует 50050 операций чтения и операций записи (в результирующую таблицу). Для ограничения результирующей таблицы потребуется более 50000 операций чтения и, если 20 строк удовлетворяют условиям поиска, то 20 операций записи. Выполнения операции проекции вызовет еще 20 операций чтения и 20 операций записи. Таким образом, обработка этого запроса обойдется системе в 100090 операций чтения и записи.

Основная идея синтаксической оптимизации лежит в использовании эквивалентных алгебраических преобразований. SQL является алгебраическим языком манипулирования множествами (представленными таблицами). Каждый оператор SELECT эквивалентен некоторой формуле этого языка. Существует набор алгебраических правил для тождественных преобразований формул над множествами. Для данного примера запроса можно использовать следующую эквивалентность:

(A JOIN B) WHERE restriction on A v (A WHERE restriction on A) JOIN B.

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

Обработка запроса в этом случае потребует 1120 операций чтения и 40 операций записи для получения того же самого результата, что и в первом случае. Преобразование, описанное в данном примере, называется синтаксической оптимизацией (syntax optimization).

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

Оптимизация, основанная на правилах

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

Кроме того, появилось много новых алгоритмов для выполнения соединения таблиц. Двумя наиболее основными алгоритмами выполнения соединения являются:

Операции соединения подчиняются как коммутативному, так и ассоциативному закону. Следовательно, теоретически возможно выполнять соединение в любом порядке. Например, все следующие предложения являются эквивалентными:

(A JOIN B) JOIN C
A JOIN (B JOIN C)
(A JOIN C) JOIN B

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

Одним из первых подходов на пути борьбы с комбинаторной сложностью выполнения соединений состоит в установлении эвристических правил для выбора между путями доступа и методами соединений, которая называется оптимизацией, основанной на правилах (rule-based optimization). В этом подходе веса и предпочтения назначаются альтернативам на основе принципов, которые являются общепризнанными. Используя эти веса и предпочтения, оптимизатор запросов производит возможные планы выполнения до тех пор, пока не будет достигнут лучший план выполнения, удовлетворяющий этим правилам. Некоторые из этих правил, используемых оптимизаторами такого типа, основываются на размещении переменных служебных символов (variable tokens), таких как имена таблиц и колонок в синтаксических структурах запроса. Когда эти имена размещаются, иногда может существовать значительная разница в производительности выполнения запроса. По этой причине оптимизаторы, основанные на правилах, как говорят, являются синтаксически зависимыми, и одним из методов настройки оптимизаторов этого типа СУБД является размещение символов (tokens) в различных позициях внутри утверждения.

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

Эти характеристики данных могут сильно влиять на эффективность обработки запроса. Использование таких характеристик приводит к следующему типу оптимизации.

Оптимизация, основанная на вычислении стоимости

Оптимизация, основанная на вычислении стоимости запроса (cost-based optimization), аналогична оптимизации, основанной на правилах, за исключением того, что оптимизатор на основе вычисления стоимости использует статистическую информацию для выбора наиболее эффективного плана выполнения запроса. Стоимость каждого альтернативного плана выполнения запроса оценивается с помощью статистики, такой как число строк в таблице и числа и распределения значений колонки таблицы. Формулы стоимости обычно учитывают количество ввода/вывода и время CPU, необходимое для выполнения плана запроса. Такая статистика хранится в системном каталоге и поддерживается СУБД.

Для понимания того, как статистика может быть использована для выбора плана выполнения запроса, рассмотрим следующий запрос к таблице CUSTOMER (ПОКУПАТЕЛЬ):

SELECT CUST_NBR, CUST_NAME
FROM CUSTOMER
WHERE STATE = "FL";

Если индекс существует на колонку STATE, оптимизатор, основанный на правилах, использовал бы его для обработки запроса. Однако если девяносто процентов строк в таблице CUSTOMER имеют FL в колонке STATE, то использование индекса будет в действительность приводить к более медленному выполнению запроса, чем простая последовательная обработка таблицы. Оптимизатор, основанный на вычислении стоимости, с другой стороны, обнаружил бы, что использование индекса не дает никаких преимуществ перед последовательным просмотром таблицы.

Подход к оптимизации, основанный на вычислении стоимости, сегодня представляет определенное искусство в технике оптимизации запросов. Большинство реляционных СУБД применяют оптимизаторы, основанные на вычислении стоимости.

Последовательность шагов оптимизации запросов

Несмотря на то, что оптимизаторы запросов современных реляционных СУБД различаются по сложности и принципам создания, все они следуют одним и тем основным этапам в выполнении оптимизации запроса.

Так как шаги 1 и 2 имеют место независимо от действительных данных, находящихся в таблицах, нет необходимости повторять их, если запрос не требует перекомпиляции. Следовательно, большинство оптимизаторов будут сохранять результаты 2-го шага и использовать его снова, когда они переоптимизируют запрос в другой раз.

Обзор оптимизатора запросов

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

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

Также будут изложены основы реализации реляционных операций SQL, с последующим изложением методов, которые использует SQLBase при фактическом выполнении этих операторов. Это множество методов, называемое физическими операторами (physical operators), является последовательностью действий, которые рассматривает оптимизатор, когда строит план доступа.

Сначала мы рассмотрим, как выполняются физические операторы. Мы также кратко суммируем основные факторы, включая стоимость каждого из них (обычно в терминах ввода/вывода). В завершении будет объяснена структура плана доступа, с акцентом на эвристиках, используемых оптимизатором при построении множества планов доступа, для которых выполняется анализ стоимости.

На протяжении всех остальных трех частей примеры, которые иллюстрируют операции оптимизатора, обычно используют команду SELECT. Однако следует помнить, что все команды манипулирования данными (DML), т.е. команды INSERT, UPDATE, DELETE, обрабатываются оптимизатором.

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

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

Реляционные операции

Основные операторы реляционной алгебры были определены Э.Ф. Коддом, когда он опубликовал свою основополагающую работу по языкам манипулирования данными в реляционной модели в 1972 году. Операции, определенные в этой реляционной алгебре, формируют логические операторы, которые должны быть обработаны оптимизатором. Эти логические операторы являются неявными для синтаксиса команд SQL DML, но именно они и обрабатываются СУБД.

Операции реляционной алгебры имеют на входе одно или более отношений на входе и одно отношение на выходе. Отношением является просто таблица некоторой степени n, где n - число атрибутов (или колонок) в таблице. Эти операторы разделяются на два класса: теоретико-множественные операции (traditional set operations) и специальные реляционные операторы (special relational operators). В то время как использование теоретико-множественных операций обычно достаточно для обработки большинства реляционных запросов, специальные операторы определяют желаемый результат более эффективно. Этот последний класс будет изучен в этом разделе более подробно, в то время как теоретико-множественные операции будут определены в общих чертах (предполагается, что они хорошо известны после изучения предыдущих л екций этого курса).

Теоретико-множественные операции

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

Специальные реляционные операторы

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

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

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

SELECT NAME, PHONE
FROM CUSTOMER;

Альтернативой к выполнению проекции является использование символа "*", который приводит к выводу всех колонок таблицы:

SELECT * FROM CUSTOMER;

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

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

SELECT * FROM CUSTOMER WHERE NAME = 'JONES';
SELECT * FROM PRODUCT WHERE STOCK_QTY <= REORDER_QTY;
SELECT * FROM ORDER WHERE
(STАTUS IN ('C','P','S')) AND (TOTAL_AMT > 1000);

Каждое сравнение, содержащееся в предложении WHERE, называется предикатом (predicate). Некоторые команды SQL, подобно последней в приведенных примерах, содержат более одного предиката. Когда операция, указанная в предикате, выполняется на строке, то это называется взятием предиката (applying the predicate). Если предикат вычисляется как TRUE, то говорят, что условие выбора удовлетворено, в противном случае - не удовлетворено. Когда утверждение имеет более чем один предикат, они должны быть связаны одним или боле логическими операторами AND или OR. Когда все предикаты связаны операцией AND, то говорят, что это конъюнкция (conjunctive), когда OR, то говорят, что это дизъюнкция (disjunctive). Эта терминология предикатов играет важную роль в том, как они используются оптимизатором запросов.

Заметим, что форма предложения WHERE, которая сравнивает колонки из различных таблиц, не является операцией селекции, но является спецификацией для операции соединения.

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

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

SELECT NAME, AMOUNT
FROM CUSTOMER, RECEIVABLE
WHERE CUSTOMER.CUST_NO = RECEIVABLE. CUST_NO;
SELECT NAME, QTY, DESC
FROM CUSTOMER C, ORDER O, PRODUCT P
WHERE ( C.CUST_NO = O. CUST_NO )
AND (P.CUST_NO = O. CUST_NO );

Во втором примере буквы С, О, Р позволяют вам квалифицировать имена колонок соответствующих таблиц без указания их полных имен. В SQL это называется корреляционными переменными (correlation variables). Так как большинство имен колонок должны быть квалифицируемыми, то они часто используются в соединениях благодаря представлению нескольких имен таблиц в предложении FROM.

Две важнейших характеристики операции соединения состоят в том, что она является коммутативной и ассоциативной:

A JOIN B = B JOIN A; (коммутативность)
A JOIN (B JOIN C) = (A JOIN B) JOIN C; (ассоциативность)
(A JOIN B) JOIN C = B JOIN (A JOIN C).

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

Тип операции сравнения часто используется для классификации операций соединения.

Эквисоединение (Equijoin). Наиболее общим примером соединения является эквисоединение, которое использует оператор сравнения "=". Эта версия операции соединения применяется, когда взаимосвязь между объектами предметной области требует комбинации информации из двух таблиц по равенству значений в соответствующих колонках. Такие соединения реализуются установкой первичного ключа родительской таблицы равным внешнему ключу таблицы-потомка.

SELECT C.CUST_NO, C.CUST_NAME, O.ITEM_NO, I.DESC
FROM CUST C, ORDER O, ITEM I
WHERE (C.CUST_NO = O.CUST_NO) AND
(O.ITEM_NO = I.ITEM_NO);

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

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

SELECT P.PROD_NO, P.PROD_DESC
FROM PRODUCT P, ORDER O
WHERE (O.PROD_NO = P.PROD_NO) AND
(O.ORD_DATE BETWEEN JAN-1-1995 AND JAN-31-1995);

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

Внешнее соединение (Outerjoin). Внешнее соединение позволяет включать в результирующие множество незадействованные строки (non-participating rows) одной из таблиц, которые не соответствуют условиям соединения. Причина, по которой эти строки называются незадействованными, состоит в том, что они содержат значения ключей, которые не ссылаются на какую-либо строку другой таблицы. Например, строка в множестве товары содержит номер продукта, который никогда не будет учитываться каким-либо производителем, - такая строка была бы незадействованной в соединении таблицы "товары" и таблицы "счета". В SQLBase эти строки могут быть включены в результирующее множество посредством указания оператора внешнего соединения "+", на ключе таблице ORDER, как показано в примере.

SELECT *
FROM PRODUCT P, ORDER O
WHERE P.PROD_NO = O.PROD_NO(+);

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

SELECET E.NAME, M.NAME
FROM EMPLOYEE E, EMPLOYEE M
WHERE E.MNGR_NO = M. EMPLOYEE_NO;

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

SQL поддерживает два типа агрегации, простейший из которых есть скалярная агрегация, которая производит единственный вывод для колонки отношения. Скалярная агрегация в SQL выполняется посредством включения функций агрегирования в запрос, который не имеет какого-либо предложения GROUP BY. Например:

SELECT SUM(SALARY) FROM EMPLOYEE;
SELECT COUNT(*)
FROM EMPLOYEE
WHERE NAME = 'DAVE';

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

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

Синтаксис SQL для выполнения функции агрегации всегда включает предложение GROUP BY. Колонки, названные в предложении GROUP BY, становятся в действительности ключом к некоторой новой таблице, которая выводится этим утверждением. Например, функцией агрегирования является

SELECT DEPT, AVG(SALARY)
FROM EMPLOYEE
GROUP BY DEPT;
SELECT @MONTH(BIRTH_DAY), COUNT(*)
FROM EMPLOYEE
GROUP BY :1;

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

Физические операции

Когда SQLBase выполняет план запроса, она читает план и вычисляет каждый указанный пункт плана. Каждый из этих пунктов плана сообщает SQLBase, какую операцию нужно выполнить на этом шаге и какие ввод и вывод требуются. При выполнении плана запроса, SQLBase использует физические операции (physical operators). Эти операции отличаются от логических операций, таких как утверждения SQL, определяющих реляционные операции, которые следует выполнить. Для каждой возможной логической операции существует по крайней мере одна и, возможно, много физических операций, которые позволяют СУБД выполнять операцию эффективным способом.

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

Сортировка и агрегация

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

Операция агрегирования также имеет одну таблицу на входе и одну таблицу на выходе. Физическая операция агрегирования SQLBase выполняет последовательное сканирование квалифицируемых строк данных, с вычислением агрегатной функции для каждой строки. Когда выполняется скалярная агрегация, входные строки могут располагаться в любой последовательности. Однако при групповой агрегации, когда функция агрегирования вычисляется, входная таблица должна быть представлена в последовательности значений колонки, указанной в предложении GROUP BY.

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

Операции доступа к диску

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

К операциям доступа к диску относятся следующие операции.

Сканирование таблицы (Table scan). Эта операция является простейшим методом доступа к физической таблице. Каждая страница данных, связанная с таблицей, читается. Для каждой страницы строки из нее экстрагируются для обработки. Заметим, что такое экстрагирование может потребовать доступа к дополнительным страницам, представляющим либо страницы экстентов, либо страницы переполнения. В отсутствии страниц экстентов или страниц переполнения число доступов к диску, требуемых для сканирования данных, равно числу страниц данных, назначенных таблице, включая страницы, необходимые для колонок типа LONG VARCHAR, которые могут быть указаны.

Сканирование нижнего уровня индекса (Index leaf scan). Этот метод доступа используется когда определенная последовательность расположения строк таблицы желательна, и индекс обеспечивает эту последовательность, но не существует никаких предикатов для поиска в таблице, которые затрагивают колонки индекса. Другими словами, этот метод доступа может заменить операцию сортировки, если индекс соответствует желаемой последовательности расположения строк.

Основой этого метода является физический метод доступа на основе В+ -дерева, который связывает вместе страницы листьев дерева. Этот связный список страниц листьев называется последовательным подмножеством индекса (sequence set). Он строится в соответствии с последовательностью ключа, для каждой из узловой строки индекса, доступной как узел при обработке. Это означает, что наихудший случай оценки ввода/вывода есть число страниц листьев в индексе плюс число строк в таблице. Это число иногда может быть увеличено, если таблица полностью или частично разбита на кластеры в индексной последовательности. Вы увидите, как оптимизатор оценивает эту возможность далее.

Сканирование индекса (Matching index scan). Сканирование индекса использует полные возможности индексной структуры В+ -дерева в SQLBase. Этот метод доступа используется, когда утверждение SQL требует только часть таблицы для обработки, основываясь на предикате, который использует колонки, представленные в индексе. Так как генетические возможности индексов В+ -дерева эксплуатируются SQLBase, этот метод доступа может использоваться для любого индекса, который имеет колонку из предиката в наиболее левой позиции ключа. Оптимизатор обычно использует этот метод доступа, если предикаты значительно ограничивают объем ввода/вывода на индексе. Также, если предикат неравенства применяется для некоторой колонки индекса, этот метод использует дерево индекса для того, чтобы найти начальный лист, и затем сканировать последовательное подмножество индекса вперед или назад от найденной точки.

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

Хэширование (Hash access). Таблица, которая имеет кластеризованный хэш-индекс на ней, может быть доступна через этот индекс, когда все колонки, содержащиеся в индексе, используются в предикате равенства утверждения SQL. Реализованный метод хэширования не обладает какими-либо генетическими или сканирующими механизмами. Это объясняет, почему ключ такого индекса должен быть полностью указан в предикате равенства в утверждении SQL.

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

Операции соединения

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

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

К операциям соединения относят следующие физические операции.

Простой алгоритм соединения в цикле (Simple loop join). Этот алгоритм является простейшим прямолинейным методом соединения двух таблиц. Он может иметь наихудшую стоимость выполнения для операции соединения, особенно если входные таблицы большие. Одно из преимуществ простого соединения в цикле состоит в том, что он может быть использован независимо от типа критерия соединения, наличия или отсутствия индексной структуры. Также существуют ситуации, где данный алгоритм может иметь лучшую производительность, в частности, если одна из входных таблиц помещается в кэш-память.

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

Благодаря вложенной циклической структуре метода наихудший случай для числа операций ввода/вывода есть число страниц данных во внутренней таблице, умноженное на число страниц данных во внешней таблице. Это может быть не так драматично, если внутренняя таблица невелика и полностью размещается в кэш-памяти. Тогда число операций ввода/вывода сокращается до суммы числа страниц данных внешней и внутренней таблиц. По этой причине SQLBase всегда выбирает меньшую из двух таблиц в качестве внутренней для размещения ее в кэш-памяти. Когда кэш-памяти достаточно для размещения одной из таблиц, то этот метод становится более предпочтительным по стоимости, чем другие.

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

Циклическое соединение с индексом (Loop join with index). Вариант вложенного циклического соединения может быть применен, когда существует индекс для одной из таблиц, который построен на колонках соединения по возрастанию значений ключа. Когда есть такая ситуация, оптимизатор использует таблицу с индексом как внутреннюю таблицу для алгоритма циклического соединения, и задействует индекс для того, чтобы ограничить поиск строк, соответствующих текущей удерживаемой строке из внешней таблицы. Это значительно уменьшает число операций ввода/вывода, необходимых для обработки внутренней таблицы. Наилучшим случаем является ситуация, когда внутренняя таблица кластеризована и обрабатывается эквисоединение, тогда объем ввода/вывода равен сумме числа страниц данных в двух таблицах, плюс высота дерева индекса, плюс число строк во внешней таблице. Последние две компоненты стоимости вычисляются для оценки доступа к индексной структуре во время реализации соединения строки.

Циклическое соединение с хэш-индексом (Loop join with hash index). Эта разновидность метода циклического соединения может применяться, когда одна из соединяемых таблиц имеет CHI. Два других требования к этому методу состоят в том, что хэш-индекс должен быть создан для всех колонок из критерия соединения (и никаких других) и соединение должно являться эквисоединением. Когда эти условия выполняются, этот метод соединения может быть очень эффективным. Наихудший случай есть ситуация, когда число операций в/в равно числу страниц данных во внешней таблице плюс число строк во внутренней таблице. Это происходит только в случае ввода/вывода, если каждая строка во внутренней таблице ссылается на внешнюю таблицу. Когда не все строки внутренней таблицы ссылаются на внешнюю таблицу, то число операций ввода/вывода ограничивается.

Соединение посредством объединения индекса (Index merge join). Этот метод может быть использован, когда существуют индексы для колонок критерия соединения обеих таблиц. Основной алгоритм состоит в сканировании подмножества последовательности этих двух индексов и объединении строк из таблицы, основываясь на соответствие ее критерия соединения. Например, когда обрабатывается эквисоединение, то сначала вход индекса читается из последовательности листьев внешней таблицы. Затем вход читается из последовательности листьев внутренней таблицы. Если колонка соединения внутренней таблицы меньше, чем внешней, то сканирование внутренней таблицы продолжается. Если больше, то сканируется последовательность листьев внешней таблицы до тех пор, пока значение, равное или большее, не будет найдено. Когда колонки соединения в обоих индексах удовлетворяют критерию соединения, строки таблиц читаются из страниц данных, добавляются одна к другой и записываются в выходную таблицу.

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

Соединение хэширования (Hash join). Этот метод может быть использован только для эквисоединения и не требует каких-либо индексов для колонок критерия соединения двух таблиц. Алгоритм сначала выполняет фазу установки, когда сканируется внешняя таблица и каждая строка помещается в хэш-таблицу согласно значению хэш-функции для критерия соединения. Наименьшая таблица всегда выбирается как внешняя, для того чтобы минимизировать память под хэш-таблицу.

На второй фазе, называемой проба (probe), внутренняя таблица сканируется, и хэш-функция используется для выборки возможных значений. Любая строка, найденная в хэш-бакете для первой таблицы, затем проверяется. Строки, которые удовлетворяют критерию поиска, добавляются к строке внутренней таблицы и записываются в выходную таблицу.

Это может быть очень быстрым методом соединения, особенно когда меньшая таблица может быть хэширована в таблицу в оперативной памяти. Когда это возможно, стоимость ввода/вывода равна сумме страниц данных двух таблиц. С другой стороны. дополнительный ввода/вывода требуется при разбиении хэш-таблицы на сегменты, а также для управления ими во временном файле на диске.

Другие физические встроенные операции

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

Выборка (Select). Операция выборки ограничивает доступ к строкам, которые не удовлетворяют логике предиката запроса. Эти предикаты оцениваются как можно раньше при выполнении запроса, который поступает обычно, когда строка, содержащая колонки в предикате, обрабатывается в первый раз. Каждый физический оператор доступа к файлу в SQLBase проверяет предикат для фильтрования строк при обработке таблицы. Если предикаты в запросе являются конъюнкцией, формируется логика, называемая обрыванием логической цепочки (short-circuit), для тестирования обрабатываемых строк. Это позволяет отказаться от обработки строк, как только встречается первое несоответствие условию запроса.

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

Проекция (Project). Операция проекции реализуется совместно с другими физическими операторами, передавая им список колонок, которые должны быть выбраны. Этот оператор затем только включает эти колонки в свой выходной файл. Выполнение проекции как можно раньше в плане запроса ограничивает ширину временной таблицы и результирующего множества, таким образом экономя пространство в памяти и на диске. Заметим, что одним посторонним действием выполнения проекции во время доступа к странице является возможное ограничение ввода/вывода благодаря отказу от доступа к экстентам или страницам LONG VARCHAR, которые не содержат требуемых колонок.

Доступ к таблице только через индекс (Index-only table access). Одним из эффектов встраивания операции проекции в другие физические операции является возможность выполнить доступ только через индекс. Это случается тогда, когда колонки, специфицируемые в проекции, все представлены в индексе. Этот индекс также можно использовать, когда предикат требуется для операции выборки. Когда это происходит, оптимизатор решает, что требования к данным запроса могут быть удовлетворены без доступа к страницам данных таблицы. Это может привести к значительному сокращению операций ввода/вывода, в зависимости от числа строк, которые удовлетворяют предикату запроса.

Структура плана запроса

Когда оптимизатор группирует множество физических операций для выполнения утверждения SQL, то полученная спецификация называется планом запроса (query plan).

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

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

Дерево запроса

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

Следующий пример показывает дерево запроса для утверждения SQL, которое получает имена авторов книг, опубликованных в 1993 году:

SELECT A.NAME
FROM AUTHORS A, BOOCKS B
WHERE (B.DATE_PUBLISHED ='1993') AND (A.NAME = B.NAME);

Построение дерева запроса

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

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

SELECT A.NAME
FROM AUTHORS A, BOOCKS B
WHERE (B.DATE_PUBLISHED ='1993') AND (A.NAME = B.NAME);

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

Преобразование логики предиката

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

WHERE COL1 > 5 OR (COL2 < 500 AND COL3 >150)

может быть переписано как

WHERE (COL1 > 5 OR COL2 < 500) AND ( COL1 >5 OR COL3 <150).

Конъюнктивная форма является предпочтительнее, так как может быть оценена с помощью метода укороченной цепочки. Набор предикатов в конъюнктивной форме будет истинным только и только тогда, когда каждая компонента с OR будет истинной. Так как число операций сравнения, которое выполняется для запроса, прямо влияет на время CPU, использование метода укороченной цепочки для конъюнктивной формы представления предикатов может сократить число циклов CPU.

Литература: [7], [23].