Физическая организация данных
 Скачать 487.44 Kb.
|
|
Индексом по полю salary система воспользоваться не может, т.к. это поле находится внутри выражения. Цель СУБД - выполнить запрос, причём сделать это как можно более эффективным способом. Итак, под оптимизациейпонимается построение квазиоптимального процедурного плана выполнения декларативного запроса. Примечание: квазиоптимальным план является потому, что система не гарантирует, что она для любого запроса выберет оптимальный план. Для гарантированного выбора опти-мального плана необходимо рассмотреть все возможные планы и сравнить их, а это может потребовать больше времени, чем выполнение самого запроса. Поэтому СУБД выбирает и анализирует лишь несколько планов выполнения каждого запроса, и сре-ди них может не оказаться оптимального плана. План выполнения запроса состоит из последовательности шагов, каж-дый из которых либо физически извлекает данные из памяти, либо делает подготовительную работу. Построением этого плана занимается оптимизатор - специальная компонента СУБД. Обработка запроса, поступившего в РСУБД и представленного на декларативном языке запросов, состоит из этапов (фаз), представленных на рис. 7.1. Рис. 7.1. Последовательность выполнения запросов в реляционных СУБД На первой фазе запрос, представленный на языке запросов, подвер-гается лексическому и синтаксическому анализу. Лексический анализатор разбивает запрос на лексические единицы - лексемы (наименования полей и таблиц, константы, знаки операций и т.д.). Синтаксический анализатор проверяет синтаксическую правильность запроса. В результате вырабатывается внутреннее представление запроса. Оно отражает структуру запроса и содержит информацию, которая характеризует объекты базы данных, упомянутые в запросе (таблицы, поля, константы). Информация об объектах базы данных выбирается из словаря-справочника данных. Внутреннее представление запроса используется и преобразуется на следующих стадиях обработки запроса. На второй фазе запрос в своём внутреннем представлении подвергается логической оптимизации. При этом могут применяться различные преобразования, "улучшающие" начальное представление запроса. Среди этих преобразований могут быть эквивалентные преобразования (см. раздел 7.2). После проведения эквивалентных преобразований получается внутреннее представление, семантически эквивалентное начальному запросу. Преобразования могут также использовать информацию об ограни-чениях целостности, существующих в БД. Такие преобразования являются семантическими, т.е. они основаны на семантике (смысле) предметной области. В этом случае получаемое представление не является семантически эквивалентным начальному запросу. Но система гарантирует, что результат выполнения преобразованного запроса совпадает с результатом запроса в начальной форме при соблюдении ограничений целостности, существующих в базе данных. Например, если для таблицы Emp определено такое ограничение целостности: (CHECK (salary>9500 AND salary<80000), то система к запросу из примера 7.1 могла бы добавить эти условия в часть WHERE, чтобы иметь возможность использовать индекс по полю salary. В любом случае после выполнения второй фазы обработки запроса его внутреннее представление остается непроцедурным, хотя и является в некотором смысле более эффективным, чем начальное. Это означает, что по этому представлению система сможет построить более эффективный план. Третий этап обработки запроса состоит в выборе альтернативных процедурных планов выполнения данного запроса в соответствии с его внутренним представлением, полученным на второй фазе. Для этого оптимизатор использует информацию из словаря-справочника данных, в первую очередь, о существующих путях доступа к данным. Единственный путь доступа, который возможен в любом случае, - это последовательное чтение (FULL). Возможность использования других путей доступа зависит от способов размещения данных в памяти (например, кластеризация или хеширование данных), от наличия индексов и формулировки самого за-проса. Также на третьем этапе для каждого из выбранных планов оценивается предполагаемая стоимость выполнения запроса по этому плану. При оценках используется либо доступная оптимизатору статистическая информация о распределении данных, либо информация о механизмах реализации путей доступа. Из альтернативных планов выбирается наиболее оптимальный с точки зрения некоторого (заранее выбранного или заданного) критерия. На четвертом этапе по внутреннему представлению наиболее оптималь-ного плана выполнения запроса формируется процедурное представление плана. Выполняемое представление плана может быть программой в машинных кодах, если, как в случае System R, система ориентирована на компиляцию запросов в машинные коды. В других системах, например, в INGRES, представление плана является машинно-независимым, что более удобно для интерпретации запросов. Для нас это непринципиально, поскольку четвертая фаза обработки запроса уже не связана с оптимизацией. Наконец, на последнем, пятом этапе обработки запроса происходит его реальное выполнение в соответствии с процедурным планом выполнения за-проса. Результат помещается в специальную область ОП (т.н. курсор).
Операндами операций реляционной алгебры (РА) являются отношения, т.е. неупорядоченные множества кортежей. Для выполнения операций необходимо просмотреть все кортежи исходного отношения (или отношений). Следствием этого является большая размерность операций РА. Уменьшения размерности можно достичь, изменяя последовательность выполняемых операций. В качестве примера приведём отношения R1 и R2, содержащие по 1000 кортежей, причём только 10 кортежей в каждом отношении удовлетворяют условию F. Если выполнять следующую последовательность операций: sF(R1 U R2), то после выполнения объединения получится 2000 кортежей (если отношения не содержат одинаковых кортежей), а после селекции останется 20 записей. Если изменить последовательность выполнения операций: sF(R1)U sF(R2) то после селекции останется по 10 записей из каждого отношения, объеди-нение которых даст 20 требуемых кортежей. Если учитывать, что объединение выполняется путем сортировки данных (для удаления одинаковых кортежей) и промежуточный результат надо хранить, то выигрыш и по объёму памяти, и по времени очевиден: гораздо быстрее отсортировать 20 кортежей, а не 2000. Оптимизация выполнения запросов реляционной алгебры основана на понятии эквивалентности реляционных выражений. Операндами выражений являются переменные-отношения Ri и константы. Каждое выражение реляционной алгебры определяет отображение кортежей переменных-отношений Ri (i= 1, ,n) в кортежи единственного отношения, которое получается в результате подстановки кортежей каждого Ri и выполнения всех определяемых выражением вычислений. Два выражения реляционной алгебры считаются эквивалентными, если они описывают одно и то же отображение. Существуют законы, которые в соответствии с этим определением позволяют выполнять эквивалентные преобразования выражений реляционной алгебры:
R1xR2=R2xR1
o sF(R1xR2)= (sF1(R1 ))x(sF2(R2)) (если F = F1vF2, где F1 содержит атрибуты, присутствующие только в R1, а F2 содержит атрибуты, присутствующие только в R2); o sF(R1xR2)=(sF(R1))xR2 (если F содержит атрибуты, присутствующие только в R1); o sF(R1xR2)=R1x(sF(R2)) (если F содержит атрибуты, присутствующие только в R2); o sF(R1xR2)= sF2(sF1(R1)xR2) (если F = F1vF2, где F1 содержит атрибуты, присутствующие только в R1, а F2 содержит атрибуты, присутствующие и в R1, и в R2).
pA 1 ,A2,... ,Am(R 1 xR2)= (pB 1,B2,...,Bn(R1 ))x(font face=symbol>pC 1 ,C2,... ,Cr(R2)) где атрибуты {Bn} d{Am}, {Cr}d{Am} и атрибуты B1,B2,...,Bn представлены в отношении R1, а атрибуты C1,C2,...,Cr - в R2.
Существуют два принципиально разных подхода к оптимизации запро-сов. Если оптимизатор основывается только на информации о механизмах реализации путей доступа, то метод оптимизации основан на синтаксисе (на правилах, RULE). Если же помимо этого используется статистическая информация о распределении данных, то это метод оптимизации, основанный на стоимости (на издержках, COST). Рассмотрим эти подходы подробнее.
При использовании этого метода план составляется на основании существующих путей доступа и их рангов. Все пути доступа ранжируются на основании знаний о правилах и последовательности осуществления этих путей. В табл. 7.1 в качестве примера приведены ранги путей доступа для СУБД Oracle8. Таблица 7.1. Ранги путей доступа для СУБД Oracle8
* ROWID (идентификатор строки, КБД) - значение, которое может быть однозначно преоб-разовано в физический адрес записи. Ранг пути доступа определяется на основании знаний о последовательности реализации этого пути. Например, самый быстрый способ доступа - это чтение по КБД: если он известен, то это одно физическое чтение. А поиск конкретного значения через индекс (ранг 9) обычно занимает меньше времени, чем поиск в закрытом интервале значений (ранг 10). Метод оптимизации по синтаксису учитывает ранги путей доступа. Если для какой-либо таблицы существует более одного пути доступа, то выбирается тот путь, чей ранг выше, т.к. при прочих равных условиях он выполняется быстрее, чем путь с более низким рангом (рис. 7.2). Рис.7.2. Построение плана выполнения запроса в методе оптимизации по синтаксису План выполнения запроса в методе оптимизации по синтаксису формируется из выбранных путей доступа с максимальными рангами.
При использовании этого метода оптимизатор сначала строит несколько возможных планов выполнения запроса (обычно, 2-3 плана). Для выбора наиболее перспективных планов он применяет некоторые эвристики, т.е. правила, полученные опытным путем. Эти правила позволяют сузить пространство поиска оптимального плана благодаря тому, что неэффективные планы отбрасываются в самом начале и не рассматриваются. Примером эвристики может послужить такое правило: хорошим является такой план, в котором селекция производится на раннем этапе выполнения запроса. Эвристики часто основаны на законах преобразования операций реляционной алгебры. Для каждого из построенных планов рассчитывается его стоимость. Стоимость - это оценка ожидаемого времени выполнения запроса с использованием конкретного плана выполнения. При расчёте стоимости оптимизатор может учитывать такие параметры, как количество необходимых ресурсов памяти, время операций дискового ввода-вывода, время процессора. |