Логическая обработка запросов: предложения FROM и объединения

Одна из предыдущих моих статей, опубликованных в журнале, была посвящена процессу логической обработки запросов. Я показал, что этот термин представляет логическую интерпретацию запроса. Мною были подготовлены демонстрационная база данных TSQLV4, два демонстрационных запроса, на которые я ссылался как на простой демонстрационный запрос и на сложный демонстрационный запрос, а также графическое описание логической обработки запроса в виде блок-схемы. Начиная с этой статьи я буду рассматривать особенности отдельных предложений; сегодня мы займемся предложением FROM и оператором JOIN.

Предложение FROM

Предложение FROM — это первое большое предложение запроса, подвергаемое логической обработке, несмотря на то что предложение SELECT помещается раньше него. В рассматриваемом предложении определяются две категории объектов. Во-первых, здесь указываются входные таблицы запроса, а во-вторых, операторы таблиц, такие как JOIN, APPLY, PIVOT и UNPIVOT; они применяются к содержимому входных таблиц.

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

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

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

Оператор JOIN

В реляционной модели понятие объединения (join) относится не столько к бинарным операторам, сколько вообще к N-арным. А в SQL оператор join определяется как бинарный оператор с двумя наборами входных данных — левым и правым. SQL поддерживает три типа соединений: перекрестное (cross), внутреннее (inner) и внешнее (outer). Каждый тип соединения реализует подмножество следующих шагов:

• 1-J1. Применить декартово произведение;
• 1-J2. Идентифицировать совпадения на базе предиката ON;
• 1-J3. Добавить внешние строки.

Перекрестное соединение предполагает выполнение только шага 1-J1, внутреннее соединение — выполнение шагов 1-J1 и 1-J2, а внешнее соединение — шагов 1-J1, 1-J2 и 1-J3.

Чтобы с этим разобраться, рассмотрим предложение FROM из простого демонстрационного запроса, приведенного в упомянутом выше обзоре «Логическая обработка запросов» (опубликованном в Windows IT Pro/RE № 3 за 2016 год):

FROM Sales.Customers AS C
   LEFT OUTER JOIN Sales.Orders AS O
      ON C.custid = O.custid

1-J1. Apply Cartesian product

Первый шаг в объединении предусматривает получение декартова произведения между двумя наборами входных данных соединения. Поскольку в таблице Customers 91 строка, а в таблице заказов — 830 строк, результат составляет 75 530 строк, представленных на рисунке 1 в сокращенной форме.

Рисунок 1. Декартово произведение двух наборов данных

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

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

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

Примечательно, что, если мы назначаем таблицам псевдонимы, мы, по сути, переименовываем таблицы на время выполнения запроса. Во всех последующих фазах логической обработки запроса если мы попытаемся сослаться на таблицу по ее полному имени, как в Customers.custid, то получим сообщение об ошибке. Здесь нужно использовать псевдоним, как в C.custid.

1-J2. Идентификация совпадений на базе предиката ON

Назначение предложения ON состоит в том, чтобы идентифицировать совпадения в результате выполнения предыдущего шага на основе указанного предиката, который в нашем случае является предикатом ON C.custid = O.custid. В SQL используется логика на основе трех наделенных значениями предикатов, где результатом предиката может быть одно из трех логических значений: true, false и unknown. При использовании оператора равенства, в случае когда обе стороны предиката не относятся к категории NULL, мы можем получать значения true или false. Значение true получается, если они идентичны, как, например, в строке на рисунке 2.

Рисунок 2. Равенство двух сторон предиката

Значение false получается, когда они отличаются друг от друга, как в строке на рисунке 3.

Рисунок 3. Две стороны предиката отличаются

Если одна из частей (или обе) имеет значение NULL, в результате мы получаем логическое значение unknown. И неважно, какие операторы (равенства или неравенства) используются при этом. В нашем демонстрационном наборе данных в столбцах C.custid и O.custid нет данных со значением NULL, поэтому предикаты получают значение true или false во всех случаях. На рисунке 4 представлен результат применения предиката ON к строкам, полученным в результате выполнения предыдущего шага (опять-таки данные приводятся в сокращенном варианте).

Рисунок 4. Результат применения предиката ON к строкам

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

1-J3. Добавить внешние строки

Третий шаг выполняется только применительно к внешним объединениям. При совершении внешнего объединения нужно отметить, какую таблицу или таблицы следует сохранить: левую, правую или обе (случай полного внешнего объединения). В нашем примере сохраняется левая таблица (Customers). Выполняя это объединение, необходимо сохранить все строки таблицы вне зависимости от того, выявило ли предложение ON случаи совпадений в содержимом правой таблицы (Orders). На данном этапе идентифицируются те строки сохраненной стороны, которые не содержат совпадений. Эти строки добавляются к результатам со значением NULL в качестве заполнителей в столбцах несохраненной стороны. В нашем примере заказов, которые ассоциировались бы с клиентами, имеющими идентификаторы 22 и 57, нет, и потому на данном этапе эти клиенты добавляются к результатам предыдущего шага (см. рисунок 5).

