Выбор и оценка альтернативных планов выполнения запросов

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

Будем называть процедурным представлением или планом выполнения запроса такое его представление, в котором в детализированной форме отображен порядок выполнения операций доступа к базе данных физического уровня. Как правило, в реляционных СУБД, ориентированных на использования традиционной аппаратуры без использования специализированных процессоров или устройств внешней памяти, выделяется подсистема управления данными на физическом уровне. Например, в System R, такая подсистема называется RSS (Relational Storage System) и обеспечивает простой интерфейс, позволяющий последовательно просматривать кортежи отношений, удовлетворяющие заданным условиям на значения полей, с использованием индексов или простым сканированием страниц базы данных. Кроме того, RSS позволяет производить отсортированные временные файлы и заносить, удалять и модифицировать индивидуальные кортежи. Более подробно интерфейс RSS описывается в [129]. Аналогичные подсистемы явно или неявно выделяются во всех подобных СУБД.

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

Тем самым, при обработке запроса на стадии, следующей за логической оптимизацией (Рис.1), решаются две задачи. Первая задача: Исходя из получаемого после произведения логической оптимизации внутреннего представления запроса и информации, характеризующей управляющие структуры базы данных (например, индексы), выбрать набор потенциально возможных планов выполнения данного запроса. Вторая задача: оценить стоимость выполнения запроса в соответствии с каждым альтернативным планом и выбрать план с наименьшей стоимостью.

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

	SELECT EMPNAME FROM EMP WHERE

DEPT# = 6 AND SALARY > 15.000 может выполняться последовательным сканированием отношения EMP с выбором кортежей с DEPT# = 6 и SALARY > 15.000; сканированием отношения через индекс I1, определенный на поле DEPT#, с условием доступа к индексу DEPT# = 6 и условием выборки кортежа SALARY > 15.000; наконец, сканированием отношения через индекс I2, определенный на поле SALARY, с условием доступа к индексу SALARY > 15.000 и условием выборки кортежа DEPT# = 6.

Аналогично, фиксированы и стратегии выполнения более сложных операций - реляционных соединений отношений, вычисления агрегатных функций на группах кортежей отношения и т.д. Например, в System R [2] для (экви)соединения двух отношений используются две основные стратегии: метод вложенных циклов и метод сортировок со слияниями. Если, например, задан запрос

	SELECT EMP.EMPNAME, DEPT.DEPTNAME FROM EMP, DEPT
	WHERE EMP.DEPT# = DEPT.DEPT# 

При использовании метода сортировок со слияниями сначала производится сортировка обоих отношений в соответствии со значениями поля DEPT# каждого отношения. При этом получаются два отсортированных временных файла EMP1 и DEPT1. Далее производится "параллельное" сканирование обоих файлов, в ходе которого выполняется "слияние" отношений в смысле операции соединения. Более точно, выбирается первый кортеж EMP1. Пусть значение поля DEPT# этого кортежа равно C1. Далее, выбирается первый кортеж из DEPT1 такой, что значение поля DEPT# этого кортежа D1 >= C1. Если удалось найти кортеж DEPT1 с D1 = C1, то это означает, что мы вошли в группу кортежей DEPT1, соединимых с текущим кортежем EMP1. Производится соединение каждого кортежа этой группы с текущем кортежем EMP1, после чего выбирается следующий кортеж EMP1, и если значение поля DEPT# в нем не изменилось, то соединение с текущей группой кортежей DEPT# повторяется. Так происходит до тех пор, пока из EMP1 не будет выбран кортеж со значением поля DEPT# С2 > C1. Тогда производится последующее сканирование DEPT1, начиная с позиции, сле- дующей за текущей группой, пока не будет выбран кортеж со значением поля DEPT# D2 >= C2 и т.д.

Если в DEPT1 найден кортеж со значением поля DEPT# D1 таким, что D1 > C1, то во временном файле EMP1 производится поиск кортежа со значением поля DEPT# C2 >= D1, и в дальнейшем EMP1 и DEPT1 меняются местами.

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

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

	SELECT R1.C1, R2.C2, R3.C3 FROM R1, R2, R3 WHERE
	R1.C4 = R2.C5 AND R2.C5 = R3.C6. 

