Blog , p.4
September 17, 2020   •   PostgreSQL
Indexes in PostgreSQL — 7 (GIN)
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 General concept GIN is the abbreviated Generalized Inverted Index. This is a so-called inverted index . It manipulates data types whose values are not atomic, but consist of elements. We will call these types compound. And these are not the values that get indexed, but individual elements; each element references the values in which it occurs. A good analogy to this method is the index at the end of a book, which for each term, provides a list of pages where this term occurs. The access method must ensure fast search of indexed elements, just like the index in a book. Therefore, these elements are stored as a familiar B-tree (a different, simpler, implementation is used for it, but it does not matter in this case). An ordered set of references to table rows that contain compound values with the element is linked to each element. Orderliness is inessential for data retrieval (the sort order of TIDs does not mean much), but important for the internal structure of the index.
September 15, 2020   •   PostgreSQL
Storing arbitrary PostgreSQL data types in JSONB
Last month Alvaro Hernandez-Tortosa published a blog post discussing how the existing JSON features in PostgreSQL can be improved. The main request was about increasing the number of data types supported in JSONB. We addressed this concern and are ready to share our development team’s commentary.
September 10, 2020   •   PostgreSQL
Indexes in PostgreSQL — 6 (SP-GiST)
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. Structure So, the idea of SP-GiST access method is to split the value domain into non-overlapping subdomains each of which, in turn, can also be split. Partitioning like this induces non-balanced trees (unlike B-trees and regular GiST). The trait of being non-intersecting simplifies decision-making during insertion and search. On the other hand, as a rule, the trees induced are of low branching. For example, a node of a quadtree usually has four child nodes (unlike B-trees, where the nodes amount to hundreds) and larger depth. Trees like these well suit the work in RAM, but the index is stored on a disk and therefore, to reduce the number of I/O operations, nodes have to be packed into pages, and it is not easy to do this efficiently. Besides, the time it takes to find different values in the index, may vary because of differences in branch depths.
September 3, 2020   •   PostgreSQL
Indexes in PostgreSQL — 5 (GiST)
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.
August 27, 2020   •   PostgreSQL
Indexes in PostgreSQL — 4 (Btree)
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. As always, index rows of the B-tree are packed into pages. In leaf pages, these rows contain data to be indexed (keys) and references to table rows (TIDs). In internal pages, each row references a child page of the index and contains the minimal value in this page. B-trees have a few important traits: B-trees are balanced, that is, each leaf page is separated from the root by the same number of internal pages. Therefore, search for any value takes the same time. B-trees are multi-branched, that is, each page (usually 8 KB) contains a lot of (hundreds) TIDs. As a result, the depth of B-trees is pretty small, actually up to 4–5 for very large tables. Data in the index is sorted in nondecreasing order (both between pages and inside each page), and same-level pages are connected to one another by a bidirectional list. Therefore, we can get an ordered data set just by a list walk one or the other direction without returning to the root each time. Below is a simplified example of the index on one field with integer keys.
August 20, 2020   •   PostgreSQL
Indexes in PostgreSQL — 3 (Hash)
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.
August 6, 2020   •   PostgreSQL
Indexes in PostgreSQL — 1
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 in 2017 on habr.com . My comments on the current state of affairs are indicated like this.
February 27, 2020   •   PostgreSQL
Patch by Anastasia Lubennikova accepted in the upcoming version of PostgreSQL
Anastasia Lubennikova, a Postgres Pro leading developer, has reported at PGConf.India that Peter Geoghegan had committed recently the long-awaited B-Tree index deduplication patch to PostgreSQL.
June 28, 2019   •   Company Updates
Postgres Professional took part in the PGIBZ conference on the beaches of Ibiza
The conference gathered about 100 people, including PostgreSQL developers, DBA and customers from all over the world.
January 9, 2017   •   PostgreSQL
Millions of Queries per Second: PostgreSQL and MySQL’s Peaceful Battle at Today’s Demanding Workloads
This blog compares how PostgreSQL and MySQL handle millions of queries per second.
September 30, 2016   •   PostgreSQL
PostgreSQL 9.6 is Released: Contribution of Postgres Professional
PostgreSQL 9.6 was released yesterday. This is a great release which provides to users set of outstanding new features. We are especially happy that Postgres Professional did substantial contribution to this release.