ся подробное описание этих тестов (а также некоторых других). Тест ТРС-А предназначен ддя измерения производительности OLTP-обработки (где сокращение OLTP означает Online Transaction Processing, т.е. оперативная анапитическая обработка). Тест ТРС-В является особой версией теста ТРС-А, предназначенной для измерения производительности СУБД и базовой операционной системы при игнорировании особенностей взаимодействия с пользователями и т.п. Тест ТРС-С моделирует работу системы приема и регистрации заказов (фактически это существенно расщиренный вариант теста ТРС-А). Тест TPC-D предназначен для измерения производительности работы системы поддержки принятия рещений. Он включает набор из 17 достаточно сложных SQL-запросов (по сути, это единственный тест из четырех перечисленных выше, который позволяет оценить качество работы собственно оптимизатора).

Замечание. Разработчики СУБД конкурируют друг с другом, добиваясь получения более высоких показателей производительности при тестировании своих продуктов с помощью перечисленных выше тестов. Однако следует отметить, что их рекламные заявления нужно интерпретировать с чрезвычайной осторожностью, поскольку разработчики и поставщики систем баз данных склонны прибегать к разнообразным уловкам и трюкам для формального повышения показателей эффективности выполнения этих тестов. Поэтому caveat emptor (пусть покупатель будет бдителен)!

17.7. Bitton D., DeWitt D.J., Turbyfill С. Benchmarking Database Systems: A Systematic Approach Proc. 9th Intern. Conf. on Very Large Data Bases. - Florence, Italy, October-November, 1983.

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

17.8. Bing Yao S. Optimization of Query Evaluation Algorithms ACM TODS. - June, 1979. -4, №2.

В работе представлена общая модель вычисления запроса, которая включает многие известные алгоритмы, как частный случай. Эта модель содержит перечисленные ниже низкоуровневые операции и соответствующие наборы формул стоимости.

Индексирование выборок Фильтрация выборки

Индексирование соединений Фильтрация соединения

Пересечение Сортировка

Доступ к записям Конкатенация

Последовательный просмотр Проекция

Связный просмотр

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

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

17.9. Blasgen M.W., Eswaran К.P. Storage and Access in Relational Databases IBM Sys. J. - 1977. - 16, №4.

Представлены результаты сравнения различных приемов обработки запросов, в которых используются операции проекции, выборки и соединения, на основе их стоимости, выраженной в операциях ввода-вывода. Основные компоненты этих методов реализованы в системе System R [17.34].

17.10.Merrett Т.Н. Why Sort/Merge Gives the Best Implementation of the Natural Join ACM SIGMOD. - January, 1983. - 13, №2.

Представлен набор интуитивно понятных аргументов в пользу утверждения, что с помошью сортировки-слияния можно достичь самых эффективных результатов. В основном, аргументы сводятся к тому, что:

а) операция соединения будет наиболее эффективной, если оба отношения будут отсортированы по значениям атрибута, по которому выполняется соединение (поскольку в данном случае, как показано выше, в разделе 17.7, слияние - достаточно эффективный метод оптимизации, а выборка каждой страницы выполняется только один раз, что действительно является оптимальным);

б) стоимость сортировки отношений в необходимом порядке (на достаточно больших машинах) будет, вероятно, меньше стоимости любой схемы, в которой не требуется упорядоченность кортежей в обоих отношениях.

Тем не менее автор допускает, что для его радикальной позиции могут существовать исключения. Например, одно из отношений может быть настолько мало (например, в случае, когда оно является результатом предыдущей операции выборки), что прямой доступ ко второму отношению через индекс или хеш-таблицу будет иметь меньшую стоимость, чем сортировка второго отношения. В [17.8]-[17.11] приведены дополнительные примеры, в которых метод сортировки-слияния на практике не является лучшим приемом обработки. IT.ll.Sacco G.M. Fragmentation: А Technique for Efficient Query Processing ACM TODS. - June, 1986. - 11, № 2.

