Query with limit and order by runs too slow

Question

I have the following table:

CREATE TABLE dpg2
(
  account_id integer NOT NULL,
  tank_id integer NOT NULL,
  battles integer,
  dmg integer,
  frags integer,
  wins integer,
  recent_battles integer[],
  recent_dmg integer[],
  recent_frags integer[],
  recent_wins integer[],
  dpg real,
  recent_ts timestamp with time zone[],
  recent_dpg real,
  CONSTRAINT dpg2_pkey PRIMARY KEY (account_id, tank_id)
)

with this index:

CREATE INDEX dpg_tank_id_idx
  ON dpg2
  USING btree
  (tank_id, dpg DESC NULLS LAST);

I ran the following query:

explain analyze
    select dpg2.account_id, tank_id, (select nickname from players2 where players2.account_id = dpg2.account_id), dpg2.battles, dpg,
                frags*1.0/dpg2.battles, wins*100.0/dpg2.battles, dpg2.recent_dpg
    from dpg2
    where tank_id=545 and battles >= 150
    order by dpg desc
    limit 50;

with the following output:

"Limit  (cost=1523898.99..1523899.12 rows=50 width=28) (actual time=23950.831..23950.838 rows=50 loops=1)"
"  ->  Sort  (cost=1523898.99..1524200.69 rows=120678 width=28) (actual time=23950.831..23950.833 rows=50 loops=1)"
"        Sort Key: dpg2.dpg"
"        Sort Method: top-N heapsort  Memory: 32kB"
"        ->  Bitmap Heap Scan on dpg2  (cost=13918.06..1519890.16 rows=120678 width=28) (actual time=434.791..23922.872 rows=21963 loops=1)"
"              Recheck Cond: (tank_id = 545)"
"              Filter: (battles >= 150)"
"              Rows Removed by Filter: 1060576"
"              Heap Blocks: exact=458918"
"              ->  Bitmap Index Scan on dpg_tank_id_idx  (cost=0.00..13887.89 rows=967310 width=0) (actual time=299.796..299.796 rows=1082539 loops=1)"
"                    Index Cond: (tank_id = 545)"
"              SubPlan 1"
"                ->  Index Scan using players2_pkey on players2  (cost=0.43..5.45 rows=1 width=10) (actual time=0.105..0.105 rows=1 loops=21963)"
"                      Index Cond: (account_id = dpg2.account_id)"
"Planning time: 0.212 ms"
"Execution time: 23953.952 ms"

What's really confusing me is that the query planner is trying to resort along the dpg column, when all it needs to do is walk down the index corresponding to the given tank_id and pick the first 50 entries that satisfy the "battles >= 150" condition.

In fact, simply removing the 'order by' clause, I get the same result in 2s because it ends up using the index, which has things sorted in the order I want.

I know I've already solved my problem but why is Postgres doing this and what are the possible solutions?

Edit: I already ran analyze on the table and autovacuum is on.

Answer 1

PostgreSQL thinks it cannot use the index defined on (tank_id, dpg DESC NULLS LAST) to satisfy this query without the sort.

If it is just DESC, that is fine. Or if it was just on (tank_id, dpg), that too would work (it would scan the relevant part of the index backwards).

If you can't change the definition of the index, then making the query match the existing index would probably also work, so:

where tank_id=545 and battles >= 150
order by dpg desc nulls last
limit 50

(which is presumably what you would want anyway?)

To execute your query as originally written with the index you originally had, it would have to execute the query in two parts. First it would have to visit the NULLs at the end of the tank_id=545 region (because ORDER BY...DESC without further qualification implicitly means NULLS FIRST), and then if it hadn't yet reached the LIMIT would have jump to the beginning of the tank_id=545 region to fulfill the ORDER BY DESC part.

So it would have to be the executor, not just the planner, which was involved. It would take a lot of annoying code to make that happen, and no one was volunteered to write it. (Also, it would probably be a rich source of hard-to-find bugs, so even if someone wrote the necessary code, it might not be accepted into the code-base)