Попытки компиляции. Хорошо известно, что компиляция и раннее связывание - неплохие идеи в тех случаях, где их можно применять. Таким образом, оптимизация во время компиляции предпочтительнее интерпретации, в частности, при выполнении повторяемых запросов, которые обычно составляют большую часть работы базы данных. С другой стороны, оптимизация запросов на основе неполной информации часто порождает планы, которые, при условии множественности их вызовов, оказываются недостаточно качественными. Ахиллесова пята оптимизации запросов - это выборочная оценка; отсутствующие статистические данные, таких как гистограммы и вычисления уникальных значений - постоянная головная боль администраторов баз данных, если СУБД автоматически не создает, не обновляет и не выдает статистические данные должным образом. Другой важный источник ошибок выборочной оценки - это отсутствие в момент компиляции информации о том, какие значения будут иметь параметры в время исполнения. Традиционно, единственным решением в этой ситуации считалась оптимизация времени исполнения. Первые исследования, посвященные динамическим, или адаптивным, планам ставили своей целью решение именно этого вопроса. Основная идея состояло в том, что оптимизированный план запроса содержит, в некотором достаточно компактном виде, различные альтернативные планы исполнения и выбирает из них в момент начала работы или даже в некоторых, тщательно запланированных предварительно точках во время исполнения. Не удивительно, что в таких случаях исполнение примитивов проектировать было относительно просто, в то время как создание эффективных оптимизаторов для динамических планов по прежнему остается в большей степени искусством, нежели наукой, и было бы весьма полезно, если бы из научных исследований оно перешло в практические методики, которые могли помочь преобразовать технологию в продукты. В итоге, динамические планы предназначены для того, чтобы избежать необходимости тратить ресурсы на частую перекомпиляцию и повторную оптимизацию; если усилия, которые тратятся на поиски единого динамического плана столь же велики или даже больше, чем усилия на повторную перекомпиляцию, это не к чему не приведет, разве только может увеличить задержку при выполнении программы.
Методики оценки затрат и динамического исполнения. Несколько менее серьезный источник ошибок при оптимизации запросов - это меняющийся объем доступных ресурсов и, как следствие, неточные вычисления затрат. Например, относительные затраты на навигацию между индексами и записями по сравнению с ориентированными на множества планами запросов, рассчитанных на сортировку или хеширование, зависят от наличия памяти, уровня загрузки процессора, наличия места на диске для хранения постоянных и временных файлов и таблиц и т.д. Для решения задачи оптимизации запросов в условиях изменения количества доступных ресурсов были предложены (хотя и в небольшом количестве) методики, применяющие динамические планы оценки запросов. Однако, вместо использования динамических планов с альтернативными алгоритмами или формы альтернативных планов, намного чаще готовности ресурсов отдается на откуп конкретным алгоритмам. В итоге, существует множество предложений и книг, касающихся работы с ресурсами в пределах одного оператора или алгоритма, в частности, с ресурсами памяти, например, гибридное хеширование-соединение (hybrid hash join), динамическое вытеснение (dynamic destaging), оптимизация слияния при внешней сортировке-слиянии (merge optimizations in external merge sort) и т.д. Интересный алгоритм для обработки определяемых данными соединений в параллельных и распределенных системах с большим объемом памяти - это симметричное хеширование-соединение, использующее две хеш-таблицы. В то же время вопросу управления памятью между несколькими операторами, во вложенных запросах или в динамических планах запросов, посвящено всего несколько статей. В современных коммерческих механизмах выполнения запросов применяется множество адаптивных методик, не только в пределах одного оператора, но и между операторами в одном запросе и между несколькими одновременно выполняемыми запросами. Примером тому является определение или настройка степени параллелизма в зависимости от текущей нагрузки, переупорядочивание и соединение диапазонов для оптимизации повторяющегося поиска в индексе, совместное сканирование в рамках нескольких запросов и пользовательских соединений, игнорирование упреждающих выборок, если большинство из них - это обращения к буферу и, как следствие, не имеют смысла, «выбрасывание» разбиения хеш-таблицы и пересортировка для алгоритмов на базе циклов или слияний, когда разбиение не эффективно (например, из-за дублирования значений ключа), и тому подобное. Несмотря на столь широкий диапазон возможностей, все эти адаптивные методики обычно игнорируются в функциях затрат коммерческих оптимизаторов запросов, частично потому, что их трудно интегрировать, а частично потому, что действительно серьезных причин для их интеграции еще не было. Это говорит о таких адаптивных методиках, как динамические планы оценки запросов.
Вложенная итерация. Хотя большинство вопросов, связанных с ресурсами, оказывают довольно незначительное влияние на выбор оптимального плана (даже если они влияют на выбор между различными планами примерно одинаковой стоимости), есть один вопрос, который имеет критически важное значение для практики, но, как правило, игнорируется в научном исследовании - это эффект промаха и попадания в буфер в сложных планах запросов. В частности, вложенные запросы SQL, а также вложенная итерация как оператор в алгебре логических и физических запросов, обычно в исследованиях пропускается. Интересные вопросы возникают, если множественные вызовы одного и того же вложенного вычисления затрагивают друг друга, например, первый вызов готовит буфер ввода/вывода для последующих вызовов. Другие интересные вопросы появляются, если различные вложенные вычисления претендуют на одни и те же ресурсы, например, буфер ввода/вывода или память для выполнения операций сортировки или хеширования в рамках внутренних запросов. Вложенные вычисления имеют важное значение на практике, во-первых, поскольку запросы создаются с использование вложенных запросов SQL, а, во-вторых, потому что вложенная итерация, основанная на навигации между индексами, - это зачастую самый лучший план исполнения. Таким образом, вложенные вычисления могут оказаться весьма плодотворной темой для исследований, как с точки зрения исполнения, так и с точки зрения оптимизации, и могла бы дать более динамичные и адаптивные методики, чем используемые сейчас. Однако при этом потребуется концептуальная модель вложенных запросов, которая была бы значительно проще, чем вложенный SQL, например, модель на основе алгебраических выражений с таблицей параметрических значений.
Индексные представления. Вероятно, самой интересной из последних разработок в области обработки запросов к базе данных стало коммерческое использование материализованных представлений. В известном смысле материализованные представления развивают концепцию ранних связей еще больше, чем оптимизация времени компиляции. Преимущества могут оказаться огромными, по мере того, как с каждым днем появляется все больше приложений и инструментальных средств оперативной аналитической обработки, время ответа которых составляет меньше секунды даже для детализированных данных большого объема. В результате, в тех случаях, когда материализованные представления действительно работают эффективно, обработка сложных запросов сводится к навигации в индексе, что весьма напоминает оперативную обработку транзакций (OLTP — online transaction processing), за исключением различий в изменении нагрузки. Сложные методики для больших запросов, например, совместное сканирование (shared scan), битовые карты (bitmap index), хеширование-соединение (hash join), и параллельная обработка запросов, могут в один прекрасный день потерять актуальность, поскольку они применялись в тех случаях, когда базы данных использовались только для бизнес-операций (OLTP), а не для анализа данных и интеллектуальных систем поддержки бизнеса. Существует множество вопросов, касающихся создания избыточных индексов на материализованных представлениях, а также согласованности, обновлений, недостоверности (invalidation), повторных вычислений, пошаговых обновлений и т.д.; вероятно самая простая стратегия (безусловно, с точки зрения разработчиков приложений и конечных пользователей) - это трактовать итоговые материализованные представления как индексы, принимая во внимание постоянные обновления внутри исходных транзакций, или даже просто как индексные представления в дополнение к таблицам, поддерживая как не кластеризованные, так и кластеризованные индексы (последние содержат все столбцы в таблице или представлении). В этом случае семантика представлений не меняется, будь они материализованные и индексированные или нет; таким образом, индексация представления - это фактически вопрос, относящийся исключительно к проектированию физической базы данных и к производительности, а не к проектированию логической базы данных и корректности.
Кэширование последних запросов. Еще одна интересная технология, которая только начинает применяться, тесно связана с материализованными представлениями: кэширование результатов последних запросов в порядке их использования в будущих запросах. Действительно, некоторый инструментальные средства OLAP добиваются поразительно высокой производительности за счет использования этой методики, в частности, если они применяются и на сервере, и на настольной системе, т. е. и для локальных, и для распределенных запросов. Вопросы, касающиеся индексации, а также недостоверности или пошаговой поддержки такие же, как для материализованных (или индексированных) представлений. Самое сложное, как и в случае с материализованными представлениями, - это правила, определяющие, какие результаты запросов сохранить и поддерживать и в течение какого времени.
Параметры производительности. Цель индексирования и кэширования результатов состоит в увеличении производительности системы. Однако существуют разные определения производительности. Прекрасную иллюстрацию тому дает анализ дискуссии о том, должна ли общая производительность в тестах TPC-D базироваться на арифметических или геометрических значениях времени отдельных запросов. Например, лучше сократить время обработки одного запроса с 10 до 1 секунды (т. е. на 9 секунд или в 10 раз) или увеличить производительность при обработке другого запроса, сократив время с 10 минут до 5 (т. е. на 300 секунд, но всего в 2 раза)? Более важной целью, чем высокая производительность, однако, является согласованная и предсказуемая производительность. Подавляющее большинство выпускаемых сейчас серверов баз данных оснащается процессорами, которые намного медленнее самых производительных из современных процессоров, порой в два раза. С учетом этого, сама по себе производительность не является основным приоритетом; если бы производительность была бы приоритетной, то намного быстрее эту цель можно было достичь путем замены процессора. Другими словами, предпочтение (в разумной степени) отдается решениям, которые обеспечивают не самую высокую производительность, а самую предсказуемую.
Предсказуемая производительность. Предсказуемая производительность имеет несколько аспектов. В частности, выполнение одного и того же запроса или очень похожего запроса всегда требует одного и того же времени. Например, если некоторый запрос вместо обычных для него пяти минут стал выполняться за две, то у пользователя мгновенно возникает раздражение (и это служит поводом для обращения в службу поддержки). Из этого наблюдения можно сделать следующий вывод: на самом деле, параллельная обработка запросов может оказаться очень плохой идеей, поскольку может не оправдать ожиданий. Другой аспект предсказуемости состоит в том, что «обычный» человек должен иметь возможность предсказать производительность. Другими словами, сложные адаптивные методики, из-за которых выполнение выбранного динамического плана запроса трудно предсказать или понять, для разработчиков и пользователей - плохая услуга, если только эти адаптивные методики не работают настолько хорошо, что разработчикам и пользователям никогда не захочется поинтересоваться, каковы эти планы запросов, как не приходит им в голову сейчас разбираться как работает виртуальная память.
Настройка индексов. Некоторые производители баз данных предлагают (или включают в состав своих основных продуктов) инструментальные средства для настройки индексов, в том числе материализованных представлений и их индексов. Эти инструментальные средства выполняют сложный анализ рабочей нагрузки и могут создавать индексы, а также удалять индексы из-за слишком высоких затрат на их обновление или из-за ограничений по памяти. Очевидно, что современные версии этих инструментальных средств не совершенны, в частности в том, что касается затрат на анализ и оперативность, т. е., насколько быстро они адаптируют физическую структуру баз данных к первоначальной рабочей нагрузке и к изменениям в рабочей нагрузке. Более того, большинство этих инструментальных средств создаются в предположении, что настройка базы данных - это деятельность, которая отделена от обработки запросов, требует обучения персонала, в частности, администратора базы данных, и предполагает использование значительных системных ресурсов, например, для анализа планов запросов для различных предлагаемых конфигураций индексов. Из-за высоких накладных расходов на вычисления, они, как правило, не допускают автоматизации.
Эвристики настройки индексов. Оказывается, однако, что достаточно простые схемы индексации часто работают весьма неплохо. Например, кластеризованные индексы на первичных ключах и некластеризованные индексы на внешних ключах - достаточно неплохое решение для начала. Поскольку некластеризованные индексы редко меняются и играют важную роль во многих приложениях, они часто помогают при работе со всеми столбцами с типами данных «date» или «time». Наконец, для столбцов, которые встречаются в предикатах «=», скорее всего полезными окажутся индексы, которые могли бы содержать индексы первичных и внешних ключей, если они уже не индексированы. Индексы на предикатах «in», а также предикаты выбора «between» обычно тоже дают результат. Чтобы усовершенствовать эти правила можно добавить первичный ключ и все внешние ключи ко всем индексам, что ускоряет навигацию между индексами. Наконец, можно отказаться от использования всех некластеризованных индексов в очень маленьких таблицах, скажем, по размеру меньше страницы, так, чтобы на индексы не тратилось больше памяти, чем на основные данные.
Запросы, создающие индексы. Благодаря таким простыми правилам индексирования, многие наборы запросов, например, TPC-D, работают достаточно неплохо (разумеется для процессоров запросов, поддерживающих пересечение индексов) - конечно, по-прежнему лишь вдвое быстрее, чего и хотят добиться многие пользователи, при этом не приобретая последние версии аппаратного обеспечения. Возникает интересный вопрос: могут ли эти индексы создаваться быстро и незаметно. Например, если выясняется, что предикат равенства не поддерживается существующим индексом, как его можно построить с минимальными накладными расходами? Создание отдельного индекса должно происходить легко, например, он не должен «захватывать» процессор или диск, и не должен мешать другим, одновременно работающим пользователям. Другими словами, интерактивное создание индекса столь же важная возможность для полностью автоматизированных «низкоуровневых» систем управления базами данных, как и для систем старшего класса, работающих круглосуточно, семь дней в неделю, которые стремятся к уровню «пяти девяток» или даже выше (готовность 99.999% , или 5 минут простоя в год, включая запланированное время отключения). Если, с другой стороны, предикат равенства при отсутствии подходящего индекса заставит систему выполнять полное сканирование, можно ли создать адаптивные планы, которые сканируют, сортируют, объединяют и оставляют соответствующий индекс для последующего использования? Может ли этот механизм по-прежнему работать, даже если есть одновременные модернизации, которые этот индекс должен отражать, а результаты запроса не должны? Может новый индекс полностью использоваться, когда тот же запрос выполняется снова, без перекомпиляции и повторной оптимизации с помощью динамического плана запроса, который использует индекс, если он существует, или создает его, если он не существует?
Эвристики для индексированных представлений. Хотя достаточно очевидные и простые правила могут дать удовлетворительные результаты для индексов в таблицах, это не аргумент в пользу материализованных (индексированных) представлений. Как в литературе, так и в реальных продуктах существует несколько очень эффективных алгоритмов и эвристик для предварительных объединений, но многие запросы, используемые в анализе данных, в частности, с учетом размеров и иерархии, могут извлекать пользу не только из предварительных объединений, но и из соединений, вложенных запросов, полусоединений (semi join), операций присваивания и т.д. Абсолютно простые и эффективные эвристики и их интеграция в обработку запросов могут существенно повысить эффективность использования систем управления базами данных, в частности РСУБД, при анализе и добыче данных.
Исследование о порядке величины. Наконец, небольшое предупреждение. Программные методики, ориентированные на производительность или пропускную способность, в результате применения которых производительность повышается на несколько процентов, могут оказаться весьма важными для производителя, стремящегося во что бы то ни стало показать высокий результат в тестах, но для исследований это плохая цель и плохой результат. Увеличение в небольшое число раз (скажем в три) достойно похвалы и полезно, но его никак нельзя назвать кардинальным - улучшения в аппаратной технологии дадут нам тот же эффект (достаточно предсказуемо!) в ближайшие год - два, т. е. за время, которое требуется для публикации статьи в журнале о новой программной методике или для реализации ее в конкретном продукте. Типичный пример такого увеличения производительности в небольшое число раз - это исследования алгоритмов, использующих кэш-память процессора, обычно за счет адаптации методик, доказавших свою состоятельность для дисков и дисковых страниц, например, B-деревья, внешняя сортировка, а также горизонтальное и вертикальное разбиение. Чтобы улучшение можно было назвать действительно кардинальным, производительность должна вырасти на порядок величины. Материализованные представления - одна из таких методик. Динамические планы запросов, с другой стороны, и близко не обеспечивают такого уровня в широком масштабе. Можно ли этого добиться? Можем ли мы добиться согласованного и предсказуемого увеличения производительности на несколько порядков для реляционных и постреляционных систем управления базами данных за счет комбинации динамических планов запросов и выполняемым «на лету» индексированием и материализованными представлениями?
Об авторе
Гетц Грифе — сотрудник подразделения SQL Server Development корпорации Microsoft. С ним можно связаться по электронной почте по адресу: goetzg@microsoft.com
Copyright 2000 IEEE. Bulletin of the Technical Committee on Data Engineering, June 2000, Vol. 23, No. 2, IEEE Computer Society. Goetz Graefe, Dynamic Query Evaluation Plans: Some course corrections?