Рисунок 5. Клиенты добавляются к результатам предыдущего шага

Не забывайте, что в системе SQL Server физическая обработка, как правило, не предусматривает разделения работы на три этапа, описанные выше; как я уже отмечал, система должна обеспечить на выходе получение идентичного результата, и не более того.

Если в предложении FROM имеется еще один оператор JOIN, результат первого объединения становится левой составляющей входных данных второго объединения, и тогда к последнему применяется соответствующее подмножество шагов в зависимости от типа объединения. На рисунке 6 общая картина представлена в виде диаграммы.

Рисунок 6. Диаграмма логической обработки запроса — объединения

Управление порядком объединений в процессе логической обработки

Как уже отмечалось, обычно логическая обработка объединений осуществляется в порядке их представления — слева направо. В качестве примера рассмотрим запрос, приведенный в листинге 1. Общее число строк, возвращаемых этим запросом, составляет 2155.

Первое объединение, выполняемое в данном примере, это объединение столбцов Customers и Orders на основе предиката ON C.custid = O.custid. Во втором объединении участвуют результат первого объединения, а также таблица OrderDetails, базирующаяся на предикате ON O.orderid = OD.orderid. Собственно, именно предикаты ON определяют, какие именно объекты подвергаются объединению. Они создают некое средство управления, которое я именую для себя неявными скобками. Вообще-то здесь можно добавлять реальные скобки. Представленный в листинге 1 запрос неявно определяет скобки в листинге 2.

Поскольку все объединения в запросе суть внутренние объединения, все несовпадения с любой стороны отбрасываются. Так, в запросе фигурируют два клиента (с идентификаторами 22 и 57), не сделавшие заказов, и потому они не упоминаются в выходных данных. А теперь представим себе, что вы хотите сохранить в результате всех клиентов. В этом случае естественно было бы преобразовать тип объединения между столбцами Customers и Orders в левое внешнее объединение, как в листинге 3.

Как ни странно, выполнив указанный запрос, мы получим те же выходные данные, что и ранее, когда у нас было 2155 строк — без тех двух дополнительных клиентов, которых вы ожидали. Почему так получается?

Логическая обработка запроса начинается с левого внешнего объединения между столбцами Customers и Orders; при этом сохраняются оба не имеющих заказов клиента. Результирующие строки для этих двух клиентов заполняются значениями NULL, которые выступают в роли заполнителей в столбцах из таблицы Orders. Второе объединение является внутренним объединением результатов первого объединения и OrderDetails. Если произвести оценку предиката O.orderid = OD.orderid для внешних строк, мы получим в результате логическое значение unknown, поскольку в этих строках O.orderid имеет значение NULL. Следовательно, внешние строки отбрасываются. В целом такой результат сводит внешнее объединение на нет, превращая его, по сути, во внутреннее объединение. Здесь можно сделать такое обобщение: результатом любого левого внешнего объединения, за которым следует внутреннее объединение или правое внешнее объединение, содержащее сравнение объектов из несохраненной стороны объединения с другими объектами, будет аннулирование внешнего объединения.

Любопытно, что в ходе оптимизации этого запроса SQL Server использует средства выявления противоречий. Система определяет, что внешнее объединение бессмысленно, и преобразует внешнее объединение во внутреннее, как следует из плана выполнения запроса, представленного на рисунке 7.

Рисунок 7. План запроса с внутренним объединением

Как же выйти из положения? Нужно начать с отказа от левого объединения между Customers и Orders, за которым следует внутреннее объединение между полученным результатом и OrderDetails. Необходимо выполнить левое объединение между Customers и результатом внутреннего объединения между Orders и OrderDetails. Помните: мы определяем, какие элементы подвергаются объединению, с помощью предложения ON, которое должно следовать за двумя объединяемыми элементами. Чтобы объединить Orders и OrderDetails, нужно поставить предикат ON O.orderid = OD.orderid сразу же после этого объединения. Дадим этому результату имя OOD. Для объединения Customers и OOD необходимо, чтобы предикат ON C.custid = O.custid располагался после этого объединения. Подведем итоги. В листинге 4 показано, как следует формулировать наш запрос.

Теперь на выходе мы имеем 2157 строк, в том числе данные о двух клиентах, не имеющих подходящих заказов.

В этом запросе используются неявные скобки, но для ясности настоятельно рекомендуется указывать их явным образом — хотя бы так, как в листинге 5.

В соответствии с планом выполнения запроса данное объединение обрабатывается как внешнее объединение (см. рисунок 8).

Рисунок 8. План запроса с внешним объединением

