8.13.9. Вложенная Оптимизация Соединения


8.13.9. Вложенная Оптимизация Соединения

Синтаксис для того, чтобы выразить разрешения на соединения вложенные соединения. Следующее обсуждение обращается к синтаксису соединения, описанному в Разделе 13.2.9.2,"JOIN Синтаксис".

Синтаксис table_factor расширяется по сравнению со Стандартом SQL. Последний принимает только table_reference, не список их в паре круглых скобок. Это - консервативное расширение, если мы рассматриваем каждую запятую в списке table_reference элементы как эквивалентный внутреннему объединению. Например:

SELECT * FROM t1 LEFT JOIN (t2, t3, t4)                 ON (t2.a=t1.a AND t3.b=t1.b AND t4.c=t1.c)

эквивалентно:

SELECT * FROM t1 LEFT JOIN (t2 CROSS JOIN t3 CROSS JOIN t4)                 ON (t2.a=t1.a AND t3.b=t1.b AND t4.c=t1.c)

В MySQL, CROSS JOIN синтаксический эквивалент INNER JOIN (они могут заменить друг друга). В стандартном SQL они не эквивалентны. INNER JOIN используется с ON пункт; CROSS JOIN используется иначе.

Вообще, круглые скобки могут быть проигнорированы в выражениях соединения, содержащих только операции внутреннего объединения. После раскрытия скобок и группировки операций налево, выражения соединения:

t1 LEFT JOIN (t2 LEFT JOIN t3 ON t2.b=t3.b OR t2.b IS NULL)   ON t1.a=t2.a

преобразовывает в выражение:

(t1 LEFT JOIN t2 ON t1.a=t2.a) LEFT JOIN t3    ON t2.b=t3.b OR t2.b IS NULL

Все же эти два выражения не эквивалентны. Чтобы видеть это, предположите что таблицы t1, t2, и t3 имейте следующее состояние:

В этом случае первое выражение возвращает набор результатов включая строки (1,1,101,101), (2,NULL,NULL,NULL), тогда как второе выражение возвращает строки (1,1,101,101), (2,NULL,NULL,101):

mysql> SELECT *    -> FROM t1    ->      LEFT
        JOIN    ->      (t2 LEFT JOIN t3 ON t2.b=t3.b OR t2.b IS
        NULL)    ->      ON t1.a=t2.a;+------+------+------+------+| a    | a    | b    | b    |+------+------+------+------+|    1 |    1 |  101 |  101 ||    2 | NULL | NULL | NULL |+------+------+------+------+mysql> SELECT *    -> FROM (t1 LEFT JOIN
        t2 ON t1.a=t2.a)    ->      LEFT JOIN t3    ->      ON t2.b=t3.b OR t2.b IS NULL;+------+------+------+------+| a    | a    | b    | b    |+------+------+------+------+|    1 |    1 |  101 |  101 ||    2 | NULL | NULL |  101 |+------+------+------+------+

В следующем примере работа внешнего объединения используется вместе с работой внутреннего объединения:

t1 LEFT JOIN (t2, t3) ON t1.a=t2.a

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

t1 LEFT JOIN t2 ON t1.a=t2.a, t3.

Для данных табличных состояний эти два выражения возвращают различные наборы строк:

mysql> SELECT *    -> FROM t1 LEFT JOIN (t2, t3) ON t1.a=t2.a;+------+------+------+------+| a    | a    | b    | b    |+------+------+------+------+|    1 |    1 |  101 |  101 ||    2 | NULL | NULL | NULL |+------+------+------+------+mysql> SELECT *    -> FROM t1 LEFT JOIN
        t2 ON t1.a=t2.a, t3;+------+------+------+------+| a    | a    | b    | b    |+------+------+------+------+|    1 |    1 |  101 |  101 ||    2 | NULL | NULL |  101 |+------+------+------+------+

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

Более точно мы не можем проигнорировать круглые скобки в правильном операнде левой работы внешнего объединения и в левом операнде правильной работы соединения. Другими словами мы не можем проигнорировать круглые скобки для внутренних табличных выражений операций внешнего объединения. Круглые скобки для другого операнда (операнд для внешней таблицы) могут быть проигнорированы.

Следующее выражение:

(t1,t2) LEFT JOIN t3 ON P(t2.b,t3.b)

эквивалентно этому выражению:

t1, t2 LEFT JOIN t3 ON P(t2.b,t3.b)

для любых таблиц t1,t2,t3 и любое условие P по атрибутам t2.b и t3.b.

Всякий раз, когда порядок выполнения операций соединения в выражении соединения (join_table) не слева направо, мы говорим о вложенных соединениях. Рассмотрите следующие запросы:

