Для чего используются индексы

Индексы в PostgreSQL

Авторизуйтесь

Индексы в PostgreSQL

Full Stack Developer в DataArt

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

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

Предназначение индексов

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

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

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

В качестве примера рассмотрим задачу поиска в списке чисел. Используя перебор элементов списка, в худшем случае, нам придется просмотреть список целиком. Алгоритмическая сложность такого метода — O(n). Но если мы будем хранить наши числа особым образом — отсортированными по возрастанию или по убыванию — сможем использовать алгоритм бинарного поиска.

2 4 5 10 23 34 38 58 112 114 115 110 123 134 138 158 180

Допустим, необходимо определить, содержит ли этот отсортированный список число 158. Для этого:

В итоге метод бинарного поиска дал нам результат всего за три шага. При полном переборе с начала списка нам потребовалось бы 16 шагов. Бинарный поиск имеет алгоритмическую сложность O(log(n)). Используя формулы алгоритмической сложности O(n) и O(log(n)), мы можем оценить, как будет меняться приблизительное количество операций при поиске разными способами с ростом объема данных:

Результат впечатляет. Храня данные в отсортированном виде, мы не только снизили скорость поиска по ним, но и колоссально сократили скорость замедления поиска при росте объема данных.

Использование индексов в базе данных дает аналогичный результат. Принцип работы одного из важнейших индексов в базе данных (индекс на основе B-дерева) основан именно на рассмотренном нами выше принципе — возможности хранить данные в отсортированном виде.

Индексы в PostgreSQL

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

SELECT * FROM table_name WHERE P(column_name) = 1

Предикат P может вычисляться от значения нескольких колонок. В этом случае для ускорения запроса используется индекс, построенный не для одной колонки, а для нескольких. Такие индексы называют составными.

Если мы хотим ускорить выполнение запроса, условие которого вычисляется по одной или нескольким колонкам, в PostgreSQL нам необходимо создать для этих колонок индекс с помощью команды CREATE INDEX :

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

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

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

CREATE INDEX index_name ON table_name(lower(text_field))

И такой индекс уже может успешно применяться для ускорения нашего запроса.

CREATE INDEX index_name ON table_name USING GIST (column_name)

B-tree

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

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

Какой тип запросов может быть ускорен с помощью B-дерева? На самом деле, практически любой запрос, условие которого является выражением, состоящим из полей входящих в индекс, логических операторов и операций равенства/сравнения. Например:

Выполнение этих и многих других запросов может быть ускорено с помощью B-дерева. Кроме того, индекс на основе B-дерева ускоряет сортировку результатов, если в ORDER BY указано проиндексированное поле.

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

Однако хранить индекс просто в виде отсортированного массива мы не можем, т. к. данные могут модифицироваться: значения могут меняться, записи — удаляться или добавляться. Чтобы эффективно поддерживать хранение индексируемых данных в отсортированном виде, индекс хранят в виде сбалансированного сильно ветвящегося дерева, называемого B-деревом (B-tree).

Корневой узел B-дерева содержит в упорядоченном виде несколько значений из общего набора, допустим, t элементов. Тогда все остальные элементы можно распределить по t+1 дочерним поддеревьям по следующему правилу:

Каждое поддерево, в свою очередь, тоже является B-деревом, имеет корневой элемент и строится далее рекурсивно по такому же принципу.

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

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

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

Индекс на основе B-дерева может ускорять запросы, которые используют не целиком входящие в индекс поля, а любую часть, начиная с начала. Например, индекс может ускорить запрос LIKE для поиска строк, которые начинаются с заданной подстроки:

SELECT * FROM table_name WHERE text_field LIKE ‘start_substring%’

Если индекс построен по нескольким колонкам, он может ускорять запросы, в которых фигурируют одна или несколько первых колонок. Поэтому важен порядок, в котором мы указываем колонки при создании индекса. Допустим, у нас есть индекс по колонкам col_1 и col_2. Тогда он может использоваться в том числе для ускорения запроса вида:

SELECT * FROM table_name WHERE col_1 = 123

