Программные продукты и системы

Проблема эффективности БД возникла практически одновременно с их появлением и заключается прежде всего в повышении скорости доступа к данным при выполнении различных операций. Ее решение для реляционных (включая объектно-реляционные) СУБД (РСУБД) носит комплексный характер и включает оптимизацию серверной, клиентской и сетевой частей системы, целый ряд способов настройки ее производительности. Проблемы и существующие методы их решения относятся к локальной оптимизации запросов (часто называемой просто оптимизацией запросов), оптимизации выполнения реляционных операций (прежде всего операции соединения как наиболее накладной реляционной операции и агрегатных функций), оптимизации распределенных вычислений и глобальной оптимизации систем запросов [1]. Естественно, что более частные проблемы возникли раньше, а эффективность их решения влияет и на эффективность решения более общих задач. Вследствие большого значения и невозможности всеобъемлющего решения локальную оптимизацию запросов можно отнести к неизменно актуальной области исследований, один из аспектов которой рассматривается в настоящей статье.

Особенности локальной оптимизации

Под запросом в РСУБД понимается процесс получения данных из БД, специфицируемый в языке SQL командой SELECT. Несмотря на то, что, строго говоря, SQL не является реляционным языком (в отличие, например, от языка Tutorial D из Третьего манифеста) и ни одна реально действующая РСУБД не отвечает всем формулируемым для них 12 правилам, команда SELECT, появившаяся среди четырех специальных реляционных операций наряду с четырьмя традиционными для множеств операций над отношениями еще в исходной версии реляционной теории Э.Ф. Кодда, является неотъемлемой частью стандартов языка SQL, весьма строго поддерживаемой различными РСУБД [2]. Обязательным наряду со списком выборки разделом команды SELECT является раздел FROM. Локальный запрос характеризуется единственным табличным выражением в разделе FROM. Разделами команды SELECT, наиболее часто и существенно влияющими на производительность выполнения локального запроса, являются WHERE и ORDER BY.

Под локальной оптимизацией SQL-запросов подразумевается способ выполнения локальных запросов по процедурному плану, наиболее оптимальному при существующих в БД управляющих структурах и распределении данных. Множественность планов обусловлена непроцедурным (описательным) характером SQL (подобно реляционному исчислению в отличие от носящей предписывающий характер реляционной алгебры), не определяющим, каким образом должны быть выполнены SQL-выражения. Такие планы вырабатываются оптимизатором (специальным компонентом РСУБД) путем синтаксических и семантических преобразований начального представления запроса и сравнения альтернативных вариантов преобразований. Формально оптимальным планом выполнения запроса в РСУБД может считаться такая последовательность применения операторов реляционной алгебры к исходным и промежуточным отношениям, которая для конкретного те- кущего состояния БД может быть выполнена с минимальным использованием имеющихся конкретных вычислительных ресурсов. На практике оптимальность выбранного плана носит достаточно условный характер в соответствии с заложенными в оптимизатор критериями и может отклоняться от реальной оптимальности.

Все современные РСУБД имеют оптимизатор планов выполнения запросов по правилам и/или по стоимости, средства их настройки и анализа предлагаемого к выполнению плана. Оптимизатор по правилам выбирает методы доступа на основе предположения о статичности БД с использованием жестко заданных правил их выбора. Оптимизатор по стоимости исторически является дальнейшим его развитием и основан на минимизации в результате анализа затрат на доступ с использованием весовых коэффициентов и хранимой внутренней статистике о распределении значений данных в таблицах. Для дальнейшего рассмотрения конкретных вопросов на примерах выбраны портируемые на многие платформы и обладающие существенными для современных РСУБД чертами широко распространенная проприетарная СУБД Oracle [3] и свободно распространяемая (лицензия BSD) PostgreSQL [4], на ядре которой созданы многочисленные коммерческие и специального назначения системы, включая отечественные.

