Классика баз данных - статьи
Для этого необходимо заменить традиционную
Для этого необходимо заменить традиционную оценку с единственным значением на функцию плотности вероятности оценки, представленную в численном виде (подход, использованный нами в экспериментах) или аналитической аппроксимацией (например, рядом, подобным [SunL93]). Задача отделения неопределенности на сегодняшний день не решена, и для ее решения требуются значительные усилия исследователей.
Использование методов оценки, которые основываются на данных, хранимых в индексах/таблицах, обеспечивает достаточную точность для нескольких вложенных операций над узлами выборки. Методы взятия образцов для разнообразных структур хранимых данных описаны в [OlRo89], [OlRo90], [Ant93], [OlRo93]. Алгоритмы и правила останова для оценки на основе взятия образцов соединений и ограничений представлены в [LiNS90], [HaSw92].
Чем больше операций включается в подзапрос, подлежащий непосредственной оценке на основе взятия образцов, тем более крупные области определенности могут потенциально остаться непокрытыми. Однако ограничения на размеры образцов, помогающие сохранить стоимость оценок более низкой, чем стоимость выполнения, ограничивают число вложенных операций до небольшого числа, при котором можно добиться разумной точности. Кроме того, при использовании комбинаторного поиска наилучшего решения требуется оценить n! подмножеств n-сторонней операции, чтобы найти наилучшее дерево выполнения. Для решения этой проблемы можно было бы применить совместные многоцелевые оценщики с общим правилом останова.
Предположим теперь, что мы эффективно отделили область неопределенности выражения запроса, применив желаемую процедуру многоцелевой оценки. Правильно оцененная часть запроса может оптимизироваться с применением известных методов, но как нам обработать операции, попадающие в область неопределенности? Ответ на этот вопрос можно вывести из вида преобладающего гиперболического распределения оценок. На основе свойств гиперболического распределения в 1990 г. мы разработали конкурентную модель [Ant91] для динамической оптимизации запросов и реализовали ее в Rdb release V4.0.
