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