Тогда, если в плане запроса выбирается порядок выполнения соединений сначала R1 с R2, а затем полученного временного отношения - с R3, и при этом для выполнения первого соединения выбирается метод сортировок со слиянием, то временное отношение будет заведомо отсортировано по C5, и одна сортировка не потребуется, если и второе соединение будет выполняться тем же методом.

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

Действительно, если оптимизатору удалось сгенерировать множество планов выполнения запроса на основе разумных стратегий декомпозиции и эффективных стратегий выполнения элементарных операций, то этого еще мало - нужно суметь выбрать один план, в соответствии с которым будет происходить реальное выполнение запроса. Если этот выбор будет неверным, то запрос будет выполнен неэффективно. Прежде всего необходимо определить, что понимается под эффективность выполнения запроса. Вообще говоря, это понятие неоднозначно и зависит от специфики операционной среды СУБД. В одних условиях можно считать, что эффективность выполнения запроса определяется временем его выполнения, т.е. реактивностью системы по отношению к обрабатываемым ею запросам. В других условиях определяющим является общаяя пропускная способность системы по отношению к смеси параллельно выполняемых запросов. Тогда мерой эффективности запроса можно считать количество системных ресурсов, требуемых для его выполнения: чем меньше ресурсов требуется, тем запрос эффективнее. Если пользователи СУБД работают в условиях бюджетной системы, то разумной мерой эффективности может быть бюджетная стоимость выполнения запроса и т.д. Заметим, что в любом случае оценка эффективности выполнения запроса опирается на ресурсные характеристики соответствующего плана; при использовании разных мер они просто по-разному участвуют в оценке.

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

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

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

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

	SELECT EMP.EMPNAME, DEPT.DEPTNAME WHERE
	EMP.SALARY = 20.000 AND EMP.DEPT# = DEPT.DEPT#.

Рассмотрим набор планов запроса, в которых сначала выполняется ограничение отношения ЕМР в соответствии с предикатом EMP.SALARY = 20.000 с формированием временного отношения EMP1, а затем производится соединение EMP1 с DEPT в соответствии с предикатом соединения EMP1.DEPT# = DEPT.DEPT#. Это именно множество планов запроса, поскольку мы не детализировали ни способ выполнения ограничения, ни способ выполнения соединения.

Ограничение EMP потенциально можно выполнить одним из двух способов. Первый способ - последовательное сканирование отношение EMP с выбором кортежей, удовлетворяющих предикату ограничения. При этом будет произведен доступ ко всем кортежам EMP, и, следовательно, ко всем блокам базы данных, содержащим хотя бы один кортеж из EMP. Второй способ - сканирование EMP с использованием индекса на поле EMP.SALARY с условием EMP.SALARY = 20.000. (Мы предполагаем, что этот индекс существует и, кроме того, обеспечивает последовательный доступ к кортежам в порядке возрастания или убывания значения ключа. Такому условию удовлетворяет, например, общепринятая организация индексов на основе техники B-деревьев.) В этом случае нам потребуется число обращений к блокам внешней памяти, не превышающее число кортежей отношения EMP со значением поля SALARY, равным 20.000.

Заметим, что в любом случае временное отношение EMP1 будет содержать ровно столько кортежей, сколько кортежей отношения EMP удовлетворяет предикату ограничения, и, следовательно, ровно столько блоков, сколько потребуется для размещения этих кортежей. Следовательно, при оценках стоимости выполнения соединения тем или иным методом мы будем иметь достаточно точную информацию о размерах отношения - первого операнда. На этом простом примере мы показали важность показателя предиката ограничения, характеризующего долю кортежей отношения, которые удовлетворяют данному предикату, и называемого степенью селективности предиката. Степени селективности простых предикатов вида R.C op const, где R.C задает имя поля отношения базы данных, op - операция сравнения (=, !=, >, <, >=, <=), а const константа являются основой для оценок стоимости планов запроса. Чем более точно удается определить степени селективности, тем точнее будут и общие оценки и тем, следовательно, правильнее будет выбираться оптимальный план запроса.

