Scalability of Postgres for table with large number of indexed columns

Question

I have a Postgres table with a large number of indexed columns (roughly 100 indexed columns total, and yes, I need them all, and yes, they all need to be separately indexed). Any row update causes all indexes to be updated, which is a lot of work for the DB engine.

I want to understand the concurrency implications of the discussion on the Postgres documentation page titled Index Locking Considerations, and also the fact that Postgres is single-threaded (multi-process), in terms of how the current design affects reader and writer performance for a large number of concurrent queries, given that I have so many column indices.

My interpretation of these things are the following (please correct any that are wrong):

• Writers that are updating individual rows don't block readers, unless the reader is running a query that produces a result set that would include the row that is being updated.
• Writers only block each other if they are trying to update the same row at the same time.
• Concurrent updates to btree-based indices from multiple writers get merged according to a set of rules that generally does the right thing (so updating the same indexes at the same time does not cause writers to block, unless they are updating the same row).

My questions are:

• How can there even be multiple concurrent readers or writers, if Postgres is single-threaded? If you have multiple processes running, do they simply rely on the inter-process consistency of disk caches (or have to manually flush contents to disk) to coordinate concurrent updates?
• What if anything can get blocked while a large number of indexes are being updated due to a row update? If anything can get blocked during an update, is it possible to turn a dial on the consistency-vs-availability tradeoff so that, for example, a row update is not atomic (i.e. so that the indexes are updated one at a time, but the update to all indexes doesn't have to happen atomically)? I'm OK with a lack of consistency in the name of higher concurrency.

Answer 1

Since it sounds like your main curiosity is around tradeoffs of consistency for improved concurrency, the topic you're probably looking to learn about is called Transaction Isolation Levels. This is an implementation in PostgreSQL (and most database systems) based on the SQL standard which control that tradeoff:

The SQL standard defines four levels of transaction isolation. The most strict is Serializable, which is defined by the standard in a paragraph which says that any concurrent execution of a set of Serializable transactions is guaranteed to produce the same effect as running them one at a time in some order. The other three levels are defined in terms of phenomena, resulting from interaction between concurrent transactions, which must not occur at each level. The standard notes that due to the definition of Serializable, none of these phenomena are possible at that level.

These are the aforementioned phenomena that can occur in various degrees depending on the isolation level:

dirty read

• A transaction reads data written by a concurrent uncommitted transaction.

nonrepeatable read

• A transaction re-reads data it has previously read and finds that data has been modified by another transaction (that committed since the initial read).

phantom read

• A transaction re-executes a query returning a set of rows that satisfy a search condition and finds that the set of rows satisfying the condition has changed due to another recently-committed transaction.

serialization anomaly

• The result of successfully committing a group of transactions is inconsistent with all possible orderings of running those transactions one at a time.

Here is the table of the isolation levels offered by PostgreSQL and their potential phenomena:

The default isolation level in PostgreSQL is Read Committed which very basically means readers block writers and writers block readers. In a different database system you might've been interested in the Read Uncommitted isolation level instead which allows reading of data that's concurrently being written, but PostgreSQL doesn't actually implement this isolation level in that manner - which is a good thing, because it's a dangerous one with risks for most use cases.

Instead PostgreSQL has multiversion concurrency control built in, which allows for optimistic concurrency. This feature allows it to maintain previous states of the data as that data is concurrently changing (being written to) to implicitly allow concurrent readers to be able to read that data too. This short DBA.StackExchange answer discusses this a little further.

---

Aside from all of that, please see my comment on your Post on how to generally improve your database design for increased performance and concurrency.

Answer 2

An individual PostgreSQL database session used to be single-threaded, in that there is a single backend process that processes the SQL statements for the connection. PostgreSQL 9.6 introduced parallel query, which allows the backend process to start additional processes for the duration of a statement. But even without that, you can have many concurrent database sessions, each of which has a backend process, so there can be plenty of concurrency. The communication between these process happens by means of inter-process communication techniques like shared memory, signals and semaphores.

Your assumptions are mostly true, except there is no merging of index modifications by concurrent writers. Concurrent data modification requests are serialized by virtue of various locking techniques (semaphores, mutexes and spinlocks).

There is no way to configure PostgreSQL for better performance at the cost of data integrity and consistency. PostgreSQL is pretty unforgiving when it comes to that. I suspect that your question is a theoretical one and not based on problems you have already encountered. With a wide table with plenty of indexes, I would expect that it is not concurrency that is your big problem, but the slowness of the data modification itself. I suggest that you change the specifications of your application; see this question for my thoughts on that.

Answer 3

Being single-threaded doesn't matter. It is multi-process with shared memory, and the ways that processes manage concurrency is not meaningfully different than how threads do.

There are two kinds of locks, heavy weight locks last for the duration of a transaction (usually), while light weight locks and spin locks last for only a very brief time.

Writers that are updating individual rows don't block readers, unless the reader is running a query that produces a result set that would include the row that is being updated.

Writers block readers using light weight locks or spin locks to the degree necessary to have one process not change data while the other one is inspecting it. This generally happens at the page level, not the row level. So while a writer is writing to a page, the readers can't inspect it. But as soon as the writer is done (a matter of microseconds or less, generally) they can. If the row they want to see has been updated, they will just extract the old value for it instead of the new value.

Writers only block each other if they are trying to update the same row at the same time.

Writers block other writers at the page level for very brief periods just like they do readers. If two writers want to update the same row, then one will block indefinitely on a heavy-weight lock, waiting for the other to commit or rollback.

Concurrent updates to btree-based indices from multiple writers get merged according to a set of rules that generally does the right thing (so updating the same indexes at the same time does not cause writers to block, unless they are updating the same row).

If they are updating the same row, that will be resolved before they get to the index. So the indexes don't impose new "heavy weight" locking issues. They do impose more light-weight locking, but only proportional to amount of work in general they impose.

I'm OK with a lack of consistency in the name of higher concurrency.

This is hard to believe, unless you mean lack of consistency in some specialized sense. Without consistency, you will get wrong results. If you don't care if the results are wrong, there is no need for any indexes, just add WHERE/AND 1=0 to all your queries and they should be fast without indexes.

Answer 4

the app details truly don't matter to the question

If you're asking a question, it means you don't know the answer. In this case it is a bit presumptuous to hide information because you feel it's not relevant: in order to know if the information is relevant, you'd need to know the answer, which you do not, because you're asking the question ;)

if you must know, it's for a dating app with very extensive profile information, many fields of which can be added to search criteria

An excellent solution for a large number of low cardinality columns is a bloom filter index. You have to load the extension:

CREATE EXTENSION bloom

Unfortunately it only supports up to 32 columns, so if you have more columns you'll need several indices. Still for 100 columns... 4 indices will probably use less resources than 100 indices.

Another option is to give each (attribute_name,value) pair a number, store that into an integer array, and put a gist index on it. It's a bit cumbersome, for example "hair=blonde" would maybe correspond to "there is the number 123 in the array".

I did a little benchmark with 1M rows and bloom index won by a large margin.

So I recommend you give it a try and benchmark with your most common search queries, also tune bloom parameters like signature length. Due to the 32 column limit, how you split columns into indices is likely to be important too.

Note your problem is identical to fulltext search. Finding rows with "hair=blonde and status=single" is exactly the same as encoding the attributes into keywords and doing a fulltext search on "hair_blonde status_single".

So another option is to just use a fast fulltext engine. But database integration is likely to suck. I wouldn't recommend using postgres' full text engine since it is based on gist indices, which means you'd get better performance using gist indices directly.

--

Data generation script for benchmark

SELECT * FROM profiles_bloom WHERE a01=1 AND a02=1 AND a03=1 AND a10=1 AND a11=1 AND a12=1

Seq scan: 44ms
Bloom: 12ms
Btree: 26ms
gist (using integer array contains operator): 63ms
gin (same): 45ms

Rows are quite small, which makes bitmap index scan less efficient. With larger rows, each page flagged by the bitmap index scan contains less rows to filter out, so it should be faster.

Unfortunately bloom filter index does not support bools, so I used integer columns.