Оценочная оптимизация для магии алгебра и реализация
Ограничение пространства поиска
Пространство опций для одного конкретного Filterjoin является обширным по трем причинам:
Имеется много возможных вариантов выбора для PartialResult. Вообще говоря, если составное внешнее отношение образуется путем соединения (k-1)-го отношения, то любое подмножество из 2(k-1)-1 непустых подмножеств множества этих отношений могло бы использоваться в качестве основы PartialResult.
При наличии конкретного PartialResult имеется много возможных вариантов выбора для фильтрующего множества. Вообще говоря, если имеется m атрибутов соединения, то любое подмножество из 2m-1 непустых подмножеств множества этих атрибутов могло бы использоваться в качестве основы фильтрующего множества. Кроме того, могло бы иметься несколько возможных реализаций фильтрующего множества (например, как отношение или как фильтр Блюма).
При наличии конкретного фильтрующего множества имеется обширное пространство возможных планов для внутреннего реляционного представления, модифицированного путем добавления фильтрующего множества.
Пункты (1) и (2) приводят к полному диапазону SIPS, обсуждавшемуся в [BR91]. Перед лицом громадных пространств поиска мы заимствуем два хорошо известных и широко используемых метода оптимизации: (a) На пространстве поиска для Filterjoin мы применяем эвристические ограничения. Будем надеяться, что большая часть пространства поиска, отбрасываемая эвристиками, не представляет интереса. (b) Мы принимаем предположения, позволяющие нам использовать приемлемо точные «интуитивные оценки» («guesstimates») стоимости для частей пространства поиска вместо того, чтобы действительно анализировать эти части и вычислять более точные оценки.