Конечно, на самом деле степень селективности предиката R.C op const зависит от вида операции сравнения, значения константы и от распределения значений поля C отношения R в базе данных, которой адресуется запрос. Если первые два параметра селективности известны при проведении оценок, то истинные распределения значений полей отношений, как правило, неизвестны. Существует ряд подходов к приближенным определениям распределений на основе статистической информации. Далее мы рассмотрим наиболее интересные из них.

Если известна степень селективности предиката ограничения отношения, то тем самым известна и мощность результирующего отношения (обычно мощности хранимых отношений известны при обработке запроса). Но в оценочных формулах учитывается необходимое для выполнения запроса число обменов с внешней памятью. В приведенном выше примере, когда отношение EMP сканируется с использованием индекса на поле SALARY, предполагаемое число кортежей, удовлетворяющих условию SALARY = 20.000, конечно, является верхней оценкой требуемого числа блоков, но эта оценка может быть очень завышенной. В данном случае все зависит от распределения кортежей по блокам внешней памяти. В ряде случаев можно получить более точную оценку числа блоков.

Наконец, для сложных запросов, включающих, например, соединения более двух отношений, требуется оценивать размеры возникающих в процессе выполнения запроса промежуточных временных отношений. Как известно, соединение двух отношений R1 и R2 в соответствии с предикатом соединения R1.C1 op R2.C2, где op операция сравнения, концептуально интерпретируется как ограничение отношения R, полученного в результате декартова произведения отношений R1 и R2, предикатом R1.C1 op R2.C2. Для того, чтобы оценить мощность результирующего отношения, вообще говоря, необходимо знать степень селективности предиката соединения по отношению к прямому произведению отношений-операндов. В общем случае степень селективности такого предиката невозможно определить на основе простой статистической информации. Обычно применяются достаточно грубые эвристические оценки, хотя предлагаются и подходы, обеспечивающие большую точность.

Прежде, чем приступить к рассмотрению современных подходов к решению отмеченных проблем, приведем короткий обзор подхода, применяемого для оценок стоимостей планов выполнения запроса в System R. При этом мы преследуем две цели. Во-первых, этот подход является достаточно распространенным и, как утверждают многие (например, [5]), оправданным на практике. Во-вторых, в нашем изложении мы постараемся выделить основные недостатки этого подхода, преодолению которых посвящено много работ.

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

В каталогах базы данных для каждого отношения R поддерживается следующая информация: число кортежей в данном отношении (T); число блоков внешней памяти, в которых располагаются кортежи отношения (N); для каждого поля C отношения хранится число различных значений этого поля (CD), минимальное хранимое значение этого поля (CMin) и максимальное значение (CMax). Для более точной оценки доступа к отношению через индексы для каждого индекса хранится число уровней этого индекса и число листовых страниц. (Напомним, что для организации индексов в System R используется техника B-деревьев. Поскольку в B-деревьях допускается наличие недозаполненных страниц, информация о числе уровней индекса и числе листовых страниц не выводится из информации об общем числе кортежей в отношении и числе различных значений поля, на котором определен индекс.) На нашем уровне изложения статистическая информация об индексах несущественна.

Заметим, что в ранних версиях System R (например, [2]) статистики о значениях полей поддерживались только для тех полей, на которых определены индексы, но затем были внедрены и для неиндексных полей, чтобы была возможность оценивать мощность временных отношений, полученных ограничением базового отношения в соответствии с простым предикатом на неиндексном поле [6].

При наличии такой информации в условиях базового предположения о равномерности распределения значений любого поля отношения степень селективности простых предикатов вычисляется очень просто (и очень точно, если распределение на самом деле равномерно). Будем обозначать степень селективности предиката P как SEL (P). Тогда SEL (R.C = const) = CD / (CMax - CMin) (естественно, что при равномерном распределении степень селективности такого предиката не зависит от значения константы). SEL (R.C > const) = (CMax - const) / (CMax - CMin). Аналогично, SEL (R.C < const) = (const - CMin) / (CMax - CMin) (опять же естественно, что при равномерном распределении значений поля доля кортежей, удовлетворяющих условию попадания значения заданного поля в указанный интервал значений, линейно возрастает при увеличении размера интервала). SEL (R.C <= const) полагается равной SEL (R.C < const), а SEL (R.C >= const) равной SEL (R.C > const).

