Стоимостные оптимизаторы для СУБД: вчера и сегодня

В классических реляционных СУБД порядок выполнения запроса выбирает сама система, и возникает задача оптимизации требуемых ресурсов, которая решается путем анализа стоимости выполнения каждого этапа запроса. В каждом конкретном случае под стоимостью понимаются затраты ресурсов (время, емкость системы хранения и т. п.), необходимых для выполнения запроса. Понятие стоимости со временем может меняться, но в любом случае чем меньше ее величина, тем лучше. Оптимизаторы запросов для реляционных СУБД начинали со следования простому набору правил, а сегодня превратились в умный, но весьма сложный организм. За десятилетия развития оптимизаторов запросов, кажется, была принята во внимание каждая мелочь — современные оптимизаторы учитывают десятки статистик (количество строк, блоков данных и т. д.); используют гистограммы, позволяющие понять объемы данных и даже их семантику; на лету собирают статистику и корректируют план оптимизации; переписывают запросы (результат выполнения запроса тот же, но меняется его форма и улучшается его декларативность) и т. п. Разработки новых игроков на рынке СУБД не обладают всеми этими возможностями и при прочих равных проигрывают старожилам, но, может быть, для NoSQL или поколоночных баз данных [1] оптимизация уже не так важна?

Рассмотрим работу СУБД, проанализировав диаграммы планов выполнения [2] оптимизаторов — графическое представление процесса выбора оптимизатором стратегии обработки запроса, например, в зависимости от размера таблиц запроса. План выполнения — это последовательность операций, необходимых для обработки запроса. Разные последовательности образуют разные планы выполнения, так же как и при вычислениях в арифметике: если, например, нужно при устном счете перемножить 97*8*0,125, то план 97*(8*0,125) будет лучше, чем (97*8)*0,125, — результат тот же, а вычислительная сложность разная.

Рис. 1. Пример диаграммы плана выполнения седьмого запроса теста TPC-H

Если каждому плану выполнения запроса сопоставить свой цвет и нанести на плоскость, то получится диаграмма (рис. 1), по осям которой в условных единицах отложены размеры таблиц — например, заказы (ORDERS) и клиенты (CUSTOMERS) седьмого запроса теста TPC-H (определение стоимости товаров, отгруженных в течение года между разными странами). Как видно из рис. 1, из всего пространства поиска оптимизатор выбрал шесть планов, два из которых — вырожденные. Если планы образуют плавные равномерно окрашенные области, которые не имеют резких переходов и не связанных друг с другом частей, то при выполнении таких запросов поведение оптимизатора легко предсказуемо: с точки зрения пользователя, СУБД работает стабильно с гарантированной производительностью. Однако такая идиллия возможна только для простых запросов, как на рис. 1, где имеется всего шесть таблиц, нет вложенных подзапросов, операторов ALL и ANY. На практике для сложных и комплексных запросов, включающих десятки таблиц, множество предикатов, представляющих собой сложные неравенства с вложенностью, исчисляемой не единицами, а десятками, диаграммы совсем иные (рис. 2).

Рис. 2. Типичная диаграмма плана выполнения для сложного запроса (восьмой запрос теста TPC-H)

Для выполнения запроса восьмого теста TPC-H — изменение доли рынка заданного государства внутри заданного региона (для поставщиков, suppliers) в течение двух лет для заданной номенклатуры (lineitem) — потребовалось 68 планов. И хотя большинство из них достаточно экзотичны, такое разнообразие значительно усложняет понимание причинно-следственных связей на фоне того, что рост объемов данных влияет на планы выполнения запросов. Без такого понимания оптимизатор представляется черным ящиком, который при изменении лишь некоторых данных в таблице вдруг бессистемно и беспорядочно меняет план выполнения запроса, а администратору поведение СУБД кажется случайным и хаотическим. Этому есть простое объяснение: сложная программа реализации оптимизатора учитывает множество факторов, а сложные системы обычно очень зависимы от первоначальных условий и небольшие изменения в окружении могут привести к непредсказуемым последствиям. Порой при изменении лишь 1% данных таблицы план выполнения запроса изменяется несколько раз подряд, и, чтобы понять, почему это происходит, требуется провести длительный и кропотливый анализ работы оптимизатора с целью устранения его ошибок. Ситуация усугубляется тем, что такие ошибки мультипликативны. Предположим, в начале расчета стоимости произошла ошибка и выборку вместо трех строк оптимизатор оценил в две. Но теперь ошибка будет повторяться и далее, и на втором шаге выборка будет оценена не в 30, а в 20 строк и т. д. При большом количестве таблиц в запросе даже малые ошибки могут в итоге приводить к заметному снижению производительности и точности выполнения запроса. Случается, что небольшие изменения размеров таблиц для запроса приводят к тому, что оптимизатор делает неверные оценки, вследствие мультипликативности ошибок время выполнения запроса вырастает в разы и администратору приходится с этим разбираться — ни разработчик СУБД, ни пользователь базы понять причины происходящего не в состоянии, однако замедление, казалось бы, на ровном месте может грозить бизнесу серьезными потерями.

