Оценочная оптимизация для магии: алгебра и реализация

Правин Сешарди (Praveen Seshadri, Univ. of Wisconsin, Madison)
Джозеф Хеллерстейн (Joseph M. Hellerstein, Univ. of California, Berkeley)
Хамид Пирамеш (Hamid Pirahesh, IBM Almaden Research Ctr.)
Клифф Леюнг (T. Y. Cliff Leung, IBM Santa Teresa Lab.)
Раджу Рамакришнан (Raghu Ramakrishnan, Univ. of Wisconsin, Madison)
Дивеш Сривастава (Divesh Srivastava, AT&T Research)
Питер Стюки (Peter J. Stuckey, Univ. of Melbourne)
С. Сударшан (S. Sudarshan, IIT, Bombay)
SIGMOD Conference 1996: 435-446

Перевод: Сергей Кузнецов

Назад Содержание Вперёд

6. Измерение производительности

Цели нашего изучения производительности состояли в следующем: (1) Показать, что для магической перезаписи существуют различные варианты выбора SIPS, и что никакой конкретный вариант выбора SIPS не является оптимальным для всех запросов и сред выполнения. (2) Показать, что оценочная магическая оптимизация обеспечивает выбор, близкий к оптимальному, для различных запросов и сред выполнения. (3) Показать, что дополнительные накладные расходы, порождаемые оценочной магической оптимизацией, не влияют на порядок сложности процесса оптимизации.

К сожалению, нет «стандартного» тестового набора для оценивания методов, подобных перезаписи на основе магических множеств. Взамен нам пришлось изобретать для этой цели экспериментальную методологию. Выбираемые нами эксперименты должны были быть относительно простыми для понимания и разъяснения. Более того, мы должны были смочь исследовать различные измерения перезаписи на основе магических множеств за небольшое число экспериментов. В следующем разделе описывается наша попытка изобретения такой методологии.

6.1 Экспериментальная методология

Тестовый набор TPC-D является общеотраслевым стандартным тестовым набором для сложных запросов [TPCD94]. В тестовом наборе имеются два запроса, к которым может быть применена перезапись на основе магических множеств (Query 2 и Query 17). Нас интересовал Query 2, потому что для него имеется большое число вариантов магической перезаписи (он включает соединение многих отношений), в то время как для другого кандидата (Query 17) имеется только один вариант.

В первом эксперименте стартовой точкой является Query 2 из TPC-D. Во внешнем блоке запроса предикаты выборки постепенно изменялись путем их удаления, модификации с целью уменьшения селективности или замены на менее селективные предикаты. Эффект состоял в том, что мощность результата запроса постепенно увеличивалась. Однако реальные таблицы в запросе не изменялись, так что всегда был возможен выбор одних и тех же вариантов SIPS. По мере изменения предикатов разные варианты выбора SIPS становятся оптимальными, и иногда бывает лучше вообще не производить магическую перезапись. Мощность результата запроса грубо связана с возможным эффектом фильтрации вследствие магических множеств; следовательно, мы ожидаем большей пользы от перезаписи на основе магических множеств при меньшей мощности результата. Оптимизатор, усовершенствованный оценочной магической оптимизацией, должен всегда выбирать правильные SIPS для всех запросов.

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

Эксперименты производились на рабочей станции IBM RS/6000, подключенной к двум дискам. База данных TPC­D объемом в 100 Мб (т.е. с коэффициентом масштабирования 0.1 в соответствии со стандартом TPC­D) была сгенерирована со всеми уместными индексами. На оси X графиков результатов отмечены варианты запросов, упорядоченные по возрастанию размера результата. В качестве основной метрики производительности использовалось время выполнения запроса. Заметим, что в графиках времени выполнения используется логарифмическая шкала, так что кажущиеся небольшими различия в действительности достаточно значительны. Мы также измеряли время компиляции запроса, чтобы показать накладные расходы на дополнительную работу оптимизатора. Все временные показатели единообразно масштабированы поправочным множителем.

6.2 Сравниваемые алгоритмы

В своих экспериментах мы сравнивали следующие алгоритмы: отсутствие перезаписи на основе магических множеств (nomag), оценочная оптимизация на основе Filter­joins (magopt) и некоторые возможные «выбранные вручную» предопределенные варианты перезаписи на основе магических множеств (mag1, mag2, mag3, mag4, mag5). Предопределенные варианты представляют некоторые осмысленные варианты выбора SIPS. Для каждого запроса алгоритм magopt должен в оценочной манере выбрать наилучшую SIPS или принять решение о невыполнении перезаписи.

В разд. 2.1 упоминался эвристический подход, изначально предложенный в Starburst [MP94]. При использовании этого подхода запросы сначала оптимизируются без какого-либо использования перезаписи на основе магических множеств, и из результирующего порядка соединений выводятся SIPS. Недостаток этого подхода состоит в том, что при оценивании нигде не вычисляется истинная стоимость магической перезаписи. Путем изучения планов, генерируемых оптимизатором при отсутствии перезаписи на основе магических множеств (nomag), мы cмогли вручную реконструировать поведение подхода Starburst. Мы называем этот алгоритм sbmag.

