Как PostgreSQL выполняет ORDER BY, если на этом поле построен индекс b-дерева?

Question

У меня есть стол bsort:

CREATE TABLE bsort(a int, data text);

Вот data может быть неполным. Другими словами, некоторые кортежи могут не иметь data значение.

И тогда я строю индекс b-дерева на таблице:

CREATE INDEX ON bsort USING BTREE(a);

Теперь, если я выполню этот запрос:

SELECT * FROM bsort ORDER BY a;

Разве PostgreSQL сортирует кортежи со сложностью nlogn или получает заказ непосредственно из индекса b-дерева?

Answer 1

Для простого запроса, подобного этому, Postgres будет использовать сканирование индекса и получать по порядку легко отсортированные кортежи из индекса. Из-за своей модели MVCC Postgres пришлось дополнительно посещать "кучу" (страницы данных), чтобы проверить, действительно ли записи видны для текущей транзакции. Цитирование Postgres Wiki при сканировании только по индексу:

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

Что в конечном итоге произошло в версии 9.2: сканирование только по индексу. Документация:

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

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

Вот почему мы иногда добавляем в индексы бесполезные столбцы. Словно data столбец в вашем примере:

CREATE INDEX ON bsort USING BTREE(a, data);

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

• Работа индексов в PostgreSQL
• Составной индекс также хорош для запросов по первому полю?

Преимущество сканирования только по индексу для каждой документации:

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

Карта видимости поддерживается VACUUM что происходит автоматически, если у вас работает автоочистка (настройка по умолчанию в современных Postgres). Подробности:

• Регулярный ВАКУУМНЫЙ АНАЛИЗ все еще рекомендуется под 9.1?

Но есть некоторая задержка между операциями записи в таблицу и следующей VACUUM запустить. Суть этого:

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

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

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

Answer 2

Вам нужно будет проверить план выполнения. Но Postgres вполне способен использовать индекс, чтобы сделать order by более эффективным. Это будет читать записи прямо из индекса. Поскольку у вас есть только один столбец, нет необходимости обращаться к страницам данных.