Введение в системы БД (542480), страница 172
Текст из файла (страница 172)
17.3. 669 Глава 1 7. Оптимизация 17.4. Огас)е О. Оцегу Еча1цайоп Тесйп!г)цез Бог Еагйе ОагаЬазез д АСМ Сощр. Бцгч.— )цпе, 1993. — 25, № 2. Еше одно прекрасное и более новое учебное пособие с обширным списком рекомендуемой литературы. "В этом обзоре представлены основы проектирования и реализации инструментов выполнения запросов... В нем описан широкий круг практических методов оценки запросов... включая итеративное выполнение сложных планов выполнения запросов, дуализм алгоритмов нахождения соответствия между множествами на основе сортировки и хеширования, типы параллельного выполнения запросов и их реализацию, а также специальные операторы для новых областей применения баз данных." Рекомендуется прочесть эту работу.
17.5. Ра1еппо Г.Р. Л Рага Вазе ЯеагсЬ РгоЫеш 0 ).Т. Тодд (ед.), 1пГоппайоп Яумешз: С01ХЯ 1й. — 14еж 'г'ог1с, Ы,'з",; Р1епцш Ргезз, 1974. Одна из наиболее ранних работ по опзимизации (фалтически уже ставшая классической). Начиная с произвольного выражения реляционного исчисления, в этой работе сначала к нему применяется алгоритм приведения Кодда для преобразования выражения в эквивалентное алгебраическое выражение (см.
главу 7), а затем вводится несколько усовершенствований этого алгоритма, включая перечисленные ниже. ° Никакой кортеж не может извлекаться дважды. ° Ненужные значения удаляются из кортежа во время его извлечения. Здесь под ненужными значениями подразумеваются либо значения атрибутов, не упомянутых в запросе, либо значения, используемые только лля организации выборки.
Этот процесс эквивалентен проекции отношения по некоторым "нужным" атрибутам, а потому позволяет сократить не только пространство, выделяемое для каждого кортежа, но и количество кортежей, с которыми ведется работа (в общем случае). ° Метод, используемый для создания результирующего отношения, основан на принципе наименьшего роста, поэтому оно растет очень медленно.
Данный метод приводит к сокращению количества выполняемых сравнений и объема памяти лля хранения промежуточных результатов. ° Для создания соединений применяется эффективный метод, основанный, вопервых, на динамическом разложении значений, используемых в соединяемых членах (например таких, как Я.Я$ = ЯР.Я1), на нолусоединения, которые фактически являются некоторой разновидностью динамически создаваемого вторичного индекса (полусоединения Палермо отличаются от полусоедннеиий. описанных в главе 6), и, во-вторых, на использовании внутреннего представления каждого соединения, называемого косвенным соединениеи (1пг11гес! )о1п), в котором для идентификации кортежей — участников соединения используются внутренние идентификаторы кортежей.
Эти методы предназначены для сокрашения количества просмотров, необходимых для выполнения соединения, за счет получения гарантии, что соединяемые кортежи каждого члена соединения логически упорядочены в соответствии со значениями атрибутов соединения. Благодаря этому допускается динамическое определение "наилучшей" последовательности операций доступа к нужным отношениям. 17.6. Огау 3. (ед,). ТЬе ВепсЬшагк НапдЬоок Гог РагаЬазе апд Тгапзасгюп Ргосезз1пй Яузгешз (2пд ед111оп), — Яап Ггапс1зсо, СаИГ.: Могйап Кацбпалп, 1993. Совет по обработке транзакций (Тгапзасгюп Ргосевмпй Соцпсй — ТРС) является независимой организацией, которая на протяжении ряда лет разработала несколько тестов, фактически принятых в качестве промышленного стандарта.
В данной книге содержит- б70 Чисть Р. Дополнительные испекты ся подробное описание этих тестов (а также некоторых других). Тест ТРС-й предназначен для измерения производительности О1 ТР-обработки (где сокращение ОЕТР означает Опйпе Тгапзаспоп Ргосезз1пй„т.е. оперативная аналитическая обработка). Тест ТРСВ является особой версией теста ТРС-л, предназначенной лля измерения производительности СУБД и базовой операционной системы при игнорировании особенностей взаимодействия с пользователями и т.п.
Тест ТРС-С моделирует работу системы приема и регистрации заказов (фактически это существенно расширенный вариант тесш ТРС- й). Тест ТРС-0 предназначен лля измерения производительности работы системы поддержки принятия решений. Он включает набор из 17 достаточно сложных З П(: запросов (по сути, это единственный тест из четырех перечисленных выше, который позволяет оценить качество работы собственно оптимизатора). Замечание. Разработчики СУБД конкурируют друг с другом, добиваясь получения более высоких показателей производительности при тестировании своих продуктов с помощью перечисленных выше тестов. Однако следует отметить, что их рекламные заявления нужно интерпретировать с чрезвычайной осторожностью, поскольку разработчики и поставщики систем баз данных склонны прибегать к разнообразным уловкам и трюкам для формального повышения показателей эффективности выполнения этих тесов.
Поэтому сачеаг елгргог (пусть покупатель будет бдителен)! 17.7. Вийон Р., Реал Р.)., ТцгЬубй С. Вепсйгпагк1пй РагаЬазе Бузгегпз; А Яумегпаггс Арргоасй гг' Ргос. 91Ь 1пгегп. Сопб оп Чегу 1.агйе Раза Вазез.— Р)огепсе, !га!у, ОсгоЬег-)л)очешЬег, 1983. В работе представлена общая модель вычисления запроса, которая включает многие известные алтари~мы, как частный случай. Эта модель содержит перечисленные ни- же низкоуровневые операции и соответствующие наборы формул стоимости, ° Индексирование выборок ° Индексирование соединений ° Пересечение ° Доступ к записям ° Последовательный просмотр ° Связный просмотр ° Фильтрация выборки ° Фильтрация соединения ° Сор~правка ° Конкатенация ° Проекция Определенный алгоритм обработки запроса выражается в терминах перечисленных низкоуровневых операций, и стоимость этого алгоритма может быть вычислена с помощью формул стоимости.
В работе рассмотрены различные классы ачго- б71 Глава 17. Оптилгизаг(ия Здесь впервые описано то, что сегодня называют "Внсконсинским тестом" (так как этот тест был разработан авторалгн ланной работы в университете штата Висконсин). В описываемом тесте используется набор о~ношений с ~очно указанными значениями атрибутов. При его выполнении определяется производительность конкретно заданных алгебраических операций на указанных отношениях (например, различных видов проекций, использующих атрибуты с разной степенью дублирования значений). Таким образом, измеряется эффективность работы оптимизатора системы на описанных выше основных операциях.
(См, также !17.б).) 17.8. Вгпй Уао Я. Орбгпьзайоп о( Оцегу Еча1цайоп А18ог11Ьгпз д АСМ ТОРБ.— )цпе, 1979. — 4, № 2. ритмов обработки запросов и для каждого класса выработаны формулы стоимости. В результате проблема оптимизации запроса сводится к решению простого набора уравнений для вычисления минимальной стоимости.
Затем выбирается класс алгоритмов, соответствуюший полученной минимальной стоимости. 17.9. В!аз8еп М. й/., Езчагап К.Р. Яогайе апд Асеева ш Ве!аз!опа! РагаЬазез //!ВМ Буз. 1. — 1977. — 16, № 4. Представлены результаты сравнения различных приемов обработки запросов, в которых используются операции проекции, выборки и соединения, на основе их стоимости, выраженной в операциях ввода-вывода.
Основные компоненты этих методов реализованы в системе Буз1еш й [17.34). 17.10.Меггеп Т.Н. й/Ьу акоп/Мегбе Огкез гйе Вез! 1шр!ешепгапоп о11Ье Хашга! )ош // АСМ Я! ОМОР. — 1апцагу, 1983. — ! 3, № 2. Представлен набор интуитивно понятных аргументов в пользу утверждения, что с помошью сортировки-слияния можно достичь самых эффективных результатов. В основном, аргументы сводятся к тому, что: а) операция соединения будет наиболее эффективной, если оба отношения будут отсортированы по значениям атрибута, по которому выполняется соединение (поскольку в данном случае, как показано выше, в разделе 17.7, слияние — достаточно эффективный метод оптимизации, а выборка каждой страницы выполняется только один раз, что действительно является оптимальным); б) стоимость сортировки отношений в необходимом порядке (на достаточно больших машинах) будет, вероятно, меньше стоимости любой схемы, в которой не требуется упорядоченность кортежей в обоих отношениях.
Тем не менее автор допускает, что для его радикальной позиции могут существовать исключения, Например, одно из отношений может быть настолько мало (например, в случае, когда оно является результатом предыдущей операции выборки), что прямой доступ ко второму отношению через индекс или хеш-таблицу будет иметь меньшую стоимость, чем сортировка второго отношения. В [17.81- [!7.111 приведены дополнительные примеры, в которых метод сортировки-слияния на практике не является лучшим приемом обработки. 17.11.$ассо О.М.
Ргайшепзабоп: А Тесйп!цце Гог Ей!с[еп1 Оцегу Ргосезгйпй // АСМ ТОРЯ. — 1цпе, 1986. — 11, № 2. Представлен один из методов, используюших принцип "разделяй и властвуй" для выполнения операции соединения. Согласно этому методу соединяемые отношения рекурсивно разбиваются на подмножества кортежей (фрагменты) и в этих фрагментах выполняется серия последовательных просмотров. В отличие от метода сортировки-слияния этот метод не требует предварительной сортировки отношений. Показано, что фрагментация всегда работает эффективнее сортировки-слияния, когда последний метод требует предварительной сортировки обоих отношений, и иногда работает лучше, если метод сортировки-слияния требует предварительной сортировки только одного [большего) отношения.
Автор утверждает, что данный метод можно применять и для других операций, таких как пересечение и вычитание. 17.12.Язар1го 1..Р. 1о!и Ргосезз[пй !и РагаЬазе Буззешз в11Ь 1.агбе Ма!и Мешопез // АСМ ТОРЗ. — ЗергешЬег, 1986. — 11, № 3. 672 Часть Р. Дополнительные аспекты Представлено три новых алгоритма хеширования при выполнении операции соединения. Один из них "особенно эффективен при наличии основной памяти в размере, значительно превышающем размер одного из соединяемых отношений". Алгоритмы работают благодаря разбиению отношений на непересекающиеся части (т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
