PostgreSQL Index – Does a Table with an Index Ever Slow Down?

indexpostgresql

  • We've got a single table where we store Events.
  • The table has an index on it's primary key

Assuming we're only doing simple SELECTs or INSERTs on that table – would the retrieval or insertion time get noticeably* slower as more and more rows are added?

My (very crude) understanding is that an index makes the lookup time non-linear (non-O(N)), therefore, at least theroreticaly, it won't be a problem – but I'd like to confirm this.

We're working with PostgreSQL 9.5.3 and at some point we expect this table to have billions of rows.

*noticeable: It takes < 1 second to retrieve 5000 events right now, noticeable would be > 2 seconds

Best Answer

Tables do not slow down or speed up, they just sit there. Statements, on the other hand, can slow down. You don't provide sufficient details about your data, but if your primary key is monotonically increasing, like a timestamp or a sequence value, you'll end up rebalancing your tree quite frequently upon inserts. At the same time with such a primary key you can create a concurrency hot spot at the tail end, where all inserts will be happening.

Meanwhile, growing from 106 to 109 entries in the index takes you from 20 comparisons to 30 for the worst case lookup, which is a 50% increase, so depending on your PK value size it's totally feasible that you exceed your noticeability threshold of 2 seconds with some "billions" of rows in the table.

Related Question