Руководство по созданию эффективных запросов

42

Еще больше теории: алгоритмы
Полное (последовательное) сканирование
При полном сканировании движок базы данных последовательно считывает 
все строки в таблице и для каждой строки проверяет условие фильтрации. 
Чтобы оценить стоимость этого алгоритма, требуется более подробное опи-
сание, показанное псевдокодом в лис тинге 3.1.
Листинг 3.1 

Псевдокод алгоритма доступа к данным полным сканированием
FOR each block IN a_table LOOP
read block
FOR each row IN block LOOP
IF filter_condition (row)
THEN output (row)
END IF
END LOOP
END LOOP
Количество операций ввода-вывода равно 
BR
; общее количество итера-
ций внутреннего цикла равно 
TR
. Нам также необходимо оценить стоимость 
операций, порождающих выходные строки. Она зависит от селективности 
(которая обозначается 
S
) и равняется 
S
*
TR
. Собрав все эти части воедино, 
мы можем вычислить стоимость полного сканирования:
c1 * BR + c2 * TR + c3 * S * TR,
где константы 
c1
, 
c2
и 
c3
представляют характеристики аппаратного обес-
печения.
Полностью просканировать можно любую таблицу; для этого не нужны до-
полнительные структуры данных. Остальные алгоритмы зависят от наличия 
индексов в таблице, как описано ниже.
Доступ к таблицам на основе индексов
Обратите внимание, что пока мы не перешли к физическим операциям, мы 
даже не упоминали алгоритмы доступа к данным. Нам не нужно «читать» 
отношения – это абстрактные объекты. Если следовать идее того, что от-
ношения отображаются в таблицы, нет другого способа получить данные, 
кроме как прочитать всю таблицу в оперативную память. Как еще мы уз-
наем, какие значения содержатся в каких строках? Но реляционные базы 
данных не были бы таким мощным инструментом обработки данных, если 
бы на этом мы и остановились. Все реляционные базы данных, включая 
PostgreSQL, позволяют создавать дополнительные, избыточные структуры, 
значительно ускоряя доступ к данным по сравнению с простым последова-
тельным чтением.
Эти дополнительные структуры называются индексами.
Как создаются индексы, мы рассмотрим позже; пока нам нужно знать два 
факта, касающихся индексов. Во-первых, индексы – «избыточные» объекты 

---

Алгоритмы доступа к данным 

43
базы данных; они не хранят никакой дополнительной информации, которую 
нельзя найти в исходной таблице.
Во-вторых, индексы предоставляют дополнительные пути доступа к дан-
ным; они позволяют определить, какие значения хранятся в строках таб-
лицы, без необходимости чтения самой таблицы – так работает доступ на 
основе индексов. И как упоминалось ранее, это происходит полностью про-
зрачно для приложения.
Если условие (или условия) фильтрации поддерживается индексом в таб-
лице, индекс можно использовать для доступа к данным из этой таблицы. 
Алгоритм извлекает список указателей на блоки, содержащие строки со зна-
чениями, удовлетворяющими условию фильтрации, и только эти блоки чи-
таются из таблицы.
Чтобы получить строку таблицы по указателю, необходимо прочитать 
блок, содержащий эту строку. Основная структура данных таблицы – это 
куча
, 
то есть строки хранятся неупорядоченно. Их порядок не гарантирован и не 
соответствует свойствам данных. Есть две отдельные физические операции, 
используемые PostgreSQL для получения строк с помощью индексов: индекс-
ное сканирование (
index
scan
) и сканирование по битовой карте (
bitmap
heap
scan
). При индексном сканировании движок базы данных считывает одну 
за другой все записи индекса, которые удовлетворяют условию фильтра-
ции, и в этом же порядке извлекает блоки. Поскольку базовая таблица пред-
ставляет собой кучу, несколько записей индекса могут указывать на один 
и тот же блок. Чтобы избежать многократного чтения одного и того же блока, 
в PostgreSQL реализована операция сканирования по битовой карте, которая 
создает битовую карту блоков, содержащих необходимые строки. Потом все 
строки в этих блоках фильтруются. Преимущество реализации PostgreSQL 
состоит в том, что она упрощает использование нескольких индексов в од-
ной и той же таблице в одном запросе, применяя логические операторы «и» 
и «или» к битовым картам блоков, порождаемым каждым индексом.
Стоимостная модель этого алгоритма намного сложнее. Неформально ее 
можно описать так: при малых значениях селективности, скорее всего, все 
строки, удовлетворяющие условиям фильтрации, будут располагаться в раз-
ных блоках, и, следовательно, стоимость будет пропорциональна количеству 
возвращаемых строк. Для больших значений селективности количество об-
рабатываемых блоков приближается к общему количеству блоков. В послед-
нем случае стоимость становится выше, чем стоимость полного сканирова-
ния, поскольку для доступа к индексу необходимы ресурсы.