В PostgreSQL используется только оптимизатор по стоимости, настраиваемый установкой значений констант планировщика и различных опций и параметров, многие из которых могут изменяться командой SET, в том числе с опцией SESSION для текущей сессии. В Oracle доступны оба вида оптимизаторов (при инициализации экземпляра БД указывается используемый), установки для сессии могут изменяться командой ALTER SESSION SET. Наиболее гибким механизмом настройки, не имеющим аналога в PostgreSQL и влияющим только на конкретный запрос, является использование подсказок оптимизатору (hint) в тексте запроса. Подсказка позволяет указывать не только метод доступа, но и имя конкретного индекса, которые система должна использовать.

Оптимизатор по правилам Oracle в процессе работы использует ранги методов доступа от 1 до 15 в порядке снижения их эффективности, от обращения к одной строке по ее идентификатору до полного сканирования таблицы. Так, методы доступа с применением индексов имеют следующие ранги: неограниченного диапазона поиска по индексированным столбцам – 11, ограниченного – 10, по индексу на основе одного столбца – 9, по составному индексу – 8. Упорядочению по индексированным столбцам присвоен значительно больший ранг 14, что справедливо к запросу, результирующее отношение которого существенно менее кардинально исходной таблицы. Однако в противном случае запрос часто выполняется более эффективно с использованием индексов по столбцам упорядочения, чем по столбцам поиска. Подобные корректировки в оптимизацию по правилам призван вносить оптимизатор по стоимости. Тем не менее в большинстве случаев преобразования, позволяющие применять методы доступа с меньшим рангом, приводят к более эффективным планам выполнения запросов, которые должны рассматриваться как кандидаты на выполнение. К таковым относится преобразование неограниченного диапазона поиска в ограниченный внесением в запрос дополнительного условия, которое гарантированно не изменяет выборку и сохраняет возможность использования соответствующего индекса.

Результат работы оптимизатора в виде предлагаемого к выполнению плана запроса может быть просмотрен вызовом команды EXPLAIN PLAN в Oracle или EXPLAIN в PostgreSQL c различной степенью детализации в соответствии с параметрами и настройками. Структура плана запроса – это дерево, листья которого означают сканирование таблицы, возвращающее ее строки. В зависимости от метода доступа используется последовательное сканирование таблицы или сканирование индексов с возможными проверками условий или фильтрацией. Последующим операциям над этими строками, таким как агрегация, объединение, сортировка, соответствуют узлы дерева, связанные с соответствующими листьями, и так далее к корню дерева. Для каждого узла в дереве плана наряду с указанием выполняемых действий приводятся оценки расхода различных ресурсов на их выполнение, как правило, приведенные к количеству считываемых (обрабатываемых) дисковых страниц с учетом различных факторов, например того, что индивидуальная выборка значительно дороже последовательного чтения целой дисковой страницы. Именно эту величину в корне дерева, принимаемую за стоимость выполнения плана, оптимизатор стремится свести к минимуму.

Одним из основных инструментов повышения производительности выборки данных из таблиц реляционных БД (при некотором снижении производительности модификации данных) является создание индексов. При их использовании в случае выбора небольшой части записей из таблицы, размещаемой более чем в двух страницах памяти, достаточно обращения к меньшему количеству страниц памяти, особенно при сортировке выборки по индексу, и возможности извлечения данных непосредственно из индексных страниц, реализуемой во многих РСУБД для индексов различных типов. Наряду с простыми индексами, в которых индексируется один столбец, существуют частичные индексы, охватывающие только строки с определенными значениями столбца, составные индексы по нескольким столбцам и функциональные индексы, в которых индексируется функция от значения данных в столбце, а также их комбинации. Применяемые в индексах функции должны зависеть только от их параметров и максимально быстро выполняться. Предопределение результата выполнения функции, при котором она будет всегда давать одинаковые результаты при одинаковых входных данных, задается атрибутом DETER­MINISTIC в Oracle и IMMUTABLE в PostgreSQL.