SELECT * FROM t1 LEFT JOIN (t2 LEFT JOIN t3 ON t2.b=t3.b) ON t1.a=t2.a  WHERE t1.a > 1SELECT * FROM t1 LEFT JOIN (t2, t3) ON t1.a=t2.a  WHERE (t2.b=t3.b OR t2.b IS NULL) AND t1.a > 1

Те запросы, как полагают, содержат эти вложенные соединения:

t2 LEFT JOIN t3 ON t2.b=t3.bt2, t3

Вложенное соединение формируется в первом запросе с левой работой соединения, тогда как во втором запросе это формируется с работой внутреннего объединения.

В первом запросе могут быть опущены круглые скобки: грамматическая структура выражения соединения продиктует тот же самый порядок выполнения для операций соединения. Для второго запроса не могут быть опущены круглые скобки, хотя выражение соединения здесь может быть интерпретировано однозначно без них. (В нашем расширенном синтаксисе круглые скобки в (t2, t3) из второго запроса требуются, хотя теоретически запрос мог быть проанализирован без них: у Нас все еще была бы однозначная синтаксическая структура для запроса потому что LEFT JOIN и ON играл бы роль левых и правых разделителей для выражения (t2,t3).)

Предыдущие примеры демонстрируют эти точки:

Запросы с вложенными внешними объединениями выполняются тем же самым конвейерным способом как запросы с внутренними объединениями. Более точно изменение алгоритма соединения вложенного цикла используется. Отзыв тем, какая алгоритмическая схема соединение вложенного цикла выполняет запрос. Предположите, что у нас есть запрос соединения более чем 3 таблицы T1,T2,T3 из формы:

SELECT * FROM T1 INNER JOIN T2 ON P1(T1,T2)                 INNER JOIN T3 ON P2(T2,T3)  WHERE P(T1,T2,T3).

Здесь, P1(T1,T2) и P2(T3,T3) некоторые условия объединения (по выражениям), тогда как P(t1,t2,t3) условие по столбцам таблиц T1,T2,T3.

Алгоритм соединения вложенного цикла выполнил бы этот запрос следующим способом:

FOR each row t1 in T1 {  FOR each row t2 in T2 such that P1(t1,t2) {    FOR each row t3 in T3 such that P2(t2,t3) {      IF P(t1,t2,t3) {         t:=t1||t2||t3; OUTPUT t;      }    }  }}

Нотация t1||t2||t3 означает "строку, созданную, связывая столбцы строк t1, t2, и t3." В некоторых из следующих примеров, NULL где имя строки кажется средства это NULL используется для каждого столбца той строки. Например, t1||t2||NULL означает "строку, созданную, связывая столбцы строк t1 и t2, и NULL для каждого столбца t3."

Теперь давайте рассматривать запрос с вложенными внешними объединениями:

SELECT * FROM T1 LEFT JOIN              (T2 LEFT JOIN T3 ON P2(T2,T3))              ON P1(T1,T2)  WHERE P(T1,T2,T3).

Для этого запроса мы изменяем образец вложенного цикла, чтобы добраться:

FOR each row t1 in T1 {  BOOL f1:=FALSE;  FOR each row t2 in T2 such that P1(t1,t2) {    BOOL f2:=FALSE;    FOR each row t3 in T3 such that P2(t2,t3) {      IF P(t1,t2,t3) {        t:=t1||t2||t3; OUTPUT t;      }      f2=TRUE;      f1=TRUE;    }    IF (!f2) {      IF P(t1,t2,NULL) {        t:=t1||t2||NULL; OUTPUT t;      }      f1=TRUE;    }  }  IF (!f1) {    IF P(t1,NULL,NULL) {      t:=t1||NULL||NULL; OUTPUT t;    }  }}

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

В нашем примере встраивается таблица внешнего объединения, выраженная следующим выражением:

(T2 LEFT JOIN T3 ON P2(T2,T3))

Отметьте, что для запроса с внутренними объединениями, оптимизатор мог выбрать различный порядок вложенных циклов, таких как этот:

FOR each row t3 in T3 {  FOR each row t2 in T2 such that P2(t2,t3) {    FOR each row t1 in T1 such that P1(t1,t2) {      IF P(t1,t2,t3) {         t:=t1||t2||t3; OUTPUT t;      }    }  }}

Для запросов с внешними объединениями оптимизатор может выбрать только такой порядок, где циклы для внешних таблиц предшествуют циклам для внутренних таблиц. Таким образом, для нашего запроса с внешними объединениями, только один порядок вложения возможен. Для следующего запроса оптимизатор оценит два различных nestings:

SELECT * T1 LEFT JOIN (T2,T3) ON P1(T1,T2) AND P2(T1,T3)  WHERE P(T1,T2,T3)