И нам не нужно создавать отдельный индекс для колонки col_1. Будет использоваться составной индекс (col_1, col_2).

Однако для запроса только по колонке col_2 такой составной индекс уже использовать не получится.

Подробнее, как индекс на основе B-дерева реализован в PostgreSQL, см. статью.

GiST и SP-GiST

GiST — сокращение от «generalized search tree». Это сбалансированное дерево поиска, точно так же, как и рассмотренный ранее b-tree. Но b-tree применимо только к тем типам данных, для которых имеет смысл операция сравнения и есть возможность упорядочивания. Но PostgreSQL позволяет хранить и такие данные, для которых операция упорядочивания не имеет смысла, например, геоданные и геометрические объекты.

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

Например, в GiST-индекс можно уложить R-дерево для пространственных данных с поддержкой операторов взаимного расположения (находится слева, справа; содержит и т. д.). Такой индекс доступен в PostgreSQL и может быть полезен при разработке геоинформационных систем, в которых возникают запросы вида «получить множество объектов на карте, находящихся от заданной точки на расстоянии не более 1 км».

SP-GiST похож GiST, но он позволяет создавать несбалансированные деревья. Такие деревья могут быть полезны при разбиении множества на непересекающиеся объекты. Буквы SP означают space partitioning. К такому типу индексов можно отнести kd-деревья, реализация которых присутствует в PostgreSQL. Его, как и R-дерево, можно использовать для ускорения запросов геометрического поиска. Свойство непересечения упрощает принятие решений при вставке и поиске. С другой стороны, получающиеся деревья, как правило, слабо ветвисты, что усложняет их эффективное хранение во внешней памяти.

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

Подробнее об алгоритмах, лежащих в основе R- и kd-деревьев см. раз и два, а об их реализации и использовании в PostgreSQL см. в этой и этой статье.

Заключение

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

PostgreSQL поддерживает разные типы индексов для разных задач:

Источник

Основы индексов в Microsoft SQL Server

В данном материале будут рассмотрены такие объекты базы данных Microsoft SQL Server как индексы, Вы узнаете, что такое индексы, какие типы индексов бывают, как их создавать, оптимизировать и удалять.

Что такое индексы в базе данных?

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

Типы индексов в Microsoft SQL Server

В Microsoft SQL Server существуют следующие типы индексов:

Создание и удаление индексов в Microsoft SQL Server

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

Примечание! В качестве SQL сервера у меня выступает версия Microsoft SQL Server 2016 Express.

Создание индексов

Для создания индексов в Microsoft SQL Server существует два способа: первый – это с помощью графического интерфейса среды SQL Server Management Studio (SSMS), и второй – это с помощью языка Transact-SQL, мы с Вами разберем оба способа.

Исходные данные для примеров

Давайте представим, что у нас есть таблица с товарами под названием TestTable, в которой есть три столбца:

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

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

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

Для примера давайте просто создадим кластеризованный индекс, без создания первичного ключа. Сначала сделаем это с помощью Management Studio.

Открываем SSMS и в обозревателе объектов находим нужную таблицу и щелкаем правой кнопкой мыши по пункту «Индексы», выбираем «Создать индекс» и тип индекса, в нашем случае «Кластеризованный».

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

После ввода всех необходимых параметров жмем «ОК», в итоге будет создан кластеризованный индекс.

Точно также можно было бы создать кластеризованный индекс, используя инструкцию T-SQL CREATRE INDEX, например, вот так

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

Пример создания некластеризованного индекса с включенными столбцами

Сейчас давайте рассмотрим пример создания некластеризованного индекса, при этом мы укажем столбцы, которые не будет являться ключевыми, но будут включаться в индекс. Это полезно в тех случаях, когда Вы создаете индекс для конкретного запроса, например, для того чтобы индекс полностью покрывал запрос, т.е. содержал все столбцы (это называется «Покрытием запроса»). Благодаря покрытию запроса повышается производительность, так как оптимизатор запросов может найти все значения столбцов в индексе, при этом не обращаясь к данным таблиц, что приводит к меньшему числу дисковых операций ввода-вывода. Но помните, что включение в индекс неключевых столбцов влечет за собой увеличение размера индекса, т.е. для хранения индекса потребуется больше места на диске, а также может повлечь и снижение производительности операций INSERT, UPDATE, DELETE и MERGE на базовой таблице.

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

