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



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


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

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


Содержание  Назад  Вперед