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

В прошлый раз мы поговорили о HOT-обновлениях и внутристраничной очистке, а сегодня займемся всем известной обычной очисткой, vacuum vulgaris. Да, про нее написано уже столько всего, что вряд ли я скажу что-то новое, но полнота картины требует жертв. Терпите.

Обычная очистка (vacuum)

Что делает очистка

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

Основная, «обычная» очистка выполняется командой VACUUM и ее мы будем называть просто очисткой (а про автоочистку мы будем говорить отдельно).

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

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

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

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

We have already discussed PostgreSQL indexing engine, the interface of access methods, and main access methods, such as: hash indexes, B-trees, GiST, SP-GiST, and GIN. In this article, we will watch how gin turns into rum.

RUM

Although the authors claim that gin is a powerful genie, the theme of drinks has eventually won: next-generation GIN has been called RUM.

This access method expands the concept that underlies GIN and enables us to perform full-text search even faster. In this series of articles, this is the only method that is not included in a standard PostgreSQL delivery and is an external extension. Several installation options are available for it:

• Take «yum» or «apt» package from the PGDG repository. For example, if you installed PostgreSQL from «postgresql-10» package, also install «postgresql-10-rum».
• Build from source code on github and install on your own (the instruction is there as well).
• Use as a part of Postgres Pro Enterprise (or at least read the documentation from there).

Limitations of GIN

What limitations of GIN does RUM enable us to transcend?

First, «tsvector» data type contains not only lexemes, but also information on their positions inside the document. As we observed last time, GIN index does not store this information. For this reason, operations to search for phrases, which appeared in version 9.6, are supported by GIN index inefficiently and have to access the original data for recheck.

Second, search systems usually return the results sorted by relevance (whatever that means). We can use ranking functions «ts_rank» and «ts_rank_cd» to this end, but they have to be computed for each row of the result, which is certainly slow.

To a first approximation, RUM access method can be considered as GIN that additionally stores position information and can return the results in a needed order (like GiST can return nearest neighbors). Let's move step by step.

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

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

Внутристраничная очистка при обычных обновлениях

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

1. Ранее выполненное на этой странице обновление (UPDATE) не обнаружило достаточно места, чтобы разместить новую версию строки на той же странице. Такая ситуация запоминается в заголовке страницы, и в следующий раз страница очищается.
2. Страница заполнена больше, чем на fillfactor. При этом очистка происходит сразу, не откладывая на следующий раз.

We have already got acquainted with PostgreSQL indexing engine and the interface of access methods and discussed hash indexes, B-trees, as well as GiST and SP-GiST indexes. And this article will feature GIN index.

GIN

«Gin?.. Gin is, it seems, such an American liquor?..»
«I'm not a drink, oh, inquisitive boy!» again the old man flared up, again he realized himself and again took himself in hand. «I am not a drink, but a powerful and undaunted spirit, and there is no such magic in the world that I would not be able to do.»
— Lazar Lagin, «Old Khottabych».

Gin stands for Generalized Inverted Index and should be considered as a genie, not a drink.
— README

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

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

Что такое снимок данных

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

Изоляция в PostgreSQL строится на основе снимков данных (snapshot): каждая транзакция работает со своим снимком данных, который «содержит» данные, которые были зафиксированы до момента создания снимка, и не «содержит» еще не зафиксированные на этот момент данные. Мы уже видели, что изоляция при этом получается более строгая, чем требует стандарт, но не лишенная аномалий.

We've already discussed PostgreSQL indexing engine, the interface of access methods, and three methods: hash index, B-tree, and GiST. In this article, we will describe SP-GiST.

SP-GiST

First, a few words about this name. The «GiST» part alludes to some similarity with the same-name access method. The similarity does exist: both are generalized search trees that provide a framework for building various access methods.

«SP» stands for space partitioning. The space here is often just what we are used to call a space, for example, a two-dimensional plane. But we will see that any search space is meant, that is, actually any value domain.

SP-GiST is suitable for structures where the space can be recursively split into non-intersecting areas. This class comprises quadtrees, k-dimensional trees (k-D trees), and radix trees.

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

Заголовок

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

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

In the previous articles, we discussed PostgreSQL indexing engine, the interface of access methods, and two access methods: hash index and B-tree. In this article, we will describe GiST indexes.

GiST

GiST is an abbreviation of «generalized search tree». This is a balanced search tree, just like «b-tree» discussed earlier.

What is the difference? «btree» index is strictly connected to the comparison semantics: support of «greater», «less», and «equal» operators is all it is capable of (but very capable!) However, modern databases store data types for which these operators just make no sense: geodata, text documents, images,…