В различных РСУБД могут использоваться индексы разных типов и допустимы их всевозможные комбинации, что в значительной степени обусловлено отсутствием соответствующих спецификаций в стандартах SQL. Однако практически все РСУБД в DDL имеют команду CREATE INDEX создания индекса для таблицы по кортежу выражений (в простейшем случае столбцов), зависящих от значений ее столбцов в индексируемой строке. Различные разделы и параметры этой команды определяют в том числе методы индексирования и классы операторов сравнения выражений различных типов. Так, текущие версии Post­greSQL поддерживают методы индексирования B-tree, hash, GiST и GIN. Из них только методы B-tree и GiST поддерживают составные индексы с ограничением по умолчанию до 32 выражений (столбцов). В Oracle нет полного аналога методу индексирования hash PostgreSQL, а в PostgreSQL – имеющемуся в Oracle типу индексов на основе битовых карт, которые имеют смысл для отдельных столбцов и используются исключительно в операторах равенства, что объединяет их с hash-индек­сами PostgreSQL.

Наиболее распространены B-tree-индексы. Они могут быть не только простыми, но и составными, функциональными и частичными, в том числе в их различных комбинациях, использоваться во всех операторах сравнения, определенных для типов столбцов (выражений). Поэтому предлагаемый метод применим прежде всего для них. Эти индексы, как и индексы других типов, по умолчанию не содержат записей для NULL-значений и соответственно не могут использоваться в запросах с выборкой по условиям IS NULL и IS NOT NULL (за исключением частичных индексов по этим условиям). Поскольку ключи в индексе упорядочены, эффективная выборка из него может выполняться только в лексикографическом порядке. В Oracle и последних версиях PostgreSQL реализована возможность извлечения данных непосредственно из страниц B-tree индекса без обращения к страницам собственно таблицы. Иногда эффективным может быть даже добавление в индекс выражений, отсутствующих в поиске и упорядочении, но выводимых в результате запроса, для исключения обращения к страницам собственно таблицы.

Составной B-tree-индекс может использоваться во всех локальных запросах, содержащих в своих разделах любое подмножество его выражений (столбцов). Однако использование индекса целесообразно только тогда, когда он эффективно (по сравнению с полным сканированием таблицы) задействован в диапазоне поиска и/или в упорядочении. Составной B-tree-индекс может быть эффективно задействован в упорядочении по индексированным столбцам только в том случае, если кортеж его выражений совпадает с кортежем выражений раздела ORDER BY запроса или является расширением последнего выражениями справа. В диапазоне поиска индекс может быть эффективно задействован, если лидирующие (самые левые) выражения его кортежа используются в соответствующих индексу операторах сравнения выражений конъюнктов раздела WHERE запроса. Применение индекса тем эффективнее, чем больше мощность подмножества таких используемых выражений и чем выше их селективность. Остальные выражения кортежа индекса, используемые в соответствующих индексу операторах сравнения выражений раздела WHERE запроса, не уменьшают часть индекса, который должен быть просмотрен, но могут уменьшить количество просматриваемых страниц таблицы.

Условие использования выражений кортежа индекса в операторах сравнения, соответствующих индексу, именно в выражениях конъюнктов принципиально важно для однократности сканирования индекса, поскольку для каждого дизъюнкта требуется отдельное сканирование. Объединение результатов сканирования нескольких индексов (или нескольких сканирований одного индекса) реализуется подобно наложению растровых изображений в памяти, с потерей упорядочения по любому из объединяемых индексов и результирующей вычислительной сложностью, более характерной для соединений, чем локальных запросов, поэтому нередко оценивается оптимизаторами планов ниже, чем полное сканирование таблицы. Взаимные преобразования дизъюнктов в конъюнкты и наоборот хорошо известны из булевой алгебры [1, 2].

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

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

Описание метода

В многочисленных методах оптимизации запросов в реляционных системах, от ставших уже классическими до недавно предложенных, большое внимание уделяется преобразованиям вы- ражений условий поиска, направленным на сокращение их избыточности, в частности, алгоритмами поглощения и минимизации логических выражений [1, 5].

Основная идея предлагаемого метода искусственного соответствия SQL-запросов индексам реляционных БД заключается в повышении эффективности выполнения локальных запросов, возможно, предварительно оптимизированных известными методами, за счет наибольшего использования составных индексов в планах их выполнения. Поставленная цель достигается совмещением условий, подобных рангам 8, 10 и 14 оптимизатора по правилам Oracle, в результате создания (или корректировки существующих) составных индексов для таблиц на основе анализа структуры разделов WHERE и ORDER BY наиболее критичных по времени выполнения локальных запросов и последующей корректировки этих разделов. Такая корректировка вносит избыточность в логически оптимальные выражения, но обеспечивает более эффективное использование индексов.