Рассматриваемый запрос представляет часть работы, проделываемой при выполнении сложного демонстрационного запроса. Кроме того, запрос должен возвращать лишь заказы, размещенные с начала 2016 года. Будьте внимательны: в предложении WHERE не указывайте predicate ordedate >= ‘20160101’, поскольку тем самым вы отфильтруете всех клиентов, которые не размещали заказы в течение данного периода, а наш запрос в соответствии с замыслом должен сохранять всех клиентов. Один из способов избежать ошибки состоит в том, чтобы добавить данный предикат к предложению ON, соединяющему Orders и OrderDetails таким образом, как показано в листинге 6.

В ходе внутреннего объединения предложение ON выполняет задачу фильтрации, поэтому при объединении между Orders и OrderDetails возвращаются только те строки, где дата заказа приходится на 2016 год или на более поздний период. Далее в ходе внешнего объединения между Customers и результатом объединения между Orders и OrderDetails сохраняются все клиенты.

Еще один способ решения задачи состоит в добавлении предиката к предложению ON внешнего объединения, как показано в листинге 7.

По своей логике оба эти запроса эквивалентны; кстати, оптимизатор разрабатывает для них идентичные планы. На мой взгляд, первый запрос представляется более естественным. Как я уже отмечал, здесь важно не указывать предикат в предложении WHERE, поскольку тем самым вы сведете к нулю внешнюю часть внешнего объединения. Различие между ON и WHERE я подробно рассмотрю в одной из следующих статей серии, посвященных предложению WHERE.

Управление порядком выполнения операций по физической обработке объединений

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

Тип перестановок, к которым может прибегать оптимизатор, зависит от применяемого типа объединения. В случае с внешними объединениями единственно возможная перестановка состоит в замене A LEFT JOIN B на B RIGHT JOIN A и наоборот. Но полное изменение порядка таблиц в предусматривающем несколько объединений запросе исключается, ибо в этом случае может измениться смысл запроса. При выполнении внутренних и перекрестных объединений оптимизатору предоставляется возможность осуществлять любые перестановки по своему усмотрению. Сюда включается порядок указания таблиц при наличии, например, таких объединений:

A INNER JOIN B INNER JOIN
   C INNER JOIN D

Их можно заменять следующими объединениями:

B INNER JOIN C INNER JOIN A INNER
   JOIN D

Это относится и к перестановке упаковки элементов. Для примера рассмотрим следующую схему:

A INNER JOIN B
    ON A.x = B.x
  INNER JOIN C
    ON B.y = C.y
  INNER JOIN D
    ON C.z = D.z

Помните: вопрос о том, какие элементы объединяются, решает предложение ON. При записи таким образом мы получаем следующие неявные скобки:

( ( A INNER JOIN B
        ON A.x = B.x )
      INNER JOIN C
        ON B.y = C.y )
  INNER JOIN D
    ON C.z = D.z

Оптимизатор может изменить это расположение, и в результате мы получим, например, такой вариант:

A INNER JOIN
      B INNER JOIN C
        ON B.y = C.y
    ON A.x = B.x
  INNER JOIN D
    ON C.z = D.z

Неявные скобки здесь расположены следующим образом:

( A INNER JOIN
        ( B INNER JOIN C
            ON B.y = C.y )
      ON A.x = B.x )
  INNER JOIN D
    ON C.z = D.z