GiST index method comes to our aid for these data types. It permits defining a rule to distribute data of an arbitrary type across a balanced tree and a method to use this representation for access by some operator. For example, GiST index can «accommodate» R-tree for spatial data with support of relative position operators (located on the left, on the right, contains, etc.) or RD-tree for sets with support of intersection or inclusion operators.

Thanks to extensibility, a totally new method can be created from scratch in PostgreSQL: to this end, an interface with the indexing engine must be implemented. But this requires premeditation of not only the indexing logic, but also mapping data structures to pages, efficient implementation of locks, and support of a write-ahead log. All this assumes high developer skills and a large human effort. GiST simplifies the task by taking over low-level problems and offering its own interface: several functions pertaining not to techniques, but to the application domain. In this sense, we can regard GiST as a framework for building new access methods.

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

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

Отношения (relations)

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

То, что таблица состоит из строк, не вызывает сомнений; для индекса это менее очевидно. Тем не менее, представьте B-дерево: оно состоит из узлов, которые содержат индексированные значения и ссылки на другие узлы или на табличные строки. Вот эти узлы и можно считать индексными строками — фактически, так оно и есть.

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

Все эти объекты в PostgreSQL называются общим словом отношение (по-английски relation). Слово крайне неудачное, потому что это термин из реляционной теории. Можно провести параллель между отношением и таблицей (представлением), но уж никак не между отношением и индексом. Но так уж сложилось: дают о себе знать академические корни PostgreSQL. Мне думается, что сначала так называли именно таблицы и представления, а остальное наросло со временем.

We've already discussed PostgreSQL indexing engine and interface of access methods, as well as hash index, one of access methods. We will now consider B-tree, the most traditional and widely used index. This article is large, so be patient.

Btree

Structure

B-tree index type, implemented as «btree» access method, is suitable for data that can be sorted. In other words, «greater», «greater or equal», «less», «less or equal», and «equal» operators must be defined for the data type. Note that the same data can sometimes be sorted differently, which takes us back to the concept of operator family.

Привет, Хабр! Этой статьей я начинаю серию циклов (или цикл серий? в общем, задумка грандиозная) о внутреннем устройстве PostgreSQL.

Материал будет основан на учебных курсах по администрированию, которые делаем мы с Павлом pluzanov. Смотреть видео не все любят (я точно не люблю), а читать слайды, пусть даже с комментариями, — совсем «не то».

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

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

Вещи, о которых пойдет речь, не сильно меняются от версии к версии, но использовать я буду текущий, 11-й «ванильный» PostgreSQL.

Первый цикл посвящен вопросам, связанным с изоляцией и многоверсионностью, и план его таков:

1. Изоляция, как ее понимают стандарт и PostgreSQL (эта статья);
2. Слои, файлы, страницы — что творится на физическом уровне;
3. Версии строк, виртуальные и вложенные транзакции;
4. Снимки данных и видимость версий строк, горизонт событий;
5. Внутристраничная очистка и HOT-обновления;
6. Обычная очистка (vacuum);
7. Автоматическая очистка (autovacuum);
8. Переполнение счетчика транзакций и заморозка.

Ну, поехали.

The first article described PostgreSQL indexing engine, the second one dealt with the interface of access methods, and now we are ready to discuss specific types of indexes. Let's start with hash index.

Hash

Structure

General theory

Plenty of modern programming languages include hash tables as the base data type. On the outside, a hash table looks like a regular array that is indexed with any data type (for example, string) rather than with an integer number. Hash index in PostgreSQL is structured in a similar way. How does this work?

As a rule, data types have very large ranges of permissible values: how many different strings can we potentially envisage in a column of type «text»? At the same time, how many different values are actually stored in a text column of some table? Usually, not so many of them.

The idea of hashing is to associate a small number (from 0 to N−1, N values in total) with a value of any data type. Association like this is called a hash function. The number obtained can be used as an index of a regular array where references to table rows (TIDs) will be stored. Elements of this array are called hash table buckets — one bucket can store several TIDs if the same indexed value appears in different rows.

The more uniformly a hash function distributes source values by buckets, the better it is. But even a good hash function will sometimes produce equal results for different source values — this is called a collision. So, one bucket can store TIDs corresponding to different keys, and therefore, TIDs obtained from the index need to be rechecked.

Interface

In the first article, we've mentioned that an access method must provide information about itself. Let's look into the structure of the access method interface.

Properties

All properties of access methods are stored in the «pg_am» table («am» stands for access method). We can also get a list of available methods from this same table:

postgres=# select amname from pg_am;

 amname
