Декларативные языки обработки данных
С началом использования SQL-технологии и систем реляционных БД стало возможным разрушить взаимосвязь между прикладными программами и физическими структурами данных. Декларативные языки обработки данных только специфицируют, какие данные необходимы прикладной программе, оставляя за СУБД привилегию определять, как осуществлять навигацию по физической структуре данных для доступа к требуемым данным. SQL есть пример декларативного языка обработки данных.
Концепция независимости прикладных программ от физической структуры данных дает несколько значительных преимуществ.
Отражение требований к изменению в структурах данных незначительно влияет на существующие прикладные программы. Например, если существующий индекс становится устаревшим, то его можно свободно удалить и создать новый индекс (в том числе и на других атрибутах) без влияния на существующие программы. Созданный новый индекс может либо улучшить производительность программы, либо ухудшить ее. Однако можно быть уверенным в том, что существующие программы будут выполняться без ошибок. Предполагается, что команда SQL будет подготовлена до выполнения (PREPARE), хотя некоторые реляционные СУБД, такие как SQLBase, могут автоматически перекомпилировать сохраняемый план доступа команды SQL (SQL access plan). В процедурных языках обработки данных не всегда является очевидным, что привело к аварийному завершению программы - изменения в физической структуре или ее несоответствие программной логике.Уменьшается сложность прикладной программы. СУБД, а не программист, определяет, как осуществлять навигацию по физической структуре данных. Такое решение освобождает программиста для решения других задач, так как этот аспект программирования является часто наиболее сложным аспектом программной логики.Снижается число ошибок в прикладных программах. Сложность доступа к данным часто приводит к программным ошибкам, если программист не обладает высокой квалификацией или не очень тщательно кодирует. Главное преимущество компьютера состоит в способность выполнять простые инструкции с высокой скоростью и без ошибок. Следовательно, СУБД в целом заменяют программиста, когда определяют, как осуществлять навигацию по физической структуре данных для доступа к требуемым данным.
Дерево запроса
Одним из способов представления запроса, которое обеспечивает понимание механизма его выполнения, является дерево запроса (query tree). Дерево запроса представляет собой древовидную структуру, в которой окончательный результат запроса находится на вершине дерева (в его корне) и таблицы БД, участвующие в запросе, являются листьями этого дерева. Промежуточные узлы дерева представляют физические операции, которые должны выполняться во время запроса. Когда план запроса выполняется, то последовательность обхода узлов осуществляется снизу вверх и слева направо.
Следующий пример показывает дерево запроса для утверждения SQL, которое получает имена авторов книг, опубликованных в 1993 году:
SELECT A.NAME FROM AUTHORS A, BOOCKS B WHERE (B.DATE_PUBLISHED ='1993') AND (A.NAME = B.NAME);
Рис. 15.1. Дерево запроса
Другие физические встроенные операции
Две наиболее часто используемые реляционные операции - выборка и проекция - реализованы с помощью других физических операций. Это позволяет оптимизатору выполнять эти операции за наименьшее возможное время в плане доступа, непосредственно ограничивающего количество данных, которым остаток плана должен управлять. Реализация операции проекции далее усиливает выполнение доступа только через индекс, когда это подходит.
Выборка (Select). Операция выборки ограничивает доступ к строкам, которые не удовлетворяют логике предиката запроса. Эти предикаты оцениваются как можно раньше при выполнении запроса, который поступает обычно, когда строка, содержащая колонки в предикате, обрабатывается в первый раз. Каждый физический оператор доступа к файлу в SQLBase проверяет предикат для фильтрования строк при обработке таблицы. Если предикаты в запросе являются конъюнкцией, формируется логика, называемая обрыванием логической цепочки (short-circuit), для тестирования обрабатываемых строк. Это позволяет отказаться от обработки строк, как только встречается первое несоответствие условию запроса.
Когда оптимизатор оценивает стоимость запроса, действие предикатов, используемое в операции выборки, принимается во внимание посредством статистики, называемой фактором селективности (selectivity factor). Это отношение представляет собой пропорцию строк в таблице, которые, как можно было ожидать, будут выбраны в конкретном предикате. Оптимизатор делает свои оценки этого фактора на основе статистики, связанной с индексами таблицы и некоторыми эвристиками, касающимися операций сравнения предикатов.
Проекция (Project). Операция проекции реализуется совместно с другими физическими операторами, передавая им список колонок, которые должны быть выбраны. Этот оператор затем только включает эти колонки в свой выходной файл. Выполнение проекции как можно раньше в плане запроса ограничивает ширину временной таблицы и результирующего множества, таким образом экономя пространство в памяти и на диске. Заметим, что одним посторонним действием выполнения проекции во время доступа к странице является возможное ограничение ввода/вывода благодаря отказу от доступа к экстентам или страницам LONG VARCHAR, которые не содержат требуемых колонок.
Доступ к таблице только через индекс (Index-only table access). Одним из эффектов встраивания операции проекции в другие физические операции является возможность выполнить доступ только через индекс. Это случается тогда, когда колонки, специфицируемые в проекции, все представлены в индексе. Этот индекс также можно использовать, когда предикат требуется для операции выборки. Когда это происходит, оптимизатор решает, что требования к данным запроса могут быть удовлетворены без доступа к страницам данных таблицы. Это может привести к значительному сокращению операций ввода/вывода, в зависимости от числа строк, которые удовлетворяют предикату запроса.
Физические операции
Когда SQLBase выполняет план запроса, она читает план и вычисляет каждый указанный пункт плана. Каждый из этих пунктов плана сообщает SQLBase, какую операцию нужно выполнить на этом шаге и какие ввод и вывод требуются. При выполнении плана запроса, SQLBase использует физические операции (physical operators). Эти операции отличаются от логических операций, таких как утверждения SQL, определяющих реляционные операции, которые следует выполнить. Для каждой возможной логической операции существует по крайней мере одна и, возможно, много физических операций, которые позволяют СУБД выполнять операцию эффективным способом.
Каждая физическая операция имеет один или два входа, в зависимости от природы операции. Также она имеет одну таблицу на выходе (которая, конечно, может содержать одну единственную строку или вовсе не содержать строк). Эта выходная таблица может быть результирующим множеством, которое представляет окончательный вывод для запроса, или может быть промежуточной таблицей, которая будет использована как вход для некоторой операции согласно плану запроса. Одному плану запроса может соответствовать много таких промежуточных таблиц. Они могут быть сохранены в кэш-памяти СУБД или во временном файле на диске. Когда шаг плана запроса завершает выполнение, временные входные таблицы удаляются из памяти или диска.
Языки обработки данных и задача оптимизации обработки данных
Базы данных (БД) можно рассматривать как коллекции данных, предназначенных для совместного, коллективного использования в организации. Это предполагает, что БД представляет собой именованную, структурированную и интерпретируемую совокупность данных пользователей. Физически данные в базах данных представляются в машиночитаемой форме. Логическая структура данных и доступ к ним поддерживаются СУБД. Доступ к данным посредством СУБД осуществляется с помощью языков обработки (манипулирования) данными. Язык манипулирования данными используется для обеспечения доступа к данным при их сохранении в БД или выборки из нее.
Независимо от того, является ли БД распределенной или централизованной, данные размещаются в файлах операционной системы компьютера (компьютеров). Ввод/вывод и актуализация данных в БД, поиск данных, требуемых при чтении, добавление новых, модификация существующих и удаление потерявших актуальность осуществляется СУБД и требует разделения используемых ресурсов процессоров, памяти и средств связи. Производительность информационной системы с базами данных определяется через среднее время реакции системы на выполнение операции поиска и предоставления требуемой информации. Время реакции системы зависит от множества факторов, таких как пропускная способность сети, пропускная способность СУБД, мощности процессоров используемых компьютеров, скорости чтения / записи на физические носители и т.д. Она также зависит от логической структуры БД и языковых средств доступа к данным.
Поэтому, для того чтобы лучше понять суть процессов оптимизации запросов в реляционных БД, необходимо сначала обсудить основные типы языков манипулирования данными. В настоящее время различают два основных типа таких языков: процедурные и декларативные.
Обзор оптимизатора запросов
В следующих разделах лекции на примере оптимизатора запросов СУБД SQLBase мы расскажем об общих принципах работы оптимизаторов. Оптимизатор запросов SQLBase (далее просто - оптимизатор) является специфической реализацией оптимизатора, основанного на вычислении стоимости, который принимает свои решения о выборе пути доступа на основе оценок потенциальной стоимости, связанной с выполнением конкретного плана доступа.
Основой этих стоимостных оценок является статистика, содержащаяся в системном каталоге SQLBase и областях управления базой данных. Преимущество такого подхода состоит в том, что решения о плане доступа могут быть сделаны на очень новой информации, связанной с действительным содержанием базы данных. Насколько нова и точна эта информация, зависит от процедур, которым вы следуете в администрировании вашей базы данных.
Также будут изложены основы реализации реляционных операций SQL, с последующим изложением методов, которые использует SQLBase при фактическом выполнении этих операторов. Это множество методов, называемое физическими операторами (physical operators), является последовательностью действий, которые рассматривает оптимизатор, когда строит план доступа.
Сначала мы рассмотрим, как выполняются физические операторы. Мы также кратко суммируем основные факторы, включая стоимость каждого из них (обычно в терминах ввода/вывода). В завершении будет объяснена структура плана доступа, с акцентом на эвристиках, используемых оптимизатором при построении множества планов доступа, для которых выполняется анализ стоимости.
На протяжении всех остальных трех частей примеры, которые иллюстрируют операции оптимизатора, обычно используют команду SELECT. Однако следует помнить, что все команды манипулирования данными (DML), т.е. команды INSERT, UPDATE, DELETE, обрабатываются оптимизатором.
Последовательность действий, используемая при обработке этих команд, виртуально идентична последовательности действий при обработке команды SELECT, с той лишь разницей, что должны быть выполнены операции блокировки и записи в журналы транзакций во время операций модификации данных. Преимущество использования команды SELECT для примеров состоит в том, что она охватывает многие реляционные операции, такие как соединение, которое более сильно влияет на характер процесса оптимизации по сравнению с другими командами DML.
Вторым преимуществом использования команды SELECT для примеров является то, что выполнение этой команды приводит к созданию результирующего множества, которое визуально показывает окончательный результат обработки запроса. Это является контрастом по сравнению с другими командами DML, которые изменяют состояние базы данных, но эти изменения не являются визуальными за исключением сообщений об ошибках или значениях встроенных переменных. Только команды SELECT будут визуально отражать эти изменения в содержании базы данных, сделанные при выполнении других команд DML.
Операции доступа к диску
Эта группа физических операций предусмотрена для выборки строк из одной таблицы. Эти строки затем могут либо быть обработаны на других шагах плана запроса, либо составлять окончательное результирующее множество в зависимости от обработки утверждения 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), внутренняя таблица сканируется, и хэш-функция используется для выборки возможных значений. Любая строка, найденная в хэш-бакете для первой таблицы, затем проверяется. Строки, которые удовлетворяют критерию поиска, добавляются к строке внутренней таблицы и записываются в выходную таблицу.
Это может быть очень быстрым методом соединения, особенно когда меньшая таблица может быть хэширована в таблицу в оперативной памяти. Когда это возможно, стоимость ввода/вывода равна сумме страниц данных двух таблиц. С другой стороны. дополнительный ввода/вывода требуется при разбиении хэш-таблицы на сегменты, а также для управления ими во временном файле на диске.
Оптимизация, основанная на правилах
Когда был достигнут некоторый прогресс в улучшении обработки запросов, были предприняты и усилия для улучшения методов доступа к таблицам. Это касается разработки методов доступа на основе использования индексов и функций хэширования. Однако использование техники индексирования и хэширования увеличивает сложность обработки запроса. Например, если таблица имеет индексы по трем различным колонкам, то любой из них может быть использован для доступа к таблице (помимо последовательного доступа к таблице в физическом порядке расположения строк).
Кроме того, появилось много новых алгоритмов для выполнения соединения таблиц. Двумя наиболее основными алгоритмами выполнения соединения являются:
соединение с помощью вложенного цикла (Nested Loop Join). В этом алгоритме строка читается из первой таблицы, называемой внешней (outer) таблицей, и затем читается каждая строка второй таблицы, называемой внутренней (inner), как кандидат для соединения. Затем читается вторая строка первой таблицы и снова каждая строка из второй, и так до тех пор, пока все строки первой таблицы не будут прочитаны. Если в первой таблице находится M строк, во второй - N, то читается M x N строк;соединение посредством объединения (Merge Join). Этот метод выполнения соединения предполагает, что таблицы отсортированы (или проиндексированы) таким образом, что строки читаются в порядке значений колонки (колонок), по которым они соединяются. Это позволяет выполнять соединение посредством чтения строк из каждой таблицы и сравнивания значений колонок соединения до тех пор, пока соответствие этих значений имеет место. В этом способе соединение завершается за один проход по каждой таблице.
Операции соединения подчиняются как коммутативному, так и ассоциативному закону. Следовательно, теоретически возможно выполнять соединение в любом порядке. Например, все следующие предложения являются эквивалентными:
(A JOIN B) JOIN C A JOIN (B JOIN C) (A JOIN C) JOIN B
Однако различные пути доступа, алгоритмы соединений и порядок выполнения соединений могут приводить и к различной производительности.
Следовательно, когда выполняется соединение нескольких таблиц, каждая из которых имеет несколько индексов, то существует несколько сотен различных комбинаций для выбора порядка выполнения соединений, алгоритмов соединений и путей доступа осуществления выборки. Каждая из этих комбинаций производит один и тот же результат, но с различными характеристиками производительности.
Одним из первых подходов на пути борьбы с комбинаторной сложностью выполнения соединений состоит в установлении эвристических правил для выбора между путями доступа и методами соединений, которая называется оптимизацией, основанной на правилах (rule-based optimization). В этом подходе веса и предпочтения назначаются альтернативам на основе принципов, которые являются общепризнанными. Используя эти веса и предпочтения, оптимизатор запросов производит возможные планы выполнения до тех пор, пока не будет достигнут лучший план выполнения, удовлетворяющий этим правилам. Некоторые из этих правил, используемых оптимизаторами такого типа, основываются на размещении переменных служебных символов (variable tokens), таких как имена таблиц и колонок в синтаксических структурах запроса. Когда эти имена размещаются, иногда может существовать значительная разница в производительности выполнения запроса. По этой причине оптимизаторы, основанные на правилах, как говорят, являются синтаксически зависимыми, и одним из методов настройки оптимизаторов этого типа СУБД является размещение символов (tokens) в различных позициях внутри утверждения.
Оптимизация, основанная на правилах, обеспечивает удовлетворительную производительность системы в тех ситуациях, когда эвристики являются точными. Однако часто общепризнанные правила не являются точными. Для обнаружения таких ситуаций оптимизатор запросов должен рассматривать характеристики данных, такие как:
число строк в таблице;интервал и распределение значений данной колонки;длину строки и, соответственно, число строк на физической странице диска;высоту индекса;число терминальных (leaf) страниц в индексе.
Эти характеристики данных могут сильно влиять на эффективность обработки запроса. Использование таких характеристик приводит к следующему типу оптимизации.
Оптимизация, основанная на вычислении стоимости
Оптимизация, основанная на вычислении стоимости запроса (cost-based optimization), аналогична оптимизации, основанной на правилах, за исключением того, что оптимизатор на основе вычисления стоимости использует статистическую информацию для выбора наиболее эффективного плана выполнения запроса. Стоимость каждого альтернативного плана выполнения запроса оценивается с помощью статистики, такой как число строк в таблице и числа и распределения значений колонки таблицы. Формулы стоимости обычно учитывают количество ввода/вывода и время CPU, необходимое для выполнения плана запроса. Такая статистика хранится в системном каталоге и поддерживается СУБД.
Для понимания того, как статистика может быть использована для выбора плана выполнения запроса, рассмотрим следующий запрос к таблице CUSTOMER (ПОКУПАТЕЛЬ):
SELECT CUST_NBR, CUST_NAME FROM CUSTOMER WHERE STATE = "FL";
Если индекс существует на колонку STATE, оптимизатор, основанный на правилах, использовал бы его для обработки запроса. Однако если девяносто процентов строк в таблице CUSTOMER имеют FL в колонке STATE, то использование индекса будет в действительность приводить к более медленному выполнению запроса, чем простая последовательная обработка таблицы. Оптимизатор, основанный на вычислении стоимости, с другой стороны, обнаружил бы, что использование индекса не дает никаких преимуществ перед последовательным просмотром таблицы.
Подход к оптимизации, основанный на вычислении стоимости, сегодня представляет определенное искусство в технике оптимизации запросов. Большинство реляционных СУБД применяют оптимизаторы, основанные на вычислении стоимости.
Оптимизация запросов
Компонента SQL СУБД, которая определяет, как осуществлять навигацию по физическим структурам данных для доступа к требуемым данным, называется оптимизатором запросов (query optimizer).
Навигационная логика (вариант алгоритма) для доступа к требуемым данным называется путем или методом доступа (access path).
Последовательность выполняемых оптимизатором действий, которые обеспечивают выбранные пути доступа, называется планом выполнения (execution plan).
Процесс, используемый оптимизатором запросов для определения пути доступа, называется оптимизацией запросов (query optimization).
Во время процесса оптимизации запросов определяются пути доступа для всех типов команд SQL DML. Однако команда SQL SELECT представляет наибольшую сложность в решении задачи выбора пути доступа. Поэтому этот процесс обычно называют оптимизацией запроса, а не оптимизацией путей доступа к данным. Далее следует отметить, что термин оптимизация запросов является не совсем точным в том смысле, что нет гарантии, что в процессе оптимизации запроса будет действительно получен оптимальный путь доступа. Более подходящим термином мог бы быть термин "улучшение запроса" (query improvement). Например, наилучший возможный путь доступа, имеющий заданную стоимость (в смысле вычислительной сложности). Далее всюду используется стандартный общепринятый термин "оптимизация запросов" во избежание недоразумений.
Ранние версии реляционных СУБД обрабатывали запросы простым и непосредственным способом без какой-либо попытки оптимизировать как запрос сам по себе, так и путь доступа. Это имело результатом неудовлетворительно большое время обработки запроса и приводило к убеждению среди некоторых прикладных программистов, что реляционные СУБД являются непрактичными и мало пригодными для широкого круга практических применений. Для того чтобы увеличить скорость обработки запросов, были выполнены обширные исследования и тестирование для поиска способов повышения эффективности обработки запросов.
Таким образом, оптимизация запросов может быть определена как сумма всех технических приемов, которые применяются для повышения эффективности обработки запросов.
Последовательность шагов оптимизации запросов
Несмотря на то, что оптимизаторы запросов современных реляционных СУБД различаются по сложности и принципам создания, все они следуют одним и тем основным этапам в выполнении оптимизации запроса.
Синтаксический разбор запроса (parsing). Оптимизатор сначала разбивает запрос на его синтаксические компоненты, проверяет ошибки в синтаксисе и затем преобразует запрос в его внутреннее представление для дальнейшей обработки.Преобразование (conversion). Далее оптимизатор применяет правила преобразования запроса для преобразования его в формат, оптимальный с точки зрения синтаксиса.Построение альтернатив (Develop alternatives). Когда запрос проходит синтаксическую оптимизацию, оптимизатор разрабатывает альтернативы для его выполнения.Создание плана выполнения запроса (Сreate execution plan). Окончательно оптимизатор выбирает лучший план выполнения запроса, либо следуя набору эвристических правил, либо вычисляя стоимость для каждой альтернативы выполнения.
Так как шаги 1 и 2 имеют место независимо от действительных данных, находящихся в таблицах, нет необходимости повторять их, если запрос не требует перекомпиляции. Следовательно, большинство оптимизаторов будут сохранять результаты 2-го шага и использовать его снова, когда они переоптимизируют запрос в другой раз.
Построение дерева запроса
Когда оптимизатор строит деревья запросов для оценки стоимости и возможного окончательного выбора, он использует некоторые правила, которые управляют размещением различных узлов дерева. Эти правила позволяют оптимизатору ограничить число узлов дерева запросов, которые строятся для дальнейшего решения задачи оценки стоимости. Ограничивая возможные альтернативы путей доступа таким образом, оптимизатор может выполнить обработку более эффективным способом.
Одна из важнейших эвристик состоит в использовании правил, таких как выполнение операций проекции и выбора как можно раньше. Это так, потому что эти операции могут ограничить размер результирующего множества. На рис. 15.2 оптимизатор улучшает дерево запросов, применяя выборку сначала для ограничения числа строк, которые являются входом операции эквисоединения.
SELECT A.NAME FROM AUTHORS A, BOOCKS B WHERE (B.DATE_PUBLISHED ='1993') AND (A.NAME = B.NAME);
Рис. 15.2. Использование эвристических правил для увеличения эффективности запроса
Следовательно, когда несколько операций выборки выполняется в запросе для доступа к таблице, операции с наименьшим значением фактора селективности выполняются позже по дереву для того, чтобы ограничить размер промежуточных результатов как можно раньше по мере возможности. Конечно, предикаты могут быть оценены в зависимости от того, когда все данные, указываемые в предикате, являются доступными. 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].
Процедурные языки обработки данных
Большинство систем БД до начала использования SQL-технологии основывались на процедурных или навигационных языках обработки данных. Примерами таких систем БД могут служить ADABAS (Software Ag.), IDMS, IMS (IBM Corp.) и dBase. Процедурные языки обработки данных требуют от программиста кодирования программной логики, необходимой для навигации по физической структуре данных для идентификации и доступа к требуемым данным. Например, при использовании ADABAS программист должен написать код для спецификации записей данных (FIND), получить специфицированное множество данных и организовать цикл его просмотра (GET), а также предоставить код для актуализации полученных данных для пользователя.
Если прикладная программа ссылается на физические структуры данных, то она естественно становится зависимой от них. Такие прикладные программы требуют модификации кода, если изменяется физическая структура данных. Например, если индекс в dBase удаляется, то все прикладные программы, которые его используют, должны быть модифицированы.
Зависимость между прикладной программой и физической структурой данных значительно увеличивает стоимость разработки и сопровождения таких программ. Во время разработки больших, сложных компьютерных систем очень часто обнаруживается несоответствие в спроектированной физической структуре БД и реализации в программах функциональности предметной области на различных этапах выполнения проекта. Для устранения таких несоответствий администратор БД должен осуществлять изменения физической структуры.
Такие изменения физической и логической схем БД вступают в противоречия со всеми существующими программами, которые ссылаются на эти измененные физические структуры. Эти программы должны быть модифицированы для того, чтобы отразить изменения в схеме БД. Если прикладная программа в значительной мере использует эту измененную физическую структуру для навигации по БД и программная логика основывается на этой навигации, то может потребоваться значительное перекодирование программы. С другой стороны, сопровождение существующих систем часто приводит к изменениям схемы БД, и, следовательно, такая зависимость приводит к увеличению стоимости сопровождения пользовательских приложений.
В дополнение к сказанному, процедурные языки обработки данных обычно являются контекстно-зависимыми в реализации. Следовательно, прикладные программы становятся полностью привязанными к конкретной системе БД, для которой они и были разработаны. Такая привязка прикладных программ к конкретным системам БД значительно ограничивает их мобильность.
Реляционные операции
Основные операторы реляционной алгебры были определены Э.Ф. Коддом, когда он опубликовал свою основополагающую работу по языкам манипулирования данными в реляционной модели в 1972 году. Операции, определенные в этой реляционной алгебре, формируют логические операторы, которые должны быть обработаны оптимизатором. Эти логические операторы являются неявными для синтаксиса команд SQL DML, но именно они и обрабатываются СУБД.
Операции реляционной алгебры имеют на входе одно или более отношений на входе и одно отношение на выходе. Отношением является просто таблица некоторой степени n, где n - число атрибутов (или колонок) в таблице. Эти операторы разделяются на два класса: теоретико-множественные операции (traditional set operations) и специальные реляционные операторы (special relational operators). В то время как использование теоретико-множественных операций обычно достаточно для обработки большинства реляционных запросов, специальные операторы определяют желаемый результат более эффективно. Этот последний класс будет изучен в этом разделе более подробно, в то время как теоретико-множественные операции будут определены в общих чертах (предполагается, что они хорошо известны после изучения предыдущих л екций этого курса).
Синтаксическая оптимизация
Первый успех в оптимизации запросов состоял в нахождении способа переформулирования запроса таким образом, чтобы новое представление запроса обеспечивало тот же результат, но было более эффективно для обработки СУБД.
Пример. Рассмотрим следующий запрос, который делает выборку данных из таблиц PRODUCT (ПРОДУКЦИЯ) и VENDOR (ПРОИЗВОДИТЕЛЬ):
SELECT VENDOR_CODE, PRODUCT_CODE, PRODUCT_DESC FROM VENDOR, PRODUCT WHERE VENDOR.VENDOR_CODE = PRODUCT.VENDOR_CODE AND VENDOR.VENDOR_CODE = "100";
Наиболее очевидный путь обработки этого запроса состоит в следующем:
Формируем декартово произведение таблиц PRODUCT и VENDOR.Ограничиваемся в результирующей таблице строками, которые удовлетворяют условию поиска в предложении WHERE.Выполняем проекцию результирующей таблицы на список колонок, указанный в предложении SELECT.
Оценим стоимость процесса обработки этого запроса в терминах операций ввода/вывода. Пусть для определенности таблица 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.
Это означает, что ограничение по условию поиска может быть выполнено как можно раньше для того, чтобы ограничить число строк, которые могут быть обработаны позже.
Применяя это правило к запросу, приведенному выше, получаем следующий процесс обработки запроса:
Ограничение по условию поиска во второй таблице (VENDOR_CODE = "100") приведет к 1000 операций чтения и 20 операциям записи.Выполнение соединения полученной на 1-м шаге результирующей таблицы с таблицей VENDOR потребует 20 операций чтения результирующей таблицы, 100 операций чтения из таблицы VENDOR и 20 операций записи в новую результирующую таблицу.
Обработка запроса в этом случае потребует 1120 операций чтения и 40 операций записи для получения того же самого результата, что и в первом случае. Преобразование, описанное в данном примере, называется синтаксической оптимизацией (syntax optimization).
Существует много формул для выполнения таких преобразований, и все современные оптимизаторы запросов используют правила преобразований для представления запроса в более эффективной форме для обработки. С точки зрения реализации является очень важным, что эти автоматические преобразования освобождают программиста от поиска эквивалентной формы запроса, чтобы получить самую лучшую реализацию, поскольку оптимизатор обычно дает такую же окончательную форму, какую вы можете получить вручную.
Сортировка и агрегация
Операция сортировки производится, когда таблица должна быть представлена в определенной последовательности в соответствии со значениями одной или более колонок, которые все вместе называются ключом сортировки (sort key). Эта физическая операция имеет одну таблицу на входе и одну таблицу на выходе.
Операция агрегирования также имеет одну таблицу на входе и одну таблицу на выходе. Физическая операция агрегирования SQLBase выполняет последовательное сканирование квалифицируемых строк данных, с вычислением агрегатной функции для каждой строки. Когда выполняется скалярная агрегация, входные строки могут располагаться в любой последовательности. Однако при групповой агрегации, когда функция агрегирования вычисляется, входная таблица должна быть представлена в последовательности значений колонки, указанной в предложении GROUP BY.
Это требование удовлетворяется оптимизатором запросов путем либо размещения операции сортировки до выполнения операции агрегирования, либо использования такого метода доступа к таблице, который возвращает строки таблицы в указанной последовательности.
Специальные реляционные операторы
SQL использует этот класс операций гораздо чаще, чем теоретико-множественные операции. К классу специальных реляционных операций обычно относят следующие:
Проекция (Projection).
Операция проекции ограничивает число колонок таблицы, на которые ссылаются в команде SQL.
Выбор (Selection or restriction).
Операция выбора ограничивает результирующее множество только теми строками, которые удовлетворяют условию поиска. Критерий поиска представляет собой сравнение одной или более колонок таблицы либо с одной, либо с несколькими константами или выражениями.
Соединение (Join).
Операция соединения создает результирующее множество посредством конкатенации строк нескольких таблиц. Эти сцепленные строки должны удовлетворять некоторому условию соединения, которое является сравнением одной или более колонок этих таблиц. Эти операции сравнения в условиях соединения отличаются от операций сравнения в условиях поиска в том, что сравнивают значения колонок различных таблиц.
Поскольку эти специальные реляционные операции играют центральную роль в командах 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);
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.
Структура плана запроса
Когда оптимизатор группирует множество физических операций для выполнения утверждения SQL, то полученная спецификация называется планом запроса (query plan).
Аналогия с задачей программирования делает роль плана запроса проще для понимания. Программист кодирует инструкции на языке высокого уровня, которые затем компилируются для получения выполняемого программного кода. Это выполняемая форма использует машинные команды для того, чтобы сказать CPU, что нужно делать. CPU выполняет машинные инструкции, а не первоначальный код.
Аналогично, программист кодирует утверждения SQL, которые затем обрабатываются оптимизатором для производства выполняемой формы этого кода. Эта выполняемая форма кода есть план запроса.
Теоретико-множественные операции
Главное отличие теоретико-множественных операций (за исключением декартова произведения) от всех других, выполняемых СУБД, состоит в том, что отношения, используемые на входе этих операций, должны иметь одинаковое число колонок. При этом каждый соответствующий атрибут определяется на одном и том же домене. Это означает, что каждая таблица должна иметь одинаковое число колонок и каждая пара колонок для любой позиции таблицы должна быть определена с одинаковым типом и масштабом.
Объединение (Union).
Объединение двух отношений есть множество всех строк, принадлежащих либо каждому из них, либо обоим вместе. Оно может быть сформировано добавлением одной таблицы к другой и исключением дублированных строк.
Пересечение (Intersection).Пересечение двух отношений состоит из строк, которые принадлежат обоим отношениям. Любая строка, которая находится только в одной таблице, но не находится в другой, не является членом пересечения.Разность (Difference).
двух отношений есть все строки, которые принадлежат первому отношению, но не принадлежат второму. Заметим, что эта операция не коммутативна, т.е. А-В<>В-А.
Декартово произведение (Cartesian product).
Декартовым произведением двух отношений является таблица, получаемая конкатенацией каждой строки одной таблицы с каждой строкой другой таблицы. Таблица, получаемая в результате этой операции, содержит число строк, равное произведению числа строк исходных таблиц. Это означает, что если имеется две таблицы с 15 и 50 строками соответственно, то их декартово произведение есть таблица с 750 строками. Как указывалось выше, это единственная теоретико-множественная операция, которая допускает различный формат исходных таблиц.
Анализ запросов с целью повышения скорости их выполнения
Рассмотрим теперь общую процедуру настройки команды SELECT, результат выполнения которой не удовлетворяет требованиям производительности. Эта процедура является итерацией на пути построения оптимального набора индексов и состоит из семи шагов. При обсуждении этой процедуры мы для простоты будем ориентироваться на СУБД SQLBase.
Шаг 1. Обновить статистику. До того как добавить индексы, необходимо убедиться, что статистика базы данных в системном каталоге является корректной. Если вы выполняете запрос без учета действительной производительности базы данных, вам следовало бы обновить статистику для всех таблиц, указанных в предложении FROM, используя команду UPDATE STSTISTICS (для SQLBаse) или другую специальную команду СУБД. С другой стороны, если вы используете небольшую тестовую базу данных, то можно вручную вычислить необходимые статистические показатели и внести их в системный каталог.
Когда вы обновляете статистику, вам следовало бы скомпилировать команду SQL, установив параметр PLANONLY в положение ON. Сравните новый план запроса со старым до обновления статистики, для того чтобы определить изменения в нем (иногда требуется довольно длительное время для построения плана). Сравнивая планы, можно избежать повторного выполнения запроса только для того, чтобы убедиться, что производительность его выполнения идентична предыдущему выполнению этого запроса. Если статистика изменилась, то выполните запрос, чтобы определить, увеличилась ли производительность и насколько.
Шаг 2. Упростить команду SELECT. Перед добавлением индексов или переписыванием плана выполнения следует попытаться упростить запрос. Задача состоит в том, чтобы сделать выражение SELECT как можно проще, сократив по мере возможности число переменных в нем. Упростив запрос, скомпилируйте команду, чтобы посмотреть план запроса. Сравните новый план запроса со старым. Определите, увеличилась ли производительность запроса, выполнив его.
Для того чтобы упростить SELECT, необходимо:
исключить ненужные предикаты и предложения;расставить скобки в арифметических и логических выражениях;преобразовать связанные переменные в константы.
Исключение ненужных предикатов и предложений. Обычно в команду SELECT включают предложений больше, чем это необходимо на самом деле. Так делается для того, чтобы гарантировать корректность ответа, или из-за плохого понимания синтаксиса SQL. До попытки настроить запрос проектировщик базы данных должен удалить все ненужные предложения и предикаты.
Примерами предложений, которые обычно включаются в запрос, но не являются необходимыми, являются следующие:
Предложение ORDER BY. Часто это предложение включается, даже если определенный порядок в результирующем множестве не требуется приложением или конечным пользователем.Предикаты предложения WHERE. Часто это предложение содержит избыточное множество предикатов ограничения. Например, предикаты в следующем предложении WHERE являются избыточными, так как DEPT_NO есть первичный ключ и, следовательно, будет уникально идентифицировать только одну строку:
WHERE DEPT_NO = 10 AND DEPT_NAME = 'PERATIONS'.
Расстановка скобок в арифметических и логических выражениях. Синтаксис SQL SQLBase включает специальные правила предшествования для оценки арифметических и логических выражений. Однако достаточно просто сделать ошибку при применении правил предшествования. Следовательно, мы рекомендуем вам расставлять скобки в этих выражениях для явного определения предшествования в выполнении операций. Вы можете подумать, что оптимизатор оценивает выражения одним способом, а в действительности он поступает по-другому.
Преобразование связанных переменных в константы. Связанные переменные обычно используются, когда компилируется команда SQL. Часто желательно использовать хранимые команды для того, чтобы исключить перекомпиляцию утверждения SQL, которое будет выполняться много раз. Эти хранимые команды являются скомпилированными, и их планы выполнения сохраняются в системном каталоге вместе с исходным текстом. Приложения тоже выполняют предкомпиляцию для многократно используемых команд выборки. В этих ситуациях связанные переменные используются для передачи некоторых значений в команду во время ее выполнения.
Природа индексной структуры на основе В-дерева такова, что она может работать с символом подстановки, если он не стоит в начальной позиции строки. Ясно, что оптимизатор не будет использовать индекс, если символ постановки будет стоять на первой позиции (как при использовании связанной переменной в предикате LIKE). В этих случаях будет применено сканирование таблицы.
Преобразовывайте связанные переменные в предикате LIKE в константы для увеличения производительности такого запроса.
Шаг 3. Пересмотреть план запроса. Выполните запрос так, чтобы посмотреть его план. Вы должны хорошо понимать план запроса, чтобы использовать его. Несколько элементов этого плана требуют особого внимания.
Преобразование подзапроса в соединение. Оптимизатор преобразует большинство подзапросов в соединения. Нужно знать, на каких этапах выполнения запроса это преобразование происходит.Когда будут создаваться временные таблицы. Если временные таблицы создаются, это может указывать, что оптимизатор сортирует промежуточные результаты. Если это происходит, можно попробовать добавить индекс на одном из следующих шагов настройки для того, чтобы избежать сортировки.Медленные методы соединения. Хэш-соединение и методы вложенного соединения не являются быстрыми, как метод слияния индексов для больших таблиц. Если эти методы используются, можно попробовать добавить индекс в шагах 5 и 6 настройки команды SELECT, так, чтобы соединения использовали метод слияния индексов. Иногда хэш-соединение может представлять более лучший метод соединения, когда большое количество данных обрабатывается.
Шаг 4. Локализовать узкие места. Запрос, который выполняется медленно, может содержать много предложений и предикатов. Если это так, нужно определить, какие предложения или предикаты приводят к плохой производительности. Если удалить одно или два предложения или предиката, производительность выполнения запроса возрастает значительно. Эти предложения являются критическими параметрами выполнения запроса.
Можно поэкспериментировать с запросом, поочередно удаляя из него предложения или предикаты до тех пор, пока не будет достигнут подходящий уровень производительности.Локализуйте критические предложения и предикаты.
Примеры:
Если запрос содержит предложение ORDER BY, закомментируйте его и посмотрите, изменится ли план этого запроса. Если план изменился, выполните запрос для того, чтобы определить, увеличилась ли производительность.Если запрос содержит несколько соединений, локализуйте то, которое замедляет выполнение. Комментируйте последовательно все соединения, кроме одного, и выполняйте запрос. Определите, какое соединение самое критичное.
Фактор селективности
Фактор селективности является статистическим показателем, который вычисляется оптимизатором для предикатов, используемых реляционной операцией выборки. В дополнение, фактор селективности используется оптимизатором для определения того, является ли путь доступа через индекс более эффективным, чем сканирование таблицы. Следовательно, фактор селективности вычисляется только для тех предикатов, которые содержат индексируемые атрибуты.
Фактор селективности оценивает число строк, которые возвращаются при применении предикатов выборки на таблицу известного размера. Это является важным моментом, когда оптимизатор оценивает использование индекса при построении плана выполнения. Индекс будет более эффективным, чем сканирование таблицы, только если высота индекса, умноженная на фактор селективности, умноженные на число строк в таблице, будет меньше, чем число физических страниц базы данных, занятых таблицей.
Другими словами, если большинство строк таблицы должны быть выбраны, использование индекса повлечет за собой увеличение числа операций ввода/вывода за счет чтения индекса. При этом именно фактор селективности проявляется виртуально в стоимости ввода/вывода, связанной с операцией доступа к индексу, которая используется оптимизатором.
Численно фактор селективности представляет вероятность, которая изменяется от 0 до 1. Умножение числа строк в таблице на фактор селективности для связанного с ним предиката будет давать ожидаемое число строк для операции выборки, при предположении, что значения колонок таблицы равномерно распределены по строкам.
Фактор селективности в случае нескольких предикатов
Когда несколько предикатов используются для выборки строк из одной таблицы, оптимизатор следует некоторым фиксированным правилам, которые комбинируют фактор селективности каждого из них в некоторый суммарный. Первое правило не зависит от того, как много предикатов рассматривается, когда вычисляется итоговый фактор селективности для предикатов, содержащих операторы равенства и неравенства. Это следующие правила.
Когда для первой по порядку колонки индексного ключа задается предикат равенства, оптимизатор может найти фактор селективности для нескольких колонок, считывая DISTINCTCOUNT до самого последнего ключа строки SYSKEYS. Когда первый предикат неравенства оценивается, то игнорируются все оставшиеся предикаты, содержащие колонки, которые появляются в индексе.
Пример. Пусть задан предикат
EMPLOYEE_NO = 45 AND DEPT = 50 AND SALARY > 25000.
Предположим, что индекс определен для составного ключа, содержащего указанные колонки в следующем порядке: EMPLOYEE_NO, DEPT, SALARY. Комбинация факторов селективности для колонки EMPLOYEE_NOи для колонки DEPT, которые появляются в колонке DISTINCTCOUNT строки DEPT таблицы системного каталога SYSKEYS, используется оптимизатором для оценки числа строк, которые будут возвращены по запросу. Действие предиката неравенства для колонки SALARY игнорируется.
Когда для первой по порядку колонки индексного ключа задается предикат неравенства, только фактор селективности этого предиката вычисляется, а все оставшиеся предикаты игнорируются. Пример. Пусть задан предикат
SALARY > 25000 AND DEPT = 50 AND YEARS_SERVICE > 3.
Предположим, что индекс определен для составного ключа, содержащего указанные колонки в следующем порядке SALARY, DEPT, YEARS_SERVICE. Оптимизатор определяет фактор селективности, просматривая корневую страницу индекса для определения числа строк таблицы, для которых выполняется предикат "Зарплата больше 25000". Это значение и становится фактором селективности для всей группы предикатов. Оставшиеся предикаты игнорируются.
Таким образом, на первом шаге своей работы оптимизатор СУБД SQLBase, подготавливая для выполнения команду SQL, строит список вариантов путей доступа, которые могли бы удовлетворить запросу (планы выполнения). Поскольку оптимизатор основан на вычислении стоимости, используется статистика базы данных как основа выполнения оценок того, какая работа требуется для реализации каждого возможного плана выполнения.
Далее оптимизатор запросов строит группу альтернативных планов выполнения, каждый план выполнения оценивается вычислением стоимости так, чтобы наиболее эффективный план мог быть выбран. При этом оцениваются два компонента общей стоимости плана выполнения - требования по вводу/выводу и требования по времени процессора. Выбирается план с наименьшим значением вычисленной стоимости.
Фактор селективности в случае одного предиката
Определение фактора селективности для одного предиката, такого как EMPLOYEE_NO=65, зависит от того, какой оператор используется в предикате. Оператор влияет на фактор селективности, так как он определяет взаимосвязь между строками, которые удовлетворяют предикату и другим операндам.
Чем большее число строк отбрасывает оператор предиката при выборке (ограничивает), тем меньше фактор селективности предиката. Наиболее трудоемким для выполнения оператором (по числу операций ввода-вывода) является оператор равенства, поскольку только одно значение колонки может удовлетворить предикату. В этом случае фактор селективности просто обратно пропорционален кардинальности колонки, которая сохраняется в колонке DISTINCTCOUNT таблицы SYSADM.SYSINDEXES для этой колонки (как индексируемого ключа).
Однако непросто вычислить фактор селективности для операторов неравенства. Рассмотрим следующие два предиката:
ORDER_DATE > JAN-01-1900 ORDER_DATE > SYSDATE -1 DAY
Очевидно, что первый предикат, как можно было бы ожидать, возвратит гораздо больше строк, чем второй, когда будет применен к таблице ORDER.
Как оптимизатор может определить это? Оказывается, что оптимизатор вычисляет фактор селективности посредством доступа к верхнему уровню индекса той индексной структуры, которая содержит колонку запроса (ORDER_DATE). Затем он оценивает число строк, которое удовлетворяет предикату, экстраполируя пропорцию индексных ключей на этом уровне индекса. Этот метод, называемый сканирование B-дерева (B-tree scan), позволяет оптимизатору сделать достаточно точную оценку результатов применения предикатов неравенства.
Другой фактор, который играет роль в определении фактора селективности одного предиката неравенства, есть ответ на вопрос, будет ли сравниваться колонка с константой или связанной переменной? Это некритично для предиката равенства потому, что оптимизатор может вычислить фактор селективности исходя из значения DISTINCTCOUNT в предположении равновероятного распределения значений колонки по строкам таблицы.
Такое предположение позволяет оптимизатору быть нечувствительным к действительным значениям операнда с другой стороны знака равенства. Однако для использования метода сканирования В-дерева оптимизатор должен быть способным найти значение другого операнда. Когда операнд является связанной переменной, оптимизатор должен опуститься назад для проверки предположения, что в действительности трудно закодировать.
Нижеследующая таблица 16.1 суммирует определения фактора селективности для одного предиката, в зависимости от операции и типа второго операнда.
| = | 1/card | 1/card |
| !=,<> | 1-1/card | 1/3 |
| > | Сканирование индекса | 1/3 |
| !> | Сканирование индекса | 1/3 |
| < | Сканирование индекса | 1/3 |
| >= | Сканирование индекса | 1/3 |
| <= | Сканирование индекса | 1/3 |
| Between | Сканирование индекса | 1/3 |
| Null | - | Не используется |
| Exists | Преобразование | Преобразование |
| Like | Сканирование индекса | Не определен |
| In | Преобразование | Преобразование |
Использование оптимизатора для оптимизации выполнения запросов
При создании физической модели реляционной базы данных мы рассмотрели общие принципы и эвристические правила создания внутренней схемы, которая обеспечивает хорошие характеристики производительности для большинства SQL запросов. Однако методики физического проектирования не гарантируют того, что некоторые запросы будут иметь хорошие характеристики производительности без дальнейшей настройки.
Существует много вариантов увеличения производительности запросов. Основной идеей для выбора самого подходящего является построение запроса таким образом, чтобы оптимизатор запросов СУБД вычислил оптимальные по стоимости пути доступа для его выполнения.
Так, например, при работе с оптимизатором СУБД SQLBase для увеличения производительности конкретной команды SELECT, проектировщик базы данных или администратор баз данных выполняет следующие действия:
Обновление статистики.Определение оптимального набора множества индексов.Переписывание плана выполнения запроса, выбранного оптимизатором.
Обновление статистики. Статистика в СУБД SQLBase поддерживается независимо как для таблиц, так и для индексов. Оптимизатор использует эти статистики для вычисления стоимости различных путей доступа. Следовательно, первым аспектом работы с оптимизатором запросов, для улучшения производительности данного запроса, является гарантия того, что эти статистики корректны и обновляемы.
Оптимальное множество индексов. Другим аспектом работы с оптимизатором запросов является добавление индексов для увеличения скорости выполнения секций и соединений, оценки сортировки в предложениях GROUP BY и ORDER BY. Если утверждение SELECT выполняется медленно, то это, вероятно, либо соединение, сортировка, либо чтение большой таблицы. Индексы могут увеличить производительность всех этих операций.
Общая стратегия индексирования состоит в создании индексов для всех первичных и внешних ключей. Это так, потому что в большинстве систем существуют колонки, которые извлекаются гораздо чаще в предикатах предложений WHERE, GROUP BY, ORDER BY.
Этот первоначальный набор индексов базы данных обеспечивает индексацию для выполнения селекции и исключений сортировок первичных и внешних ключей. Следовательно, часто соединения являются наиболее критическим временным аспектом конкретного запроса. Самый быстрый алгоритм соединения для больших таблиц есть объединение индексов. Первоначальный набор индексов гарантирует, что путь доступа с объединением индексов доступен для оптимизатора запросов, когда колонка соединения является первичным или внешним ключом. Для всех других соединений оптимизатор ограничивается более медленными алгоритмами соединения, хэш-соединением или одним из алгоритмов соединения в цикле. Однако для большинства утверждений SELECT пути доступа, допустимые для оптимизатора на первоначальном наборе индексов, обеспечивают адекватную производительность.
С другой стороны, первоначальный набор индексов может не удовлетворять требованиям по производительности для всех запросов. Например, некоторые запросы, содержащие колонки соединения, не являющиеся ни первичным, ни внешним ключами, могут выполняться медленно. Для таких запросов, чтобы они удовлетворяли критериям производительности, необходимо добавить дополнительные индексы. Однако нецелесообразно создавать один или более индексов для каждого оператора выборки, поскольку:
индексы замедляют обновление командами DML;поддержка индексов увеличивает и время обработки, и стоимость запроса;индексы занимают дополнительное дисковое пространство;индексы также могут блокировать доступ к страницам данных при блокировке страницы индекса.
Следовательно, общая цель проектирования состоит в том, чтобы создать набор индексов, который отвечает требованиям производительности для всех транзакций к базе данных. Это и есть оптимальный набор индексов.
Переписывание плана выполнения запроса, выбранного оптимизатором. В СУБД SQLBase такая процедура выполняется с помощью настройки команды SELECT. Она может быть применена в при использовании других реляционных СУБД.
Однако в некоторых СУБД, например СУБД Oracle, проектировщик базы данных может явно влиять на выбор тех или иных вариантов улучшения скорости выполнения запросов.
На уровне экземпляра режим работы оптимизатора задается администратором базы данных. На уровне сессии используется команда вида
ALTER SESSION SET OPTIMIZER_GOAL = <режим>;
В качестве режима может быть задано одно из следующих значений:
CHOOSE - это значение задает использование оптимизации, основанной на вычислении стоимости, в противном случае будет использоваться оптимизация, основанная на правилах;RULE - это значение задает использование оптимизации, основанной на правилах. Такой режим оптимизации будет применен и при использовании подсказок (см. таблицу 16.2);
| ROWID | Использование идентификатора |
| CLUSTER | Сканирование ключа кластера |
| HASH | Сканирование хэш-индекса |
| INDEX | Сканирование индекса |
| INDEX_ASC | Сканирование индекса в порядке возрастания |
| INDEX_DECS | Сканирование индекса в порядке убывания |
| AND_FFS | Быстрое полное сканирование индекса |
| AND_EQUAL | Использование нескольких индексов со слиянием результатов |
| FULL | Полное сканирование таблицы |
Более подробно об использовании оптимизатора запросов СУБД Oracle можно прочитать в рекомендованной к лекции литературе.
Для управления оптимизатором СУБД Oracle используются специальные подсказки, которые записываются в SQL-командах. Такие подсказки влияют на выбор конкретного способа обращения к данным. Пример ниже содержит подсказку оптимизатора для использования индекса (в предположении, что таблица имеет один индекс):
Пример
SELECT /* + index */ EMPLOYEE_NO, DEPT, SALARY FROM EMPLOYEE WHERE EMPLOYEE_NO = 65;
Подсказка является частью комментария, следующего за ключевым словом команды, и отмечается символом "+".
Для эффективного переписывания плана выполнения запроса необходимо в течение некоторого времени накопить знания о работе СУБД с базой данных, в частности, определить список проблемных запросов и их характеристик. При решении задач оптимизации проблемных запросов нужно следовать следующим рекомендациям:
При необходимости доступа к значительной части строк какой-либо таблицы полное сканирование таблицы предпочтительнее, чем использование индексов. Это связано с дополнительным чтением записей индекса. Индексы, как правило, эффективны, если запрос захватывает до 10% строк таблицы. Для небольших таблиц использование индексов практически неэффективно.На различных этапах выполнения запросов следует максимально использовать результаты предыдущих этапов, чтобы не переписывать лишний раз результирующий набор как результат выполнения команды. Например, если результирующий набор данных требуется отсортировать по значениям некоторой колонки, то при выполнении соединения таблиц можно указать способ выполнения этой операции, при котором будет проведена сортировка этих значений. Полученные результаты будут использованы при окончательной сортировке.При использовании различных видов подзапросов на основе знаний о данных следует учитывать особенности выполнения предикатов и операторов теоретико-множественных операций.
Одним из важных вопросов при работе с оптимизатором запросов является выбор режима его работы (если такая возможность предоставляется СУБД). Так, для оптимизатора СУБД Oracle режим оптимизации может быть задан на уровне экземпляра базы данных, на уровне сессии или SQL-команды.
Реализация оптимизатора SQLBase
На примере оптимизатора СУБД SQLBase рассмотрим основные принципы реализации оптимизаторов обработки запросов, основанных на вычислении стоимости, и покажем, как использовать эти принципы в случае ручной настройки запросов.
Статистика базы данных
Когда оптимизатор запросов SQLBase осуществляет выбор пути доступа, он использует статистику базы данных для оценки стоимости, связанной с каждым вариантом пути доступа, т.е. планом выполнения. Эта статистика, которая сохраняется в системном каталоге SQLBase, связана с различными таблицами и индексами, содержащимися в базе данных. Часть статистических данных поддерживается динамически, т.е. сервер SQLBase сам поддерживает ее обновление во время обычных операций сервера. Однако большая часть статистической информации поддерживается статически, т.е. она вычисляется и сохраняется, когда происходят определенные события.
Событие, которое обычно приводит к обновлению статистики базы данных, есть выполнение команды SQL UPDATE STATISTIC. Эта команда проверяет таблицы и индексы базы данных, вычисляет требуемые статистические показатели и затем сохраняет их в соответствующих таблицах системного каталога. Статистика также создается для индексов или таблиц при их первоначальном создании. Если никаких строк не вставляется в таблицы и индексы до момента обновления статистики по команде SQL UPDATE STATISTIC, то статистические показатели устанавливаются к значениям по умолчанию.
Как правило, статистика базы данных может быть обновлена администратором базы данных. После выполнения обновления пути доступа выбираются оптимизатором на основе вычисления стоимости по статистике, сохраненной в системном каталоге. В этом случае системный администратор может влиять на выбор путей доступа оптимизатором, исходя не из текущего содержания базы данных, а из ее предполагаемого содержания в будущем. Для того, чтобы точно вычислить и сохранить эту статистику, системный администратор должен знать, что эта статистика означает.
Статистика базы данных, которая поддерживается динамически, используется оптимизатором независимо от того, было ли сделано обновление статистики в системном каталоге. Она основывается на сборе статистики в результате действий пользователей над таблицами и индексами. Однако если статистика была обновлена в системном каталоге, то при выборе решений оптимизатор будет отдавать предпочтение обновленным статистическим показателям.
Статистика индексов
Статистика, связанная с индексами таблицы, также поддерживается в двух отдельных таблицах системного каталога. Все колонки (за исключением одной - HEIGTH - в таблице SYSINDEXES) поддерживаются статически и заполняются, когда выполняется команда UPDATE STАTISTICS или создается индекс.
В таблице SYSADM.SYSINDEXES статистическая информация поддерживается в следующих колонках:
HEIGTH. Высота индексного дерева есть число узлов, которые нужно прочитать начиная с корневого уровня и заканчивая уровнем листьев включительно. Также она называется глубиной дерева (depth). Этот статистический показатель также поддерживается и динамически в странице управления индексами. Это поле равно нулю для хэш-индекса.LEAFCOUNT. Общее число узлов на нижнем уровне (число листьев) индекса равно значению, сохраняемому в этой колонке. Также это есть число страниц в подмножестве индексной последовательности. Равно нулю для хэш-индеса.CLUSTERCOUNT. Общее число изменений страниц, которое происходило бы, если вся таблица была прочитана через подмножество индексной последовательности. Для полностью кластеризованного индекса эта колонка равна числу основных страниц данных в таблице. С другой стороны, наибольшее значение для общего некластеризованного индекса равно числу строк в таблице. Равно нулю для хэш-индекса.PRIMPAGECOUNT. Число базовых страниц, которые были распределены основной таблице для размещения в хэш-индексе. Это есть число слотов хэширования доступных для распределения строк. Равно нулю для В+-индекса.OVFPAGECOUNT. Эта колонка содержит число страниц переполнения, которые распределены таблицы для размещения в хэш-индексе. Когда таблица и индекс первоначально создаются, это число отражает число страниц переполнения, которое предполагается распределить. Затем это число увеличивается, когда дополнительная страница переполнения требуется для разрешения коллизии при хэшировании. Это поле равно нулю для В+-индекса.AVRKEYLEN. Для В+-индексов эта колонка содержит среднюю длину ключа для всех входов индекса.
Это число необходимо для того, чтобы поддерживать все входы индекса как данные с переменной длиной. Это поле равно нулю для хэш-индексов.
В таблице SYSADM.SYSKEYS поддерживается следующая статистическая информация.
DISTINCTCOUNT. Эта колонка содержит число различных ключей в индексе. Для каждой из существующих возможных комбинаций значений составного ключа существует это число, равное произведению кардинальности каждой колонки составного ключа. Кардинальность (cardinality) равна числу различных значений, которые колонка имеет в таблице.
Простейший пример есть колонка Пол (SEX_CODE), которая имеет кардинальность 2. Рассмотрим следующий индекс:
CREATE INDEX XNKSALS ON EMPLOYEE (DEPT, SALARY, YEARS_SERVICE);
Таблица EMPLOYEE содержит 250 строк, по одному для каждого служащего компании. Кардинальность множества значений колонок есть:
DEPT 10.SALARY - никакие два служащих компании не имеют одинаковой зарплаты, т.е. 250.YEARS_SERVICE - компания прошла три различных временных периода, т.е. 3.
При этих заданных условиях строки таблицы, которые описывают эти индексируемые колонки, имеют следующие значения DISTICTCOUNT:
DEPT 10, по одному для каждого отдела в компании.SALARY - 250. Так как каждый служащий имеет дискретное значение зарплаты, число ключей в этой точке индекса равно числу строк в таблице. Альтернативно, если существует только пять размеров зарплат, выплачиваемых компанией, и каждый отдел имеет кого-нибудь с этими пятью размерами зарплат, то DISTICTCOUNT равно 50 (=5*10).YEARS_SERVICE - 250. Так как поле зарплаты имеет уже кардинальность, равную числу строк в таблице, это поле не может превышать этого значения. Можно ожидать, что число входов индекса на каком-либо уровне может превысить число строк в таблице.
Статистика таблиц
Статистика, связанная с таблицами базы данных, поддерживается в двух различных таблицах системного каталога, каждая из которых описывается ниже. Все колонки, не указанные специально как динамически поддерживаемые, являются статическими и заполняются при выполнении команд UPDATE STATISTIC или CREATE.
В таблице системного каталога SYSADM.SYSTABLES для сохранения статистики используются следующие колонки:
ROWCOUNT. Значение этой колонки есть число строк в таблице. Этот статистический показатель поддерживается динамически в странице управления таблицей (table's control page), и принимает конкретное значение при выполнении команды UPDATE STATISTIC.PAGECOUNT. Значением этой колонки является общее число страниц данных в таблице. Этот статистический показатель также поддерживается динамически, но принимает конкретное значение только когда команда UPDATE STATISTIC выполняется. Когда эта колонка поддерживается системой, она всегда будет суммой двух нижеследующих колонок ROWPAGECOUNT и LONGPAGECOUNT. Если DBA устанавливает этот статистический показатель явно, то указанное соотношение может не выполняться.ROWPAGECOUNT. Эта колонка содержит число основных станиц строк, занятых под таблицу, плюс число всех страниц расширения, которые могут быть распределены для таблицы. Этот динамический статистический показатель генерируется только по команде.LONGPAGECOUNT. Эта колонка содержит число страниц, распределенных таблице для колонок типа LONG VARCHAR. Этот динамический статистический показатель генерируется только по команде.EVENT_PAGECOUNT. Эта колонка содержит среднюю долю данных, сохраненных в основных станицах строк и страницах расширения. Это число не включает страницы для длинных строк.AVRROWLEN. Эта колонка содержит действительную среднюю длину строк в таблице. Это значение может значительно отличаться от заданной длины строки, так как СУБД SQLBase сохраняет все колонки как данные переменной длины, независимо от типа данных, используемого в определении колонок. Заметим, что эта длина строки является только длиной строки, сохраняемой в основной странице и странице расширения, и, следовательно, исключает все колонки типа LONG VARCHAR.AVRROWLONGLEN. Эта колонка содержит действительную среднюю длину всех колонок типа LONG VARCHAR, хранимых в таблице. Она будет содержать нуль, если переменных такого типа в таблице нет.
В таблице системного каталога SYSADM.SYSCOLUMNS поддерживается следующая статистическая информация:
AVRCOLLEN. Эта колонка содержит действительную среднюю длину данной колонки для всех строк таблицы. Это значение может значительно отличаться от заданной при определении длины колонки, так как СУБД SQLBase сохраняет все колонки как данные переменной длины. Основная страница строки хранит описание длины данных для каждой непустой колонки.AVRCOLLONGLEN. Эта колонка содержит действительную длину колонки типа LONG VARCHAR для всех строк в таблице. Это значение равно нулю, если такие колонки отсутствуют в таблице.