Далее переходим на вкладку «Включено столбцы» и с помощью кнопки «Добавить» добавляем столбцы, которые мы хотим включить в индекс, в нашем случае, например, ProductName.

На Transact-SQL это будет выглядеть следующим образом.

Пример удаления индекса в Microsoft SQL Server

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

или также можно использовать инструкцию DROP INDEX, например

Следует отметить, что инструкция DROP INDEX неприменима к индексам, которые были созданы путем создания ограничений PRIMARY KEY и UNIQUE. В данном случае для удаления индекса нужно использовать инструкцию ALTER TABLE с предложением DROP CONSTRAINT.

Оптимизация индексов в Microsoft SQL Server

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

В каких случаях использовать реорганизацию индекса, а в каких перестроение?

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

В данном случае нас интересует столбец avg_fragmentation_in_percent, т.е. процентная доля логической фрагментации.

Так вот, Microsoft рекомендует:

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

Реорганизация индексов

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

Для реорганизации индекса можно использовать как графический инструмент SSMS, так и инструкцию Transact-SQL.

Реорганизация индекса с помощью Management Studio

Реорганизация индекса с помощью Transact-SQL

Перестроение индексов

Перестроение индекса – это процесс, при котором происходит удаление старого индекса и создание нового, в результате чего фрагментация устраняется.

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

Первый. Используя инструкцию ALTER INDEX с предложением REBUILD. Эта инструкция заменяет инструкцию DBCC DBREINDEX. Обычно для массового перестроения индексов используется именно этот способ.

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

В Management Studio функционал для перестроения также доступен. Правой кнопкой по нужному индексу «Перестроить».

На этом материал по основам индексов в Microsoft SQL Server закончен, если Вас интересует SQL и T-SQL, рекомендую посмотреть мои видеокурсы по T-SQL, с помощью которых Вы «с нуля» научитесь работать с SQL и программировать с использованием языка T-SQL в Microsoft SQL Server, удачи!

Источник

Индексы в PostgreSQL — 1

В этой серии статей речь пойдет об индексах в PostgreSQL.

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

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

В этой части мы поговорим про разделение сфер ответственности между общим механизмом индексирования, относящимся к ядру СУБД, и отдельными методами индексного доступа, которые в PostgreSQL можно добавлять как расширения. В следующей части мы рассмотрим интерфейс метода доступа и такие важные понятия, как классы и семейства операторов. После такого длинного, но необходимого введения мы подробно рассмотрим устройство и применение различных типов индексов: Hash, B-tree, GiST, SP-GiST, GIN и RUM, BRIN и Bloom.

Изоляция и многоверсионность:

Индексы

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

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

Несмотря на все различия между типами индексов (называемыми также методами доступа), в конечном счете любой из них устанавливает соответствие между ключом (например, значением проиндексированного столбца) и строками таблицы, в которых этот ключ встречается. Строки идентифицируются с помощью TID (tuple id), который состоит из номера блока файла и позиции строки внутри блока. Тогда, зная ключ или некоторую информацию о нем, можно быстро прочитать те строки, в которых может находиться интересующая нас информация, не просматривая всю таблицу полностью.

Важно понимать, что индекс, ускоряя доступ к данным, взамен требует определенных затрат на свое поддержание. При любой операции над проиндексированными данными — будь то вставка, удаление или обновление строк таблицы, — индексы, созданные для этой таблицы, должны быть перестроены, причем в рамках той же транзакции. Заметим, что обновление полей таблицы, по которым не создавались индексы, не приводит к перестроению индексов; этот механизм называется HOT (Heap-Only Tuples).

Расширяемость влечет некоторые следствия. Чтобы новый метод доступа можно было легко встроить в систему, в PostgreSQL выделен общий механизм индексирования. Его основной задачей является получение TID от метода доступа и работа с ними:

Информация о методе доступа нужна не только оптимизатору. При создании индекса системе надо решить: можно ли построить индекс над несколькими столбцами? может ли данный индекс обеспечить уникальность?

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

В задачи же самого метода доступа входит все остальное:

Механизм индексирования

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

Основные способы сканирования

Индексное сканирование

Можно по-разному работать с TID, поставляемыми индексом. Рассмотрим пример:

postgres=# create table t(a integer, b text, c boolean);
CREATE TABLE
postgres=# insert into t(a,b,c)
select s.id, chr((32+random()*94)::integer), random()
Мы создали таблицу с тремя полями. Первое поле содержит числа от 1 до 100000, и по нему создан индекс (пока нам не важно, какой именно). Второе поле содержит различные ASCII-символы, кроме непечатных. Наконец, третье поле содержит логическое значение, истинное примерно для 1% строк, и ложное для остальных. Строки вставлены в таблицу в случайном порядке.

Попробуем выбрать значение по условию «a = 1». Заметим, что условие имеет вид «индексированное-поле оператор выражение», где в качестве оператора используется «равно», а выражением (ключом поиска) является «1». В большинстве случаев условие должно иметь именно такой вид, чтобы индекс мог использоваться.

postgres=# explain (costs off) select * from t where a = 1;
QUERY PLAN
——————————-
Index Scan using t_a_idx on t
Index Cond: (a = 1)
(2 rows)

В данном случае оптимизатор принял решение использовать индексное сканирование (Index Scan). При индексном просмотре метод доступа возвращает значения TID по одному, до тех пор, пока подходящие строки не закончатся. Механизм индексирования по очереди обращается к тем страницам таблицы, на которые указывают TID, получает версию строки, проверяет ее видимость в соответствии с правилами многоверсионности, и возвращает полученные данные.

Сканирование по битовой карте

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