Как отмечает Бенджамин Неварес в статье Optimizing Join Orders (http://www.benjaminnevarez.com/2010/06/optimizing-join-orders/), в соответствии с положениями комбинаторики число возможных вариантов расположения для N таблиц составляет (2N? 2)! (N? 1)!, где восклицательный знак (!) означает факториал. Так, при наличии 5 таблиц мы имеем 1680 вариантов расположения. А если таблиц 10, это число возрастает до 17 643 225 600. Поскольку в оптимизаторе предусмотрены пороговые значения по времени и затратам, нетрудно понять, что чем больше таблиц в запросе, тем меньше вероятность того, что он сможет предложить действительно оптимальный порядок. Если вы подозреваете, что порядок, предложенный оптимизатором, явно неэффективен, можете принудительно заложить в него порядок, который, по вашему мнению, ближе к оптимальному. Для этого в конце запроса нужно добавить подсказку запроса OPTION (FORCE ORDER). Если вы хотите принудительно использовать порядок объединений во всех запросах данного сеанса, можете присвоить параметру FORCEPLAN значение ON. Учтите: такую меру, как принудительное указание порядка, рекомендуется применять главным образом в процессе диагностики. Использование этой меры в производственном процессе допускается лишь в качестве временного решения. Объясняется это тем, что оптимизатор должен быть в состоянии по прошествии какого-то времени изменять предлагаемые варианты под влиянием изменившихся условий, таких как новые параметры индексирования и характеристики данных.

В качестве примера принудительного указания порядка физического объединения рассмотрим запрос, приведенный в листинге 8. На моей системе оптимизатор выбрал для этого запроса план, показанный на рисунке 9.

Рисунок 9. План для запроса, предусматривающего несколько объединений

Оптимизатор физически переупорядочил объединения, предложив порядок их выполнения, как в листинге 9.

Если вы, к примеру, полагаете, что первоначально написанный порядок является оптимальным, то можете принудительно применить его таким образом, как в листинге 10.

Помните, что неявные скобки здесь выглядят так, как в листинге 11. План для этого запроса показан на рисунке 10.

Рисунок 10. План запроса с форсированным порядком

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

SELECT C.custid, C.country, O.orderid, OD.productid, OD.qty, OD.unitprice
FROM Sales.Customers AS C
  INNER JOIN Sales.Orders AS O
    ON C.custid = O.custid
  INNER JOIN Sales.OrderDetails AS OD
    ON O.orderid = OD.orderid;

SELECT C.custid, C.country, O.orderid, OD.productid, OD.qty, OD.unitprice
FROM ( Sales.Customers AS C
         INNER JOIN Sales.Orders AS O
           ON C.custid = O.custid )
  INNER JOIN Sales.OrderDetails AS OD
    ON O.orderid = OD.orderid;

SELECT C.custid, C.country, O.orderid, OD.productid, OD.qty, OD.unitprice
FROM Sales.Customers AS C
  LEFT OUTER JOIN Sales.Orders AS O
    ON C.custid = O.custid
  INNER JOIN Sales.OrderDetails AS OD
    ON O.orderid = OD.orderid;

SELECT C.custid, C.country, O.orderid, OD.productid, OD.qty, OD.unitprice
FROM Sales.Customers AS C
  LEFT OUTER JOIN
      Sales.Orders AS O
        INNER JOIN Sales.OrderDetails AS OD
          ON O.orderid = OD.orderid
    ON C.custid = O.custid;

SELECT C.custid, C.country, O.orderid, OD.productid, OD.qty, OD.unitprice
FROM Sales.Customers AS C
  LEFT OUTER JOIN
      ( Sales.Orders AS O
          INNER JOIN Sales.OrderDetails AS OD
            ON O.orderid = OD.orderid )
    ON C.custid = O.custid;

SELECT C.custid, C.country, O.orderid, OD.productid, OD.qty, OD.unitprice
FROM Sales.Customers AS C
  LEFT OUTER JOIN
      ( Sales.Orders AS O
          INNER JOIN Sales.OrderDetails AS OD
            ON O.orderid = OD.orderid
            AND O.orderdate >= '20160101' )
    ON C.custid = O.custid;

SELECT C.custid, C.country, O.orderid, OD.productid, OD.qty, OD.unitprice
FROM Sales.Customers AS C
  LEFT OUTER JOIN
      ( Sales.Orders AS O
          INNER JOIN Sales.OrderDetails AS OD
            ON O.orderid = OD.orderid )
    ON C.custid = O.custid
    AND O.orderdate >= '20160101';

SELECT C.custid, C.country, O.orderid, OD.productid, OD.qty, OD.unitprice
FROM Sales.Customers AS C
  LEFT OUTER JOIN
      ( Sales.Orders AS O
          INNER JOIN Sales.OrderDetails AS OD
            ON O.orderid = OD.orderid )
    ON C.custid = O.custid
    AND O.orderdate >= '20160101';

SELECT C.custid, C.country, O.orderid, OD.productid,
  P.productname, OD.qty, OD.unitprice
FROM Production.Products AS P
  INNER JOIN
      Sales.Customers AS C
          INNER JOIN
              ( Sales.Orders AS O
                  INNER JOIN Sales.OrderDetails AS OD
                    ON O.orderid = OD.orderid )
            ON C.custid = O.custid
    ON Od.productid = P.productid;

SELECT C.custid, C.country, O.orderid, OD.productid,
  P.productname, OD.qty, OD.unitprice
FROM Sales.Customers AS C
  INNER JOIN Sales.Orders AS O
    ON C.custid = O.custid
  INNER JOIN Sales.OrderDetails AS OD
    ON O.orderid = OD.orderid
  INNER JOIN Production.Products AS P
    ON Od.productid = P.productid
OPTION (FORCE ORDER);

SELECT C.custid, C.country, O.orderid, OD.productid,
  P.productname, OD.qty, OD.unitprice
FROM ( ( Sales.Customers AS C
           INNER JOIN Sales.Orders AS O
             ON C.custid = O.custid )
         INNER JOIN Sales.OrderDetails AS OD
           ON O.orderid = OD.orderid )
       INNER JOIN Production.Products AS P
         ON Od.productid = P.productid
OPTION (FORCE ORDER);