При оценках числа блоков, в которых могут располагаться кортежи, удовлетворяющие предикату R.C op const, различаются два случая: отношение кластеризовано по полю C или не кластерозовано по этому полю. Заметим, что оценивать это число блоков имеет смысл только в том случае, когда сканирование отношения для его ограничения в соответствии с предикатом производится с использованием индекса на поле C. Для варианта сканирования без использования индекса понадобится всегда обратиться ровно к N блокам внешней памяти.

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

В этом случае селективность предиката по отношению к кортежам распространяется и на блоки, занимаемые этими кортежами. Например, если в блоке внешней памяти базы данных размещается K кортежей отношения R (параметр K в System R определяется при создании отношения и не изменяется во все время его существования), то число блоков кластеризованного отношения, содержащих кортежи, удовлетворяющие предикату R.C op const, определяется по формуле T * SEL (R.C op const) / K. (Первый член формулы задает количество кортежей, удовлетворяющих предикату.)

При оценках числа блоков, в которых могут располагаться кортежи отношения, удовлетворяющие предикату R.C op const, в случае, когда отношение не кластеризовано по полю C, при разработке начального варианта оптимизатора исходили из того, что в этом случае кортежи могут быть произвольным образом разбросаны по блокам базы данных, содержащим кортежи данного отношения. Поэтому оценка производилась по формуле T * SEL (R.C op const). Однако впоследствии было замечено, что эта формула дает завышенный результат, если число кортежей отношения, удовлетворяющих предикату, достаточно велико (т.е. селективность предиката низкая) [6].

Записи листовых блоков индекса отношения R на поле C в System R имеют следующую структуру: значение ключа, список уникальных идентификаторов кортежей отношения R, у которых поле C имеет тоже значение, что и ключ. Уникальный идентификатор кортежа (tid) обеспечивает прямой доступ к кортежу и содержит, в частности, номер блока, в котором располагается кортеж (более подробно организация блоков базы данных System R и способ адресации кортежей описываются в [129]).

Если при организации списка tid'ов в записи индекса поддерживать в каждом списке упорядоченность tid'ов в соответствии с номерами блоков, содержащих соответствующие кортежи, то при последовательном просмотре кортежей с фиксированным значением ключа появляется некоторый элемент порядка. В уточненном варианте оптимизатора System R для оценки числа блоков, обращения к которым должны произойти при таком просмотре используется формула N * (1 - (1 - 1/N) ** CD). Эта формула была впервые выведена и обоснована Яо [74]. Понятно, что на основе этой формулы можно оценить и число блоков, обращения к которым потребуются при сканировании отношения через индекс для ограничения отношения в соответствии с предикатом с известной (оцененной ранее) селективностью.

Заметим, что и в этом подходе к оценке числа блоков с жестким разделением случаев кластеризованности отношения R по полю C и отсутствия такой кластеризованности проявляется некоторая ограниченность System R. В реальных условиях кластеризованность отношения по одному полю не обязательно означает полное отсутствие кластеризованности того же отношения по другим полям (предположение System R о независимости распределений значений разных полей отношения). Ниже мы рассмотрим один из предложенных в последнее время подходов к более адекватному учету реально существующих кореляций атрибутов отношений.

Предположения о равномерности распределений значений атрибутов отношений позволяют достаточно просто оценивать и мощности отношений, являющихся результатами двухместных реляционных и теоретико-множественных операций над отношениями. Рассмотрим, например, как можно оценить степени селективности двух предикатов соединения - R1.C1 = R2.C2 и R1.C1 > R2.C2.

