Классика баз данных - статьи

       

Обучающийся оптимизатор


В этом разделе описывается архитектура LEO, самонастраивающегося оптимизатора, который следит за реальным выполнением запроса и использует реальные значения мощности для проверки достоверности и повышения качества модельных оценок и для повторной оптимизации выполняемого запроса без вмешательства пользователя. Обсудим две важнейшие функции LEO: замедленное обучение для будущих запросов и поступательная оптимизация запроса, выполняемого в данное время.

Замедленное обучение на основе обратной связи. При замедленном обучении эмпирические результаты реального выполнения запросов используются для инкрементальной проверки достоверности модели оптимизатора, определения того, какая часть модели оптимизатора является ошибочной, и вычисления поправок к модели для оптимизации последующих запросов. Замедленное обучение в LEO работает при наличии того предположения, что последующие запросы будут похожи на предыдущие, т.е. в них будут использоваться один или несколько одинаковых предикатов. В настоящее время прототип LEO корректирует статистику для таблиц (эта статистика может быть устаревшей) и таким образом оценивает селективность отдельных предикатов.

Рис. 1. Отложенное обучение

Как показано на рис. 1, цикл обратной связи LEO состоит из четырех шагов: мониторинга, анализа, обратной связи и использования обратной связи. Во время компиляции запроса компонент мониторинга сохраняет оценки мощности, выведенные оптимизатором для наилучшего (т.е. обладающего наименьшей стоимостью) плана, а во время выполнения запроса сохраняет реальные значения мощности, наблюдаемые для данного плана. Компонент анализа использует эту информацию, обучаясь, тем самым, выявлять ошибки моделирования и вычислять корректирующие поправки. Этот анализ является автономным процессом, который может запускаться отдельно от сервера базы данных и даже на другой системе. Компонент обратной связи изменяет статистику в каталоге базы данных в соответствии с накопленной информацией. Компонент использования закрывает цикл обратной связи, используя информацию из системного каталога, чтобы обеспечить поправки для оценок мощности, полученных оптимизатором запросов.



Эти четыре компонента могут действовать независимо, но они образуют последовательность, составляющую механизм непрерывного обучения за счет инкрементального сбора данных о планах, наблюдения за их исполнением, анализа результатов этих наблюдений и вычисления поправок, которые применяются при компиляции последующих запросов. Этот механизм поддерживает замедленное обучение, поскольку эффект от обратной связи будет ощутим только при выполнении будущих запросов.

Механизм замедленного обучения реализован с использованием DB2 Universal Database (UDB) для платформ Linux, Unix и Windows. Эксперименты с прототипом [18] показали, что мониторинг занимает менее 4% всего времени исполнения запроса, в то время как производительность может увеличиться на несколько порядков, особенно в тех случаях, когда оптимизатор «понимает», что нужно использовать метод массивного соединения, а не метод соединения на основе вложенных циклов, по причине большой мощности входных данных.

Безотлагательное обучение на основе обратной связи. Отслеженные данные о значениях мощности промежуточных результатов можно использовать не только для обработки последующих запросов. Если реальные значения мощности значительно отличаются от их оценок, выбранный план запроса может оказаться весьма неоптимальным. В рамках проекта LEO исследуется, как можно немедленно использовать эти знания путем динамической повторной оптимизации текущего запроса и изменения его плана выполнения, если все строки промежуточного результата материализуются до их использования в какой-либо точке плана.

Как правило, время ответа и память являются оптимизированными, если каждая строка полностью обрабатывается и возвращается пользователю конвейерным образом. Но иногда строки промежуточного результата должны быть полностью материализованы в виде отсортированной или не отсортированной временной таблицы (TEMP). Соответствующую точку QEP мы называем точкой материализации. Наличие таблиц TEMP обеспечивает естественную возможность подсчитать число строк и, возможно, повторно оптимизировать план прежде, чем какая-либо строка будет возвращена пользователю.




