Выбор путей доступа
Как оценки стоимости используются при оптимизации запросов? Как отмечалось в разд. 5.2, имеются эвристические процедуры, в которых они вообще не используются. В других подходах эвристическое сокращение выбора объединяется с перечислительной (enumerative) минимизацией стоимости в "конце игры" [Youssefi and Wong 1979]. Эксперименты показывают, что эффективность баз данных может существенно улучшить комбинаторный анализ [Epstein and Stonebraker 1980].
Имеются два способа использования оценок стоимости в процессе выбора. Во-первых, стоимость каждого альтернативного плана доступа можно определить полностью [Blasgen and Eswaran 1976; Yao 1979]. Преимуществом этого подхода является реалистичный способ применения методов, подобных параллелизму и обратной связи. С другой стороны, высоки расходы на оптимизацию.
Во-вторых, стоимость стратегий можно вычислять инкрементально в параллель с их генерацией. Этот подход позволяет параллельно оценивать полное семейство стратегий с общими компонентами, что существенно сокращает расходы на оптимизацию. Например, в методе, предложенном в [Rosenthal and Reiner 1982], сохраняется только стоимость минимального способа получения промежуточного результата, и отвергается любой другой метод, распознаваемый как неоптимальный.
Расширением этого второго подхода является динамическая процедура оптимизации запросов, которая происходит из того наблюдения, что в каждый момент времени требуется принятие решение только по поводу выполнения следующей операции. Чтобы гаранировать общую оптимальность, должны оцениваться только последствия этого решения на оставшуюся часть вычисления. У динамической процедуры имеются реальные данные обо всех ее операндах, включая промежуточные результаты. Эта информация может также использоваться для обновления оценок оставшихся шагов. У динамического метода имеются два недостатка: его стоимость и опасность ошибки в локальном оптимуме, если не применять заглядывания вперед. Однако при аккуратном использовании этот метод может сократить оценки стоимости для запросов, в которых размер реальных промежуточных результатов отличается оцененных размеров.
