Диссертация (Оптимизация обработки вложенных запросов в многопроцессорной базе данных), страница 4

Обработка оптимизации вложенных запросов1.2.1. Вложенные подзапросыВложенный подзапрос - это подзапрос, заключенный в круглые скобки ивложенный в WHERE (HAVING) фразу предложения SELECT или других предложений,использующих WHERE фразу. Вложенный подзапрос может содержать в своей WHERE(HAVING) фразе другой вложенный подзапрос и т.д. Вложенный подзапрос создается длятого, чтобы при отборе строк таблицы, сформированным основным запросом, можнобыло использовать данные из других таблиц.Существуют простые и коррелированные вложенные подзапросы. Они включаютсяв WHERE (HAVING) фразу с помощью условий IN, EXISTS или одного из условийсравнения ( = | <> | < | <= | > | >= ). Простые вложенные подзапросы обрабатываютясистемой "снизу вверх". Первым обрабатывается вложенный подзапрос самого нижнегоуровня. Множество значений, полученное в результате его выполнения, используется приреализации подзапроса более высокого уровня и т.д.Запросыскоррелированнымивложеннымиподзапросамиобрабатываютсясистемой в обратном порядке.

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

Простые вложенные подзапросыПростые вложенные подзапросы используются для представления множествазначений, исследование которых должно осуществляться в каком-либо предикате IN, чтоиллюстрируется в следующем примере: выдать название и статус поставщиков продукта сномером 11, т.е. Микропроцессор.Результат:SELECT Название, СтатусFROMНазвание СтатусПоставщикиWHERE ПС IN(SELECT ПСFROMПоставкиWHERE ПР = 11 );КОМПДилерЭВМПроизводительСТЕЛАОАОВЫМПЕЛ ЗАОПри обработке полного запроса система выполняет прежде всего вложенныйподзапрос. Этот подзапрос выдает множество номеров поставщиков, которые поставляютпродукт с кодом ПР = 11, а именно множество (1, 5, 6, 8). Поэтому первоначальный запросэквивалентен такому простому запросу:SELECT Название, СтатусFROMПоставщикиWHERE ПС IN (1, 5, 6, 8);Подзапрос с несколькими уровнями вложенности можно проиллюстрировать натом же примере.

Пусть требуется узнать не поставщиков продукта 11, а поставщиковмикропроцессоров, являющихся продуктом с номером 11. Для этого можно дать запросSELECT Название, СтатусFROMПоставщикиWHERE ПС IN(SELECT ПСFROMПоставкиWHERE ПР IN(SELECT ПРFROMПродуктыWHERE Продукт = Микропроцессор));В данном случае результатом самого внутреннего подзапроса является толькоодно значение (11). Как уже было показано выше, подзапрос следующего уровня в своюочередь дает в результате множество (1, 5, 6, 8).

Последний, самый внешний SELECT,вычисляет приведенный выше окончательный результат. Вообще допускается любаяглубина вложенности подзапросов.Тот же результат можно получить с помощью соединенияSELECT Название, СтатусFROMПоставщики, Поставки, ПродуктыWHERE Поставщики.ПС = Поставки.ПСANDПоставки.ПР = Продукты.ПРANDПродукт = Микропроцессор;При выполнении этого компактного запроса система должна одновременнообрабатывать данные из трех таблиц, тогда как в предыдущем примере эти таблицыобрабатываются поочередно.

Естественно, что для их реализации тебуются различныересурсы памяти и времени.1.2.3. Использование одной и той же таблицы во внешнем ивложенном подзапросеВыдать номера поставщиков, которые поставляют хотя бы один продукт,поставляемый поставщиком 6.Результат:SELECT DISTINCT ПСПСFROM Поставки1WHERE ПР IN(SELECT ПРFROMПоставкиWHERE ПС = 6);3568Отметим, что ссылка на Поставки во вложенном подзапросе означает не то жесамое, что ссылка на Поставки во внешнем запросе. В действительности, два имениПоставки обозначают различные значения. Чтобы этот факт стал явным, полезноиспользовать псевдонимы, например, X и Y:SELECT DISTINCT X.ПСFROM Поставки XWHERE X.ПР IN(SELECT Y.ПРFROMПоставки YWHERE Y.ПС = 6 );Здесь X и Y √ произвольные псевдонимы таблицы Поставки, определяемые вофразе FROM и используемые как явные уточнители во фразах SELECT и WHERE.Напомним, что псевдонимы определены лишь в пределах одного запроса.1.2.4.

