Введение в системы БД (542480), страница 173
Текст из файла (страница 173)
выборки), которые можно обрабатывать в основной памяти. Автор заявляет, что, исходя из наблюдаемого снижения цен на первичную память, методы на основе хеширования могут стать одними из лучших. 17.13.Хейг! М., Ре!айацс б. ОВспЬойте )о!и: А Ьсезт А!8опсйгп Гог 1олцпй Ке!айопз Д АСМ ТООЫ вЂ” ОесетЬег, 1991. — 16, № 4. Здесь представлен другой метод соединения, использующий принцип "разделяй и властвуй", который "...базируется на идее о том, что... не нужно полностью сортировать оба отношения... Достаточно отсортировать одно отношение полностью, а другое — лишь частично, избежав таким образом расходов на выполнение полной сортировки второго отношения". При частичной сортировке рассматриваемая переменная-отношение разбивается на последовательность неупорядоченных подмножеств кортежей Р1, Р2, ..., Рп (похоже на метод Сакко (Бассо) [17.11], за исключением того, что в методе Сакко используется хеширование вместо сортировки), обладающих следующим свойством: МРЛ[Р[8]) < М1Н(Р[Ь+1)) лля всех 8 (1, 2, ..., л-1).
Утверждается, что данный метод работает эффективнее метода сортировки-слияния. 17.14.бгаеГе б., Со!е К.Ь. Гам А18опсйгпз Гог Оп!тегза! ОоапссТссас!оп !и 1.агйе ОасаЬазез 0 АСМ ТООЫ вЂ” 1нпе, 1995. — 20, № 2. Квантор всеобщности (РОКлЬЬ) в языке БЯЬ непосредственно не поддерживается, а потому он не поддерживается и в современных коммерческих СУБД, хотя он чрезвычайно важен для формулировки широкого класса запросов. В этой статье описываются и сравниваются "три известных алгоритма и один недавно предложенный алгоритм реляционного деления, которое является алгебраическим оператором, включающим квантор всеобщности'. В ней также показано, что новый алгоритм работает "с той же скоростью, с какой выполнение хешированного полусоединения позволяет получить оценку значения квантора существования для тех же отношений". Помимо всего прочего, авторы делают вывод, что квантор РОКАЬЬ необходимо включить в пользовательский язык, так как большинство оптимизаторов "не распознает его косвенные формулировки на языке Б(;Н.", 17.15.Всцоп О., Ое%!ц Охй Оцр!квасе Кесогс[ Е!лп!пасюп сп 1.аг8е Оаса Г!!ез д АСМ ТОВО.
— )цпе, ! 983, — 8, № 2. Традиционный метод исключения кортежей-дубликатов состоит в сортировке записей с последующим последовательным просмотром. Данная работа предлагает альтернативное решение, более эффективное для файлов большого размера. 17.16. Ыпппеп О., БЬе[с!са Е., Майсеглнз Т. Гцпс!агпепса! Тесйп!с[вез Гог Оп!ег Орс!ппглс!оп /! Ргос. 1996 АСМ ЫОМОО 1пс. СопГ оп Мапайегпепс оГ Оаса. — Мопсгеа[, Салаг[а, 1цпе, ! 996. В этой работе прелставлены методы оптимизации или исключения сортировок. Они частично основаны на работе Дарвена [1С).6] и именно в таком виде реализованы в СУБД ОВ2. 17.17.Мапйц О.Ы, Ка)айора!ап Ы, 1лпбзау В.б.
Арргохнпасе Мес)!апз апс[ О!Бег ()цап!!с!ез сп Опе Раьз апс[ зк!сЬ Е!гп!сес! Мегпогу 7 Ргос. 1998 АСМ Б!ОМОО 1пс. СопГ. оп Мапа8ешепс оГ Раса. — Беац!е, %азЬ,, 1цпе, 1998. Глава 17. Олтимизас[ия 673 17.18.$ппгЬ Л.М., Уеп-Тапй СЬап» Р. Оргпп!х!п8 гЬе РегГоппапсе об а Ке1абопа1 А!»еЬга ОагаЬазе!пгегбасе 0 САСМ. — ОсгоЬег, 1975. — 18, № 10. Описан алгоритм, использовавшийся в языке»бшагг Оцегу 1псегбасе Гог а Ке!агюпа1 А1»еЬга" (8 13! КАЕ). Этот алгоритм включает следующее.
° Преобразование исходного алгебраического выражения в эквивалентную, но более эффективную последовательность операций в соответствии с принципами, обсуждавшимися выше, в разделе ! 7.4. ° Привязка отдельных операций в преобразованном выражении к определенным процессам и использование параллельной и конвейерной обработок для выполнения операций. ° Координация порядка сортировки в промежуточных результатах, передаваемых между процессами. ° Использование индексов и попытки локализации страничных ссылок. Эта статья была одной из первых работ, посвященных преобразованиям выражений. 17.19.Най Р.А.Ч. Орг!ш!хаг!оп об а 8!п81е Ке!а!юла! Ехргезз!оп !и а Ке1агюпа! Вага Вазе Бузгегл 1/ 1ВМ 3.
К кО. — Мау, 1976. — 20, № 3. Описаны некоторые методы оптимизации, используемые в системе РКТЧ !6.9$ которая, как и язык Я( 13!КА1. [17.18], начинает обработку запроса с преобразования данного алгебраического выражения в некоторую более эффективную форму. Особенностью системы РКТЧ является то, что она не вычисляет каждое выражение автоматически, как только оно будет получено. Вместо этого выражения комбинируются с полученными ранее в более сложное выражение и вычисление откладывается до последнего момента (см. обсуждение пошаговой формулировки запроса в главе 6, раздел 6.5).
Таким образом, "отдельное реляционное выражение*' (из заголовка статьи) на самом деле представляет целую последовательность операций пользователя. Данный метод оптимизации подобен методу языка ЯЯ)!КА1„но в некоторых перечисленных ниже случаях работает лучше. ° Выборка выполняется настолько рано, насколько это возможно. ° Последовательность проекций комбинируется в одну операцию проекции. ° Избыточные операции исключаются. ° Выражения, нспользуюц!ие пустые отношения и тривиачьные условия, упрощшотся. ° Общие выражения выносятся за скобки.
В заключении работы изложены результаты некоторых экспериментов, а также указаны направления дальнейших исследований. 17.20. Заг)се М., КосЬ 3. Капйе Хезг!п8; А Гам МегЬод со Еча1цасе Оцапббед Оцег!ез П Ргос. ! 983 АСМ Б!ОМОВ !пгегп. Сопб оп Мапабегпепг об Оага. — Бап )озе, Сай)» Мау, 1983. Предложен вариант реляционного исчисления, в котором допускается применение некоторых дополнительных (и полезных) правил синтаксического преобразования. Представлены алгоритмы вычисления выражений в описанном исчислении. (Это исчисление очень напоминает исчисление кортежей, упомянутое в главе 7.) Кроме того, описана оптимизация в предложенном исчислении отдельного класса выражений, называемых "точными вложенными выражениями".
Изложены методы преобразования в точные выражения относительно сложных за- 674 Часть И Дополнитетьные аспекты просов (в частности, запросов, использующих квантор РОНАЬА). Авторы показывают, что в точные выражения можно преобразовать большое количество запросов, используемых на практике. 17.21.СЬацс!Ьаг! Я., ЯЫш К. 1пссцг)!пй Огоцр-Ву !и Овесу Орс!гп!гас!оп !! Ргос. 201Ь 1пс. Сопб опмету Ьагйе Васа Вазез.
— Яапйайо, СЫ!е, ЯерсегпЬег, 1994. 17.22.Ма!с!поцсЬ! А., Тегц1са М., Кйа1сапц! Н., Ас!асЬ! я. ТЬе Орйппгайоп я!гасе у Сог Овесу Еча!цайоп !и КВВ/Ч1 д Ргос. 71Ь 1псепс. Сопб оп Чесу Еагйе Васа Вазез — Саппез, Ргапсе, ЯерсешЬег, 1981. Система КОВШ! является прототипом будущего программного продукта А!МЖВВ компании Рц]!сзц (это ЯО!.-система), В публикации описаны приемы оптимизации, используемые в данном прототипе. Онн кратко сравниваются с аналогичными приемами, используемыми в прототипах систем 1ЬСОИЕЯ и Яуыет К. Один из приемов является новым и состоит в применении динамически полученных значений функции ИАХ и И1И для выполнения дополнительных выборок. Подобный прием приводит к упрощению процесса выбора порядка соединения и повышает производительность самой операции соединения.
В качестве простого примера лля последнего утверждения предположим, что нужно соединить отношения поставщиков Я и деталей Р по атрибуту С1ТХ. Сначала отношение Я сортируется по атрибуту Я. С1Т1. В процессе сортировки для атрибута Я.С1ТХ определяются значения функций ИАХ и И1И; обозначим их через Н16Н и ЪОН соответственно. Тогда для уменьшения количества кортежей отношения Р, которые потребуется проверять в процессе выполнения соединения, можно использовать следующую выборку. 1. АОН < Р.С1ТТ АИО Р.С1ТТ < Н16Н 17.23.Р!гаЬезЬ Н., Не!1егзсесп 1.М., Назап %.
ЕхсепсйЫе Кц!е Вазес! Овесу Иепт!се Орс!ш!гас!оп 'а ЯсагЬцгзс П Ргос, 1992 АСМ Я!ОМОВ 1псегп. Сопб оп Мапайешепс Васа. — Яап Всейо, Са!!Т., )цпе, 1992. Как отмечалось в разделе 17.1, лля преобразования выражений используется еше одно название — перезапись запросов (с!вегу гешгпе).
По мнению авторов, несколько неожиданно то, что в современных реляционных СУБД мало внимания уделяется такому преобразованию (по крайней мере, по состоянию на 1992 год). В работе описан механизм преобразования выражений прототипа системы ЯсагЬцгсп корпорации 1ВМ [17.50], [25.14], [25.17], [25.21], [25.22]. Пользователи с соответствующей квалификацией могут в любое время добавить в систему новые правила преобразования выражений (вот почему в заголовке статьи указано слово "расширяемый" — "ехсепз!Ые"). 17.24. Мцпцс1с 1.Я., Р!п1сеВсе!и ЯН., Р!гаЬезЛ Н., КашайпзЬпап К. Маус В Ке!ечапс /! Ргос.
1990 АСМ Я!ОМОВ!псегп. Сопб оп Мала егпепс Васа. — Ас!ансис Спу, ЬСН., Мау, 1990. Неудачный термин 7шай!с" (" волшебный" ) используется в данной публикации для ссылок на метод оптимизации, косорый изначально создавался для обработки запросов (в частности, рекурсивных), записанных на языке логических баз данных Васа!о8 (глава 23). Данная работа расширяет этот подход до условно-реляционных систем, утверждая на основе экспериментальных измерений, что он часто эффективнее традиционных приемов оптимизации (заметьте, что запрос не обязательно должен быть рекурсивным, чтобы можно было применить к нему описанный 675 Глава 1 7.
Осслсилсизацил метод). Основная идея метода состоит в декомпозиции данного запроса на несколько меньших запросов, которые определяют "вспомогательные отношения" (нечто похожее на метод декомпозиции запросов, рассмотренный в разделе 17.б) таким образом, что их можно использовать для фильтрации кортежей, не относя- шихся к данному запросу.
Ниже приведен пример запроса, который базируется на примере из данной работы. И := ЕХ.ЕНАМЕ МНЕНЕ ЕХ.ЛОВ = 'С1егХ' йМО ЕХ.ЯАР > АЧО ( Еу ННЕНЕ ЕХ.РЕНТ)) = ЕХ.РЕРТ(), ЯАР ) ) (" Выбрать имена клерков ('С1егК'), чья зарплата больше средней зарплаты по отделу.") Если этот запрос выполнять "прямолинейно" (т.е. именно так, как он записан), система будет проверять отношение, содержащее данные о сотрудниках, кортеж за кортежем, пока не вычислит среднюю зарплату для каждого отдела, в котором работает более одного клерка. Традиционный оптимизатор разобьет исходный запрос на два запроса меньшего размера.
Т! := ( ЕХ.ОЕРТ)), АЧО ( ЕУ ИНЕНЕ ЕУ.ОЕРТ)) = ЕХ.РЕРТ)) БАР ] йБ АВАР ) Т2 := ЕМР.ЕНАМЕ ННЕКЕ ЕМР.ЛОВ = 'С1егй' АМР ЕХ1ЯТЯ Т1 ( ЕМР.РЕРТФ = Т).РЕРТ() АХР ЕМР.БАРАНУ > Т1.АВАР ) Теперь ни для одного отдела средняя зарплата не будет вычисляться больше одного раза, но будут обрабатываться некоторые не относящиеся к запросу кортежи, в частности кортежи с данными об отделах, в которых клерки вовсе не работают.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