Начнем с предиката эквисоединения R1.C1 = R2.C2. Пусть Ti и CDi - число кортежей в отношении Ri и число различных значений поля Ci, соответственно. Тогда в отношении Ri существует Ti/CDi групп кортежей с одинаковыми значениями поля Ci. Очевидно, что при выполнении операции соединения кортежи каждой группы кортежей отношения R1 могут быть соединены с кортежами не более, чем одной группы отношения R2 (и наоборот). Если кортежи двух групп соединяются, то в результирующем отношении образуется (T1/CD1) * (T2/CD2) кортежей. (Оценка числа кортежей в каждой группе в виде Ti/CDi правомерна в соответствии с предположением о равномерности распределения). Очевидно, что соединиться могут не более, чем Min (CD1, CD2) групп. Поэтому верхней оценкой мощности результирующего отношения может быть Min (CD1, CD2) * (T1/CD1) * (T2/CD2). Соответственно, степень селективности предиката эквисоединения можно оценить, как Min (CD1, CD2) / (CD1 * CD2).Заметим, что эта оценка достаточно точна (при соблюдении предположении о равномерности распределения), если отношения "хорошо" соединяются, как, например, отношения EMP и DEPT из нашего примера по полю DEPT#.

Формула для оценки степени селективности предиката соединения R1.C1 > R2.C2 выводится немного более сложно. Обозначим через CiMax и CiMin, соответственно, максимальное и минимальное значения поля Ci.Пусть кортежи из j-ой группы кортежей отношения R1 имеют значение поля C1, равное cj. Тогда число кортежей отношения R2, удовлетворяющих предикату соединения относительно j-ой группы отношения R1 можно оценить как ((C2Max - cj) / (C2Max - C2Min)) * T2. Число кортежей в результирующем отношении, возникающих при соединении j-ой группы кортежей отношения R1 с кортежами отношения R2 оценивается как (T1/CD1) * ((C2Max - cj) / (C2Max - C2Min)) * T2. Для получения оценки общего числа кортежей в результирующем отношении необходимо просуммировать полученную формулу по j для всех групп отношения R1. При этом можно воспользоваться тем, что в силу предположения о равномерности распределения значений поля C1 сумму cj можно оценить как CD1 * AVG (cj) = CD1 * (C1Max C1Min) / CD1 = C1Max - C1Min. Результирующая формула для оценки мощности результирующего отношения имеет вид: T1 * T2 * (C2Max - C1Max + C2Min) / (C2Max - C2Min). Соответственно, селективность предиката оценивается по формуле (C2Max C1Max + C2Min) / (C2Max - C2Min).

Аналогично строятся формулы для оценок мощностей результатов других двухместных операций.

Оценки селективности предикатов используются в оценочных формулах оптимизатора и для оценки затрат ресурсов процессора. Эти оценки базируются на предположении (подтверждаемом на практике) о том, что основная часть процессорной обработки производится в RSS. Поэтому процессорные затраты измеряются просто числом обращений к RSS, которое в свою очередь определяется числом кортежей, получаемых при сканировании хранимого или временного отношения, т.е. селективностью логического выражения, состоящего из простых предикатов. (Напомним, что при сканировании отношения при каждой операции взятия следующего кортежа RSS получает параметр - логическое выражение, состоящее из простых предикатов и представляющее условие, которому должен удовлетворять следующий кортеж. На самом деле при использовании RSS в System R это логическое условие всегда одно и то же в пределах каждого сканирования и представляет собой предикат ограничения соответствующего отношения [129].) При предположениях о равномерности и независимости значений разных полей отношения селективность логического выражения, составленного из простых предикатов, легко оценить при известных степенях селективности простых предикатов.

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

Например, пусть для выполнения запроса

	SELECT EMP.EMPNAME, DEPT.DEPTNAME FROM EMP, DEPT WHERE
	EMP.SALARY = 20.000 AND DEPT.DEPT# > 4
	AND EMP.DEPT# = DEPT.DEPT# 

оценивается следующий план выполнения: выполнить ограничение отношения EMP с использованием некластеризованного индекса на поле EMP.SALARY и порождением временного отношения EMP1 (элементарная операция ОП1); выполнить ограничение отношения DEPT с использованием кластеризованного индекса на поле DEPT.DEPT# и порождением временного отношения DEPT1 (элементарная операция ОП2); отсортировать отношение EMP1 в соответствии со значениями поля EMP.DEPT# с порождением отсортированного файла EMP2 (элементарная операция ОП3); отсортировать отношение DEPT1 в соответствии со значениями поля DEPT.DEPT# с порождением отсортированного файла DEPT2 (элементарная операция ОП4); соединить файлы EMP2 и DEPT2 по полю DEPT# (элементарная операция ОП5). Стоимость элементарных операций ОП1 и ОП2 оценивается на основе формул и статистической информации об отношениях EMP и DEPT. Стоимость элементарных операций ОП3, ОП4 и ОП5 оценивается на основе формул и оценок операций ОП1 и ОП2 (мощности отношений EMP1 и DEPT1). Оценка общей стоимости плана выполнения запроса складывается из оценок для ОП1, ОП2, ОП3, ОП4 и ОП5.