Но, может быть, в мире Больших Данных с его СУБД нового поколения ситуация лучше? Проанализируем приемы и подходы к выбору планов выполнения запросов двух характерных представителей мира Больших Данных — поколоночной СУБД Vertica с оптимизатором V2Opt и фреймворка SparkSQL из стека Hadoop с оптимизатором Catalyst.

Ключевое понятие Vertica — проекция, или оптимизированная коллекция колонок таблицы, ближайшим аналогом которой в классических СУБД являются материализованные представления, позволяющие многократно ускорить выполнение запросов. Однако слабое место материализованных представлений — синхронизация данных, тогда как в Vertica проекция всегда синхронизируется автоматически, прозрачно для администратора системы и, что самое важное, может быть отсортирована в нужном порядке. Таким образом, данные хранятся уже не «в куче», а в упорядоченном виде или во множестве видов — проекций на одну таблицу может быть несколько. Таблица в Vertica представляет собой метаописание, а данные образуют ту же проекцию, но называемую «суперпроекцией». Она обладает теми же свойствами, что и обычные проекции: хранится в упорядоченном виде, для нее явно задано, как данные будут распределены по узлам базы, а для отдельных столбцов указан способ их упаковки. Все проекции образуют физическое хранилище в Vertica, где больше нет других структур данных: ни традиционных таблиц, ни индексов, ни материализованных представлений. Оптимизация осуществляется за счет использования нужных проекций: если данные уже подготовлены и лежат в нужном виде на узле, то их соединение или фильтрация выполняются быстро.

СУБД Vertica ориентирована на использование массового параллелизма при выполнении «тяжелых» аналитических запросов над огромными массивами данных. Для таких задач применяются крупные кластеры, и главное здесь — правильно загрузить ресурсы всего кластера, а не его отдельного сервера. В больших кластерах важно не столько оптимизировать работу систем хранения, сколько наладить сетевой обмен данными и исключить избыточную пересылку промежуточных результатов между узлами. Этим процессом можно управлять еще на этапе проектирования базы данных, указывая, как будут распределены данные проекций между узлами кластера. Предположим, что требуется соединить большую таблицу фактов со справочником по внешнему ключу, тогда можно указать, что копия данных справочника будет храниться на каждом узле кластера, поэтому операция соединения будет выполнена одновременно на всех узлах кластера без пересылок промежуточных данных. Предположим теперь, что две большие таблицы фактов надо соединять по внешнему ключу. Для такого запроса можно создать проекции этих двух таблиц с одинаковым распределением данных по узлам на основе ключа соединения. Операция соединения будет выполнена одновременно на всех узлах кластера без пересылок промежуточных данных по сети. Задача оптимизатора в этом случае сводится к анализу списка проекций и выбору подходящей пары для выполнения операции. Разница в эффективности использования подходящей проекции здесь столь очевидна, что ее выбор становится возможным на основе правил, без анализа стоимости.

