Оценочная оптимизация для магии алгебра и реализация

       

Ограничение пространства поиска


Пространство опций для одного конкретного Filter­join является обширным по трем причинам:

  • Имеется много возможных вариантов выбора для PartialResult. Вообще говоря, если составное внешнее отношение образуется путем соединения (k-1)-го отношения, то любое подмножество из 2(k-1)-1 непустых подмножеств множества этих отношений могло бы использоваться в качестве основы PartialResult.
  • При наличии конкретного PartialResult имеется много возможных вариантов выбора для фильтрующего множества. Вообще говоря, если имеется m атрибутов соединения, то любое подмножество из 2m-1 непустых подмножеств множества этих атрибутов могло бы использоваться в качестве основы фильтрующего множества. Кроме того, могло бы иметься несколько возможных реализаций фильтрующего множества (например, как отношение или как фильтр Блюма).
  • При наличии конкретного фильтрующего множества имеется обширное пространство возможных планов для внутреннего реляционного представления, модифицированного путем добавления фильтрующего множества.

    Пункты (1) и (2) приводят к полному диапазону SIPS, обсуждавшемуся в [BR91]. Перед лицом громадных пространств поиска мы заимствуем два хорошо известных и широко используемых метода оптимизации: (a) На пространстве поиска для Filter­join мы применяем эвристические ограничения. Будем надеяться, что большая часть пространства поиска, отбрасываемая эвристиками, не представляет интереса. (b) Мы принимаем предположения, позволяющие нам использовать приемлемо точные «интуитивные оценки» («guess­timates») стоимости для частей пространства поиска вместо того, чтобы действительно анализировать эти части и вычислять более точные оценки.



    Содержание раздела