Blog , p.5
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.
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.
Indexes in PostgreSQL — 1
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.
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.
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.
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.
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.
Galy Lee at PgConf2016 Russia presented a talk «Growing acceptance of PostgreSQL in China» - Video
This talk gave an overview about the Postgres adoption in 2015 in China.
Bruce Momjian at PgConf2016 Russia with talk «Postgres Going in Multiple Directions» - Video
This talk covers the top ten new features that appeared in the Postgres 9.5 release. It also covers some of the major focuses for post-9.5 releases.
Leonid Libkin from the University of Edinburgh will give a talk "Making SQL Queries Correct on Databases with Nulls" 9 August at 14:00
What is the scientifically correct way if using NULLs ?
Scalable Real-time Product Search using PostgreSQL with Citus
We are delighted to repost the article by Citusdata, and appreciate the recogintion of our contribution: "Special thanks to the people at Postgres Professional for contributing most of the full-text search, JSONB, and GIN index features in PostgreSQL, as well as the initial code for the Citus COPY feature"