Введение в системы БД (542480), страница 175
Текст из файла (страница 175)
( ЯР 301й Я ) ( Р1 ) Тем не менее, как было показано в разделе 17.4, приведенный ниже запрос дает тот же результат, хотя он вовсе не использует операции соединения (т.е. количество соединений в исходном запросе минимизировано). ЯР ( Р1 ) Поэтому следует заметить, что, поскольку алгоритмы сжатия табло, описанные в данной работе, учитывают все явно выраженные функциональные зависимости между атрибутами (см. главу 1О), они являются ограниченным примером метода сечангллческай оптимизации.
17.32.5ая!ч У., Уаппа1сак!з М. Еоц!ча1епсез Аглопя Ке1а!!опа) Ехргеааюпз чч1!Ь !Ье 1!пюп апг) 0йуегепсе Орега!огз 0 УАСМ. — Ос!оЬег, 1980. — 27, № 4, В этой статье идеи работы [17.31) расширены так, чтобы их можно было применять к запросам, используюшим операции объединения и вычитания. 17.33.Ьечу АХ., Мцглкй ЬБ., Вая!ч У. снегу Орйшнзабоп Ьу Ргедка!е Моче-Агоцпг( I! Ргос.
1979 АСМ Б!ОМО0 1п!. Сопб оп Чегу Ьагяе 0а!а Вазез. — Вап!!аяо, СЬ~1е, Бер!ешЬег. 1994. 17.34.5е!1пйег Р.О. е! а1. Ассеаз Ра!Ь Бе1ес!!оп !и а Ке[а!юпа1 0а!аЬазе $уз!егл 0 Ргос. !979 АСМ б! ОМО0 !п!егп, Сопб оп Мапаяешеп! оТ0ага. — Важоя, Маза., Мау-)опе, 1979. В этой важной статье обсуждаются некоторые методы оптимизации, используемые в прототипе системы Буз!еш К. Глава 17. Оптимизация 679 Замечание. Оптимизатор системы Яумеш К является предшественником оптимизатора СУБД )3В2. В [17.35) дана более подробная информация, специфическая для СУБД ОВ2. В системе Бумеш К запрос представляет собой Я Н:выражение, поэтому состоит из набора блоков ЕЕЬЕСТ-ГНОМ-ИНЕНЕ (блоков запроса).
Одни блоки могут быть вложены в другие. Оптимизатор Бумеш К сначала определяет порядок, в котором будут вычисляться блоки запроса, а затем пытается снизить общую стоимость запроса посредством выбора реализации с наименьшей стоимостью для каждого отдельного блока запроса. Обратите внимание, что данная стратегия (сначала — выбор порядка блоков, а затем — оптимизация отдельных блоков) означает, что конкретный план выполнения всего запроса никогда не рассматривается, и это приводит к "сужению пространства поиска" (см. замечания по этому поводу почти в конце раздела 17.3). Замечание.
В случае вложенных блоков оптимизатор вычисляет блоки во вложенном порядке, который указал пользователь, т.е. внутренний блок выполняется первым. В [17.39)-[!7.45) можно найти критику и дальнейшее обсуждение данной стратегии. Для каждого блока запроса существует два случая, которые следует рассмотреть (первый из них можно рассматривать как частный случай второго). 1. Для блока, в котором используется только выборка и (или) проекция единственного отношения, оптимизатор применяет статистические данные из каталога совместно с формулами (представленными в этой публикации) для немедленной оценки размера результата и стоимости низкоуровневых операций, а также для выбора стратегии построения выборки и (или) проекции. 2.
Для блоков, в которых используются два или больше отношений, соединенных с помощью операции Л01М, возможно, с локальными выборками и (или) проекциями отдельных о~ношений, оптимизатор, во-первых, трактует каждое отдельное отношение, как случай 1, и, во-вторых, определяет последовательность выполнения соединений. Зти две операции не являются независимыми одна от другой. Так, для отдельного отношения А может быть выбрана определенная стратегия доступа (например, на основе некоторого индекса), поскольку она позволяет получать кортежи из А в том порядке, который удобен для выполнения последующего соединения отношения А с другим отношением В. Соединения реализуются с помощью метода сортировки-слияния, поиска по индексу или метода последовательного просмотра.
В работе особое значение автор придал тому, что при вычислении, например, вложенного соединения (А Л01М В) Л01М С необязательно полностью вычислять вложенное соединение А ЛОХМ В перед соединением его результата и отношения С. Наоборот, каждый кортеж соединения А Л01М В сразу после вычисления передается процессу, соединяющему этот кортеж с кортежами из отношения С.
Поэтому нет необходимости материализовать отношение А Л01М В полностью. (Зта идея конвейерной обработки кратко обсуждалась в главе 3, раздел 3.2. См. также [17.181, [17.601,) Зта работа включает и некоторые соображения о стоимости самого процесса оптимизации. Для соединения двух отношений стоимость приблизительно равна стоимости 5 — 20 операций выборки. При многократном выполнении оптимизированного запроса это довольно незначительные расходы. (Отметим, что система Буззеш К, как и 680 Часть )'. Дополнительные аспекты СУБД РВ2, является компилирующей, поэтому однажды оптимизированный запрос может выполняться сотни и даже тысячи раз.) В работе утверждается, что оптимизация сложных запросов требует "всего нескольких тысяч байтов пространства для хранения и нескольких десятых долей секунды" на компьютере 1ВМ Бумегп 370 Моде! 158.
"Соединение восьми таблиц было оптимизировано за несколько секунд." 17.35.СЬепй ).М., Еооз!еу С.К., БЬ!Ьагп!уа А., зЧопЬ)п8!оп Р Б. !ВМ РАТАВАБЕ 2 Реггоппапсе; Рез!8п, 1гпр!етепсайоп, апг) Тцп!п8!!!ВМ Буз. 1. — 1984. — 23, № 2. Здесь содержится краткое описание тактики оптимизации в СУБД РВ2 (в первой версии этой системы): методы преобразования запросов, обработка вложенных блоков запроса, методы соединения, выбор пути доступа и обработка индексов. Замечание. В эту работу также включен интересный материал о других аспектах работы СУБД РВ2, влияющих на ее производительность. 17.36.%оп8 Е., Уоцяаеб К. Оесогпровйюп — А 5!гаге8у гое 0цегу Ргосезз!п8 0 АСМ ТОРЕ. — БергетЬег, 1976.
— 1, № 3. 17.37. Уоцьзеб К., %оп8 Е. ()негу Ргосезяпб 1и а Ее!а!!опа1 Оа!аЬазе Мапайеглепг Бузгегп Р Ргос. 5гй! и!егп. Сопб оп Чегу 1.агйе Рага Вазез. — Кю 0е )апе!го, Вгаг)1, БергегпЬег, 1979. 17.38.йозче 1..А., 5!опеЬга1сег М. ТЬе Согпгпегс!а! !ХСКЕБ Ерйойце д М. БгопеЬга1гег (ед.). ТЬе 1ХОКЕБ Рарегз: ТЬе Апагогпу ог" а Ке1айопа! РагаЬазе Мапайегпеп! Бумет.— Кеаг)!п8, Маза.: Аг!Жзоп-%ез!еу, 1986. Коммерческая СУБД Сотгпегс!а1!ХОКЕБ — это программный продукт, полученный из прототипа Нп!чегз!гу!ХСКЕБ (Университетская система). Ниже перечислены некоторые различия между оптимизаторами систем Сотгпегс)а! !ХбКЕБ и 1)п!чеггйгу !ХОКЕБ.
!. Университетский оптимизатор использует инкрементное планирование, т.е. определяет, что нужно сделать сначала, и делает это, затем определяет, что делать дальше, исходя из размера полученного промежуточного результата, и т.д. Коммерческий оптимизатор определяет полный план перед началом выполнения на основе оценок размеров промежуточных результатов.
2. Университетский оптимизатор обрабатывает запросы с двумя переменными (например, соединения) с помощью метода подстановки кортежей, обсуждавшегося в разделе 17.6. Коммерческий оптимизатор поддерживает несколько мощных методов обработки подобных запросов, включая, в частности, метод сортировки-слияния, описанный в разделе 17.7.
3. Коммерческий оптимизатор поддерживает более сложный набор статистических показателей по сравнению с университетским оптимизатором. 4. Университетский оптимизатор выполняет инкрементное планирование (см. п. 1). Коммерческий оптимизатор выполняет более обширный поиск.
Тем не менее поиск прекращается, если на оптимизацию будет затрачено время, превышающее наилучшую оценку времени выполнения запроса (в противном случае выполнение оптимизации не даст никаких преимуществ). 5. Коммерческий оптимизатор рассматривает все возможные комбинации индексов, все возможные последовательности соединения и "все доступные методы выполнения соединения — сортировку-слияние, частичную сортировку- слияние, поиск по хеш-таблице,15АМ-поиск, поиск по В-дереву и метод последовательного просмотра" (см. раздел 17.7). Глава 17. Оигпимцзация 681 17.39.К||в %. Оп Орй|п|я!пй ап БОЬ-Ь!Ке Неа|ег! Овесу Н АСМ ТОРЯ. — Бер|егпЬег, 1982.
— 7, № 3. См. комментарий к (17.431. 17.40.К!еая1!п8 Ч|г. Оп Бе|пап|!с Кееб апг! ЕЖс!епг Ргосеаз!п8 оГ Со|те!айоп Оцепез чч!1Ь АЕЕге8а|ез 0 Ргос. 1!гй (псегп. СопГ. оп Чету 1.агйе Рага Вазез. — Б1осКЬо1щ, Бччег(еп, АцЕцаг, 1985. См. комментарий к (17.431. 17.41. Оапз(ц Р.А., %оп8 Н.К.Т.
Орг!гп!яапоп оР 1чеягег( Б| Ь Оцепез Кеч!з!гег) Р Ргос. 1987 АСМ Б!ОМОР !п|егп. Сопб оп Мапа ел|ел| оТРага. — Бап Ггапс!зйо, Са(1~., Мау, 1987. См. комментарий к (17.43). 17.42.Обп|ег чоп Вц(гя!п8з1оечгеп. Тгапа!айпй апг( Орбщпйп8 БОЬ Оцег!ез Нач!п8 АЕЕгеЕагея Н Ргос. 13|И 1п|егп. Сопб оп Чету (.аг8е Раса Ваяеь. — Вг!ЕЬюп, Еп81апг(, Берге|пЬег, 1987. См. комментарий к [17.43].
17.43. Мцга!йгг!яйла М. 1|пргочег( ()ппезг(пй А!8опгйгпя гог 5о!и АЕЕгейа|е БОЬ Оцег!ея д Ргос. 18|И 1п|егп. Сопй оп Чету 1.агЕе Рага Вааек — Чапсоцчег, Сапа|(а, Ац8цай 1992. Язык БОЬ позволяет создавать "вложенные подзапросы", т.е. блоки ЯЕЬЕСТ-РКОМИНЕКЕ, вложенные внутрь других подобных блоков. Эта конструкция порождает некоторые трудности при реализации. Рассмотрим следующий Я,>Ь-запрос (" Определить имена поставщиков детали с номером 'Р2'"), на который далее будем ссылаться, как на запрос 01. ЯЕЬЕСТ Я.ЯМКМЕ РКОМ Я ИНЕКЕ Я.Я$ 1М ( ЯЕЬЕСТ ЯР.Я$ РКОМ ЯР ИНЕКЕ ЯР.Р$ = 'Р2' ) 1 В системе Буагещ К (17.34) этот запрос будет реализован следующим образом. Сначала будет вычислен внутренний блок и создана временная таблица Т, содержащая номера требуемых поставщиков.
После этого кортеж за кортежем будет проверена вся таблица Я и для каждого выбранного из нее кортежа будет просматриваться таблица Т с целью определения, содержится ли в ней соответствующий номер поставщика. Эта стратегия достаточно неэффективна (поскольку таблица Т не имеет индекса). Теперь рассмотрим запрос О2. ЯЕЬЕСТ Я.ЯИКМЕ ГКОМ Я, ЯР ИНЕКЕ Я.Я$ = ЯР.Я$ КИО ЯР.Р$ = 'Р2' Легко установить, что он семантически идентичен предыдущему, но система Буя|е|п К проанализирует дополнительную стратегию реализации данного запроса.
В частности, если таблицы Я и ЯР окажутся физически сохраненными в последовательности номеров поставщиков, то система применит слияние, которое будет вы- б82 Часупь 'г'. Дополнительные аспекты полняться весьма эффективно. Предположив, что два рассмотренных выше запроса логически эквивалентны, но второй вариант более удобен с точки зрения эффективности реализации, мы придем к выводу, что возможность преобразования запросов, подобных 01, в запросы, подобные 02, требует более глубокого изучения. Эта возможность и является предметом обсуждения в [17.39] — [17.45].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
