Классика баз данных - статьи
в отделении чисто языковые аспекты
Многообещающий подход к этой проблеме заключается в отделении чисто языковые аспекты от собственно оптимизации, которую можно доверить нескольким "экспертам оптимизации".
Существует естественная связь между затратами на оптимизацию и качеством результирующего плана выполнения. Высокие затраты на оптимизацию оправданы для регулярно выполняемых запросов, поскольку стоимость оптимизации окупается снижением затрат на выполнение и амортизируется многократностью выполнения. Однако нерационально тратить слишком много ресурсов на оптимизацию однократно выполняемых сиюминутных запросов. Большую часть затрат оптимизации составляет поиск в пространстве решений, представляющих альтернативные планы выполнения. Для распределенных систем характерны большие размеры пространства решений, поскольку число распределенных стратегий выполнения очень велико. Следовательно, важное значение здесь имеют исследования, направленные на выработку эффективных методов обхода пространства решений, исключающих его исчерпывающий перебор.
Глобальная оптимизация запросов производится заранее, до их выполнения, поэтому она называется статической. Основная проблема, возникающая в связи с этим, заключается в том, что модель стоимости, которая использовалась при оптимизации, со временем становится неточной, как из-за изменения размеров фрагментов, так и из-за реорганизаций базы данных, проводимых для балансировки нагрузки. Таким образом, задача состоит в том, чтобы определить оптимальные интервалы рекомпиляции/реоптимизации запросов с учетом соотношения затрат на их оптимизацию и выполнение.
Критически важной проблемой с точки зрения стратегии поиска является проблема упорядочения соединений, которая является NP-полной от числа отношений [Ibaraki and Kameda, 1984]. Типичный подход к решению этой задачи – применение динамического программирования [Selinger et al., 1979], которое является детерминированной стратегией. Эта почти исчерпывающая стратегия, гарантирующая нахождение наилучшего плана из всех возможных.Затраты (по времени и памяти) на ее реализацию приемлемы для небольшого числа отношений. Однако уже для 5-7 отношений такой подход становится слишком дорогостоящим. В связи с этим в последнее время возрос интерес к стратегиям случайного перебора (randomized strategy), которые снижают сложность оптимизации, но не гарантируют нахождение наилучшего плана. Стратегии случайного перебора исследуют пространство решений контролируемым образом, в том смысле что оптимизация завершается по исчерпанию заданного для нее бюджета времени. Еще один способ снизить сложность оптимизации – применение эвристических подходов. В отличие от детерминированных стратегий, стратегии случайного перебора позволяют управлять соотношением затрат на оптимизацию и выполнение запросов [Ioannidis and Wong, 1987, Swami and Gupta, 1988, Ioannidis and Kang, 1990].