Разделами команды SELECT, определяющим образом влияющими на эффективность выполнения локального запроса, являются WHERE и ORDER BY в случае достаточно большого (чтобы быть отсортированными в памяти) количества возвращаемых запросом строк, в полном соответствии с классически признанным значением алгоритмов сортировки и поиска. Содержанием раздела WHERE является условие (логическое выражение), синтаксически определяемое стандартом SQL как булевское выражение, основывающееся на предикатах, специфицирующих условия, результатом вычисления которых могут быть значения true, false или unknown. Среди допустимых в стандарте предикатов для дальнейшего рассмотрения важны предикаты сравнения, использующие операторы сравнения =, <, >, £, ³ и <> (упорядоченные по их селективности), а также пре- дикат IS NULL (с селективностью равенства). Соответствующие предикаты с отрицанием имеют обратную упорядоченность по селективности. Следует отметить, что такие допустимые стандартом предикаты, как BETWEEN и IN, могут быть преобразованы к конъюнктам предикатов сравнения. Само логическое выражение раздела WHERE путем применения к нему законов булевой алгебры может быть преобразовано в конъюнктивную форму. Содержанием раздела ORDER BY является кортеж выражений в общем случае различных типов. Для каждого выражения явно или неявно задается оператор сравнения его значений, как правило, < и >, в соответствии с которым сортируются строки начиная с самых левых выражений кортежа. Неопределенные NULL-значения при сортировке считаются наибольшими, а строковые данные сортируются в соответствии с национальными установками в БД.

Исходно считаются заданными: Z={Zi; i=1, …, ni} – множество критичных по времени выполнения и подлежащих преобразованию (по внешним условиям) локальных запросов к единственной таблице; Wi={Wij; j=1, …, nji} – множество выражений конъюнктов поиска раздела WHERE запроса Zi (полученных в результате его преобразо- вания известными методами к конъюнктивной форме и входящих в предикаты сравнения и сопоставления с NULL-значением), для каждого из которых имеется оценка wij их селективности; Si= – кортеж выражений сортировки раздела ORDER BY запроса Zi (для запросов без сортировки кортеж пустой, а для запросов с оценкой кардинальности результирующего отношения, принятой несущественной для выполнения сортировки, задается пустым). Здесь и далее nji означает верхнюю границу j при заданном значении i. Граница wÙ оценки существенной селективности выражений конъюнктов и оценка несущественной для выполнения сортировки кардинальности принимаются как внешние условия, зависящие от распределения данных, особенностей РСУБД, технических характеристик сервера и прочего, и в частном случае могут отсутствовать.

Реализующий предлагаемый метод алгоритм состоит из следующих семи шагов.

Шаг 1. Формируется множество W={Wr; r=1, …, nr} всех существенно селективных выражений конъюнктов поиска всех запросов Z объединением выражений, удовлетворяющих условию селективности: W:=ÈWij:wij³wÙ (i=1, …, ni, j=1, …, nji). В результате выполняется условие \"i,j: wij³wÙ $r: Wr=Wij Ù \"r $i,j: Wij=Wr (i=1, …, ni,  j=1, …, nji, r=1, …, nr). Поскольку при объединении множеств исключаются дубликаты, nr£ånji.

Шаг 2. Формируется множество I={Ip; p=1, …, np} непустых кортежей Ip= выражений составных индексов из множества S={Si; i=1, …, ni} кортежей выражений сортировки, такое, что ни один из его кортежей не является левым подкортежем другого его кортежа и любой кортеж выражений сортировки либо входит в это множество, либо является левым подкортежем одного из его кортежей.

Здесь под левым подкортежем Y= непустого кортежа X=¹Æ будем понимать непустой кортеж Y¹Æ, для которого существует непустой кортеж V¹Æ (правый подкортеж), конкатенацией которых получается исходный кортеж X=Y||V. Естественно, что ny

Алгоритм формирования множества I состоит из следующих четырех шагов.

1. I:=Æ; p:=0; i:=0.