Тем самым предотвращается передача пользователю строк-дубликатов, порождаемых при повторной инициации выполнения запроса. Однако здесь возникают два важных вопроса.

  • Поскольку повторная оптимизация требует определенных затрат, то когда она оправдана?
  • Как можно эффективно выполнить повторную оптимизацию?

    Первый из этих вопросов рассматривается ниже. Что касается второго вопроса, самое очевидное решение — просто еще раз выполнить запрос «с самого начала» по новому плану. Однако при этом придется отказаться от всей (возможно, значительной) работы, которая уже была проделана до точки материализации, сохраненной в таблице TEMP. В большинстве случаев для повторно оптимизированного плана было бы предпочтительнее избежать потребности в повторном выполнении этой работы путем использования готовой TEMP в повторно оптимизированном плане.





    Рис. 2. План запроса, который может оптимизироваться динамически
    Так, на рис. 2 показан план запроса для простого соединения двух таблиц, в котором группировка/ агрегация таблицы Orders по столбцу Product_Id выполняется до соединения. Для выполнения сортировки, которая может понадобиться для выполнения этой агрегации, необходимо полностью сформировать все входные данные до начала сортировки; эти данные образуют таблицу TEMP. Поскольку большая часть агрегатных функций может вычисляться в инкрементальном режиме, по мере сортировки строк, в своем окончательном виде TEMP будет содержать результат выполнения раздела GROUP BY. Оптимальный алгоритм соединения (соединение методом вложенных циклов, соединение через хеширование или соединение слиянием) для последующего соединения Orders и Products критически зависит от размера результата GROUP BY. Оптимизатор запросов может выбрать неоптимальный алгоритм слияния при переоценке или недооценке размера этого результата.

    Однако во время выполнения запроса оптимизатор может отслеживать размер результата GROUP BY и повторно оптимизировать при обнаружении серьезных ошибок оценки, например, изменяя при необходимости алгоритм соединения.


    Такая повторная оптимизация усложняется для более сложных планов запросов с несколькими точками материализации. В [12] предлагается оформлять TEMP в виде таблиц и преобразовывать часть плана запроса, оставшуюся после формирования TEMP, в SQL-запрос, который снова передается оптимизатору запросов. К сожалению, у этого подхода имеются два недостатка. Во-первых, может оказаться, что использование таблиц TEMP в том виде, в каком они существуют, не является оптимальным. В тех случаях, когда размер TEMP оказывается намного больше, чем предполагалось, в оптимальном плане может повторно использоваться только часть TEMP, или TEMP может вообще полностью игнорироваться, если в полностью новом плане напрямую используются базовые таблицы. Во-вторых, часть плана, оставшуюся после формирования TEMP, не всегда можно выразить в виде оператора SQL, особенно в этой части содержатся операции обновления, возникающие по причине наличия подзапросов.

    Более хороший подход состоит в том, чтобы не оформлять TEMP в виде таблиц, а определять их как материализованные представления [13] (в DB2 их называют Automatic Summary Table [14]) и предоставлять их определения оптимизатору запросов. Тогда оптимизатор может опираться на стандартные методы проверки соответствия представлений [15] для определения того, какие TEMP стоит использовать повторно. Затраты на повторную оптимизацию с использованием дополнительных материализованных представлений практически идентичны затратам на оптимизацию исходного запроса, поскольку от оптимизатора требуется всего лишь рассмотрение одного альтернативного метода доступа к промежуточной таблице для каждого материализованного представления.

    Более того, если TEMP определяются в виде материализованных представлений, нет оснований ограничивать их использование только текущим запросом. Материализованные TEMP потенциально могут использоваться во всех последующих запросах таким же образом, как в них используются материализованные представления, определенные пользователями.Конечно, этот подход может привести к лавинообразному росту числа таких представлений, поэтому процессор запросов должен периодически удалять редко используемые представления; это сродни проблеме подвыбора материализованных представлений [16].


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