postgres=# explain (costs off) select * from t where a Bitmap Index Scan on t_a_idx
Index Cond: (a
Сначала метод доступа возвращает все TID, соответствующие условию (узел Bitmap Index Scan), и по ним строится битовая карта версий строк. Затем версии строк читаются из таблицы (Bitmap Heap Scan) — при этом каждая страница будет прочитана только один раз.

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

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

postgres=# create index on t(b);
CREATE INDEX
postgres=# analyze t;
ANALYZE
postgres=# explain (costs off) select * from t where a BitmapAnd
-> Bitmap Index Scan on t_a_idx
Index Cond: (a Bitmap Index Scan on t_b_idx
Index Cond: (b = ‘a’::text)
(7 rows)

Здесь узел BitmapAnd объединяет две битовые карты с помощью битовой операции «и».

Сканирование по битовой карте позволяет избежать повторных обращений к одной и той же странице данных. Но что, если данные в страницах таблицы физически упорядочены точно так же, как и записи индекса? Безусловно, нельзя полностью полагаться на физический порядок данных в страницах — если нужны отсортированные данные, в запросе необходимо явно указывать предложение ORDER BY. Но вполне возможны ситуации, в которых на самом деле «почти все» данные упорядочены: например, если строки добавляются в нужном порядке и не изменяются после этого, или после выполнения команды CLUSTER. Тогда построение битовой карты — лишний шаг, обычное индексное сканирование будет ничем не хуже (если не учитывать возможность объединения нескольких индексов). Поэтому при выборе метода доступа планировщик заглядывает в специальную статистику, которая показывает степень упорядоченности данных:

Последовательное сканирование

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

postgres=# explain (costs off) select * from t where a
И будет прав. Дело в том, что индексы работают тем лучше, чем выше селективность условия, то есть чем меньше строк ему удовлетворяет. При увеличении выборки возрастают и накладные расходы на чтение страниц индекса.

Ситуация усугубляется тем, что последовательное чтение выполняется быстрее, чем чтение страниц «вразнобой». Это особенно верно для жестких дисков, где механическая операция подведения головки к дорожке занимает существенно больше времени, чем само чтение данных; в случае дисков SSD этот эффект менее выражен. Для учета разницы стоимости доступа существуют два параметра seq_page_cost и random_page_cost, которые можно устанавливать не только глобально, но и на уровне табличных пространств, учитывая таким образом характеристики разных дисковых подсистем.

Покрывающие индексы

Как правило, основная задача метода доступа — вернуть идентификаторы подходящих строк таблицы, чтобы механизм индексирования мог прочитать из них необходимые данные. Но что, если индекс уже содержит все необходимые для запроса данные? Такой индекс называется покрывающим (covering), и в этом случае оптимизатор может применить исключительно индексное сканирование (Index Only Scan):

postgres=# vacuum t;
VACUUM
postgres=# explain (costs off) select a from t where a
Название может навести на мысль, что механизм индексирования совсем не обращается к таблице, получая всю необходимую информацию исключительно от метода доступа. Но это не совсем так, потому что индексы в PostgreSQL не содержат информации, позволяющей судить о видимости строк. Поэтому метод доступа возвращает все версии строк, попадающие под условие поиска, независимо от того, видны они текущей транзакции или нет.

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

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

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

Число вынужденных обращений к таблице можно узнать, используя команду explain analyze:

postgres=# explain (analyze, costs off) select a from t where a
В данном случае обращаться к таблице не понадобилось (Heap Fetches: 0), так как только что была выполнена очистка. Вообще, чем ближе это число к нулю, тем лучше.

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

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

Но особое значение требует и особого к себе отношения. Обычная булева логика превращается в трехзначную; непонятно, должно ли неопределенное значение быть меньше обычных значений или больше (отсюда специальные конструкции для сортировки NULLS FIRST и NULLS LAST); не очевидно, надо ли учитывать неопределенные значения в агрегатных функциях или нет; требуется специальная статистика для планировщика…

С точки зрения индексной поддержки с неопределенными значениями тоже имеется неясность: надо ли индексировать такие значения или нет? Если не индексировать null, то индекс может получиться компактнее. Зато если индексировать, то появляется возможность использовать индекс для условий вида «индексированное-поле IS [NOT] NULL», а также в качестве покрывающего индекса при полном отсутствии условий на таблицу (поскольку в этом случае индекс должен вернуть данные всех строк таблицы, в том числе и с неопределенными значениями).

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

Индексы по нескольким полям

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

postgres=# create index on t(a,b);
CREATE INDEX
postgres=# analyze t;
ANALYZE

Оптимизатор скорее всего предпочтет такой индекс объединению битовых карт, поскольку здесь мы сразу получаем нужные TID без каких-либо вспомогательных действий:

postgres=# explain (costs off) select * from t where a
Многоколоночный индекс может использоваться и для ускорения выборки по условию на часть полей — начиная с первого:

postgres=# explain (costs off) select * from t where a Bitmap Index Scan on t_a_b_idx
Index Cond: (a
Как правило, если на первое поле не наложено условие, индекс использоваться не будет. Но в некоторых случаях оптимизатор может счесть, что это все-таки выгоднее последовательного сканирования. Подробнее мы затронем эту тему, когда будет рассматривать индексы btree.

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

Индексы по выражениям

Мы говорили о том, что условие поиска должно иметь вид «индексированное-поле оператор выражение». В примере, приведенном ниже, индекс не будет использоваться, поскольку вместо самого имени поля используется выражение с ним:

postgres=# explain (costs off) select * from t where lower(b) = ‘a’;
QUERY PLAN
——————————————
Seq Scan on t
Filter: (lower((b)::text) = ‘a’::text)
(2 rows)

Этот конкретный запрос не составляет труда переписать так, чтобы слева от оператора стояло только имя поля. Но если это невозможно, на помощь приходят индексы по выражениям (функциональные индексы):

postgres=# create index on t(lower(b));
CREATE INDEX
postgres=# analyze t;
ANALYZE
postgres=# explain (costs off) select * from t where lower(b) = ‘a’;
QUERY PLAN
—————————————————-
Bitmap Heap Scan on t
Recheck Cond: (lower((b)::text) = ‘a’::text)
-> Bitmap Index Scan on t_lower_idx
Index Cond: (lower((b)::text) = ‘a’::text)
(4 rows)

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

Стоит также иметь в виду, что по индексированному выражению собирается отдельная статистика. Ее можно увидеть в представлении pg_stats по имени индекса:

postgres=# \d t
Table «public.t»
Column | Type | Modifiers
———+———+————
a | integer |
b | text |
c | boolean |
Indexes:
«t_a_b_idx» btree (a, b)
«t_a_idx» btree (a)
«t_b_idx» btree (b)
«t_lower_idx» btree (lower(b))

postgres=# select * from pg_stats where tablename = ‘t_lower_idx’;
.

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

postgres=# \d t_lower_idx
Index «public.t_lower_idx»
Column | Type | Definition
———+——+————
lower | text | lower(b)
btree, for table «public.t»

postgres=# alter index t_lower_idx alter column «lower» set statistics 69;
ALTER INDEX

Частичные индексы

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

Разумеется, можно построить обычный индекс по столбцу «c», и он будет работать так, как мы ожидаем:

postgres=# create index on t(c);
CREATE INDEX
postgres=# analyze t;
ANALYZE
postgres=# explain (costs off) select * from t where c;
QUERY PLAN
——————————-
Index Scan using t_c_idx on t
Index Cond: (c = true)
Filter: c
(3 rows)

postgres=# explain (costs off) select * from t where not c;
QUERY PLAN
——————-
Seq Scan on t
Filter: (NOT c)
(2 rows)

При этом индекс занимает 276 страниц:

postgres=# select relpages from pg_class where relname=’t_c_idx’;
relpages
———-
276
(1 row)

Но, поскольку столбец «c» имеет значение true только для одного процента строк, 99% индекса просто никогда не используются. В этом случае можно построить частичный индекс:

postgres=# create index on t(c) where c;
CREATE INDEX
postgres=# analyze t;
ANALYZE

Размер такого индекса уменьшился до 5 страниц:

postgres=# select relpages from pg_class where relname=’t_c_idx1′;
relpages
———-
5
(1 row)

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

Сортировка

Если метод доступа возвращает идентификаторы строк в порядке сортировки, это дает оптимизатору дополнительные варианты выполнения запроса.

Можно просканировать таблицу и затем отсортировать данные:

postgres=# set enable_indexscan=off;
SET
postgres=# explain (costs off) select * from t order by a;
QUERY PLAN
———————
Sort
Sort Key: a
-> Seq Scan on t
(3 rows)

А можно прочитать данные с помощью индекса сразу в порядке сортировки:

postgres=# set enable_indexscan=on;
SET
postgres=# explain (costs off) select * from t order by a;
QUERY PLAN
——————————-
Index Scan using t_a_idx on t
(1 row)

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

Параллельное построение

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

В этом можно убедиться, если в момент создания индекса, скажем, на таблице t, в другом сеансе выполнить запрос:

postgres=# select mode, granted from pg_locks where relation = ‘t’::regclass;
mode | granted
————+———
ShareLock | t
(1 row)

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

В этом случае можно воспользоваться параллельным созданием индекса:

postgres=# create index concurrently on t(a);
CREATE INDEX

Такая команда устанавливает блокировку типа SHARE UPDATE EXCLUSIVE, которая разрешает и чтение, и изменение данных (запрещается только изменение структуры таблицы, а также одновременное выполнение очистки, анализа, или построения другого индекса на той же таблице).

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

Во-вторых, при параллельном построении индекса может возникнуть взаимоблокировка или нарушение ограничения уникальности. Индекс тем не менее создается, но в «нерабочем» состоянии; в таком случае его надо удалить и пересоздать еще раз. Нерабочие индексы отмечены словом INVALID в выводе команды psql \d, а полный список можно получить запросом:

postgres=# select indexrelid::regclass index_name, indrelid::regclass table_name from pg_index where not indisvalid;
index_name | table_name
————+————
t_a_idx | t
(1 row)

Продолжение.

Источник