В оптимизаторе Vertica V2Opt [3] широко используются правила, или эвристики. Процесс оптимизации начинается с выбора списка проекций, причем количество вариантов выбора растет экспоненциально с ростом количества таблиц и проекций для них. Поэтому для сокращения пространства поиска все проекции разбиваются на «удачные» и «неудачные». Например, каждая таблица в запросе имеет набор физических характеристик: список столбцов, требуемый порядок сортировки и т. д. Для каждой физической характеристики определяется самая «дешевая» проекция (проекция, отсортированная в нужном виде, будет дешевле всех прочих для характеристики «способ сортировки»), которая и будет в дальнейшем рассматриваться оптимизатором. Далее наборы проекций сокращенного пространства поиска перебираются для выбора наилучшего варианта. Если в классических СУБД, как правило, один набор таблиц и требуется найти для них оптимальную стоимость, то в Vertica наборов таблиц множество и требуется найти в первую очередь оптимальный набор проекций. Для каждого набора проекций опять применяется широкий набор эвристик с целью сокращения пространства поиска и скорейшего расчета его лучшей стоимости. Для этого на этапе выбора порядка соединения проекции эвристически упорядочиваются исходя из размера таблиц и способа соединения. Для каждой таблицы определяется ее категория (большие таблицы, средние и маленькие), и порядок соединения фиксируется по старшинству категории — выполнение запроса всегда начинается с самой «тяжелой» таблицы, затем идут таблицы среднего размера, а затем — маленькие. Стоимость здесь учитывается только при выборе порядка соединения для таблиц с одинаковыми номерами категории. Глобально для выбора наилучшего варианта оптимизатор V2Opt анализирует стоимости наборов проекций, а для каждого набора выполняются уже локальные оптимизации с целью выбора порядка соединений отдельных пар проекций.

При увеличении числа машин кластера происходят качественные изменения. В кластере из 1000 машин естественна ситуация, когда какая-то из машин выходит из строя. Ставшая уже традиционной парадигма MapReduce позволяет справиться с отказом узлов кластера, однако предполагает сохранение промежуточных результатов на диске и, как следствие, весьма нетороплива. В стеке Hadoop сейчас идет активное развитие альтернативных решений, одно из которых — Spark, где в 2014 году появился модуль SparkSQL, позволяющий бесшовно выполнять запросы к структурированным данным, используя как SQL, так и специальный API DataFrame. DataFrame и SQL позволяют унифицировать работу с разнообразными источниками, такими как система поддержки хранилищ данных Hive, система сериализации Avro, поколоночные хранилища Parquet и ORC, JSON и JDBC (рис. 3).

Рис. 3. Интерфейсы к SparkSQL и взаимодействие со Spark

DataFrame API предоставляет обширные возможности реляционной и процедурной интеграции для Spark-программ. DataFrames — это коллекции структурированных записей, которыми можно манипулировать и с помощью традиционных процедурных API, и с помощью реляционных операторов, что открывает богатые возможности для оптимизации. Коллекции могут быть созданы как непосредственно из распределенных Spark-коллекций объектов на Java/Python, так и из библиотек машинного обучения. При этом операции над DataFrames производятся с использованием оптимизатора Catalyst [4].

Расширяемость — основное свойство оптимизатора Catalyst, который был реализован на Scala таким образом, чтобы в дальнейшем допускать простое и быстрое добавление компонентов (языков, источников и т. д.). Catalyst работает с множеством источников данных (Hive, реляционные СУБД, JSON, объекты на Java/Scala/Python), а не только со Spark и RDD (Resilient Destributed Datasets, устойчивые распределенные наборы данных). Большинство оптимизаций в Catalyst эвристические, основанные на правилах, — от оптимизатора требуется правильно организовать конвейерную обработку данных, уметь «проталкивать» предикаты внутрь операций соединения без промежуточной материализации результата. Стоимость учитывается при выборе планов только на этапе физической оптимизации и только при выборе способа соединения таблиц: для таблиц, о малом размере которых заранее известно, выбирается способ соединения на основе широковещательных сообщений, а не выборочных схем обмена данными. И хотя фреймворк поддерживает более широкие возможности для стоимостной оптимизации, сейчас они не используются.

Таким образом, оптимизаторы мира Больших Данных менее совершенны, чем их аналоги в реляционных СУБД: используют больше эвристик и их пространство поиска существенно уже, однако и поведение их предсказуемо, а диаграммы плана выполнения похожи на диаграммы из рис. 1. Сами планы выполнения «стабильны»: заранее известно, как поведет себя система. В их работе уже не требуется участия администратора системы. Однако разработчик (архитектор) в таких системах уже не может всецело полагаться на оптимизатор — ему необходимо заранее подумать о том, как будет исполнен его запрос и все ли структуры данных созданы. С точки зрения эксплуатации такие системы не лучше и не хуже, это просто иной способ обработки.

