Обзор статьи "The SQL Double Double"

Уважаемые читатели!

Статья, краткий пересказ которой предлагается вашему вниманию, не содержатся какие-либо открытия. Мне показалось полезным познакомить вас с ней только потому, что на особенности условия NOT EXISTS пользователи языка SQL редко обращают внимание. Конечно, потребность в формулировке запросов, имитирующих операцию реляционного деления, на практике возникает не слишком часто. Тем не менее, нужно быть готовым к этому. Заметка Шерила Ларсена содержит несколько хороших примеров с подробными разъяснениями. Надеюсь, что вам это пригодится.

С уважением, Сергей Кузнецов

The SQL Double Double

DB2 Magazine Online, Spring 1998
Оригинал статьи можно найти по адресу www.db2mag.com/98spLars.htm

Sheryl Larsen, всемирно известный исследователь, консультант и лектор, имеющий богатый практический опыт использования языка SQL

В условиях выборки языка SQL помимо прочего можно использовать подзапросы, или вложенные запросы. Имеется много типов подзапросов, но их основное назначение состоит в возможности подразделения наборов данных - выполнении процесса, называемого "реляционным делением". Для выполнения реляционного деления можно применять и соединения, но при определенных обстоятельствах подзапросы представляют более мощную альтернативу.

Проще всего понять подзапросы без корреляции. Они выполняются снизу вверх по одному разу на каждом уровне. Вот пример подзапроса без корреляции с использованием NOT EXISTS:


	SELECT A.COL1, A.COL2, A.COL6, A.COL7

	FROM TAB1 A

	WHERE NOT EXISTS

	  (SELECT 1

	   FROM TAB2 B

	   WHERE B.COL4 = :hv1)

При выполнении оператора проверяется существование значения :hv1 в столбце COL4 таблицы TAB2. Если такое значение не входит в состав значений COL4, SELECT верхнего уровня возвращает в результирующую таблицу значения столбцов COL1, COL2, COL6 и COL7 из всех строк таблицы TAB1. Если по меньшей мере одно значение :hv1 находится в COL4, SELECT верхнего уровня не выполняется и результатом является пустое множество строк или SQLCODE = +100. Первым выполняется нижний SELECT, возвращающий ответ true, если удается найти хотя бы одну строку, которая удовлетворяет условию B.COL4 = :hv1, и false, если ни одной такой строки найти не удается. Верхний запрос выполняется только в том случае, когда результат нижнего запроса есть false (поскольку используется NOT EXISTS).

Достаточно часто используются одиночные подзапросы с корреляцией. В подзапросе присутствует корреляция, если в нижнем SELECT имеется ссылка на столбец верхнего SELECT (одноуровневое распространение). Такие подзапросы легко распознать, если в разделах FROM применяются псевдонимы, и эти псевдонимы предшествуют любому имени столбца в разделе WHERE. Одиночные подзапросы с корреляцией выполняются в манере сверху-вниз-наверх по одному разу для каждой строки верхнего SELECT. Вот пример запроса с одиночным вложенным запросом и использованием псевдонимов A и B:


	SELECT A.COL1, A.COL2, A.COL6, A.COL7

	FROM TAB1 A

	WHERE A.COL7 = 'X'

	  AND NOT EXISTS

	    (SELECT 1

	     FROM TAB2 B

	     WHERE A.COL2 = B.COL4)

Выполнение этого запроса начинается с обнаружения первой уточненной строки верхнего запроса (WHERE COL7 = 'X'). После этого проверяется существование A.COL2 (с использованием значения этого столбца в первой уточненной строке TAB1) где-либо в стробце COL4 таблицы TAB2. Если значение A.COL2 не входит в состав набора значений COL4, верхний SELECT выбирает значения столбцов COL1, COL2, COL6 и COL7 таблицы TAB1 из первой уточненной строки. Если хотя бы одно значение A.COL2 обнаруживается в COL4, то верхний SELECT продвигается к следующей уточненной строке (WHERE COL7 = 'X'). Процесс продолжается до тех пор, пока верхний запрос не сможет обнаружить следующую уточненную строку. Тем самым, сначала выполняется верхний запрос, подготавливающий список строк, для которых будет проверяться условие существования, по одной строке за раз. Нижний запрос выполняется вторым, возвращая ответ true, если удается найти хотя бы одну строку, и false, если ни одна строка не удовлетворяет условию. Верхний запрос перемещает информацию текущей строки в окончательный результат только в том случае, когда результатом нижнего запроса является false (поскольку используется NOT EXISTS).