2. i:=i+1. Если $j=1, …, p:Ij=Si Ú $k=i+1, …, ni: SiÌlSk , то переход к 4.

3. p:=p+1; Ip:=Si , nqp=nki.

4. Если i

Шаг 3. Корректируются выражения поиска, для которых имеются сопоставления с NULL-значением: \"WrÎW: ($Wij=Wr Ù $PÆ(Wij) (i=1, …, ni, j=1, …, nji, r=1, …, nr)), где PÆ(Wij) – предикат сопоставления выражения Wij с NULL-значением, выполняются замены выражений Wr IS NULL на F(Wr,c)=c и Wr IS NOT NULL на F(Wr, c)¹c, для которых введем общее обозначение Wr®F(Wr, c). Здесь F(Wr, c) – функция, которая возвращает Wr при Wr IS NOT NULL и константу c в противном случае. Практически все РСУБД имеют эффективные встроенные функции, которые могут использоваться в таком качестве, например COALESCE() в PostgreSQL. В качестве константы c принимается значение, не меньшее любого возможного значения Wr для сохранения сортировки, а при неиспользовании значения Wr в сортировке, то есть \"i,k: Sik¹Wr (i=1, …, ni, k=1, …, nki), допустимо в качестве константы c принимать любое соответствующее типу Wr значение.

Если не исключена возможность совпадения значения Wr с константой c, то наряду с заменой Wr®F(Wr, c) сохраняется и исходное выражение W:=WÈWr. В этом случае выполняются условия |W|=n’r: n’r>nr, F(Wr, c)ÎW (r=1, …, nr), WrÎW (r=nr+1, …, n’r), WrÏW (r=1, …, nr). Искусственно введенная избыточность целесообразна ввиду замены фильтрации по исходному конъюнкту при последовательном сканировании всех записей на такую фильтрацию только среди записей, отсканированных по составному индексу по условию конъюнкта с функцией F(Wr, c).

Аналогичные преобразования выполняются с соответствующими выражениями конъюнктов поиска (с возможным сохранением исходного выражения), кортежей сортировки и кортежей составных индексов:

Wij®F(Wij, c):(Wij=Wr Ù F(Wr, c)ÎW);

Wi:=WiÈWij:(Wij=Wr Ù F(Wr, c)ÎW Ù WrÎW);

Sik®F(Sik, c):(Sik=Wr Ù F(Wr, c)ÎW);

Ipq®F(Ipq, c):(Ipq=Wr Ù F(Wr, c)ÎW).

Шаг 4. Каждый кортеж Ip= выражений составных индексов дополняется справа отсутствующими в нем выражениями конъюнктов поиска запросов, которые планируется выполнять с использованием соответствующего составного индекса исходя из сортировки результатов запросов, в порядке убывания селективности выражений.

Алгоритм дополнения справа кортежей Ip состоит из следующих пяти шагов.

1. p:=0.

2. p:=p+1; Wp:=ÈWij:((Si=IP Ú SiÌlIP) Ù $j=1, …, nji, k=1, …, nki:Wij=Sik).

3. Ip:=Ip||Wij:wij=max(wuv:WuvÎWp); Wp:=Wp\\Wij.

4. Если Wp¹Æ, то переход к 3.

5. Если p

Шаг 5. Формируется множество M={Mt; t=1, …, nt} пар Mt= соответствия запроса без сортировки результатов и составного индекса, с использованием которого планируется выполнять запрос. В качестве составного индекса для запроса без сортировки результатов принимается индекс, в выражениях которого отсутствует минимальное количество выражений конъюнктов поиска запроса. То есть для \"i=1, …, ni, p=1, …, np: Si=Æ вычисляется (dip:=0, \"j=1, …, nji, q=1, …, nqp: Wij¹Ipq dip:=dip+1), после чего для \"i=1, …, ni: Si=Æ присваивается Mt:=: div=min(dip, p=1, …, np).

Шаг 6. Каждый кортеж Ip= выражений составных индексов дополняется справа отсутствующими в нем выражениями конъюнктов поиска запросов без сортировки результатов, которые планируется выполнять с использованием соответствующего составного индекса, в порядке убывания селективности выражений.

