PostgreSQL Performance – CREATE INDEX vs CREATE INDEX CONCURRENTLY

Index creation is essentially a sort operation, so is at best has a growth complexity of the order n log n on average (you might find it does better in some cases, and is not likely to do much worse).

If all your relevant data pages fit into RAM and are already in RAM, and the index will fit also, and your DBMS does not force index pages to be written before the creation is complete (so index blocks are not updated on disk multiple times during the operation), then the speed of writing the resulting index to disk will be more significant than the time taken to perform the sort - so you might find you get closer to a linear relationship between number of rows and the time the index creation takes - but if you assume the worse case you are less likely to be unpleasantly surprised!

Remember that unless you are not going to stop access to the production database during the operation any index create will be competing for IO bandwidth and/or locks with other activity, so you should try to account for this if you are doing your timing estimation tests on another system even if it is identically configured.

As I understand your question you are asking why highly selective index scans might be much slower after a certain number of records are returned or after the table reaches a certain size. As it turns out your query plans provide most of the information needed. Understanding of course is the first step in trying to figure out how to solve the problem. It looks to me like your slow query is hitting a much more heavily used db than the fast query.

As I look at your query plans, I see two immediate pieces of bad news.

The first piece of bad news is in the buffer usage. Your rows returned are less than double, but you hit about six times the number of buffer pages. This is bad news because it means that PostgreSQL, following the index scan, is scanning through at least six times more information to find the rows to retrieve. Significantly worse, you shift from the rarely used db of mostly read buffers (fast, but few db-specific services) to shared buffers which require more overhead.

The second piece of bad news is that the recheck condition in the slow query weeds out about three times as many records as are returned. This tells me you need to vacuum and/or reindex this table.

I would recommend vacuum analyze and reindex first, followed if necessary by slightly lowering the shared buffer settings and see if this improves performance.