Введение в системы БД (542480), страница 163
Текст из файла (страница 163)
В противоположность этому в нереляционных системах, гле запросы пользователей выражаются на более низком семантическом уровне. любая "оптимизация" должна выполняться самим пользователем вручную (здесь термин "оптимизация' взят в кавычки, поскольку обычно он употребляется для обозначения автоматической, а не ручной оптимизации), В подобных системах пользователь (а не система) определяет, какие именно низкоуровневые операции должны быть выполнены и в какой последовательности.
И если пользователь принял неправильное решение, то система никак не сможет исправить положение. Заметьте также, что для работы в подобных системах пользователь должен обладать некоторыми навыками в программировании, иначе он не сможет достаточно полно их применять. Преимущество автоматической оптимизации заключается в том, что пользователь может не задумываться над наилучшим способом выражения своих запросов (т.е.
над тем, как следует сформулировать запрос, чтобы система выполнила его с максимальной производительностью). Но и это далеко не все. Вполне вероятно, что оптимизатор сформулирует запрос лучше, чем сам пользователь. Для подобного утверждения есть несколько веских причин. Ниже приведены лишь некоторые из них. 1. Хороший оптимизатор — обратите внимание на слово "хороший" ! — обладает большим объемом полезной информации, которая пользователю обычно недоступна. Говоря конкретнее, оптимизатор владеет определенными статистическими данными, в частности перечисленными ниже: ° количество значений в каждом домене; ° текущее количество значений в каждой базовой переменной-отношении; ° текущее количество различающихся значений для кажлого атрибута в базовой переменной-отношении; ° количество вхождений каждого значения в каждом из атрибутов и т.п.
(Вся эта информация хранится в системном каталоге, о чем речь пойдет ниже в этой главе, в разделе 17.5.) Благодаря наличию таких данных оптимизатор способен более точно оценить эффективность любой возможной стратегии реализации конкретного запроса. Исходя из полученных результатов он сможет выбрать наилучшую стратегию реализации запроса. 639 Глава 17. Оптимизация 2. Если со временем статистические показатели базы данных значительно изменятся (например, в результате ее физической реорганизации), то при реализации запроса может оказаться целесообразнее использовать иную стратегию, отличную от применявшейся ранее.
Другими словами, возникнет необходимость в повторной оптимизации или реоптимизации. В реляционных системах процесс реоптимизации вполне тривиален и сводится к простой повторной обработке исходного запроса системным оптимизатором. В нереляционных же системах выполнение реоптимизации, как правило, требует переписывания программы и, вполне возможно, может оказаться вообще невыполнимым. 3. Оптимизатор — это программа, которая по опрелелению более "настойчива", чем человек. Оптимизатор способен рассматривать буквально сотни различных стратегий реализации конкретного запроса, в то время как программист едва ли проанализирует более трех-четырех возможных стратегий (по крайней мере, достаточно глубоко).
4. В оптимизаторе реализованы знания и опыт "лучших из лучших" программистов, в результате чего эти знания и опыт становятся доступными для всех. Это позволяет применять ограниченный набор ресурсов, предоставленный широкому кругу пользователей, наиболее эффективно и экономично.
Приведенные выше соображения служат убедительным доказательством сделанного в начале данного раздела заявления о том, что оптимизируемость (т.е. возможность оптимизации запросов) является сильной стороной реляционных систем. Общее назначение оптимизатора состоит в выборе наиболее эффективной стратегии вычисления реляционного выражения. В этой главе описаны некоторые фундаментальные принципы н методы, применяемые в процессе оптимизации. После обсуждения вступительного примера, приведенного в разделе 17.2, в разделе 17.3 предложен обзор принципов работы оптимизатора.
Затем, в разделе 17.4, обсуждается один из важнейших аспектов процедуры оптимизации — преобразование выражений (или переписывание запроса). Далее, в разделе 17.5, кратко излагается вопрос о статистических показателях базы данных. В разделе 17.6 дается более подробное описание одного из конкретных методов оптимизации, известного как декомпозиция запросов. Затем, в разделе 17.7, обсуждается вопрос о том, как в действительности реализуются некоторые реляционные операторы (например, оператор Л)1й), и кратко описывается использование рассматривавшихся в разделе 17.5 статистических показателей для вычисления стоимостных оценок. И наконец в разделе 17.8 приводится краткое резюме по всему материалу данной главы. Еи1е одно вводное заиечание.
Достаточно часто на данную тему ссылаются, как на оптимизацию запросов. Однако подобный термин несколько неточен, поскольку выражение, которое нужно оптимизировать ("запрос"), на самом деле может формироваться в контексте, отличном от интерактивного опроса базы данных. В частности, оно может быть частью операции обновления, а не операции выборки, понимаемой под запросом.
Более того, сам по себе термин оптимизация является несколько преувеличенным, так как не существует гарантий, что выбранная стратегия реализации действительно оптимачьна в любом понимании. На практике под "оптимизированной*' стратегией реализации обычно понимается несколько улучшенный вариант исходного не оптимизированного выражения. (Тем не менее в некоторых немногочисленных случаях можно вполне обоснованно утверждать, что выбранная стратегия реализации будет действительно оптимальной в определенном смысле 117.31).) 640 Часть К Дополнительные аспекты 17.2.
Пример выполнения оптимизации Начнем изложение с простого примера (он уже кратко рассматривался в разделе 6.6), дающего представление о поразительных результатах, которых можно достичь с помощью оптимизации. Рассмотрим следующий запрос: "Определить имена поставщиков детали с номером 'Р2'".
Алгебраическая запись этого запроса такова. ( ( ЯР Л01М Б ) ИНЕССЕ Р! = Р)) ( 'Р2' ) ) ( БМ))ИЕ ) Предположим, что в базе данных содержится информация о 100 поставщиках и 1О 000 поставках деталей, из которых только 50 включают партии деталей с номером 'Р2'. Предположим для простоты, что переменные-отношения Я и БР сохраняются на диске, как два отдельно хранимых файла, в кажлой записи которых помещается по одному кортежу данных, В этом случае, если система будет вычислять данное выражение "прямо" (т.е. вообще без оптимизации), последовательность выполняемых операций будет такой.
!. Соединение переменных-отношений ЯР и Я (по атрибуту ЯБ). При выполнении этой операции потребуется считать информацию о 10 000 поставках партий деталей и ! 0 000 раз считать информацию о ! 00 поставщиках (однн раз для каждой поставки деталей). В результате будет получен промежуточный набор данных, содержащий ! 0 000 соединенных кортежей. Этот набор данных записывается на диск (предположим, что для размещения промежуточного результата в основной (оперативной) памяти не хватает места).
2. Выборка из полученного на этапе ! результата кортежей с данными о детали с номером 'Р2'. На этом этапе выполняется чтение 10 000 соединенных кортежей обратно в оперативную память, причем полученный результат состоит только из 50 кортежей, которые, по нашему предположению, вполне могут поместиться в оперативной памяти. 3. Выполнение проекции по атрибуту Яйййй результата, полученного на этапе 2. На этом этапе формируется результирующий набор исходного запроса (состоящий максимум из 50 кортежей, которые вполне могут быть размещены в оперативной памяти).
Представленная ниже процедура полностью эквивалентна описанной выще в том смысле, что она обязательно приведет к тому же конечному результату, но он будет получен более эффективным способом. 1. Выборка из переменной-отношения ЯР кортежей с данными только о детали с номером 'Р2'. На этом этапе выполняется чтение 1О 000 кортежей и созлается результирующий набор, состоящий только из 50 кортежей, который, как мы предполагаем, может поместиться в оперативной памяти.
2. Соединение полученного на этапе 1 результата с переменной-отношением Я (по атрибуту БЕ). На этом этапе выполняется считывание данных обо всех 100 поставщиках (но только один раз, а не по одному разу дпя каждой поставки партии деталей, так как данные обо всех поставленных партиях деталей с номером 'Р2' уже находятся в оперативной памяти). Результат содержит 50 соединенных кортежей (которые также помещаются в оперативной памяти). Глава 17. Оптимизация 641 3.
Выполнение проекции по атрибуту ЯйдИЕ результата, полученного на этапе 2 (аналогично этапу 3 предыдущей последовательности действий). Требуемый результат (не более 50 кортежей) помещается в оперативной памяти. В первой из показанных процедур в целом выполняется 1 030 000 операций ввода- вывода кортежей, в то время как во второй процедуре выполняется только 1О 100 операций ввода-вывода.
Следовательно, совершенно очевидно. что если принять в качестве меры оценки производительности количество выполненных операций ввода-вывода кортежей, то вторая процедура в 100 раз эффективнее первой. (На практике мерой оценки произволительностн служит количество операций ввода-вывода саранки, а не отдельных кортежей, но для лаиного примера это уточнение можно игнорировать.) Кроме того, вполне понятно, что предпочтительнее реализовать данный запрос именно с помощью второй процедуры, а не первой! Приведенный пример показывает, что следствием даже незначительных изменений в алгоритме реализации (выполнения выборки, а затем соединения вместо соединения и последующей выборки) может быть существенное увеличение произволительности. Производительность повысится еще больше, если переменная-отношение ЯР будет индексирована или хеширована по атрибуту Р$.
В этом случае количество кортежей, считываемых на этапе 1 второй процедуры, уменьшится с 1О 000 до всего лишь 50, в результате чего вся процедура окажется в 7 000 раз эффективнее ее исходного варианта. Аналогично этому наличие индекса или хеш-таблицы для атрибута Я. Я4 позволит уменьшить количество операций ввода-вывода кортежей на этапе 2 со 100 до 50, в результате чего процедура вычисления запроса окажется более чем в 10 000 раз эффективнее исходного варианта.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
