1

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.
13
  • 1
    You'll probably find most of the answers here and here. If not, they'll help you to formulate a more specific question that can be answered by something less than a book.
    – mustaccio
    Jan 25 at 19:39
  • 1
    @J.D. yeah me too: lots of low cardinality "attribute" columns can be packed into INT[] column with gist index on it.
    – bobflux
    Jan 26 at 10:20
  • 1
    @LukeHutchison "the app details truly don't matter to the question" - Eh they kinda do, since you're asking about performance and concurrency, which are affected by your less than optimal design choice (as pointed out by Laurenz). "it's for a dating app with very extensive profile information" - Cool, been there done that. There's multiple ways to improve your design as opposed to indexing every sparse column (which doesn't really help you anyway), such as bonflux's suggestion, breaking the table down into multiple tables (to improve concurrency), partial indexes, & indexing by location...
    – J.D.
    Jan 27 at 14:56
  • 1
    ...instead, which should be a required field, and getting rid of all the other indexes on low cardinality columns. All predicates will include location, and then using geospatial querying can efficiently reduce the data down significantly by location first, such that filtering on any other unindexed attribute is much faster (being against a smaller subset of rows). This typically is how dating app databases work since it's unlikely Bob in NYC, USA is wanting to match with Jessica from Sydney, Australia. So yes there are many ways to improve the index architecture.
    – J.D.
    Jan 27 at 14:59
  • 1
    @LukeHutchison Glad you found them helpful! Cheers, best of luck!
    – J.D.
    Jan 28 at 14:40

4 Answers 4

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:

Transaction Isolation Levels

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.

1

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.

1

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.

4
  • Thanks for all this detail. What I mean by being OK with lack of consistency is that it's OK for a result to briefly be missed from a result set because an index is still being updated. Every application has some amount of consistency they are willing to live without, whether that amount is zero or greater than zero. For apps at say Facebook scale, you can't afford to enforce strong consistency worldwide for every view of the data. For my application, scalability is more important than consistency. Jan 27 at 5:24
  • @LukeHutchison "For apps at say Facebook scale, you can't afford to enforce strong consistency worldwide for every view of the data" - FWIW, it depends on the database. In their RDBMS (which I believe is MySQL still), they are doing such that. They have other database systems they use for other use cases, but a RDBMS is their database for a lot of their main use cases, and the data is consistent. The point is, when you architect your system properly, most times, you don't have to worry about trading consistency away to maximize performance.
    – J.D.
    Jan 27 at 15:05
  • @J.D. Fair enough, I shouldn't have used Facebook as my main example, since I didn't realize they were still using MySOL -- Amazon and Google would be better examples, since both have implemented custom "planet-scale databases". I worked at Google for many years, and briefly during that time did some DB infrastructure work. All the major custom database frameworks there (there are several) have a knob that applications can turn to tune the consistency vs. availability tradeoff (e.g. selecting for eventual consistency or strong consistency). Jan 28 at 3:18
  • 1
    @LukeHutchison No doubt. I will preface by saying, I find FAANG devs are pretty apt for reinventing the wheel to try to be revolutionary when solving a problem. It's not uncommon I run into strong software devs who hardly understand how traditional database systems work or how to properly architect with one to build a performant system (not at their fault, rather due to a lack of training in academia, but that's a whole other tangent). "a knob that applications can turn to tune the consistency vs. availability tradeoff" - Generally this is transaction isolation levels as my answer discusses.
    – J.D.
    Jan 28 at 3:34
1

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.

4
  • On your first point -- this wasn't hiding information, I was trying to extract only the salient technical points of the problem. The pushback I was getting seemed to be repeat attempts to claim that my database design must be wrong, because DBAs never deal with tables with this many indexes. That's not a reasonable inference. I'm not asking for anyone to redesign my database, I'm asking how to get better performance given the design that I have! (Which you have provided, thank you...) Jan 28 at 3:08
  • The Bloom filter suggestion is a great one, that may be exactly what I need. I didn't realize you could index more than one column with a Bloom filter. I'm going to have to see if that fit though, because I need queries of the form a AND b AND c, where a, b, and c are Boolean columns (so basically I need to test for rows that contain a subset of all-true bits in a requested set of columns, according to a query mask, regardless of the value of the non-masked bits). Jan 28 at 3:11
  • Currently I'm using partial indexes for this, since the true values are sparse. When you say "bloom index won by a large margin", do you mean on writes or reads, or both? I assume this is vs. full indexes? What column types were you using? PS I very much disagree that this is identical to fulltext search. Rendering a search over sparse Boolean bits into a fulltext search would be a horrenous over-engineering of the problem, probably with high index size overhead! Jan 28 at 3:14
  • 1
    I included details about the benchmark in the answer.
    – bobflux
    Jan 28 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.