Классика баз данных - статьи
приводятся коэффициенты селективности для
В таб. 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) |
