Хранение данных и доступ к ним

11.1.3 Строки таблиц в блоках базы

Посмотрим, как строки размещаются в блоках таблиц все того же Oracle. Формат строки приведен на рисунке 11.3.:

Заголовок строки состоит из трех байтов — Flag, Lock и Column Count. Отдельные биты байта Flag описывают состояние и расположение строки.

Второй байт определяет особенности блокировок. Третий определяет количество столбцов в строке.

Столбец определяется двумя полями. Первое задает длину столбца, во второе записываются сами данные. Поле Column length принимает значения:

Величина 253 получается потому, что из возможных 256 вариантов три

выпали. Значение 0 не употребляется, так как ширина столбца не может быть нулевой. Код FF обозначает NULL, а FE обозначает столбцы большой длины.

Интересны детали работы со строками в блоке. Запись новых строк ведется от хвоста блока к его голове, где находится заголовок блока. При этом имеющиеся свободные места между строками не учитываются. При удалении строки устанавливается в единицу бит удаления. С данными ничего не происходит. Все остается на прежних местах. При обновлении строки с уменьшением размера она не останется на прежнем месте, а перейдет наверх. И только при обновлениях с сохранением длины всех столбцов строка останется на прежнем месте. Таким образом, при выполнении удалений и обновлений блок постоянно фрагментируется. Тип CHAR в этом отношении имеет преимущества перед VARCHAR. Ниже мы обратим внимание на то, что СУБД может дефрагментировать пространство блока данных.

11.1.4 Заполнение табличного сегмента и миграция строк

Табличный сегмент заполняется последовательно, начиная с первых блоков первого экстента. Указатель, называемый High Water Mark (HWM) устанавливается на первом блоке незаполненной части сегмента. Если затем один или несколько блоков освободятся, HWM сам не сместится вниз. То есть, HWM это что-то вроде медицинского термометра: вверх столбик ртути лезет сам (это соответствует занятию данными очередного блока), а для сбрасывания столбика ртути необходимо встряхнуть термометр (в базе данных это делается с помощью специальной инструкции).

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

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

Если в один блок строку поместить не удается, то ее разбивают на части. Первая часть строки остается в том же блоке (конечно, этот блок исключается из списка свободных блоков), остальные ее части размещаются в других блоках. Такие строки называются сцепленными. Для доступа к ним может потребоваться несколько чтений с диска, что значительно замедлит обработку.

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

Теперь пример раздела 10.3.1 с извлечением информации о созданной таблице с помощью метода get_ddl() стал значительно понятнее: начальный размер сегмента таблицы 64K, PCTFREE = 10%, PCTUSED = 40%, "PCTPNCREASE 0" означает, что увеличение сегмента производится равными экстентами, "FREELISTS 1" определяет единственный список блоков пригодных для записи, сегмент таблицы находится в табличном пространстве USERS и т. д.

11.1.5 Фрагментация

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

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

Фрагментация сегментов — это естественное явление, которое мало влияет на производительность.

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

Основные производители СУБД прекрасно понимают проблемы, связанные с фрагментацией базы, и движение в сторону автоматического обнаружения фрагментации и устранения ее вредных разновидностей наблюдается давно и уже близко к завершению.

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

11.1.6 Столбцовая и строчная организация таблиц

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