Подход к построению альтернативных планов выполнения запроса и вычислению оценок их стоимостей и набор применяемых в System R оценочных формул подробно описан в [4]. В более доступной работе [5] содержится систематическое описание оценочных формул, применимых при тех же предположениях, но не соответствующих точно System R.

Последнее, что мы заметим по поводу подхода System R, касается поддержания статистической информации об отношениях базы данных. Естественно, что поддерживать в динамике изменений базы данных точную информацию, например, о числе различных значений полей отношения, было бы слишком накладно (особенно для тех полей, на которых не определены индексы). Поэтому эта информация не корректируется при каждом изменении базы данных. В System R существует специальная утилита сбора статистики, которая и производит соответствующие коррекции либо периодически, либо по явному указанию оператора.

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

Естественно, что если отказаться от предположения о равномерности распределения значений поля отношения, то необходимо каким-то образом уметь установить реальное распределение значений. Как отмечается, например, в [90], существует два базовых подхода к оценкам распределения значений поля отношения: параметрический и основанный на методе сигнатур. Подход System R является тривиальным частным случаем метода параметрической оценки распределения - любое распределение оценивается как равномерное. Более развитый подход был предложен Христодолакисом в [81]. Он предложил использовать для оценки реального распределения значений поля отношения серию распределений Пирсона, в которую входят распределения от равномерного до нормального. Выбор распределения из серии производится путем вычисления нескольких параметров на основе выборок реально встречающихся значений.

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

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

Традиционный подход, описываемый, например, в [81], состоит в том, что область значений поля разбивается на N интервалов равного размера, и для каждого интервала подсчитывается число значений полей из кортежей данного отношения, попадающих в интервал. Например, предположим, что наше отношение регистрации сотрудников предприятия EMP расширено еще одним полем AGE - возраст сотрудника. Пусть всего в организации работает 60 сотрудников в возрасте от 10 до 60 лет. Тогда гистограмма, изображающая распределение значений поля AGE может иметь вид, показанный на Рис.2. Гистограмма построена исходя из разбиения диапазона значений поля AGE на 10 интервалов.

Рассмотрим, как можно оценивать селективность простых предикатов, задаваемых на поле AGE, с использованием такой гистограммы. Пусть в интервал значений AGE Si попадает Ki значений. Тогда SEL (EMP.AGE = const), если значение константы попадает в интервал значений Si, можно оценить следующим образом: 0 <= SEL (EMP.AGE) <= Ki/T (T - общее число кортежей в отношении EMP). Отсюда средняя оценка степени селективности предиката - Ki / (2 * T). Например, SEL (AGE = 29) оценивается в 40/200 = 0.2, а SEL (AGE = 16) оценивается в 5/200 = 0.025. Это, конечно, существенно более точные оценки, чем те, которые можно получить, исходя из предположений о равномерности распределений. Но не так хорошо обстоят дела с оценками селективности простых предикатов с неравенствами.

Например, пусть требуется оценить степень селективности предиката EMP.AGE < const. Если значение константы попадает в интервал Si, и SUMi - суммарное количество значений AGE, попадающих в интервалы S1, S2, ..., Si, то SUMi-1 / T <= SEL (AGE < const) <= SUMi / T. Тогда средняя оценка степени селективности (SUMi-1 + SUMi) / (2 * T), и ошибка оценки может достигать половины веса подобласти, в которую попадает значение константы предиката. Самое неприятное, что ошибка оценки зависит от значения константы и тем больше, чем больше значений поля содержится в соответствующем интервале гистограммы. Например, SEL (AGE < 29) оценивается как 46/100 <= SEL (AGE < 29) <= 86/100, откуда оценка степени селективности (46 + 86) / 200 = 0.66; при этом ошибка оценки может достигать 0.2. В то же время SEL (AGE < 49) оценивается существенно более точно.

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