Алгоритм окончательного формирования кортежей Ip состоит из следующих пяти шагов.

1. p:=0.

2. p:=p+1; Wp:=ÈWij:(ÎM Ù \"j=1, …, nji, q=1, …, nqp: Wij¹Ipq).

3. Ip:=Ip||Wij:wij=max(wuv:WuvÎWp); Wp:=Wp\\Wij.

4. Если Wp¹Æ, то переход к 3.

5. Если p

Шаг 7. Для каждого запроса множество выражений конъюнктов поиска объединяется с множеством выражений составного индекса, планируемого для использования при выполнении этого запроса: \"i=1, …, ni, p=1, …, np: (ÎM Ú Si=IP Ú SiÌlIP) Wi’:=WiÈIp. Для каждого добавленного выражения Wij:(WijÎWi¢ Ù WijÏWi) в раздел WHERE этого запроса добавляются конъюнкты с содержащими это выражение предикатами, гарантированно возвращающими true на всех результирующих отношениях и использующими при этом наиболее селективный из возможных операторов. При априори известной информации в идеале это может быть оператор сравнения с константой, а в общем случае полной неопределенности может использоваться оператор сравнения с крайним значением, допустимым типом данных.

На этом работа алгоритма, реализующего предлагаемый метод, завершается.

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

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

Для РСУБД, поддерживающих составные индексы по нескольким таблицам, данный метод может быть расширен за пределы локальной оптимизации запросов на оптимизацию выполнения реляционной операции соединения.

Пример использования предлагаемого метода

Рассмотрим следующий вырожденно простейший вариант, доступный всем пользователям СУБД PostgreSQL. В системном каталоге БД с целью поддержания целостности данных, хранящихся в системной таблице описаний pg_cata­log.pg_description, создан единственный для этой таблицы уникальный составной индекс pg_des­cription_o_c_o_index типа btree по набору полей (objoid, classoid, objsubid). Для демонстрации эффективности метода в зависимости от технических средств и версий ОС и СУБД, как правило, достаточно нескольких тысяч записей в этой таблице. В данном случае на выбранной для результативности эксперимента низко производительной ПЭВМ среди 1830 записей в ней имеется единственная запись с classoid=1262. Данные по полю classoid распределены в таблице следующим образом:

SELECT classoid,COUNT(*) FROM pg_cata­log.pg_description GROUP BY classoid;     1247 |   52

    1255 | 1501

    1259 |  266

    1262 |    1

   16396 |    4

   16402 |    3

   16597 |    3

с существенным отличием от статистики по результату выполнения команды ANALYSE. Исходный запрос SELECT * FROM pg_catalog.pg_description WHERE classoid=1262; имеет план выполнения (отображаемый оператором EXPLAIN):

Seq Scan on pg_description (cost=0,00 … 38,88 rows=13 width=34)    Filter: (classoid = 1262::oid)

и выполняется в среднем за 3,8 мс без использования приведенного индекса. Создание нового или корректировка существующего индекса системной таблицы, тем более созданного для поддержания целостности данных, не допускается. Для выбранной единственной записи выполняется условие objoid=1. При априори известном данном значении преобразованный в соответствии с предлагаемым методом запрос выборки всех полей этой же записи

SELECT * FROM pg_catalog.pg_description WHERE classoid=1262 AND objoid=1;

имеет план выполнения

Index Scan using pg_description_o_c_o_index on pg_description                 (cost=0.00..5.65 rows=1 width=34)    Index Cond: ((objoid = 1::oid) AND (classoid = 1262::oid))

и выполняется в среднем за 2,1 мс c использованием индекса. При априори неизвестном значении objoid (или выполняемом для него условии) можно использовать известный факт присвоения всем объектным идентификаторам только натуральных значений. В этом случае преобразованный запрос выборки всех полей этой же записи

SELECT * FROM pg_catalog.pg_description WHERE classoid=1262 AND objoid>0;

имеет план выполнения

Index Scan using pg_description_o_c_o_index on pg_description

                (cost=0.00..5.65 rows=1 width=34)

   Index Cond: ((objoid > 0::oid) AND (classoid = 1262::oid))

и выполняется в среднем за 2,4 мс также c использованием приведенного индекса. Это несколько медленнее, чем для предыдущего запроса, но даже в этом вырожденно простейшем случае существенно быстрее, чем без использования имеющегося составного индекса. Аналогичные преобразования выполняются в случае запроса, возвращающего несколько записей, отфильтрованных по полю classoid и отсортированных по полю objoid. Возвращающий десять записей запрос

SELECT * FROM pg_catalog.pg_description WHERE classoid>15000 AND classoid<17000

   ORDER BY objoid;

выполняется в среднем за те же 3,8 мс по плану

Sort (cost=43.46..43.47 rows=2 width=34)   SORT Key: objoid

   Seq Scan on pg_description  (cost=0.00..43.45 rows=2 width=34)

      Filter: ((classoid > 15000::oid) (classoid < 17000::oid))

а после преобразования запрос

SELECT * FROM pg_catalog.pg_description WHERE classoid>15000 AND classoid<17000

   AND objoid>0 ORDER BY objoid;

выполняется в среднем также за 2,4 мс по плану

Index Scan using pg_description_o_c_o_index on pg_description

                (cost=0.00..7.79 rows=2 width=34)

   Index Cond: ((objoid > 0::oid) AND (classoid > 15000::oid)

                 AND (classoid < 17000::oid))

Полученные результаты во многом определяются низкой кардинальностью таблицы, специфическим распределением данных и соизмеримым количеством дисковых страниц памяти, занимаемых индексом и собственно таблицей (10 и 16 страниц соответственно). Подобные столь же простые вычислительные эксперименты можно произвести и с системной таблицей зависимостей pg_catalog.pg_depend, имеющей два типа btree неуникальных составных индексов pg_depend_de­pender_index по набору полей (classid, objid, objsubid) и pg_depend_reference_index по набору полей (refclassid, refobjid, refobjsubid).

Случай практически значимого применения данного метода, позволившего на порядки сократить время выполнения отдельных запросов, можно рассмотреть на примере постобработки БД тренажерного комплекса «Тест» (НИИ «Центрпрограммсистем», г. Тверь), предназначенного для проведения индивидуальных, автономных и комплексных тренировок радиотехнического подразделения. Особенностью этой постобработки является аналитический разбор проведенного занятия в результате специфического сопоставления в ограниченное время большого количества записей в регистрационных таблицах БД.

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

Литература

1.    Кузнецов С.Д. Базы данных: языки и модели. М.: Бином-Пресс, 2008. 720 с.

2.    Дейт К.Дж. Введение в системы баз данных; [пер. с англ.]. М.: Вильямс, 2005. 8-е изд. 1328 с.

3.    Кайт Т. Oracle для профессионалов: архитектура, методики программирования и особенности версий 9i, 10g и 11g; [пер. с англ.]. М.: Вильямс, 2011. 2-е изд. 848 с.

4.    PostgreSQL 9.1 Documentation, http://www.postgresql. org/files/documentation/pdf/9.1/postgresql-9.1-US.pdf (дата обращения: 11.09.2012).

5.    Кузнецов С.Д., Мендкович Н.А. Оптимизация конъюнктов условий в составе запросов // Моделирование и анализ информационных систем. 2011. Т. 18. Вып. 3. С. 144–154.

References

1.  Kuznetsov S.D., Bazy dannykh: yaziki i modeli [Databases: languages and models], Moscow, Binom-Press, 2008, 720 p.

2.  Date  C.J.,  An Introduction to Database Systems, 8th ed., Addison Wesley, 2004.

3.  Kyte  T.,  Expert Oracle Database Architecture: Oracle Database 9i, 10g and 11g Programming Techniques and Solutions , 2nd ed., Moscow, Apress, 2010.

4.  PostgreSQL  9.1  Documentation, Available at:  http://www. postgresql.org/files/documentation/pdf/9.1 /postgresql-9.1-US.pdf (accessed 11 Sept. 2012).

5.  Kuznetsov S.D., Mendkovich N.A., Modelirovanie i analiz  informatsionnykh sistem  (Modeling and Analysis of Inform. Sys-tems), 2011, Vol. 18, no. 3, pp. 144 –154.