Базы данных Oracle - статьи

         

Новые алгоритмы обработки запросов.


Выполнение SQL-запроса - особенно имеющего сложную структуру - обычно распадается на несколько взаимосвязанных операций. Само это разбиение, а тем более выбор методов выполнения операций как правило допускают множество альтернативных решений. Выбор оптимальной их комбинации - задача оптимизатора, который на основании как характера запроса, так и имеющейся информации о задействованных таблицах и индексах, наличии тех или иных системных ресурсов (кстати в Oracle 7.3 расширен набор видов предоставляемой оптимизатору информации: теперь он может учитывать частотные гистограммы индексируемых полей) строит т.н. оценку стоимости разных вариантов решения. В принципе пользователь может не особенно заботиться о том, как именно выполняется его запрос, но при настройке системы, этот вопрос часто встает, тем более, что Oracle позволяет “помогать” оптимизатору (все-таки практика показывает, что при принятии неформальных решений опытный специалист часто оказывается эффективнее даже самых “умных” программ). Поэтому небезынтересно бывает представлять, какие именно алгоритмы применяются при работе с данными, каковы их достоинства и недостатки.

Помимо “джентльменского” набора более или менее универсальных методов существует также целый ряд более узкоспециализированных, т.е. таких, которые очень хорошо работают в некоторых ситуациях, но могут быть совсем неэффективными (или даже неприменимыми) в других. Несмотря на такой недостаток, применение этих методов может дать очень заметный эффект, особенно при выполнении сложных запросов над большими объемами данных, что характерно для систем поддержки принятия решений (DSS) - или, как сейчас стало модно говорить, для хранилищ данных. Другое дело, что ни один из методов не является панацеей, а стало быть система должна уметь использовать как можно большее их число.

В Oracle 7.3 введен целый ряд таких специализированных алгоритмов. Перечислим их без подробного рассмотрения (иначе статья достигнет уже совсем неприличных размеров).

  • “Звездообразные запросы” (star queries). В DSS-системах довольно часто применяются запросы, выполняющие соединение одной большой таблицы (т.н. таблицы фактов - например с описанием продаж товаров) с несколькими маленькими (т.н. справочными таблицами - например с описаниями различных видов товаров, регионов, где производятся продажи и пр.). При выполнении подобных запросов оказывается эффективным достаточно экзотический алгоритм, выполняющий сначала вычисление декартова произведения справочных таблиц, а затем слияние сортировкой полученного результата с таблицей фактов. Собственно говоря данный алгоритм был реализован еще в Oracle 7.2, но в версии 7.3 его возможности были заметно расширены. “Звездообразные” запросы являются рабочей лошадкой ряда ROLAP-систем, поэтому для них поддержка данной возможности в Oracle весьма важна.

  • “Слияние хэшированием”. Альтернативный слиянию сортировкой метод выполнения соединений таблиц (еще одна альтернатива - вложенные циклы). Краткая (хотя не совсем полная) характеристика этого алгоритма дана в статье [1].


  • Применение битовых строк для индексирования. До версии 7.3 Oracle применял для индексирования только B-деревья и хэш-функции (если таблица помещалась в хэш-кластер). В версии 7.3 появилась возможность использования индексов с битовыми строками (bit-map indexes). Их идея очень проста. Если некоторое поле таблицы может принимать ограниченное число значений, то каждому такому значению можно сопоставить битовую строку (количество бит равно количеству записей в таблице), в которой единицы находятся в позициях, соответствующим тем записям, которые имеют данное значение в индексируемом поле. Ясно, что такой индекс позволяет очень быстро находить нужные записи по значениям проиндексированного поля (и любым их логическим комбинациям), а также выполнять операции агрегирования опять-таки по этому полю. Недостатки метода: эффективен лишь для полей с небольшим количеством допустимых значений, неэффективны операции сравнения с предшествованием (больше/меньше), неэффективны операции вставки, удаления и модификации записей (в действительности “в чистом виде” битовые строки не применяются: они размещаются в концевых листах B-дерева, что позволяет смягчить указанные недостатки, но очевидно, что в целом они носят принципиальный характер, а потому не устранимы полностью). Ввиду этого очень важно то, что Oracle позволяет применять bit-map индексирование в сочетании с другими методами индексирования на одной и той же таблице.



  • Содержание раздела