На самом деле существуют СУБД реляционного типа, которые хранят данные в столбцах (Sybase IQ и др.). В других используется строчное представление основных типов данных, а большие типы (BLOB'bi) хранятся в столбцах (Oracle).

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

SELECT coll FROM TABLE WHERE COl25=1

к таблице из 25 столбцов со столбцовой организацией теперь не нужно читать "лишние" данные из 23 столбцов.

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

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

Большой интерес представляют СУБД столбцового типа BigTable фирмы Google, Everest фирмы Yahoo, Hadoop и Hbase. Все они предназначены для создания хранилищ данных очень большого объема в больших кластерах серверов или облаках. CouchDB столбцовая, документно-ориентированная база.

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

11.2 Словари в базах данных

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

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

Структура словаря не может изменяться пользователем базы. Кроме того, пользователь не может манипулировать данными словаря, содержащими метаданные, непосредственно. Он выполняет некоторые действия в базе, а СУБД, проверяя возможность исполнения действия, сама анализирует словарь и, при необходимости, вносит в него изменения.

Например, прежде чем выполнить запрос SELECT * FROM emp, СУБД проверит существует ли таблица с именем emp, а затем прочитает перечень имен столбцов этой таблицы, чтобы заменить им символ *. После этого запрос будет выполнен.

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

Метаданные можно разделять по нескольким основаниям. По долговечности метаданных отделим постоянные метаданные, изменяемые только при выполнении инструкций DDL, от переменных метаданных, характеризующих состояние хранимого объекта, например, число записей в наборе (таблице). Для каждого из хранимых объектов базы необходимы свои метаданные. Типовой список хранимых объектов:

В объектно-реляционной модели могут быть добавлены:

Существуют объекты не зависимые или не обязательно зависимые от схемы:

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

11.2.1 О структурах словаря

По сути, словарь представляет собой вторую базу данных с двумя пользователями. Главный пользователь словаря это СУБД. Пользователи-люди сильно ограничены в правах. Они могут читать метаданные, но не могут менять структуру словаря и заносить в него метаданные непосредственно.

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

Обратите внимание на то, что в Oracle имя схемы совпадает с именем владельца схемы, так что поле OWNER можно еще читать как СХЕМА.

Метаданные управления доступом к данным также слишком отличаются, чтобы можно было представить какую-то общую структуру.

Если база данных интегрирована с построенными на ее основе приложениями, то она может содержать метаданные приложений, в том числе, интерфейсов пользователя. Упомянем в качестве примера Microsoft Access.

11.3 Индексы

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

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

Второй, авторский, позволяет выбрать книги по авторам.

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

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

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

Таблица может иметь внутренний псевдостолбец с именем ROWTD. Он не виден при выполнении команды SELECT * FROM ... , но обычно может быть выбран запросом с явным указанием ROWTD как имени столбца, что-нибудь вроде SELECT ROWID, ename FROM emp.

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

В ROWID содержатся, например, поле, определяющее один из файлов данных, принадлежащих табличному пространству, поле блока данных и поле номера строки в блоке. Современные СУБД поддерживают, как минимум следующие типы индексов:

Альтернатива индексированию — хеширование.

11.3.1 B*-индексы

Что такое B-дерево?

B*-дерево отличается тем, что в нем каждый ключ сопровождается указателем на запись (или записи) с этим ключом.

Следует помнить, что в отличие от графов, изучаемых в математике, узлы B-дерева это блоки базы данных..

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

Могут существовать другие типы индексов и структур, связанных с ними, например, индексные таблицы (index-organized table). Это разновидность B*-индекса, в которой листовые блоки индекса содержат не значения ROWID, адресующие данные, а сами данные в виде строки, не разделяемой на поля.

Рассмотрим пример работы B*-индекса, построенного на столбце ename (рисунок 11.4). Из таблицы emp выбираем по индексу строку с именем BLAKE, удовлетворяющую условию ENAME='BLAKE'. Такой поиск называется поиском по точному совпадению.

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

Сначала просматривается корневой блок, и по условиям <KJNG и >=KJNG определяется, на который из двух дочерних блоков перейти. Идем по левой ветви. В блоке первого уровня проверяются условия <BLAKE, >=BLAKE и >=JAMES и выбирается второе. Затем из листового блока второго уровня, содержащего три значения ROWID, выбираем идентификатор для BLAKE и, используя его как адрес, выбираем значение из файла данных.

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

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

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

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

Заметим, что блокирование на уровне строк удобно реализуется при описанной структуре индекса, задающего адреса именно строк.

Если строки индекса постоянно удаляются и добавляются, то через какое-то время индекс может "разредиться" или фрагментироваться. Обычно индекс расширяется вправо, и разрежается слева. Дело в том, что "брошенные" записи не заменяются новыми. Со временем объем индекса может существенно превысить объем данных. Дерево индекса может при этом стать глубже, чем должно быть для такого числа значений. Это уменьшает скорость индексного доступа. Поскольку типовой механизм организации B*-индекса не поддерживает динамического уплотнения и перебалансирования дерева, то лучшее решение в этом случае — пересоздание индекса. Например, при односменной работе вечером копируем таблицу, сортируя данные. Старую таблицу и индекс уничтожаем. Затем восстанавливаем таблицу по сортированной копии и создаем новый индекс. Дальше все зависит от того, насколько таблица изменится за следующий день.

11.3.2 Когда B*-индекс ускоряет запрос?

В литературе 80-х-90-х годов можно было найти "золотое правило", в соответствии с которым неуникальным индекс ускоряет работу, если запрос возвращает меньше, чем 10-15% строк таблицы. Попозже эти цифры заменили на 3-5% и правило перестали называть золотым.

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

Рассмотрим два крайних случая. Пусть таблица содержит 100 000 строк по 100 строк в каждом из 1000 блоков. Ключевой столбец содержит числовые значения от 0 до 99. Строки случайно распределены по блокам, так что в любом блоке с большой вероятностью содержатся строки с любым ключевым значением. При выполнении запроса по одному значению ключа, скорее всего, будут прочитаны все блоки, хотя нужно выбрать всего один процент строк. Кроме того, будут прочитаны еще и все блоки индекса, причем некоторые многократно. Это увеличит время выполнения запроса. Если индекс не используется, то также выбираются все 1000 блоков таблицы. В рассмотренной ситуации индекс не эффективен.

Теперь отсортируем строки таблицы по ключу. При использовании индекса будет выбран всего один блок данных и несколько блоков индекса. Без индекса пришлось бы выбирать все 1000 блоков таблицы. Теперь индекс ускоряет запрос.

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

Использование индекса ускоряет выполнение запроса за счет того, что позволяет считывать только блоки, содержащие нужные строки.

11.3.3 Индексы битовой карты

Побитовые (BitMapped) индексы это разновидность неуникальных индексов. Побитовые индексы предназначены в первую очередь для работы с хранилищами данных. Эффективны они при малой разрешающей способности столбца. Функционально битовый индекс идентичен обычному древесному индексу, хотя внутреннее их устройство различно. Сами битовые индексы хранятся в виде B*-структуры.

Структура строки битового индекса в Oracle (рисунок 11.5): (<зна-чение_ключа, начальное_значение_rowid, конечное_значение_rowid, сег-мент_двоичной_карты>). где:

Сравним индексы. Пара <значение ключа, rowid> в B*-индексе заменена парой <значение ключа, сегмент двоичной карты>, где "значение_ключа" состоит из колонок "значение_ключа", "начало_rowid" и "конец_rowid". Битовые индексы, как и древесные, могут быть конкатенироваными.

Операции с индексами битовой карты могут выполняться очень быстро, так как логические операции над битовыми матрицами транслируются непосредственно в команды центрального процессора, выполняющие побитовые операции над словами длиной 32 или 64 бита.

Рассмотрим пример выполнения операции поиска в группе из 14-ти человек сильных программистов высокого роста.

Пример битовой карты приведен в таблицах 11.2 и 11.3.

Тогда запрос "Найти сильных программистов высокого роста" оформляется как обычно:

SELECT фамилия FROM программисты
WHERE Рост = 'Высокий' AND Сила = 'Большая'

В действительности сначала будет выполнено побитное И над битовыми картами для полей Рост и Сила (таблица 11.4).

Подходят 4-я, 9-я, 11-я и 13-я строки. Они и будут выбраны.

11.3.4 Замечание о других индексах

Вспомним, что В*-индексы строятся в предположении возможности линейной упорядоченности значений столбца.

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

Используя Z-упорядочение, кривую Гильберта и другие средства, можно отобразить многомерное пространство в одномерное.

Ниже показано порождение кривой Гильберта (рисунок 11.6).

Однако, при этом топологические свойства нарушаются. Обратим внимание на следующие особенности:

И еще одна проблема: как выполнять операции над объектами, описанными в разных сетках?

Естественным расширением В*-деревьев на многомерные области являются R-деревья. Это сбалансированные деревья, в которых листья ссылаются на минимальные прямоугольники, имеющие стороны параллельные осям координат и ограничивающие все объекты, по которым выполняются запросы.

11.4 Буферы базы

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

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

Рассмотрим один вариант буферизации данных. Кэш буферов данных, реализующий алгоритм LRU (рисунок 11.7) может содержать большое количество блоков, исчисляемое сотнями тысяч и более. Вспомним, что название стратегии LRU (Least Recently Used) переводится как "самый давно используемый". По этой стратегии в первую очередь должны быть удалены блоки, к которым дольше всего не было обращений.

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

При логическом чтении выбранный блок из середины кэша перемещается в голову. Часть кэша левее выбранного блока смещается вправо на один блок.

Со временем кэш заполнится. Часто используемые блоки будут находиться ближе к голове. Редко используемые блоки будут сдвигаться к хвосту.

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

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

Заметим, что существуют более эффективные стратегии, например, LRU-K. Можно также использовать несколько кэшей буферов базы.

11.5 Представление таблиц в базах данных реляционного типа

В современных СУБД используются следующие виды таблиц:

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

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

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

Индексно-организованные таблицы это B*-индексы, в которых листовые узлы вместо ссылок на строки таблицы содержат саму строку.

Временные таблицы предназначены для хранения данных во время транзакции или сеанса. Это промежуточные таблицы при расчетах или составлении отчетов. Обычно данные временной таблицы невидимы из других сеансов или транзакций. По завершении транзакции или сеанса данные временных таблиц удаляются.

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

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

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

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

Внешние таблицы это некоторые объекты, лежащие вне базы, например, таблицы Excel. Их можно только читать.

11.6 Доступ к данным

Рассмотрим основные способы доступа к данным одной или многих таблиц. Знакомство с ними позволит нам в разделе 11.7 разобраться с планами исполнения запросов.

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

11.6.1 Доступ к единственной таблице

Существует два варианта доступа к одной таблице:

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

11.6.2 Соединения

Рассмотренные в лекции 8 эталонные алгоритмы выполнения запросов SQL к нескольким таблицам, основаны на создании декартового произведения, которое даже для не очень больших таблиц вычисляется неприемлемо медленно.

Мы рассмотрим три способа реализации соединений, используемые в практике — соединения при помощи вложенных циклов (nested loops), соединения хешированием (hash join) и соединения с сортировкой слиянием

(merge join). В соединениях хэшированием и с сортировкой слиянием сначала обращаются к каждой таблице отдельно, а затем соединяют соответствующие строки и отбрасывают ненужные.

В дальнейшем это позволит нам понимать конструкции планов исполнения запросов SQL. А овладение знаниями и навыками управления планами исполнения — это еще один слой знаний SQL, совершенно необходимый для написания запросов на профессиональном уровне.

Первый вариант — соединение при помощи вложенных циклов (рисунок 11.8)

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

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

Третий вариант — соединение с сортировкой слиянием (рисунок 11.10) Таблицы считываются независимо. Оба результирующих набора предварительно сортируются по ключу соединения и затем соединяются.

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

Сравним соединения:

11.7 Оптимизация запросов в SQL

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

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

Приложение это программа, создающая вызовы к базе данных и, может быть связывающее несколько баз данных и средства обработки информации. Необходимо управлять способом обращения к СУБД и объемами запрашиваемых или передаваемых данных.

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

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

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

Существует два типа оптимизаторов:

Из всего многообразия имеющихся здесь задач мы, очень поверхностно, рассмотрим несколько примеров для небольшого, но важного раздела настройки SQL (SQL tuning) в варианте оптимизации по правилам.

11.7.1 Планы исполнения

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

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

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

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

11.7.2 Примеры планов исполнения

Из-за ограниченности объема мы можем только показать несколько примеров планов, дав минимальные пояснения. Искусство управления планами, работа с оптимизаторами, сбор статистики останутся за кадром.

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

Управлять планом исполнения можно размещая после слова SELECT подсказки в виде комментариев специального вида (hints). Например, подсказка в запросе

SELECT /*+INDEX*/ empno FROM emp WHERE empno = 1739;

означает требование воспользоваться индексом. Правда оптимизатор может и не выполнить указание.

Перечислим некоторые подсказки используемые для управления планом исполнения (таблица 11.6)

Примеры планов, приведенные ниже получены в СУБД Oracle. Их следует читать из глубины вверх. Помните, что выбор плана исполнения сильно зависит от настройки СУБД и ее версии, так что при самостоятельной работе вы можете получить совсем другие результаты. Как писал один из авторов хорошей книги по SQL-тюнингу, "не верь тому, что здесь написано".

Для просмотра планов исполнения в Oracle ХЕ необходимо выбрать закладку Explain.

Примеры планов:

SELECT * FROM emp;

SELECT STATEMENT
TABLE ACCESS full emp

SELECT * FROM emp WHERE sal>1000;

SELECT * FROM emp ORDER BY ename;

SELECT STATEMENT SORT order by
TABLE ACCESS full emp

SELECT * FROM emp ORDER BY ename;

SELECT STATEMENT
TABLE ACCESS full emp
INDEX full scan i_emp_ename

SELECT job,  sum(sal) FROM emp GROUP BY job HAVING sum(sal)> 100000;

SELECT STATEMENT FILTER
SORT group by
TABLE ACCESS full emp

SELECT * FROM emp WHERE rowid=,00004F2A00A2 000C';

SELECT STATEMENT
TABLE ACCESS by rowid emp

SELECT * FROM emp, dept;

SELECT STATEMENT
NESTED LOOPS TABLE ACCESS full dept
TABLE ACCESS full emp

SELECT ename FROM emp WHERE job  || ''^MANAGER';

SELECT * FROM emp, dept WHERE emp.deptno=dept.deptno;

SELECT STATEMENT
MERGE JOIN
SORT JOIN
TABLE ACCESS full emp
SORT JOIN TABLE ACCESS full emp

SELECT STATEMENT NESTED LOOPS TABLE ACCESS full dept
TABLE ACCESS by rowid emp
INDEX range scan idx_fk_emp_deptno

В Cache для просмотра плана исполнения достаточно в окне исполнения SQL-инструкции выбрать позицию Explain, но планы там описываются иначе.

11.8 Об архитектуре системы управления базами данных

Пытаться построить полную общую модель СУБД дело заведомо безнадежное. Например, архитектуры изучавшейся нами Cache и Oracle вообще трудно сопоставимы. Однако, общее на уровне выполняемых функций и в работе с памятью найти можно.

11.8.1 Архитектура памяти

Очевидно, любая СУБД должна управлять оперативной и внешней памятью.

В оперативной памяти обязательно поддерживаются кэш буферов базы и кэш буферов журналов (рисунок 11.11), которые мы изучали. Выделяется место для пользовательских и серверных процессов. Разделяемый пул содержит кэш словаря и библиотечный кэш. Последний предназначен для хранения и обработки курсоров, представляющих рекомендованный стандартом механизм исполнения запросов в SQL.

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

Курсоры могут использоваться процедурными языками, которыми снабжаются все SQL базы данных. В Oracle это PL/SQL, в MS SQLServer язык TransactSQL. В Cache с курсорами можно работать из программ написанных в COS.

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

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

11.8.2 Пользователи

Пора вспомнить незаслуженно забытого нами пользователя (user). Обычно пользователь имеет имя, пароль и конфигурацию.

Команда создания пользователя может начинаться так:

CREATE USER имя_пользователя IDENTIFIED BY пароль ...

Конфигурация в Oracle определяет:

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

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

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

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

11.9 Администрирование и программирование

Ограниченность объема и выбранная направленность книги не позволяют нам больше задерживаться на вопросах администрирования баз данных.

Все же полученных скудных сведений об архитектуре СУБД достаточно, чтобы представить себе сложность управления базами данных и тот громадный объем труда, который был вложен в создание любой СУБД, а тем более таких долгожителей как Cache и Oracle.

Начинающим полезно иметь хотя бы общие представления о той "закулисной" деятельности, которую ведет СУБД, исполняя инструкции какого-нибудь языка, и о том, что современная СУБД может сама анализировать структуры данных и даже исправлять их недостатки. Есть основания полагать, что в задачах оптимизации планов исполнения, автоматического исправления индексов и устранения вредной фрагментации данных используются системы искусственного интеллекта.

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

В целом, администрирование баз данных — это обширная область, требующая большого объема специфических знаний и навыков. Конечно, знания программиста и администратора во многом пересекаются. Однако, существует принципиальное различие в жизненных позициях администратора и программиста. У программиста при виде чужой программы от желания все переделать начинают чесаться шаловливые ручки. Администратор, как хорошая мама, живет жизнью своего ребенка, то есть приложения, базы данных. Он должен понимать состояние приложения сегодня, и знать, как оно меняется в последнее время. Он должен знать, что для улучшения положения дел ему часто придется двигаться методом проб и ошибок. Поэтому он всегда обеспечивает возможность возврата к прежнему состоянию. Как сказал один хороший администратор: "Я из тех людей, которые, прежде чем взяться за ручку двери думают, а как я оттуда буду выходить?".

Можно предположить, что администрирование — это преимущественно женская профессия. Но женщин-администраторов все же немного. Слишком тяжел груз ответственности и слишком многое нужно знать.