Вложенный подзапрос с оператором сравнения, отличным от INВыдать номера поставщиков, находящихся в том же городе, что и поставщик сномером 6.Результат:SELECT ПСПСFROM1ПоставщикиWHERE Город =(SELECT ГородFROMПоставщики46WHERE ПС = 6 );В подобных запросах можно использовать и другие операторы сравнения (<>, <=,<, >= или >), однако, если вложенный подзапрос возвращает более одного значения и неиспользуется оператор IN, будет возникать ошибка.1.2.5. Коррелированные вложенные подзапросыВыдать название и статус поставщиков продукта с номером 11.SELECT Название, СтатусFROMПоставщикиWHERE 11 IN(SELECT ПРFROMПоставкиWHERE ПС = Поставщики.ПС );Такой подзапрос отличается от рассмотренного в п.1.2.2.

тем, что вложенныйподзапрос не может быть обработан прежде, чем будет обрабатываться внешнийподзапрос. Это связано с тем, что вложенный подзапрос зависит от значения Поставщики.ПС а оно изменяется по мере того, как система проверяет различные строки таблицыПоставщики. Следовательно, с концептуальной точки зрения обработка осуществляетсяследующим образом:1. Система проверяет первую строку таблицы Поставщики. Предположим, что этострока поставщика с номером 1. Тогда значение Поставщики.ПС будет в данныймомент имеет значение, равное 1, и система обрабатывает внутренний запрос( SELECT ПРFROM ПоставкиWHERE ПС = 1 );получая в результате множество (9, 11, 12, 15).

Теперь система может завершитьобработку для поставщика с номером 1. Выборка значений Название и Статус для ПС=1(КОМП и Дилер) будет проведена тогда и только тогда, когда ПР=11 будет принадлежатьэтому множеству, что, очевидно, справедливо.2. Далее система будет повторять обработку такого рода для следующего поставщикаи т.д. до тех пор, пока не будут рассмотрены все строки таблицы Поставщики.Подобные подзапросы называются коррелированными, так как их результатзависит от значений, определенных во внешнем подзапросе. Обработка коррелированногоподзапроса, следовательно, должна повторяться для каждого значения извлекаемого извнешнего подзапроса, а не выполняться раз и навсегда.Рассмотрим пример использования одной и той же таблицы во внешнемподзапросе и коррелированном вложенном подзапросе.Выдать номера всех продуктов, поставляемых только одним по-ставщиком.Результат:ELECT DISTINCT X.ПРX.ПРFROM Поставки X17WHERE X.ПР NOT IN(SELECT Y.ПРFROMПоставки YWHERE Y.ПС <> X.ПС );Действие этого запроса можно пояснить следующим образом: "Поочередно длякаждой строки таблицы Поставки, скажем X, выделить значение номера продукта (ПР),если и только если это значение не входит в некоторую строку, скажем, Y, той жетаблицы, а значение столбца номер поставщика (ПС) в строке Y не равно его значению встроке X".Отметим, что в этой формулировке должен быть использован по крайней мереодин псевдоним - либо X, либо Y.1.2.6.

Запросы, использующие EXISTSКвантор EXISTS (существует) - понятие, заимствованное из формальной логики. Вязыке SQL предикат с квантором существования представляется выражением EXISTS(SELECT * FROM ...).Такое выражение считается истинным только тогда, когда результат вычисления"SELECT * FROM ..." является непустым множеством, т.е. когда существует какая-либозапись в таблице, указанной во фразе FROM подзапроса, которая удовлетворяет условиюWHERE подзапроса.

(Практически этот подзапрос всегда будет коррелированныммножеством.)Рассмотрим примеры. Выдать названия поставщиков, поставляющих продукт сномером 11.Результат:SELECT НазваниеНазваниеFROM ПоставщикиКОМПWHERE EXISTSЭВМ(SELECT *FROMСТЕЛАПоставкиВЫМПЕЛWHERE ПС = Поставщики.ПСANDПР = 11 );Система последовательно выбирает строки таблицы Поставщики, выделяет из нихзначения столбцов Название и ПС, а затем проверяет, является ли истинным условиесуществования, т.е. существует ли в таблице Поставки хотя бы одна строка со значениемПР=11 и значением ПС, равным значению ПС, выбранному из таблицы Поставщики.