Оценивание FilterCostRk
Чтобы моделировать перезапись на основе магических множеств как Filterjoin и получать оценку его стоимости, нам не требуется явно планировать модифицированное внутреннее представление. Нам нужно всего лишь оценить мощность модифицированного представления и стоимость наилучшего плана его генерирования. На этой стадии не нужен реальный план, потому что в архитектуре оптимизации, представленной в разд. 2.2, требуется второй проход оптимизации после выполнения магической перезаписи. Размер фильтрующего воздействия фильтрующего множества (т.е. его селективность) зависит от его мощности. Поскольку точно оценить мощность проекции трудно [LNSS93], в существующих оптимизаторах принимаются некоторые предположения для оценки мощности проекции [Yao77].
Нам требуется параметризованный план для ограничения Rk, параметром которого является фильтрующее множество. Далее, нам хотелось бы иметь возможность генерировать параметризуемый план только один раз. Каждый конкретный план получается путем параметризации плана конкретным фильтрующим множеством. По экземпляру плана можно получить его стоимость и мощность результата. Поскольку параметризуемая оптимизация запросов является темой проводимого в данное время исследования [INSS92], результаты носят слишком предварительный характер, чтобы их можно было применить к нашей проблеме. Нам нужен конкретный метод для работы с параметризацией в нашем контексте. Тривиальное решение состоит в том, чтобы выполнять вложенный вызов оптимизатора при создании каждого экземпляра плана. Однако время создания каждого экземпляра должно быть небольшой константой, а поскольку Rk может сложным выражением, включающим несколько соединений, этого добиться невозможно.
Заметим, что мощность отфильтрованного внутреннего отношения Rk’ является функцией только от селективности фильтрующего множества (которая известна) и не зависит от физического размера или реализации фильтрующего множества. После того как мощность Rk’ подсчитана для нескольких значений селективности F, можно соединить полученные точки линией, определяя тем самым функцию мощности Rk’ для всех фильтрующих множеств.
В действительности, в своей реализации мы решили вычислять всего две точки и производить прямую линейную интерполяцию. Выбранные точки соответствуют селективности 0 (когда мощность результата, очевидно, равняется нулю) и 1 (когда мощность результата совпадает с мощностью не модифицированного представления Rk).
Оценивание стоимости Rk’ является более сложным, потому что функции стоимости соединений могут быть нелинейными, особенно в границах размеров, когда отношение перестает помещаться в основной памяти, доступной для некоторой операции. Поэтому простая линейная интерполяция может быть неточной. Один из подходов состоит в том, чтобы определить несколько классов эквивалентности на основе размера магического множества (например, «меньше размера буфера» и «больше размера буфера») и внутри каждого класса использовать прямую линейную интерполяцию. Следует заметить, что на практике фильтрующие множества обычно бывают небольшими, поскольку содержат проекцию (без дубликатов) только на столбец соединения. Поэтому простая линейная интерполяция может выполняться удовлетворительным образом; на самом деле, в своем прототипной реализации мы использовали именно этот метод.
