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

       

Проблемы самонастраивающейся оптимизации запросов


При создании первого прототипа LEO выявилось несколько серьезных исследовательских проблем, решение которых требуется для какого-либо практического применения оптимизатора в коммерческом продукте. Обсудим эти проблемы и возможные подходы к их решению.

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

Предположение о независимости предикатов в то время, когда в действительности между данными имеется корреляция, как правило, приводит к заниженным оценкам мощности промежуточных результатов, используемых оптимизатором для определения стоимости QEP. Такая недооценка вынудит оптимизатор предпочесть план, основанный на недостоверных знаниях, плану, опирающемуся на надежные факты. Недооценка мощностей может привести к полному анализу пространства поиска; система будет принимать решение только после выбора и изучения всех QEP, содержащих заниженные оценки. Однако завышенные оценки могут привести к локальному минимуму (т.е. к неоптимальному QEP); оптимизатор предпочтет другие QEP плану с завышенными оценками. Поэтому завышенные оценки вряд ли удастся обнаружить и скорректировать.

Чтобы достичь разумного уровня стабильности, самонастраивающимуся оптимизатору следует, например, прежде чем приступать к производству, сначала использовать исследовательский режим. В начале в этом будет иметься больший уровень риска выбора многообещающих QEP на основе недостоверных знаний. Это даст возможность проверить достоверность модели и собрать надежные факты о распределении данных и рабочей нагрузке. Во втором, операционном режиме выбор QEP будет основываться на опыте.
В этом режиме QEP, основанные на надежных фактах, предпочитаются перед более дешевыми QEP, опирающимися на недостоверные знания. По-видимому, переход от одного режима к другому должен быть постепенным, напоминающим методы моделируемой сходимости [17] в машинном обучении.

Для преодоления локального оптимума, вызванного завышенными оценками, необходимо исследовать недостоверные знания, используемые для вероятно неоптимальных, но многообещающих QEP, например, путем синхронного или асинхронного взятия образцов [10].

Выявление и использование корреляции. В практических приложениях между данными часто имеется корреляция. Например, в базе данных автомобилей селективность конъюнкции (make = «Honda» and model = «Accord») не равна произведению селективностей предикатов make = «Honda» и model = «Accord», поскольку между столбцами make и model имеется корреляция — только Honda выпускает модель Accord. Поскольку наличие корреляции нарушает предположение о независимости, в современных оптимизаторах оценки селективности для предикатов, в которых присутствует корреляция, могут отличаться от реальных значений на несколько порядков. Наш подход обеспечивает возможность выявлять и исправлять такие ошибки.

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


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

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

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


Или же можно усовершенствовать оптимизатор таким образом, чтобы он предсказывал не только оптимальный план, но и также и тот диапазон селективности каждого предиката, внутри которого план является оптимальным. Предсказывать «чувствительность» любого плана по отношению к одному произвольному параметру исключительно сложно, поскольку в модели оценок имеются нелинейности.

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

Изучение иной информации. Обучение и адаптация к динамической среде не ограничиваются мощностью и селективностью. При использовании цикла обратной связи может быть обеспечена самопроверка достоверности значений стоимости и других параметров, оцениваемых в настоящее время оптимизатором. Например, основной аспект стоимости, число физических операций ввода/вывода, которое сейчас оценивается вероятностным образом на основе оцененного процента удач в предположении, что каждому приложению доступна часть пула буферов одного и того же размера. Оптимизатор мог бы проверить для данного плана достоверность этих оценок путем слежения за реальным вводом/выводом, реальным процентом удач и реальным числом операций доступа к таблицам. Другим примером является максимальный объем памяти, выделяемый для выполнения в плане конкретной сортировки в плане. Если бы СУБД определила с помощью обратной связи запроса, что операция сортировки не может быть выполнена в основной памяти, она могла бы отрегулировать размер «кучи», предназначенной для сортировки, чтобы избежать внешней сортировки при выполнении таких последующих операций.

Обратная связь не ограничивается службами и ресурсами, потребляемыми СУБД, а распространяется также и на приложения, обслуживаемые СУБД. Например, СУБД могла бы измерить, сколько строк из результата запроса действительно потребляется каждым приложением, и оптимизировать производительность каждого запроса именно для этой части результата путем, например, явного добавления к данному запросу раздела OPTIMIZE FOR <n> ROWS.Подобным образом, обратная связь при выполнении могла бы использоваться для автоматической установки многих устанавливаемых в настоящее время вручную конфигурационных параметров совместно используемых ресурсов. Физические параметры, такие как скорость сети, время доступа к диску и скорость обмена данными с диском, используются для определения веса вклада этих ресурсов в стоимость плана и обычно считаются постоянными после первоначальной настройки. Однако установка этих параметров на основе измеренных значений является более саморегулируемой и более точно фиксирует реальную скорость. Аналогичным образом, распределение памяти между различными буферными пулами, общий размер «кучи» для сортировки и так далее могут настраиваться автоматически с учетом процента удач, наблюдавшегося за последнее время.


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