Двойные подзапросы с корреляцией нетипичны для разработчиков, использующих SQL. В частности, меньше 10% разработчиков на базе DB2 когда-либо видели такие запросы. Такие запросы выполняются в стиле сверху-вниз-в середину-вниз-в середину-наверх. Первым выполняется верхний запрос, который подготавливает список строк, для которых будет проверяться условие существования, по одной строке за раз. Затем выполняется средний запрос, который тоже подготавливает список строк, для которых будет проверяться условие существования, по одной за раз. Последним выполняется нижний запрос, как обычно, возвращающий true, если удается найти хотя бы одну строку, удовлетворяющую условию, и false, если не удается найти ни одной такой строки. Вот пример запроса с двойной корреляцией, в котором используются псевдонимы имен таблиц BLK1, BLK2 и BLK3:


	SELECT SNAME

	FROM S BLK1

	WHERE NOT EXISTS

	  (SELECT 1

	   FROM SP BLK2

	   WHERE BLK2.S# = 'S2'

	     AND NOT EXISTS

	       (SELECT 1

	        FROM SP BLK3

	        WHERE BLK3.S# = BLK1.S#

	          AND BLK3.P# = BLK2.P#))

Этот запрос выдает список поставщиков, поставляющих все детали, поставляемые поставщиком S2. Всем процессом управляет верхний список поставщиков (BLK1.S#). Один поставщик передается нижнему запросу. Далее выполняется средний запрос, формирующий список деталей, уточненных условием WHERE BLK2.S# = 'S2'. Одна деталь (BLK2.P#) передается от среднего нижнему запросу. Затем выполняется нижний запрос и возвращает true или false среднему запросу. Если результатом нижнего запроса является true, средний запрос передает нижнему другую деталь (BLK2.P#). Этот цикл продолжается до тех пор, пока либо не встретится результат false, либо не исчерпаются все детали. Если нет больше деталей, то это означает, что результат среднего запроса пуст и верхнему запросу передается false. Это является условием пропуска текущей строки верхнего запроса в окончательный результат. В результирующее множество попадет имя поставщика, поставляющего по меньшей мере все те детали, что и поставщик S2.

Если в какой-то момент результатом нижнего запроса является false, то среднему запросу разрешается выполняться, и он возвращает верхнему запросу true. По этому поводу верхний запрос выбирает следующего поставщика (BLK1.S#) и начинает заново весь цикл. Этот процесс позволяет найти всех поставщиков, которые поставляют по меньшей мере все детали, поставляемые поставщиком S2.

Двойная корреляция с двойным условием NOT EXISTS представляет мощный оператор реляционного деления. Рассмотрим следующий запрос:


	SELECT DISTINCT MAJOR             <----- Верхний запрос

	FROM PARTS T1

	WHERE NOT EXISTS

	  (SELECT *                       <----- Средний запрос

	   FROM QUE T2

	   WHERE NOT EXISTS

	     (SELECT *                    <----- Нижний запрос

	      FROM PARTS T3

	      WHERE T1.MAJOR=T3.MAJOR

	        AND T3.MINOR=T2.ID))

Таблицы имеют следующую структуру и содержание:


	Таблица PARTS       Таблица QUE

	10000000 строк        2 строки

	

	MAJOR MINOR              ID

	----- -----              --

	 10     1                 1

	 10     2                 3

	 10     3

	 11     2

	 11     3

	 12     1

	 12     3

	 12     4

В этом запросе выполняется деление всех значений столбца ID таблицы QUE на значения столбца MINOR таблицы PARTS. Запрос возвращает все значения столбца MAJOR, для каждого из которых набор значений столбца MINOR включает по меньшей мере все значения столбца ID таблицы QUE. Запрос вычисляется следующим образом: в верхнем запросе выбирается строка со значением столбца MAJOR, равным 10. Это значение передается в нижний запрос. Выполняется средний запрос, выбирается строка со значением столбца ID, равным 1, и это значение передается в нижний запрос. Поскольку результатом нижнего запроса является true, продолжает работать средний запрос и передает нижнему запросу значение id, равное 3. Нижний запрос опять дает значение true, но у среднего запроса больше нет строк, поэтому он вырабатывает значение true, и 10 помещается в окончательный результат. На следующем шаге нижний запрос получает значение MAJOR, равное 11, и значение ID, равное 3. Поскольку нижний запрос вычисляется в false, средний запрос вычисляется в true, и это не дает возможности поместить 11 в результирующий набор. Аналогичные рассуждения показывают, что 12 войдет в результирующий набор.

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


	SELECT SNAME

	FROM S BLK1

	WHERE NOT EXISTS

	  (SELECT 1

	   FROM IT BLK2, ORDERS O

	   WHERE O.STATE = 'CA'

	     AND O.ITEM = BLK2.ITEM

	     AND NOT EXISTS

	       (SELECT 1

	        FROM SI BLK3

	        WHERE BLK3.ITEM = BLK2.ITEM

	          AND BLK3.S# = BLK1.S#))

Эффективность выполнения запросов с двойной корреляцией и двойным NOT EXISTS зависит от возможности использования индексов, по крайней мере, для среднего и нижнего запросов. Если в верхнем запросе проверяется каждая строка таблицы, то наиболее подходит последовательный просмотр таблицы. Наличие индексов позволяет запросу передавать значения из списка без потребности предварительной полной материализации списка.

Конечно, чем больше значений true возвращает нижний запрос, тем медленнее выполняется весь запрос целиком. Поэтому, если вероятна выработка более 25% значений true, более эффективно использовать следующий синтаксис:


	SELECT P.MAJOR

	FROM PARTS P, QUE Q

	WHERE P.MINOR = Q.ID

	GROUP BY P.MAJOR

	HAVING COUNT(*) =

	  (SELECT COUNT(*)

	   FROM QUE)

Этот запрос выбирает все значения столбца MAJOR, для каждого из которых множество значений столбца MINOR совпадает с множеством значений столбца ID таблицы QUE. При наличии более 25% значений столбца MAJOR, удовлетворяющих условию запроса этот запрос будет выполняться более эффективно. Если вероятность нахождения "всего ____ что имеет _____ условие(я)" мала, то SQL Double Double является эффективным оператором реляционного деления.

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