Рис. 5. Общее сравнение

6.3 Общие результаты

Графики на рис. 5 показывают общие результаты измерения производительности. Оптимизация путем магической перезаписи на основе Filter­join (т.е. magopt) может сильно повысить скорость выполнения запросов по сравнению с nomag. Так происходит при небольших размерах результата, поскольку в этом случае и фильтрующее множество является небольшим и достаточно селективным. Это позволяет ограничить вычисление сложного представления и тем самым сократить время выполнения. Однако, если размер фильтрующего множества возрастает, его преимущества медленно уменьшаются, а стоимость растет, так что в последней точке графика (размер 11986) алгоритм перестает выполнять перезапись на основе магических множеств. Это объясняет, почему в последней точке значения времени одинаковы для nomag и magopt. Алгоритм sbmag хорошо работает для более крупных запросов, на с двумя наиболее мелкими запросами справляется плохо. Чтобы понять причины такого поведения sbmag, обратим внимание на тот факт, что оптимизатор трактует сложное представление как временное отношение без индексов. Если другие соединения в запросе очень селективны, и другие отношения проиндексированы, то в наиболее дешевом плане представление часто ставится в начало порядка соединений. Основываясь на этом плане, sbmag принимает решение не использовать магические множества. Однако это именно те запросы, для которых можно ожидать наибольшей пользы от магии!

Интересный предмет для обсуждения представляет четвертый запрос (размер 236) на рис. 5. Мы видим, что производительность magopt слегка хуже, чем у nomag. Очевидно, что оптимизатор, выбирая для magopt магическую перезапись, ожидал, что результат будет лучше, чем у nomag. Это показывает, что оценки стоимости, принимаемые оптимизатором, отличаются от реальной стоимости из-за неточных статистики и/или предположений. Алгоритмы, подобные оценочной магической оптимизации, построенные поверх этих ошибок, могут время от времени могут приводить к неоптимальной производительности.

Рис. 6. Варианты перезаписи на основе магических множеств

6.4 Фиксированные варианты SIPS

Диаграмма на рис. 6 показывает эффективность различных фиксированных вариантов SIPS для перезаписи на основе магических множеств. При существующем состоянии дел требуется, что пользователь базы данных выбрал один такой вариант для каждого запроса. Как показывает диаграмма, наилучшие варианты существенно отличаются для разных запросов, хотя единственным реальным различием между запросами являются предикаты на соответствующих таблицах. Сравнение диаграмм на рис. 5 и 6 показывает, что для каждого запроса выбор magopt близок к наилучшему варианту; алгоритм формирует нижнюю огибающую доступных вариантов. В этом состоит отдельный важный результат данной статьи; он мотивирует нашу работу и демонстрирует успех нашего подхода.

Рис. 7. Общее время компиляции

6.5 Результаты времени компиляции

На диаграмме на рис. 7 показано общее время компиляции (перезапись + оптимизация) при использовании magopt и nomag. Это время включает второй проход оптимизатора, выполняемый при выборе перезаписи на основе магических множеств (заметим, что в данном случае используется линейная, а не логарифмическая шкала). Для более мелких запросов выбирается перезапись на основе магических множеств, и поэтому время компиляции для magopt почти вдвое больше времени для nomag. Эти накладные расходы представляются нам приемлемыми, поскольку для запросов поддержки принятия решений время компиляции обычно мало по сравнению со временем выполнения.

Рис. 8. Исходные накладные расходы оптимизации

Для более крупных запросов перезапись на основе магических множеств не выбирается и поэтому второй проход оптимизатора отсутствует. Как показывает диаграмма, имеются очень небольшие накладные расходы на анализ целесообразности перезаписи. Это важно в тех случаях, когда накладные расходы на оптимизацию являются существенными. Диаграмма на рис. 8 показывает это более отчетливо; на ней изображено время, затраченное в первом проходе оптимизации, когда magopt анализирует возможность применения Filter­join. Хотя magopt анализирует большее число планом, в число которых входят планы, включающие Filter­join, затрачиваемое на это время не очень велико. Этот результат подтверждает наше утверждение о том, что оценочная магическая оптимизация не изменяет порядок сложности оптимизации запросов.

6.6 Вариации экспериментов

В отдельных экспериментах мы изменяли сложное представление, чтобы оно становилось более дорогим, и повторяли все экспериментальные вариации внешнего блока запроса. Испытывалась также пара вариаций среды выполнения (путем ликвидации некоторых индексов). Результаты оказались очень похожими на приведенные выше, изменялись только абсолютные числа, а не их относительное расположение. По причине ограниченности объема статьи мы не приводим диаграммы результатов. Во всех экспериментах magopt производил выбор, близкий к оптимальному. На основе этого исследования мы заключаем, что метод оптимизации, базирующийся на Filter­join, является стабильным; его успех не зависит от природы сложного представления, природы блока запроса, в котором используется это представление, а также от наличия индексов.

Назад Содержание Вперёд