@User do you have autovacuum turned on and have you confirmed that it has been running? we can reproduce the dichotomy in query latency just by inserting a bunch of rows and running the query without an

analyze

call first