На Рис.3 область значений поля AGE отношения EMP разбита на 10 интервалов таким образом, что в каждый интервал попадает ровно по 10 значений поля AGE. При этом, естественно, интервалы имеют разные размеры. Граничные значения интервалов показаны над вертикальными линиями. Особенностью псевдогистограммы является то, что в ней возможны, в частности, интервалы, правая и левая граница которых совпадают. На нашем рисунке таким интервалом является интервал (28,28). Он образовался по причине наличия в отношении EMP большого (большего десяти) числа кортежей со значением AGE = 28.

Очевидно, что с использованием такой "псевдогистограммы" ошибки при оценках степеней селективности предикатов с операцией, отличной от равенства, уменьшаются. В [84] приводятся два метода оценок селективности простых предикатов на основе такого способа описания распределения с минимизацией возможной ошибки в худшем случае и в среднем. При этом размер ошибки уже не зависит от значения константы предиката и уменьшается при увеличении числа интервалов.

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

Подход основывается на статистике Колмогорова, из которой применительно к случаю реляционных баз данных следует, что если из отношения выбирается образец из 1064 кортежей, и b - доля кортежей в образце со значениями поля C < V, то с достоверностью 99% доля кортежей во всем отношении со значениями поля C < V находится в интервале [b-0.05, b+0.05]. При уменьшении мощности образца достоверность, естественно, уменьшается.

В системе FASTSCAN, упоминаемой в [84], псевдогистограмма строится точно для отношений, включающих не более 1064 кортежей, иначе для построения псевдогистограммы используется образец из 1064 кортежей. Приведены экспериментальные результаты оценок селективности простых предикатов в FASTSCAN в сравнении с реальной селективностью и оценками System R. Если не учитывать того, что эксперименты производились на специально сгенерированной базе данных, результаты FASTCSAN существенно превосходят результаты System R.

Тем не менее, несмотря на все недостатки предположений System R о равномерности распределений значений полей, заметим, что подход этой системы хорошо сбалансирован, и отказ от этого предположения повлек бы далеко идущие последствия. Чтобы учитывать неравномерность распределения значений, в общем случае при оценке селективности простого предиката должно быть известно значение его константы. Но в System R, вообще говоря, это не так. В языке SQL, когда он используется как язык, встроеннный в традиционный язык программирования, допускается использование констант, задаваемых переменными объемлящей программы. Поскольку обработка предложений SQL происходит на стадии прекомпиляции программы (подробно этот процесс описывается в [129]), то значения таких констант, конечно, неизвестны. Тем не менее нужно оценивать планы выполнения запроса. Предположения о равномерности распределений значений позволяют это сделать. Нам неизвестны предложения, которые могли бы при сохранении базового подхода System R к обработке запросов (а он нам кажется очень удачным) позволить воспользоваться в полном объеме информацией о реальных (или оцененных статистически) распределениях значений.

Остановимся теперь на предложениях, касающихся более точной оценки числа блоков внешней памяти, обращения к которым потребуются при выполнении запроса. Как мы отмечали, основным предположением, на котором основываются оценки System R, является предположение о независимости распределений значений различных полей отношения. При этом по-разному оценивается число блоков, обращения к которым потребуются при сканировании отношения без использования индекса, при сканировании через некластеризованный и кластеризованный индексы. Оценки, касающиеся случаев сканирования без индекса и с использованием кластеризованного индекса, достаточно удовлетворительны (при выбранных в System R подходах к организации внешней памяти и оценке селективности простых предикатов). В [86] предлагается подход, позволяющий более точно оценивать число блоков, затрагиваемых при сканировании отношения через некластеризованный индекс.

Основная идея состоит в отказе от предположения о независимости распределений значений разных полей отношения. В действительности, достаточно часто всречается случай, когда атрибуты отношения коррелируют. Например, в нашей базе данных, описывающей струтуру организации, в отношении EMP значения полей SALARY и AGE, скорее всего, распределены не независимо: достаточно часто оклад сотрудника возрастает по мере возрастания его возраста. Следовательно, если отношение EMP кластеризовано в соответствии со значениями поля SALARY, то кортежи этого отношения, вообще говоря, не разбросаны произвольно по блокам внешней памяти относительно значений поля AGE. Поэтому, если оценивать число блоков внешней памяти, к которым потребуются обращения при сканировании отношения с использованием индекса на поле AGE для ограничения отношения по предикату AGE op const, с применением подхода System R, то оценки могут оказаться весьма завышенными. Предлагается учитывать зависимость распределений значений полей при оценках числа блоков.