Представлен один из методов, использующих принцип разделяй и властвуй для выполнения операции соединения. Согласно этому методу соединяемые отношения рекурсивно разбиваются на подмножества кортежей (фрагменты) и в этих фрагментах выполняется серия последовательных просмотров. В отличие от метода сортировки-слияния этот метод не требует предварительной сортировки отношений. Показано, что фрагментация всегда работает эффективнее сортировки-слияния, когда последний метод требует предварительной сортировки обоих отношений, и иногда работает лучше, если метод сортировки-слияния требует предварительной сортировки только одного (большего) отношения. Автор утверждает, что данный метод можно применять и для других операций, таких как пересечение и вычитание. 17.12.Shapiro L.D. Join Processing in Database Systems with Large Main Memories ACM TODS. - September, 1986. - 11, № 3.

Представлено три новых алгоритма хеширования при выполнении операции соединения. Один из них особенно эффективен при наличии основной памяти в размере, значительно превышаюшем размер одного из соединяемых отношений . Алгоритмы работают благодаря разбиению отношений на непересекаюшиеся части (т.е. выборки), которые можно обрабатывать в основной памяти. Автор заявляет, что, исходя из наблюдаемого снижения цен на первичную память, методы на основе хеширования могут стать одними из лучших. 17.13.Negri М., Pelagatti G. Distributive Join: А New Algorithm for Joining Relations ACM TODS. - December, 1991. - 16, № 4.

Здесь представлен другой метод соединения, используюший принцип разделяй и властвуй , который ...базируется на идее о том, что... не нужно полностью сортировать оба отношения... Достаточно отсортировать одно отношение полностью, а другое - лишь частично, избежав таким образом расходов на вьшолнение полной сортировки второго отношения . При частичной сортировке рассматриваемая переменная-отношение разбивается на последовательность неупорядоченных подмножеств кортежей Р1, Р2, Рп (похоже на метод Сакко (Sacco) [17.11], за исключением того, что в методе Сакко используется хеширование вместо сортировки), обладающих следуюшим свойством: MAX{P[i]) < MIN(P[i+l]) для всех i (1, 2, п-1). Утверждается, что данный метод работает эффективнее метода сортировки-слияния. 17.14.Graefe G., Cole R.L. Fast Algorithms for Universal Quantification in Large Databases ACM TODS. - June, 1995. - 20, № 2.

Квантор всеобшности (FORALL) в языке SQL непосредственно не поддерживается, а потому он не поддерживается и в современных коммерческих СУБД, хотя он чрезвычайно важен для формулировки широкого класса запросов. В этой статье описываются и сравниваются три известных алгоритма и один недавно предложенный алгоритм реляционного деления, которое является алгебраическим оператором, включающим квантор всеобщности . В ней также показано, что новый алгоритм работает с той же скоростью, с какой выполнение хешированного полусоединения позволяет получить оценку значения квантора существования для тех же отношений . Помимо всего прочего, авторы делают вывод, что квантор FORALL необходимо включить в пользовательский язык, так как большинство оптимизаторов не распознает его косвенные формулировки на языке SQL . 17.15.Bitton D., DeWitt D.J. Duplicate Record Elimination in Large Data Files ACM TODS. - June, 1983. - 8, № 2.

Традиционный метод исключения кортежей-дубликатов состоит в сортировке записей с последующим последовательным просмотром. Данная работа предлагает альтернативное решение, более эффективное для файлов большого размера. 17.16. Simmen D., Shekita Е., Malkemus Т. Fundamental Techniques for Order Optimization Proc. 1996 ACM SIGMOD Int. Conf on Management of Data. - Montreal, Canada, June, 1996. В этой работе представлены методы оптимизации или исключения сортировок. Они частично основаны на работе Дарвена [10.6] и именно в таком виде реализованы в СУБД DB2.

17.17.Manku G.S., Rajagopalan S., Lindsay B.G. Approximate Medians and Other Quantities in One Pass and with Limited Memory Proc. 1998 ACM SIGMOD Int. Conf. on Management of Data. - Seattle, Wash., June, 1998.