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




Оценка промежуточных потоков данных - часть 2


При заданных распределениях для оценок на самом нижнем (сканирование таблиц/индексов) уровне дерева плана выполнения мы проверили распределения оценок промежуточных потоков данных с использованием предположения о смешанной корреляции. Чтобы обнаружить паттерны распространения распределения вверх по дереву выполнения, мы, прежде всего, исследовали преобразования, порождаемые различными операциями, а потом рассматривали общее влияние вложенных операций.

Результаты этого эксперимента (опубликованные в [Ant93]) демонстрируют следующие паттерны преобразований распределений:

  1. Равномерное распределение селективности операндов AND преобразуется путем ANDing в распределение, хорошо апроксимируемое усеченной гиперболой.
  2. ORing производит «зеркальную» гиперболу с пиком при селективности, равной 1.
  3. Соединения и объединения повторяют паттерны AND/OR соответственно, наличие дубликатных ключей соединения увеличивает скошенность гиперболы.
  4. Вкладывание AND и соединений производит гиперболы с быстро возрастающей скошенностью, для вложенных OR и объединений сохраняется зеркальная симметрия.
  5. В некоторой точке вложенного баланса AND/OR преобразованное распределение является близким к равномерному.
  6. Для любых исходных паттернов распределения, включая точную (с одним значением) оценку имеется тенденция к преобразованию к гиперболам, часто при наличии одной или нескольких вложенных операций.

Базовые паттерны преобразования равномерного распределения иллюстрируются на рис. 1. Для операндов операций AND/OR предполагается смешанная корреляция.

Равномерное распределение pX(s) селективности s для предиката X преобразуется в усеченную гиперболу для предиката X&X, в сильно скошенную гиперболу для предиката X&X&X&X и в зеркальную гиперболу для X|X.

Рис. 1. Преобразования равномерного распределения

На основе своего производственного опыта мы также обнаружили, что гиперболы с нулевым пиком (распределение Зипфа 1/n [Zipf49]) доминирует среди всех распределений промежуточных оценок.Простое объяснение этого состоит в том, что редко встречаются запросы, производящие поиск по всей базе данных, а часто обрабатываются небольшие запросы и подзапросы.




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