Обзор методов оптимизации запросов в реляционных системах

Сураджит Чаудхари

Перевод: Сергей Кузнецов

Предыдущий раздел - Содержание - Следующий раздел

5.1 Статистические сводки данных

5.1.1 Статистическая информация о базовых данных

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

В большом числе систем информация о распределении данных в столбце обеспечивается с помощью гистограмм. В гистограмме значения столбца делятся на k порций. Во многих случаях k является константой и представляет степень точности гистограммы. Однако k определяет также и использование памяти, поскольку при оптимизации запроса подходящие столбцы гистограммы загружаются в основную память. Имеется несколько вариантов разбиения значений на порции. Во многих системах баз данных для представления распределения данных в столбце используются равноглубокие гистограммы (по-другому их называют равновысокими). Если в таблице содержится n записей, и гистограмма состоит из k порций, то в равноглубокой гистограмме набор значений этого столбца делится на k диапазонов, в каждом из которых присутствует одно и то же число значений, т.е. n/k. В сжатых гистограммах часто встречающиеся значения помещаются в отдельные порции. Число таких отдельных порций может настраиваться. Как показано в [52], такие гистограммы эффективны для сильно или слабо скошенных распределений данных. Одним из аспектов гистограмм, отноящихся к оптимизации, является предположение о данных внутри одной порции. Например, для равноглубоких гистограмм можно предположить, что данные на границах порций распределены равномерно. Это предположение, так же как и широкая таксономия гистограммного подхода и влияние структуры гистограмм на точность обсуждаются в [52]. При отсутствии гистограмм может использоваться такая информация, как минимальное и максимальное значения столбца. Однако на практике используются следующее за минимальным и предыдущее максимальному значения, потому что минимум и максимум с большой вероятностью являются отдаленными значениями. Гистограммная информация дополняется информацией о таких параметрах, как число различных значений в данном столбце.

Хотя гистограммы обеспечивают информацию об одном столбце, они не обеспечивают информации о корреляции между столбцами. Для принятия в учет корреляций нам требуется совместное распределение значений. Один из вариантов состоит в использование двумерных гистограмм [45, 51]. К сожалению, пространство возможностей очень велико. Во многих системах вместо детального совместного распределения используется только сводная информация, такая как число различных пар значений. Например, статистическая информация, ассоциированная с индексом на нескольких столбцах, может состоять из гистограммы на первом столбце и общего числа различных комбинаций существующих в таблице значений столбцов.

5.1.2 Оценка статистики базовых данных

Базы данных масштаба предприятия часто имеют большую схему и содержат большие объемы данных. Поэтому для наличия гибкости при получении статистики для улучшения точности важно иметь возможность точно и эффективно оценивать статистические параметры. Один из возможных подходов основывается на взятии проб данных. Однако задачей является ограничение ошибки оценки. В [48] Шапиро и Коннелл показывают, при наличии заданного запроса требуется только небольшая проба, чтобы построить гистограмму, которая с большой вероятностью будет точной для этого запроса. Но этот подход не достигает цели, которая состоит в том, чтобы построить гистограмму, являющуюся достаточно точной для большого класса запросов. Эту проблему затрагивает наша недавняя работа [11]. Мы также показали, что задача оценки различных значений вероятно подвержена ошибкам, т.е. для любой схемы оценок существует база данных, для которой ошибка будет существенной. Этот результат объясняет возникавшие в прошлом трудности в оценке числа различных значений [50, 27]. В одной из недавних работ рассматривается также проблема поддержки статистики в инкрементальной манере [18].

5.1.3 Распространение статистической информации

Недостаточно использовать только информацию о базовых данных, поскольку запрос обычно содержит много операций. Поэтому важно быть в состоянии распространять статистическую информацию через операции. Простейший случай такой операции - это селекция. Если имеется гистограмма на столбце A, и запрос состоит из единственной селекции на столбце A, то гистограмму можно модифицировать таким образом, чтобы она отражала действие селекции. На этом шаге такие предположения, как равномерное распределение данных внутри порции данных гистограммы, приводят к некоторой неточности. Более того, ключевым источником ошибок является невозможность учета корреляции. В приведенном примере это выражается в том, что не модифицируются распределения значений других атрибутов таблицы (кроме A), а это подвергает значительным ошибкам последующие операции. Подобно этому, если в запросе присутствует несколько предикатов, то принимается предположение об их независимости и общей селективностью условия считается произведение селективностей предикатов. Однако в некоторых системах используется селективность наиболее селективного предиката, и они могут установить наличие потенциальной корреляции [17]. При наличии гистограмм на столбцах, участвующих в предикате соединения, гистограммы могут "соединяться". Однако это порождает вопрос о выравнивании границ соответствующих порций. Наконец, если гистограммная информация недоступна, то для оценки селективности используются специально подобранные константы, как в [55].

Предыдущий раздел - Содержание - Следующий раздел