• 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

  • 2
    SELECTs that do a lookup through the primary key should stay pretty much constant with regards to execution time. – a_horse_with_no_name Nov 22 '17 at 12:29
  • what about INSERT? I'm assuming that's not a problem for a modern RDBMS regardless of index – nicholaswmin Nov 22 '17 at 12:29
  • 1
    O(N) is linear. But a B-tree lookup is O(logN), smaller than linear. – ypercubeᵀᴹ Nov 22 '17 at 12:48
  • Yes I know, I meant non-O(N) there. – nicholaswmin Nov 22 '17 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 Nov 22 '17 at 20:42

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.

| improve this answer | |
  • Is there some relevant paper/blog-post you can point me at for the info you provided? I find it quite useful – nicholaswmin Nov 22 '17 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 Nov 22 '17 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.

| improve this answer | |
  • 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 – nicholaswmin Nov 22 '17 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. – Ben Schmeltzer Nov 22 '17 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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