--------
 btree
 hash
 gist
 gin
 spgist
 brin
(6 rows)

Although sequential scan can rightfully be referred to access methods, it is not on this list for historical reasons.

In PostgreSQL versions 9.5 and lower, each property was represented with a separate field of the «pg_am» table. Starting with version 9.6, properties are queried with special functions and are separated into several layers:

• Access method properties — «pg_indexam_has_property»
• Properties of a specific index — «pg_index_has_property»
• Properties of individual columns of the index — «pg_index_column_has_property»

The access method layer and index layer are separated with an eye towards the future: as of now, all indexes based on one access method will always have the same properties.

Introduction

This series of articles is largely concerned with indexes in PostgreSQL.

Any subject can be considered from different perspectives. We will discuss matters that should interest an application developer who uses DBMS: what indexes are available, why there are so many different types of them, and how to use them to speed up queries. The topic can probably be covered in fewer words, but in secrecy we hope for a curious developer, who is also interested in details of the internals, especially since understanding of such details allows you to not only defer to other's judgement, but also make conclusions of your own.

Development of new types of indexes is outside the scope. This requires knowledge of the C programming language and pertains to the expertise of a system programmer rather than an application developer. For the same reason we almost won't discuss programming interfaces, but will focus only on what matters for working with ready-to-use indexes.

In this article we will discuss the distribution of responsibilities between the general indexing engine related to the DBMS core and individual index access methods, which PostgreSQL enables us to add as extensions. In the next article we will discuss the interface of the access method and critical concepts such as classes and operator families. After that long but necessary introduction we will consider details of the structure and application of different types of indexes: Hash, B-tree, GiST, SP-GiST, GIN and RUM, BRIN, and Bloom.

Before we start, I would like to thank Elena Indrupskaya for translating the articles to English.
Things have changed a bit since the original publication. My comments on the current state of affairs are indicated like this.

Предлагаем вашему вниманию перевод статьи Джозефа Хеллерштейна «Looking Back at Postgres», опубликованной в соответствии с международной лицензией Creative Commons «С указанием авторства» версии 4.0 (CC-BY 4.0). Авторы оставляют за собой право распространять эту работу на личных и корпоративных веб-сайтах с надлежащей ссылкой на источник.

Перевод выполнен Еленой Индрупской. От себя добавлю, что «программист, который отчаянно хотел построить систему с многоверсионностью» — судя по всему, Вадим Михеев, ну а «добровольцев из России», переписавших GiST, мы все хорошо знаем.

Аннотация

Это воспоминание о проекте Postgres, выполняемом в Калифорнийском университете в Беркли и возглавляемом Майком Стоунбрейкером (Mike Stonebraker) с середины 1980-х до середины 1990-х годов. В качестве одного из многих личных и исторических воспоминаний, эта статья была запрошена для книги [Bro19], посвященной награждению Стоунбрейкера премией Тьюринга. Поэтому в центре внимания статьи — руководящая роль Стоунбрейкера и его мысли о дизайне. Но Стоунбрейкер никогда не был программистом и не мешал своей команде разработчиков. Кодовая база Postgres была работой команды блестящих студентов и эпизодически—штатных университетских программистов, которые имели немного больше опыта (и только немного большую зарплату), чем студенты. Мне посчастливилось присоединиться к этой команде в качестве студента в последние годы проекта. Я получил полезный материал для этой статьи от некоторых более старших студентов, занятых в проекте, но любые ошибки или упущения являются моими. Если вы заметили какие-либо из них, пожалуйста, свяжитесь со мной, и я постараюсь их исправить.

Спешу поделиться хорошей новостью: жизнь авторов статей про PostgreSQL и их читателей стала немного лучше.

Как знают все хаброписатели, для оформления исходного кода используется специальный тег <source>, который подсвечивает синтаксис. Не секрет также, что подсветка не всегда получается идеальной, и тогда авторы (которым не все равно, как выглядят их статьи) вынуждены заниматься самодеятельностью — расцвечивать свой код с помощью <font color=...>.

Особенно печально все было с PostgreSQL, поскольку подсветка охватывала более или менее стандартный SQL и категорически не понимала специфики нашей СУБД. Шло время, Алексей boomburum старательно исправлял мои font-ы на source (а я — обратно), пока не стало очевидно, что подсветку надо чинить. Наконец Далер daleraliyorov подсказал выход: добавить поддержку PostgreSQL в библиотеку highlightjs, которой пользуется Хабр. И вот — готово, встречайте.

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

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

Зачем тогда вообще вникать в этот вопрос? Могу назвать несколько причин:

• Хотя оконные функции объективно сложнее обычных агрегатных, но ничего запредельного в них нет; это абсолютно необходимый инструмент для SQL-разработчика. А создание собственной оконной функции, даже совсем простой, позволяет лучше разобраться с тем, как работают стандартные.
  
• Оконные и агрегатные функции — прекрасный способ совместить процедурную обработку с декларативной логикой. В некоторых ситуациях получается выполнить сложные действия, оставаясь в рамках парадигмы решения задачи одним SQL-запросом.
  
• Да и просто интересная тема, а уж тем более интересно сравнить две системы.
  

Пример, на котором будем тренироваться — подсчет среднего, аналог стандартной функции avg для типа numeric (number в Oracle). Мы напишем такую функцию и посмотрим, как она работает в агрегатном и оконном режимах и может ли она вычисляться несколькими параллельными процессами. А в заключение поглядим на пример из реальной жизни.

В прошлых статьях мы рассмотрели механизм индексирования PostgreSQL и интерфейс методов доступа, а также хеш-индексы, B-деревья, GiST, SP-GiST, GIN, RUM и BRIN. Нам осталось посмотреть на индексы Блума.

Bloom

Общая идея

Классический фильтр Блума — структура данных, позволяющая быстро проверить принадлежность элемента множеству. Фильтр очень компактен, но допускает ложные срабатывания: он имеет право ошибиться и счесть элемент принадлежащим множеству (false positive), но не имеет права сказать, что элемента нет в множестве, если на самом деле он там присутствует (false negative).

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

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

Благодаря выбору размера сигнатуры m, можно находить компромисс между объемом индекса и вероятностью ложного срабатывания. Область применения Блум-индекса — большие, достаточно «широкие» таблицы, запросы к которым могут использовать фильтрацию по любым из полей. Этот метод доступа, как и BRIN, можно рассматривать как ускоритель последовательного сканирования: все найденные индексом совпадения необходимо перепроверять по таблице, но есть шанс вовсе не рассматривать значительную часть строк.

В прошлых статьях мы рассмотрели механизм индексирования PostgreSQL, интерфейс методов доступа и следующие методы: хеш-индексы, B-деревья, GiST, SP-GiST, GIN и RUM. Тема этой статьи — BRIN-индексы.

BRIN

Общая идея

В отличие от индексов, с которыми мы уже познакомились, идея BRIN не в том, чтобы быстро найти нужные строки, а в том, чтобы избежать просмотра заведомо ненужных. Это всегда неточный индекс: он вообще не содержит TID-ов табличных строк.

Упрощенно говоря, BRIN хорошо работает для тех столбцов, значения в которых коррелируют с их физическим расположением в таблице. Иными словами, если запрос без предложения ORDER BY выдает значения столбца практически в порядке возрастания или убывания (и при этом по столбцу нет индексов).

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

Работает это следующим образом. Таблица разбивается на зоны (range) размером в несколько страниц (или блоков, что то же самое) — отсюда и название: Block Range Index, BRIN. Для каждой зоны в индексе сохраняется сводная информация о данных в этой зоне. Как правило, это минимальное и максимальное значения, но бывает и иначе, как мы увидим дальше. Если при выполнении запроса, содержащего условие на столбец, искомые значения не попадают в диапазон, то всю зону можно смело пропускать; если же попадают — все строки во всех блоках зоны придется просмотреть и выбрать среди них подходящие.

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

Мы уже рассмотрели механизм индексирования PostgreSQL, интерфейс методов доступа и все основные методы доступа, как то: хеш-индексы, B-деревья, GiST, SP-GiST и GIN. А в этой части посмотрим на превращение джина в ром.

RUM

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

Этот метод доступа развивает идею, заложенную в GIN, и позволяет выполнять полнотекстовый поиск еще быстрее. Это единственный метод в этой серии статей, который не входит в стандартную поставку PostgreSQL и является сторонним расширением. Есть несколько вариантов его установки:

• Взять пакет yum или apt из репозитория PGDG. Например, если вы ставили PostgreSQL из пакета postgresql-10, то поставьте еще postgresql-10-rum.
• Самостоятельно собрать и установить из исходных кодов на github (инструкция там же).
• Пользоваться в составе Postgres Pro Enterprise (или хотя бы читать оттуда документацию).

Ограничения GIN

Какие ограничения индекса GIN позволяет преодолеть RUM?

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

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

Метод доступа RUM в первом приближении можно рассматривать как GIN, в который добавлена позиционная информация, и который поддерживает выдачу результата в нужном порядке (аналогично тому, как GiST умеет выдавать ближайших соседей). Пойдем по порядку.