nestings - они:

FOR each row t1 in T1 {  BOOL f1:=FALSE;  FOR each row t2 in T2 such that P1(t1,t2) {    FOR each row t3 in T3 such that P2(t1,t3) {      IF P(t1,t2,t3) {        t:=t1||t2||t3; OUTPUT t;      }      f1:=TRUE    }  }  IF (!f1) {    IF P(t1,NULL,NULL) {      t:=t1||NULL||NULL; OUTPUT t;    }  }}

и:

FOR each row t1 in T1 {  BOOL f1:=FALSE;  FOR each row t3 in T3 such that P2(t1,t3) {    FOR each row t2 in T2 such that P1(t1,t2) {      IF P(t1,t2,t3) {        t:=t1||t2||t3; OUTPUT t;      }      f1:=TRUE    }  }  IF (!f1) {    IF P(t1,NULL,NULL) {      t:=t1||NULL||NULL; OUTPUT t;    }  }}

В обоих nestings, T1 должен быть обработан во внешнем цикле, потому что он используется во внешнем объединении. T2 и T3 используются во внутреннем объединении, так, чтобы соединение было обработано во внутреннем цикле. Однако, потому что соединение является внутренним объединением, T2 и T3 может быть обработан в любом порядке.

Обсуждая алгоритм вложенного цикла для внутренних объединений, мы опустили некоторые детали, воздействие которых на производительность выполнения запроса может быть огромным. Мы не упоминали так называемые "вниз продвинутые" условия. Предположите что наш WHERE условие P(T1,T2,T3) может быть представлен соединительной формулой:

P(T1,T2,T2) = C1(T1) AND C2(T2) AND C3(T3).

В этом случае MySQL фактически использует следующую схему вложенного цикла для выполнения запроса с внутренними объединениями:

FOR each row t1 in T1 such that C1(t1) {  FOR each row t2 in T2 such that P1(t1,t2) AND C2(t2)  {    FOR each row t3 in T3 such that P2(t2,t3) AND C3(t3) {      IF P(t1,t2,t3) {         t:=t1||t2||t3; OUTPUT t;      }    }  }}

Вы видите что каждый из conjuncts C1(T1), C2(T2), C3(T3) продвигаются из большинства внутреннего цикла к самому внешнему циклу, где это может быть оценено. Если C1(T1) очень рестриктивное условие, это условие pushdown может значительно сократить количество строк от таблицы T1 переданный к внутренним циклам. В результате время выполнения для запроса может улучшиться очень.

Для запроса с внешними объединениями, WHERE условие состоит в том, чтобы быть проверено только после того, как было найдено, что у текущей строки от внешней таблицы есть соответствие во внутренних таблицах. Таким образом оптимизация продвижения условий из внутренних вложенных циклов не может быть применена непосредственно к запросам с внешними объединениями. Здесь мы должны представить условное выражение вниз продвинутые предикаты, которые охраняют флаги, которые включаются, когда с соответствием встретились.

Для нашего примера с внешними объединениями с:

P(T1,T2,T3)=C1(T1) AND C(T2) AND C3(T3)

схема вложенного цикла, используя охраняла вниз продвинутые условия, похож на это:

FOR each row t1 in T1 such that C1(t1) {  BOOL f1:=FALSE;  FOR each row t2 in T2      such that P1(t1,t2) AND (f1?C2(t2):TRUE) {    BOOL f2:=FALSE;    FOR each row t3 in T3        such that P2(t2,t3) AND (f1&&f2?C3(t3):TRUE) {      IF (f1&&f2?TRUE:(C2(t2) AND C3(t3))) {        t:=t1||t2||t3; OUTPUT t;      }      f2=TRUE;      f1=TRUE;    }    IF (!f2) {      IF (f1?TRUE:C2(t2) && P(t1,t2,NULL)) {        t:=t1||t2||NULL; OUTPUT t;      }      f1=TRUE;    }  }  IF (!f1 && P(t1,NULL,NULL)) {      t:=t1||NULL||NULL; OUTPUT t;  }}

Вообще, вниз продвинутые предикаты могут быть извлечены из условий объединения такой как P1(T1,T2) и P(T2,T3). В этом случае вниз продвинутый предикат охраняет также флаг, который предотвращает проверку предиката для NULL- дополненная строка сгенерирована соответствующей работой внешнего объединения.

Отметьте, что доступ по ключу от одной внутренней таблицы до другого в том же самом вложенном соединении запрещается, если это вызывается предикатом от WHERE условие. (Мы могли использовать условный ключевой доступ в этом случае, но этот метод еще не используется в MySQL 5.6.)




Spec-Zone.ru - all specs in one place