Классика баз данных - статьи

Одиночная таблица


В оптимизаторах DB2 имеются два базовых пути доступа: через индекс и через сканирование таблицы. При доступе через сканирование таблицы просто проверяется каждая ее строка с возможным применением предикатов. Оптимизатор должен тщательно разделять и моделировать как «SARGable»-предикаты (SARG происходит от Search ARGument), так и «остаточные» предикаты. SARGable-предикаты применяются, когда страница закрепляется за буфером, чтобы избежать нетребуемых расходов ЦП на копирование строки. Предикаты, включающие вложенный подзапрос (еще один блок запроса SELECT FROM WHERE), который зависит от некоторого значения в сканируемой таблице (коррелирует с ним), должны заново вычисляться для каждого такого значения. Чтобы избежать потенциального самоблокирования, когда дополнительные страницы считываются в буфер для подзапроса, в DB2 откладывается применение таких «остаточных» предикатов до того времени, когда строка будет скопирована из буфера.

В DB2/* записи каждой таблицы хранятся отдельно от записей любой другой таблицы. В DB2/2 Version 1 все они помещаются в один файл, в то время как в DB2/6000 Version 1 они расщепляются на разделы, называемые сегментами. Это ограничение ослабляется в DB2 для MVS, но обычно клиенты считают более эффективным размещение каждой таблицы в своем собственном физическом пространстве.

В DB2 и DB2/* индексы поддерживаются за счет многостолбцовых B+-деревьев и используются для упорядочения, группирования схожих значений, обеспечения уникальности, обеспечения альтернативы доступа к базовой таблицы (доступ только к индексу) и прямого доступа к только тем строкам, которые удовлетворяют некоторым предикатам. В оптимизаторах DB2 используются разнообразные и очень сложные стратегии индексного доступа.

Возможно, наиболее важной ролью индексов является последняя из перечисленных выше: применение предикатов для минимизации числа страниц данных, которые требуется посетить. Предикаты со ссылками только на столбцы индекса могут применяться в качестве SARG’ов к значениям ключа индекса во время сканирования листовых страниц.
Однако SARG’и, которые могут быть использованы для определения стартового и завершающего значений ключа, еще больше сокращают объем ввода/вывода за счет ограничения сканирования индекса некоторым поддеревом. Поэтому оптимизаторы DB2 идут на многое, чтобы использовать как можно больше предикатов в качестве стартового/завершающего условий.

Простые предикаты, включающие простое сравнение столбца со значением ил выражением (например, DEPTNO = 'K55'), являются кандидатами в старт/стоповые условия, равно как и предикаты соединения, «проталкиваемые» (pushed down) на внутреннюю таблицу соединения с вложенными циклами (см. следующий подраздел), и даже подзапрос, возвращающий единственное значение (например, EMP.SALARY= (SELECT MAX(SALARY) FROMEMP)).

Более сложные предикаты, такие как BETWEEN (пара предикатов диапазона), LIKE (пара предикатов диапазона может быть извлечена, если первым символом шаблона LIKE не является метасимвол) и предикат IS NULL также могут использоваться как старт/стопные условия. Может использоваться даже предикат IN <list> либо путем стортировки <list> и успешного использования каждого значения в качестве старт/стопного ключа (в DB2 для MVS), либо использования объединения идентификаторов строк (в DB2/*), описываемого ниже.

Для поддержания эффективности индексных операций наличие выражений и даже преобразований типа на индексном столбце обычно препятствуют использованию этого столбца как условия старта или остановки. Однако в DB2/* типы данных в сравнении не обязаны быть идентичными; они должны лишь удовлетворять требованиям совместимости ANSI между строками и символами.

Оказывается поразительно сложно определить, когда предикаты могут использоваться как старт/стопные условия, и когда их можно применить и как SARG’и. Ключи индекса формируются путем конкатенации значений столбцов из любого числа столбцов индекса, но старт/стопные условия сократят сканирование индекса, только если старшие по порядку (лидирующие, или префиксные) столбцы ограничиваются предикатами.


Например, индекс на столбцах X и Y не может получить удачное старт/стопное условие при наличии предиката на Y, если не имеется предиката и на X.



Предикат может всегда применяться как старт/стопный ключ, только если операцией сравнения в предикате является «=». Если имеется предикат на столбце «=», «≥» или «≤», то предикаты на последующих столбцах являются кандидатами на старт/стопные условия. Однако после первого предиката со сравнением на неравенство последующие столбцы индекса не являются полезными и могут быть применены как SARG’и. Например, предположим, что имеется единственный индекс на столбцах X, Y и Z. Для предикатов X = 5, Y ≥ 7, Z ≥ 'B' в DB2 был бы построен стартовый ключ 57, стоповый ключ 5, и предикат на Z применялся бы как SARG. В DB2/* с использованием Stardurst будет построен ключ 57'B', и предикат на Z будет применен и как SARG, потому что сканирование индекса, начинающееся с этого значения ключа, может включать такие значения, как 58'A', не удовлетворяющие предикату на Z. Если бы предикат на Y ≥ 7 был строгим неравенством, в DB2/* Version 1 сканирование начиналось бы с 57, и предикаты на Y и Z применялись бы как SARG’и.

Поскольку столбцы индекса могут в индивидуальном порядке объявляться как упорядоченные по возрастанию или по убыванию, для столбцов индекса с упорядочением по убыванию старт/стопные условия должны перевертываться; например, если столбец Z упорядочивается по убыванию, то Z > 'B' является его стоповым условием. Наконец, когда уникальный индекс является «полностью уточненным» (т.е. со всеми его столбцами связаны предикаты сравнения по равенству), все оптимизаторы DB2 понимают, что может быть выбрана, самое большее, одна строка, так что менеджер данных может пользоваться ускоренным доступом, и могут быть предприняты другие средства эффективной обработки.

Если оптимизатор определяет, что индекс содержит все столбцы таблицы, к которой адресуется запрос, или если запрос имеет вид SELECT MIN(SALARY) FROM EMP,

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


В противном случае чтение этих страниц может производиться незамедлительно или откладываться до тех пор, пока не будут собраны все RID’ы, получаемые из индекса. В этом случае возможна дальнейшая обработка списков RID’ов.

Например, в DB2 для MVS имеется возможность сначала отсортировать RID’ы, упорядочивая RID’ы в (физическом) порядке страниц, что улучшает действующую кластеризацию некластеризованных индексов и, таким образом, минимизирует число выборок данной страницы. В DB2/* с использованием Starburst также будет поддерживаться эта стратегия.

Когда в разделе WHERE содержится более одного предиката или комбинации предикатов, которые могут использоваться как старт/стопные ключи на индексе, оптимизаторы DB2 принимают во внимание возможность множественного сканирования одного и того же индекса или даже сканирования нескольких индексов для одной и той же таблицы. Например, если предикат имеет вид ZIPCODE BETWEEN 90100 AND 90199 OR ZIPCODE BETWEEN 91234 AND 91247,

и имеется индекс на столбце ZIPCODE, в DB2 будет рассматриваться план, в котором к этому индексу доступ производится дважды: один раз со старт/стопными ключами (90100,90199) и другой – с (91234,91247). Затем списки кортежей будут объединены с удалением дубликатов. Иногда это называют «index Oring».

В DB2/* на основе Starburst эта обработка списков RID будет расширена включением пересечения («ANDing») списков RID’ов, что позволит избежать чтения страниц данных при наличии индексов на всех используемых в запросе столбцах. Например, для запроса SELECT C1, C2 FROM T WHERE C1 = 10 AND C2 = 47

будут сохранены RID’ы от сканирования индекса по C1 со стартовым ключом 10 и стоповым ключом 10, и пересечены с RID’ами от другого индексного сканирования по C2 со стартовым и стоповым ключом 47. Поскольку все столбцы, на которые имеются ссылки в запросе, доступны через индексы, не требуются чтения страниц данных.

В DB2 для MVS в настоящее время выполняется как Oring, так и ANDing с многими индексами в сложных комбинациях предикатов с AND и OR с использованием методов, представленных в [MHWC90].


Один и тот же индекс может использоваться много раз. Например, если для таблицы T имеется единственный индекс I на столбцах C1 и C2, то для запроса SELECT C1,C2 FROM T WHERE C1 = 10 AND (C2 = 32 OR C2 = 97)

в DB2 для MVS индекс I мог бы использоваться дважды, один раз со стартовым и стоповым ключом 1032, а другой раз – 1097. Поддерживается любой уровень вложенности AND/OR, и может использоваться любое число индексов с учетом возможных ограничений по памяти. Для обработки нескольких индексов оптимизатор производит очень подробный анализ для определения наилучшего порядка обработки, минимизирующего как использование памяти (число RID’ов), так и число обращений к таблице. Во время выполнения этот план может быть изменен или остановлен, как это описывается в разд. 7.4.

Одной из опасностей использования индекса в операторе UPDATE является то, что обновленные строки могут быть помещены далее текущей позиции индексного скана и обновлены еще раз, если выбирается инекс на обновляемом столбце. Например, следующий оператор мог бы привести к бесконечному увеличению зарплаты, если бы для сканирования EMP использовался индекс на SALARY: UPDATE EMP
SET SALARY = SALARY * 1.1

Эта семантическая аномалия была любовно названа «проблемой Хеллоуин» покойным Мортоном Астраханом (Morton Astrahan), посольку Пат Селинджер (Pat Selinger) обнаружила ее в Хеллоуин. Эта проблема возникает только из-за того, что доступ к строкам и их обновления конвейеризуются, что обычно бывает полезно, и ее можно избежать путем сбора всех RID’ов строк, подлежащих обновлению, до начала их обновления.


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