Классика баз данных - статьи
При заданных распределениях для оценок
При заданных распределениях для оценок на самом нижнем (сканирование таблиц/индексов) уровне дерева плана выполнения мы проверили распределения оценок промежуточных потоков данных с использованием предположения о смешанной корреляции. Чтобы обнаружить паттерны распространения распределения вверх по дереву выполнения, мы, прежде всего, исследовали преобразования, порождаемые различными операциями, а потом рассматривали общее влияние вложенных операций.
Результаты этого эксперимента (опубликованные в [Ant93]) демонстрируют следующие паттерны преобразований распределений:
- Равномерное распределение селективности операндов AND преобразуется путем ANDing в распределение, хорошо апроксимируемое усеченной гиперболой.
- ORing производит «зеркальную» гиперболу с пиком при селективности, равной 1.
- Соединения и объединения повторяют паттерны AND/OR соответственно, наличие дубликатных ключей соединения увеличивает скошенность гиперболы.
- Вкладывание AND и соединений производит гиперболы с быстро возрастающей скошенностью, для вложенных OR и объединений сохраняется зеркальная симметрия.
- В некоторой точке вложенного баланса AND/OR преобразованное распределение является близким к равномерному.
- Для любых исходных паттернов распределения, включая точную (с одним значением) оценку имеется тенденция к преобразованию к гиперболам, часто при наличии одной или нескольких вложенных операций.
Базовые паттерны преобразования равномерного распределения иллюстрируются на рис. 1. Для операндов операций AND/OR предполагается смешанная корреляция.
Равномерное распределение pX(s) селективности s для предиката X преобразуется в усеченную гиперболу для предиката X&X, в сильно скошенную гиперболу для предиката X&X&X&X и в зеркальную гиперболу для X|X.
Рис. 1. Преобразования равномерного распределения
На основе своего производственного опыта мы также обнаружили, что гиперболы с нулевым пиком (распределение Зипфа 1/n [Zipf49]) доминирует среди всех распределений промежуточных оценок.Простое объяснение этого состоит в том, что редко встречаются запросы, производящие поиск по всей базе данных, а часто обрабатываются небольшие запросы и подзапросы.