Итак, можно ли для решения задачи оптимизации в V2Opt и Catalyst использовать старые подходы из мира SQL?

В Vertica стратегия оптимизации состоит в правильном выборе списка проекций, ближайший аналог которых в мире классических СУБД — это материализованные представления. Аналогии прослеживаются и для задачи оптимизации: необходимо выбрать не только порядок выполнения операций, но и список таблиц (их копий в виде материализованных представлений или проекций), участвующих в запросе. Выбор набора из списка — еще одна классическая комбинаторная задача: можно выбрать в качестве первого источника таблицу 1 или одну из ее копий, в качестве второго источника — таблицу 2 или копию и т. д. — количество вариантов в этом случае будет расти экспоненциально. Общий подход к решению — это двухфазная оптимизация. На первой фазе выбирается набор таблиц, на второй — выполняется физическая оптимизация. Далее происходит возврат к первой фазе и анализ следующего набора — процесс физической оптимизации повторяется множество раз. Однако неясно, можно ли на основе стоимости заранее исключить некоторые наборы, поэтому для сокращения перебора вариантов используются правила, различные догадки и эвристики.

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

Основная проблема оптимизации в SparkSQL сейчас состоит в объединении разнородных источников данных. С одной стороны, нужно уметь из SparkSQL работать не только со Spark, но и с Hive, и с классическими реляционными СУБД, решая задачу оптимизации при работе с данными в формате Spark и преобразуя выражения диалекта SparkSQL в выражения диалекта HiveQL или SQL (управлять внешними оптимизаторами). С другой стороны, нужно уметь работать с разнородными потребителями SparkSQL — это может быть как запрос на языке SparkSQL, так и выражение на Java или Python. При этом интерфейс доступа с использованием Catalyst подразумевает применение всего набора улучшений, а не их части — интерфейсы доступа и форматы данных строго не фиксированы. Hadoop представляет собой каркасную систему, и для разных задач наборы компонентов системы могут кардинально различаться. Каркас — это новый способ организации, и здесь пока нет ясности с постановкой задачи стоимостной оптимизации. В случае большого разнообразия (таблицы во множестве форматов, выражения, оптимизаторы внешних систем) непонятно, что является объектом оценки стоимости. Таким образом, для SparkSQL задачу стоимостной оптимизации еще предстоит сформулировать, а пока в Catalyst стоимостная оптимизация используется для решения только отдельной частной задачи выбора способа соединения двух таблиц.

***

Стоимостная оптимизация в СУБД мира Больших Данных направлена на решение конкретных практических задач по выбору самого дешевого способа соединения или нахождения правильной проекции таблицы. Поэтому говорить о преемственности оптимизаторов для мира NoSQL можно лишь применительно к решению именно конкретных задач — старые подходы годятся лишь для частных задач локальной оптимизации, а новые задачи, связанные с глобальной оптимизацией, еще только предстоит сформулировать.

Литература

1. Сергей Кузнецов. Пусть расцветают сто цветов // Открытые системы. — 2013. — № 2. URL: http://www.osp.ru/os/2013/02/13034557 (дата обращения: 08.02.2016).
2. Naveen Reddy, Jayant Haritsa. Analyzing plan diagrams of database query optimizers // Proceedings of the 31st international conference on Very large data bases (August 30 — September 02, 2005, Trondheim, Norway). — 2005. — P. 1228–1239. URL: http://www.vldb.org/conf/2005/papers/p1228-reddy.pdf (дата обращения: 31.12.2015).
3. V2Opt Modular Query Optimizer US Patent 2010/0131490 A1. URL: https://www.google.com.ar/patents/US20100131490 (дата обращения: 07.01.2016).
4. Michael Armbrust, Reynold Xin, Cheng Lian, Yin Huai, Davies Liu, Joseph K. Bradley, Xiangrui Meng, Tomer Kaftan, Michael Franklin, Ali Ghodsi, Matei Zaharia. Spark SQL: Relational Data Processing in Spark // Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (May 31 — June 04, 2015, Melbourne, Victoria, Australia). — 2015. URL: http://people.csail.mit.edu/matei/papers/2015/sigmod_spark_sql.pdf (дата обращения: 07.02.2016).

Леонид Борчук (le.borchuk@gmail.com) — администратор баз данных, «Яндекс» (Москва).