Чтобы писать эффективные SQL запросы, разработчик базы данных должен понимать, как запросы обрабатываются движком базы данных. А для этого необходимы основы реляционной теории. Если слово «теория» звучит слишком сухо, можно назвать это «тайной жизнью запроса в базе данных». В этой главе мы рассмотрим эту «тайную жизнь», объяснив, что происходит с запросом между моментом, когда вы щелкаете мышью по кнопке Выполнить или нажимаете клавишу Enter, и моментом, когда вы видите набор результатов, возвращаемый базой данных.
Как обсуждалось в предыдущей главе, SQL-запрос указывает, какие результаты необходимы или что нужно изменить в базе данных, но не указывает, как именно достичь ожидаемых результатов. Работа движка базы данных состоит в том, чтобы преобразовать исходный SQL-запрос в исполняемый код и выполнить его. В этой главе рассматриваются операции, используемые движком базы данных при интерпретации SQL-запроса, и их теоретические основы.
оБзор оБраБотки заПросов
Чтобы получить результаты запроса, PostgreSQL выполняет следующие шаги:
О компилирует и преобразует инструкцию SQL в выражение, состоящее из логических операций высокого уровня, называемое логический план;
О оптимизирует логический план и превращает его в план выполнения; О выполняет (интерпретирует) план и возвращает результаты.
Компиляция
Компиляция SQL-запроса аналогична компиляции кода, написанного на императивном языке. Исходный код анализируется, и генерируется внутреннее представление. Но компиляция инструкций SQL имеет два существенных отличия.
Во-первых, в императивном языке в исходный код обычно включаются определения идентификаторов, тогда как определения объектов, на которые ссылаются запросы SQL, в основном хранятся в базе данных. Следовательно, смысл запроса зависит от структуры базы данных: разные серверы баз данных могут интерпретировать один и тот же запрос по-разному.
Во-вторых, вывод компилятора императивного языка обычно представляет собой (почти) исполняемый код, например байт-код для виртуальной машины Java. Напротив, вывод компилятора запросов - это выражение, состоящее из высокоуровневых операций, которые остаются декларативными - они не дают никаких инструкций о том, как получить требуемый результат. На данном этапе указывается возможный порядок операций, но не способ их выполнения.
Оптимизация и выполнение
Инструкции по выполнению появляются на следующем этапе обработки запроса, при оптимизации. Оптимизатор выполняет два вида преобразований: заменяет логические операции на алгоритмы выполнения и, возможно, изменяет структуру логического выражения, меняя порядок выполнения логических операций.
Ни одно из этих преобразований не является простым; логическая операция может вычисляться с использованием разных алгоритмов, и оптимизатор пытается выбрать лучший. Один и тот же запрос может быть представлен несколькими эквивалентными выражениями, дающими один и тот же результат, но требующими существенно разного количества вычислительных ресурсов для выполнения. Оптимизатор пытается найти логический план и физические операции, которые минимизируют необходимые ресурсы, включая время выполнения. Для этого применяются сложные алгоритмы, которые не рассматриваются в данной книге. Однако мы расскажем, как оптимизатор оценивает количество ресурсов, необходимых для физических операций, и как эти ресурсы зависят от особенностей хранения данных.
Результатом работы оптимизатора является выражение, содержащее физические операции. Это выражение называется (физическим) планом выполнения. По данной причине оптимизатор PostgreSQL называют планировщиком запросов.
Наконец, план выполнения запроса интерпретируется движком выполнения запроса, который в сообществе PostgreSQL часто называют исполнителем, и вывод возвращается в клиентское приложение.
Давайте подробнее рассмотрим каждый шаг обработки запроса и используемые операции.
реляЦионные, логические и физические оПераЦии
Чтобы подробнее выяснить, как движок базы данных понимает SQL, мы должны, наконец, обратиться к главной теме этой главы: теории. Многие
современные системы управления базами данных, включая PostgreSQL, называются реляционными, потому что они основаны на реляционной тео- рии[I]. Несмотря на то что некоторым теория кажется сухой, непонятной или неуместной, понимание небольшой части реляционной теории - а именно реляционных операций - просто необходимо для того, чтобы овладеть оптимизацией. Выражаясь точнее, нам нужно будет понять, как реляционные операции соответствуют логическим операциям и языку, используемому в запросах. В предыдущем разделе были рассмотрены три этапа обработки запросов на высоком уровне; в этом разделе более подробно описывается каждый уровень, начиная с описания реляционных операций.
Некоторые читатели могут счесть представленный здесь материал элементарным и понятным, а другие могут воспринять его как ненужное усложнение. Пока просто верьте, что он закладывает основу для того, что будет дальше.
Реляционные операции
Центральная концепция реляционной теории - отношение. Для наших целей мы рассматриваем отношение в виде таблицы, хотя теоретики могут поспорить, что это исключает некоторые тонкие, но важные различия.
Любая реляционная операция принимает одно или несколько отношений в качестве аргументов и порождает еще одно отношение в качестве результата. Это результирующее отношение можно использовать как аргумент другой реляционной операции, порождая следующее отношение, которое, в свою очередь, тоже может стать аргументом. Таким образом, мы можем создавать сложные выражения и представлять сложные запросы.
Возможность построения сложных выражений делает набор реляционных операций (который называют реляционной алгеброй) мощным языком запросов.
Кроме того, выражения в реляционной алгебре могут использоваться для определения дополнительных операций.
Первые три операции, которые следует обсудить, - это фильтрация, проекция и произведение.
Фильтрацию (изображенную на рис. 2.1) часто называют селекцией, а в реляционной теории - ограничением. Мы предпочитаем использовать термин фильтрация, чтобы избежать путаницы с SQL-командой SELECT, а у термина ограничение слишком глубокие математические корни. Операция фильтрации принимает в качестве аргумента одно отношение и включает в результат все кортежи (или строки), удовлетворяющие условию фильтрации, например:
SELECT * FROM flight
WHERE departure_airport = 'LAG'
AND (arrival_airport = 'ORD' OR arrival_airport = 'MDW')
AND scheduled_departure BETWEEN '2020-05-27' AND '2020-05-28'
Рис. 2.1 ❖ Фильтр
Здесь мы начинаем с отношения flight и применяем ограничения на значения атрибутов arrival_airport, departure_airport и scheduled_departure. Результат представляет собой множество записей, то есть тоже отношение.
Рис. 2.2 ❖ Проекция
Проекция (представленная на рис. 2.2) также принимает одно отношение в качестве аргумента и удаляет некоторые атрибуты (столбцы). Реляционная проекция удаляет из результата все дубликаты, но проекция SQL этого не делает. Например, запрос
SELECT city, zip FROM address
при выполнении в PostgreSQL вернет столько строк, сколько записей в таблице address. Но если выполнить реляционную проекцию, то для каждого почтового индекса останется одна запись. Чтобы добиться того же результата в PostgreSQL, нужно добавить к запросу ключевое слово DISTINCT:
SELECT DISTINCT city, zip FROM address
Рис. 2.3 ❖ Произведение
Произведение (также называемое декартовым произведением и изображенное на рис. 2.3) порождает множество всех пар строк из первого и второго аргументов. Очень трудно найти полезный пример произведения из реальной жизни, но давайте представим, что мы ищем все возможные рейсы, которые только могут существовать (из любого аэропорта мира в любой аэропорт). Операция произведения будет выглядеть так:
SELECT d.airport_code AS departure_airport,
a.airport_code AS arrival_airport
FROM airport a, airport d
Теперь, когда мы рассмотрели эти основные реляционные операции, вы, наверное, чувствуете себя обманутыми: где же соединения? Мы знаем, что соединения очень важны. Ответ на поверхности: соединение можно выразить как произведение, за которым следует фильтрация. С точки зрения реляционной теории соединение избыточно. Это прекрасный пример того, как работает декларативный язык; формальное определение - один (но не единственный) из способов получить результат соединения. Если мы вычислим декартово произведение двух таблиц, а затем применим фильтрацию, то получим желаемый результат. Но надеемся, что ни один из движков баз данных не делает так для больших наборов данных; на это могли бы уйти годы в буквальном смысле! В главе 3 мы обсудим, как реализовать соединение более эффективно, чем прямое вычисление на основе формального определения.
К реляционным операциям также относятся группировка, объединение, пересечение и разность множеств.
Последний элемент реляционной теории, который нужен для оптимизации, - правила эквивалентности. Реляционные операции удовлетворяют некоторым правилам эквивалентности, включая:
О коммутативность - JOIN(R,S) = JOIN (S,R).
Коммутативность означает, что порядок двух отношений не важен. Если у нас есть два отношения, R и S, то R JOIN S даст тот же результат, что и S JOIN R;
О ассоциативность - JOIN(R, JOIN(S,T) = JOIN(JOIN(R,S), T).
Ассоциативность означает, что если у нас есть три отношения, R, S и T, мы можем сначала выполнить R JOIN S, а затем присоединить T к результату, или сначала выполнить S JOIN T, а затем присоединить R к результату первого соединения, и результаты будут эквивалентны в обоих случаях;
О дистрибутивность - JOIN(R, UNION(S, T)) = UNION(JOIN(R,S), JOIN(R, T)). Дистрибутивность означает, что если мы соединим отношение с объединением двух других отношений, результат будет таким же, как если бы мы выполнили два соединения, R JOIN S и R JOIN T, по отдельности, а затем объединили результаты.
Правила эквивалентности, перечисленные выше, - всего лишь единичные примеры среди десятков других. Почему важно знать об этих правилах? Может оказаться, что в целях эффективности лучше выполнять операции не в том порядке, в котором они записаны. В последующих главах будет несколько примеров таких преобразований. Эквивалентность гарантирует, что запрос может быть представлен разными выражениями, и это дает оптимизатору простор для деятельности.
Логические операции
Набор логических операций, необходимых для представления SQL-запросов, включает в себя все реляционные операции, но с другой семантикой. Как отмечалось ранее, проекция SQL не удаляет дубликаты; для удаления дубликатов включена отдельная операция.
Другие дополнительные операции необходимы для представления конструкций SQL, которые нельзя выразить в реляционной теории, например левое, правое и полное внешние соединения дают результат, который не является отношением (но является таблицей SQL).
Многие правила эквивалентности также действительны и для логических операций. Для любого относительно сложного запроса оптимизатор может выбрать лучшее из огромного количества выражений.
Более подробную информацию о реляционной теории можно найти в ресурсах, приведенных в заключительных примечаниях.
Запросы как выражения: мыслить множествами
Написание декларативных запросов - непростая задача. Нам более привычны действия, нежели правила или условия. Мышление множествами[II] облегчает задачу: мы можем думать о действиях и операциях с таблицами, а не с отдельными объектами (или строками).
Все упомянутые ранее логические операции можно легко выразить на языке SQL. Эти операции принимают таблицы в качестве аргументов: и те, что хранятся в базе данных, и те, что являются результатом предыдущих операций.
Выражение PostgreSQL, записанное как SQL-запрос, будет обработано оптимизатором и, скорее всего, будет заменено другим эквивалентным выражением с использованием обсуждавшихся ранее правил эквивалентности.
Поскольку результатом любой реляционной операции является отношение, ее можно передать непосредственно следующей реляционной операции без необходимости промежуточного хранения. Некоторые разработчики баз данных предпочитают создавать временные таблицы для промежуточных результатов, но такая практика может привести к ненужным вычислительным затратам и помешать оптимизатору.
Говоря языком теории, в предыдущем абзаце говорится, что способность оптимизатора создавать эффективный план выполнения зависит от двух факторов:
О богатый набор эквивалентностей обеспечивает большое пространство эквивалентных выражений;
О реляционные операции не имеют побочных эффектов, таких как временные таблицы, то есть единственное, что они порождают, - это результат операции.
Операции и алгоритмы
Чтобы сделать запрос исполняемым, логические операции необходимо заменить физическими (которые также называют алгоритмами). В Post- greSQL эту замену выполняет планировщик, а общее время выполнения запроса зависит от того, какие выбраны алгоритмы и правильно ли они выбраны.
Когда мы переходим с логического уровня на физический, математические отношения превращаются в таблицы, которые хранятся в базе данных, и нам нужно определить способы получения данных из этих таблиц. Любые сохраненные данные должны извлекаться одним из алгоритмов доступа к данным, обсуждаемых в следующей главе. Обычно алгоритмы доступа к данным сочетаются с операциями, которые пользуются их результатами.
Более сложные логические операции, такие как соединение, объединение и группировка, можно реализовать несколькими альтернативными алгоритмами. Иногда сложная логическая операция заменяется несколькими физическими операциями.
Эти алгоритмы подробно обсуждаются в главе 3.
выводы
Движок базы данных интерпретирует запросы SQL, преобразовывая их в логический план, трансформируя результаты, выбирая алгоритмы для реализации логического плана и, наконец, выполняя выбранные алгоритмы. Логические операции, используемые движком базы данных, основаны на операциях реляционной теории, и их понимание исключительно важно для умения мыслить как база данных.
[I] К. Дж. Дейт. Введение в системы баз данных; Дж. Ульман. Принципы систем баз данных. 2-е изд.
[II] Joe Celko, Joe Celko's Thinking in Sets: Auxiliary, Temporal, and Virtual Tables in SQL (The
Morgan Kaufmann Series in Data Management Systems).
