Slow postgresql query with pagination and filtering
I now believe my question to be a duplicate of Slow ORDER BY with LIMIT.

I simplified the query (taking out the complication of a join table) to what matters.

Fast query

explain (analyze, buffers)
SELECT *
FROM big_table

where small_table_id = 822573
ORDER BY sort_key_1, sort_key_2, sort_key_3


Sort  (cost=24642.79..24686.64 rows=17540 width=113) (actual time=0.983..1.471 rows=227 loops=1)
  Sort Key: sort_key_1, sort_key_2, transmitter_id
  Sort Method: quicksort  Memory: 56kB
  Buffers: shared hit=1 read=8
  -&gt;  Index Scan using big_table_small_table_index on big_table  (cost=0.56..23406.36 rows=17540 width=113) (actual time=0.055..0.514 rows=227 loops=1)
        Index Cond: (small_table_id = 822573)
        Buffers: shared hit=1 read=8
Total runtime: 1.941 ms


Slow query

Note: only change is the addition of a  LIMIT clause.

explain (analyze, buffers)
SELECT *
FROM big_table

where small_table_id = 822573
ORDER BY sort_key_1, sort_key_2, sort_key_3

LIMIT 1


Limit  (cost=0.56..6061.27 rows=1 width=113) (actual time=206737.547..206737.550 rows=1 loops=1)
  Buffers: shared hit=13259226 read=303563
  -&gt;  Index Scan using pagination_index on big_table  (cost=0.56..106304766.93 rows=17540 width=113) (actual time=206737.541..206737.541 rows=1 loops=1)
        Filter: (small_table_id = 822573)
        Rows Removed by Filter: 15520057
        Buffers: shared hit=13259226 read=303563
Total runtime: 206737.643 ms


Fast query, with limit

As suggested in the linked question, disabling index scans makes the limited query fast:

SET enable_indexscan = OFF;

explain (analyze, buffers)
SELECT *
FROM big_table

where small_table_id = 822573
ORDER BY sort_key_1, sort_key_2, sort_key_3

LIMIT 1

Limit  (cost=62302.77..62302.77 rows=1 width=113) (actual time=0.897..0.899 rows=1 loops=1)
  Buffers: shared hit=9
  -&gt;  Sort  (cost=62302.77..62346.62 rows=17540 width=113) (actual time=0.894..0.894 rows=1 loops=1)
        Sort Key: sort_key_1, sort_key_2, transmitter_id
        Sort Method: top-N heapsort  Memory: 25kB
        Buffers: shared hit=9
        -&gt;  Bitmap Heap Scan on big_table  (cost=388.50..62215.07 rows=17540 width=113) (actual time=0.040..0.477 rows=227 loops=1)
              Recheck Cond: (small_table_id = 822573)
              Buffers: shared hit=9
              -&gt;  Bitmap Index Scan on big_table_small_table_index  (cost=0.00..384.11 rows=17540 width=0) (actual time=0.030..0.030 rows=227 loops=1)
                    Index Cond: (small_table_id = 822573)
                    Buffers: shared hit=4
Total runtime: 0.932 ms


Fast query, with Common Table Expression

The following query is also fast:

SET enable_indexscan = ON;

explain (analyze, buffers)
with t as (
SELECT *
FROM big_table

where small_table_id = 822573
ORDER BY sort_key_1, sort_key_2, sort_key_3
)
select * from t
LIMIT 1

Limit  (cost=24686.64..24686.66 rows=1 width=3172) (actual time=1.011..1.013 rows=1 loops=1)
  Buffers: shared hit=9
  CTE t
    -&gt;  Sort  (cost=24642.79..24686.64 rows=17540 width=113) (actual time=1.001..1.001 rows=1 loops=1)
          Sort Key: big_table.sort_key_1, big_table.sort_key_2, sort_key_3
          Sort Method: quicksort  Memory: 56kB
          Buffers: shared hit=9
          -&gt;  Index Scan using big_table_small_table_index on big_table  (cost=0.56..23406.36 rows=17540 width=113) (actual time=0.025..0.504 rows=227 loops=1)
                Index Cond: (small_table_id = 822573)
                Buffers: shared hit=9
  -&gt;  CTE Scan on t  (cost=0.00..350.80 rows=17540 width=3172) (actual time=1.007..1.007 rows=1 loops=1)
        Buffers: shared hit=9
Total runtime: 1.070 ms