• 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

Update after 7 years: We now have ~4 billion rows and it did slow down. Unfortunately it's hard to say how much because we're obviously on much more performant infrastructure.

  • 2
    SELECTs that do a lookup through the primary key should stay pretty much constant with regards to execution time.
    – user1822
    Commented Nov 22, 2017 at 12:29
  • what about INSERT? I'm assuming that's not a problem for a modern RDBMS regardless of index Commented Nov 22, 2017 at 12:29
  • 1
    O(N) is linear. But a B-tree lookup is O(logN), smaller than linear. Commented Nov 22, 2017 at 12:48
  • Yes I know, I meant non-O(N) there. Commented Nov 22, 2017 at 12:50
  • As the index gets deeper, when it does not fit into the cache anymore it will get slower. Same is true for table size exceeding cache. Biggest problem is of course that sometimes you run out of space with no deletes.
    – eckes
    Commented Nov 22, 2017 at 20:42

2 Answers 2


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.

  • Is there some relevant paper/blog-post you can point me at for the info you provided? I find it quite useful Commented Nov 22, 2017 at 22:02
  • I don't know of any single paper addressing B-Tree index performance, but this answer has some links, and there's also this.
    – mustaccio
    Commented Nov 22, 2017 at 23:00

Speed on table select or insert statements depend on many factors:

  • table size - number of rows in table
  • column type(s) - VARCHAR, INT...
  • number of users in the database, including admin functions like running stored procedures.
  • number of queries/inserts/deletes/edits on the table in question when your select statement runs. (Any resource contention, table locks)
  • the server the database runs on - RAM, storage, other apps or DBs
  • database settings cache, buffers

All of these things can impact your queries. Your index helps increase speed in certain statements (the ones that can use the data in the index without needing to search the entire table.) The index in itself is not a bad thing.

Now, speed changes: under normal operating conditions you should not see appreciable changes in query speed. (normal = average work day, abnormal = day when you have a large data load or delete, when another DB is created on that box and is in production, the power goes out and you're running on battery.) That being said, depending on how many concurrent users you have a 1 second difference in a query may be normal.

Here's what I look for if I suspect DB performance issues: 1. Any recent changes to the database or the server? 2. Is the running query substantially different from normal? A query with 4 joins will not be as efficient as a query on 1 table with no joins. 3. Any environmental issues lately? Such as power, unexpected reboots. 4. Review the DB logs and look for errors, locks and the like. 5. Review the server logs and look for errors. 6. Any network issues lately? Check with the network group on their logs. 7. Make a test query that is your baseline. You run this at the beginning of the database life, note the time to run and the number of rows returned. Then when you suspect things are not performing well, run your test query again. Is there a substantial change from your baseline? Additional rows and some increase in time are to be expected. Very different data, table lock on the query or a 10x slowing from your last test run would be unusual. If so, investigate why.

Try some or all of these steps and see if you discover any problems.

  • Ty - I'm not saying that it's slow - I'm more or less looking for advice whether it's theoretically possible for it to get slower as time goes by, only in the context of an index Commented Nov 22, 2017 at 13:21
  • You can use those steps to test if you think you have a problem. And theoretically yes it can get slower, if the table and hence the index grow exponentially. 500,000 rows is a different experience than 5,000,000 rows. Commented Nov 22, 2017 at 13:33

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.