Классика баз данных - статьи

       

приводятся коэффициенты селективности для


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

column = value
F = 1 / ICARD(column index), если на столбце имеется индекс

Здесь предполагается равномерное распределение кортежей по значениям ключа индекса

Иначе F = l/10
 
column1 = column2
  F = l/MAX(ICARD(columnl index), ICARD(column2 index))

            если имеются индексы и на columnl, и на column2

Здесь предполагается, что для каждого значения ключа в индексе с меньшей мощностью имеется соответствующее значение в другом индексе

F = l/ICARD(column-i index), если имеется индекс только на column-I

Иначе F = l/10
 
column > value (или любое другое открытое сравнение)
  F = (high key value - value) / (high key value - low key value)

F получается путем линейной интерполяции заданного значения в диапазоне значений ключа, если у столбца арифметический тип, и значение известно во время выбора пути доступа

Иначе F = l/3 (например, тип столбца не является арифметическим)

Последнее число не слишком существенно, за исключением того факта, что оно показывает меньшую селективность, чем у предиката сравнения на равенство, для которого нет индексов, и это число больше 1/2. У нас имеется гипотеза, что лишь в немногих запросах используются предикаты, которым удовлетворяет более половины кортежей.
 
column BETWEEN value1 AND value2
  F = (value1 - value2) / (high key value - low key value)

В качестве коэффициента селективности используется отношение размера диапазона значений BETWEEN к размеру общего диапазона ключа, если тип столбца является арифметическим, и value1 и value2 известны во время выбора пути доступа

Иначе F = l/4

В последней формуле опять не слишком много смысла за исключением того, что значение находится между коэффициентами по умолчанию для предиката сравнения по равенству и предиката сравнения с открытым неравенством.
 
column IN (список значений)
  F = (число элементов в списке) * (коэффициент селективности для column = value)

Здесь допускается значение, большее l/2
 
columnA IN subquery
  F = (ожидаемая мощность результата подзапроса) / (произведение мощностей всех

отношений из списка FROM подзапроса)

Вычисление мощности результата запроса будет обсуждаться позже

Эта формула выводится на основе следующих аргументов:

Рассмотрим простейший случай, когда подзапрос имеет вид "SELECT columnB FROM relationC". Предположим, что множество всех значений columnB в relationC содержит множество всех значений columnA. Если подзапрос выбирает все кортежи relationC, то значением предиката всегда является TRUE, и F = 1. Если кортежи подзапроса ограничиваются коэффициентом селективности F', то предположим, что множество уникальных значений в результате подзапроса, которые соответствуют значениям columnA, ограничено в той же пропорции, т.е. коэффициентом селективности предиката должно быть F'. F' является произведением всех коэффициентов селективности подзапроса, а именно, (мощность подзапроса) / (мощность всех возможных ответов на подзапрос). При наличии некоторого оптимизма мы можем расширить эти соображения на подзапросы с соединениями и подзапросы, в которых columnB заменяется арифметическим выражением, содержащим имена столбцов. Это приводит к указанной выше формуле.
 
(pred expression1) OR (pred expression2)
  F = F(pred1) + F(pred2) - F(pred1) * F(pred2)
 
(pred1) AND (pred2)
  F = F(pred1) * F(pred2)

Заметим, что здесь предполагается, что значения столбцов независимы.
 
NOT pred
  F = 1 - F(pred)
<

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