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

       

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


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

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

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


Содержание раздела