Pull to refresh
71.33

PostgreSQL *

Object-relational database management system (ORDBMS) with an emphasis on extensibility and standards compliance

Show first
Rating limit
Level of difficulty

PostgreSQL 16: Part 5 or CommitFest 2023-03

Level of difficulty Medium
Reading time 28 min
Views 1K

The end of the March Commitfest concludes the acceptance of patches for PostgreSQL 16. Let’s take a look at some exciting new updates it introduced.

I hope that this review together with the previous articles in the series (2022-072022-092022-112023-01) will give you a coherent idea of the new features of PostgreSQL 16.

Read more
Total votes 10: ↑10 and ↓0 +10
Comments 0

Indexes in PostgreSQL — 10 (Bloom)

Reading time 11 min
Views 6.8K
In the previous articles we discussed PostgreSQL indexing engine and the interface of access methods, as well as hash indexes, B-trees, GiST, SP-GiST, GIN, RUM, and BRIN. But we still need to look at Bloom indexes.

Bloom


General concept


A classical Bloom filter is a data structure that enables us to quickly check membership of an element in a set. The filter is highly compact, but allows false positives: it can mistakenly consider an element to be a member of a set (false positive), but it is not permitted to consider an element of a set not to be a member (false negative).

The filter is an array of $m$ bits (also called a signature) that is initially filled with zeros. $k$ different hash functions are chosen that map any element of the set to $k$ bits of the signature. To add an element to the set, we need to set each of these bits in the signature to one. Consequently, if all the bits corresponding to an element are set to one, the element can be a member of the set, but if at least one bit equals zero, the element is not in the set for sure.

In the case of a DBMS, we actually have $N$ separate filters built for each index row. As a rule, several fields are included in the index, and it's values of these fields that compose the set of elements for each row.

By choosing the length of the signature $m$, we can find a trade-off between the index size and the probability of false positives. The application area for Bloom index is large, considerably «wide» tables to be queried using filters on each of the fields. This access method, like BRIN, can be regarded as an accelerator of sequential scan: all the matches found by the index must be rechecked with the table, but there is a chance to avoid considering most of the rows at all.
Read more →
Total votes 17: ↑16 and ↓1 +15
Comments 2

Indexes in PostgreSQL — 9 (BRIN)

Reading time 18 min
Views 8.7K
In the previous articles we discussed PostgreSQL indexing engine, the interface of access methods, and the following methods: hash indexes, B-trees, GiST, SP-GiST, GIN, and RUM. The topic of this article is BRIN indexes.

BRIN


General concept


Unlike indexes with which we've already got acquainted, the idea of BRIN is to avoid looking through definitely unsuited rows rather than quickly find the matching ones. This is always an inaccurate index: it does not contain TIDs of table rows at all.

Simplistically, BRIN works fine for columns where values correlate with their physical location in the table. In other words, if a query without ORDER BY clause returns the column values virtually in the increasing or decreasing order (and there are no indexes on that column).

This access method was created in scope of Axle, the European project for extremely large analytical databases, with an eye on tables that are several terabyte or dozens of terabytes large. An important feature of BRIN that enables us to create indexes on such tables is a small size and minimal overhead costs of maintenance.

This works as follows. The table is split into ranges that are several pages large (or several blocks large, which is the same) — hence the name: Block Range Index, BRIN. The index stores summary information on the data in each range. As a rule, this is the minimal and maximal values, but it happens to be different, as shown further. Assume that a query is performed that contains the condition for a column; if the sought values do not get into the interval, the whole range can be skipped; but if they do get, all rows in all blocks will have to be looked through to choose the matching ones among them.

It will not be a mistake to treat BRIN not as an index, but as an accelerator of sequential scan. We can regard BRIN as an alternative to partitioning if we consider each range as a «virtual» partition.

Now let's discuss the structure of the index in more detail.
Read more →
Total votes 14: ↑14 and ↓0 +14
Comments 0

Indexes in PostgreSQL — 8 (RUM)

Reading time 11 min
Views 8.3K
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.
Read more →
Total votes 10: ↑10 and ↓0 +10
Comments 2

Indexes in PostgreSQL — 7 (GIN)

Reading time 18 min
Views 24K
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
Read more →
Total votes 17: ↑16 and ↓1 +15
Comments 0

Indexes in PostgreSQL — 6 (SP-GiST)

Reading time 11 min
Views 8.3K
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.
Read more →
Total votes 12: ↑12 and ↓0 +12
Comments 0

Indexes in PostgreSQL — 5 (GiST)

Reading time 22 min
Views 9.4K
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.
Read more →
Total votes 18: ↑16 and ↓2 +14
Comments 0

Optimisations for PostgreSQL serving Rails application

Reading time 6 min
Views 5.1K

As Senior Software Engineer at company building messaging platform for healthcare industry I am responsible, including other duties, for performance of our application. We develop pretty standard web-service using Ruby on Rails application for business logic and API, React + Redux for users' facing single page application, as database we use PostgreSQL. Common reasons for performance problems in similar stacks are heavy queries to database and I would like to tell the story how we applied non-standard but fairly simple optimisations to improve performance.


Our business operates in US, so we have to be HIPAA compliant and follow certain security policies, security audit is something that we are always prepared for. To reduce risks and costs we rely on a special cloud provider to run our applications and databases, very similar to what Heroku does. On one hand it allows us to focus on building our platform but on the other hand it adds an additional limitation to our infrastructure. Talking shortly — we cannot scale up infinitely. As a successful startup we double number of users every few month and one day our monitoring told us that we were exceeding disk IO quota on the database server. Underlying AWS started throttling which was resulting in a significant performance degradation. Ruby application was not capable to serve all incoming traffic because Unicorn workers were spending too much time awaiting for database's response, customers were unhappy.

Read more →
Total votes 15: ↑14 and ↓1 +13
Comments 0

Indexes in PostgreSQL — 2

Reading time 5 min
Views 7.4K

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.
Read more →
Total votes 15: ↑15 and ↓0 +15
Comments 2

Indexes in PostgreSQL — 1

Reading time 13 min
Views 24K

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.
Read more →
Total votes 23: ↑22 and ↓1 +21
Comments 8

Authors' contribution