Более точно, если отношение R кластеризовано по полю С1 и оценивается число блоков, к которым потребуются обращения при сканировании отношения с использованием индекса на поле C2, то предлагается учитывать зависимость распределений значений полей C1 и C2 (корреляцию атрибутов отношения). Фактически, исходя из фактов кластеризации отношения по полю C1 и зависимости распределений значений C1 и C2, можно оценить степень кластеризации отношения по полю C2. Эта идея кажется очень интересной и полезной, поскольку неформулизуемая на уровне разного рода зависимостей корреляция атрибутов может быть очень распространенным явлением и, конечно, ее хотелось бы уметь учитывать. Весь вопрос в том, как это делать практически. Алгоритм, предлагаемый в [86], служит только для иллюстрации идеи и не имеет практического значения. Может быть, можно разработать какой-либо метод на основе сигнатурных описаний распределений значений разных полей отношения. На сегодняшний день никакие разработки на эту тему нам неизвестны. Заметим еще по этому поводу, что непосредственной логической связи между методами оценок селективности простых предикатов и методами учета корредяции атрибутов нет.

В некоторых работах, например, в [41, 87-88] приводятся критика подхода System R и соответствующие предложения по части более правильного учета стоимости обменов с внешней памяти при выполнении запроса. В оценочных формулах System R участвует оцениваемое число блоков внешней памяти, к которым потребуются обращения при выполнении запроса. При этом неявно подразумевается, что обмен с каждым блоком требует одних и тех же накладных расходов независимо от того, как реально расположены эти блоки на устройстве внешней памяти. Не учитываются те факты, что, во-первых, основное время при выполнении обмена с дисковым устройством с подвижными головками тратится на подвод головок к нужному цилиндру. Если несколько обменов выполняется последовательно с блоками, расположенными на одном цилиндре, то все обмены, кроме первого, занимают существенно меньшее время. Из этого следует, что при распределении блоков внешней памяти для хранения отношения базы данных не произвольным образом, а стремясь расположить блоки одного отношения на одном или близком цилиндрах, оценки System R для последовательного сканирования отношения без использования индекса могут быть весьма завышенными.

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

Наиболее естественно можно применить этот подход в аппаратных или программных процессорах реляционной алгебры, когда элементарным действием процессора является выполнение реляционной операции. Тем не менее, иногда эту особенность аппаратуры можно эффективно использовать даже при использовании такого мало приспособленного для этого интерфейса, как интерфейс RSS System R. Например, в интерфейсе RSS предусмотрена операция, позволяющая за одно обращение к RSS выполнить ограничение указанного отношения и отсортировать получаемое подотношение в соответствии со значениями указанного поля (более подробно это описано в [129]). При выполнении такой операции может оказаться выгодно полностью узурпировать дисковое устройство, на котором располагается отношение, на все время его сканирования.

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

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

В рассматриваемой системе, основанной на развитии СУБД INGRES, допускается определение пользователем процедур оценки селективности простых предикатов. Допускается определение глобальных и локальных процедур оценки селективности предикатов. Глобальные процедуры связываются с предикатами указанного вида, локальные - с предикатами, задаваемыми для указанного отношения или указанного поля. При выборе процедуры оценки локальные процедуры имеют более высокий приоритет, чем глобальные. Интерфейс всех оценочных процедур фиксирован: на входе к ним поступают реальные параметры предиката и статистическая информация, поддерживаемая СУБД; на выходе процедура выдает оценочное число кортежей, удовлетворяющих предикату. Подчеркивается, что поставляемые пользователями оценочные процедуры могут базироваться на статистике, связанной с реальным потоком запросов, из-за чего точность оценок повышается. К сожалению, в статье не описываются детали реализации, но подход представляется нам очень перспективным.