PostgreSQL Query Performance – Slow Query with Pagination and Filtering

For the DB in question, I have followed the advice of Pagination Done the
PostgreSQL Way

That is, results are being paginated on a composite index with a definite sort order.

Now, my problem is that when this is combined with a where-clause filter on a join table, the query becomes very slow.

How can I make my query faster in the filtering case?

Note: pagination_index is a unique index on sort_key_1, sort_key_2, sort_key_3.

Query without filter

EXPLAIN (ANALYZE, BUFFERS) SELECT *
FROM big_table

join small_table on small_table_id = small_table.id
--WHERE small_table.filter_column = 9173

ORDER BY sort_key_1, sort_key_2, sort_key_3
LIMIT 20

Limit  (cost=0.85..124.26 rows=20 width=293) (actual time=49.947..50.254 rows=20 loops=1)
  Buffers: shared hit=64 read=1
  ->  Nested Loop  (cost=0.85..318749153.46 rows=51655908 width=293) (actual time=49.942..50.189 rows=20 loops=1)
        Buffers: shared hit=64 read=1
        ->  Index Scan using pagination_index on big_table  (cost=0.56..106181666.21 rows=51655908 width=113) (actual time=0.019..0.054 rows=20 loops=1)
              Buffers: shared hit=5
        ->  Index Scan using small_table_pkey on small_table  (cost=0.28..4.11 rows=1 width=180) (actual time=2.498..2.500 rows=1 loops=20)
              Index Cond: (id = big_table.small_table_id)
              Buffers: shared hit=59 read=1
Total runtime: 92.107 ms

Query with filter

EXPLAIN (ANALYZE, BUFFERS) SELECT *
FROM big_table

join small_table on small_table_id = small_table.id
WHERE small_table.filter_column = 9173

ORDER BY sort_key_1, sort_key_2, sort_key_3
LIMIT 20

Limit  (cost=0.85..79443.10 rows=20 width=293) (actual time=1331003.261..2376282.943 rows=16 loops=1)
  Buffers: shared hit=45840126 read=1148265
  ->  Nested Loop  (cost=0.85..108506196.66 rows=27317 width=293) (actual time=1331003.257..2376282.873 rows=16 loops=1)
        Join Filter: (big_table.small_table_id = small_table.id)
        Rows Removed by Join Filter: 154967708
        Buffers: shared hit=45840126 read=1148265
        ->  Index Scan using pagination_index on big_table  (cost=0.56..106181666.21 rows=51655908 width=113) (actual time=0.010..1544834.357 rows=51655908 loops=1)
              Buffers: shared hit=45840121 read=1148265
        ->  Materialize  (cost=0.28..14.60 rows=3 width=180) (actual time=0.002..0.007 rows=3 loops=51655908)
              Buffers: shared hit=5
              ->  Index Scan using small_table_id_index on small_table  (cost=0.28..14.59 rows=3 width=180) (actual time=0.008..0.017 rows=3 loops=1)
                    Index Cond: (filter_column = 9173)
                    Buffers: shared hit=5
Total runtime: 2376283.041 ms

Query with filter but no order by

This is relatively fast also.

EXPLAIN (ANALYZE, BUFFERS) SELECT *
FROM big_table

join small_table on small_table_id = small_table.id
WHERE small_table.filter_column = 9173

--ORDER BY sort_key_1, sort_key_2, sort_key_3
LIMIT 20

Limit  (cost=0.56..78.57 rows=20 width=293) (actual time=0.035..100.824 rows=16 loops=1)
  Buffers: shared hit=18 read=132
  ->  Nested Loop  (cost=0.56..106540.40 rows=27317 width=293) (actual time=0.031..100.759 rows=16 loops=1)
        Buffers: shared hit=18 read=132
        ->  Seq Scan on small_table  (cost=0.00..200.91 rows=3 width=180) (actual time=0.014..10.124 rows=3 loops=1)
              Filter: (filter_column = 9173)
              Rows Removed by Filter: 5670
              Buffers: shared hit=2 read=128
        ->  Index Scan using big_table_small_table_index on big_table  (cost=0.56..35179.54 rows=26696 width=113) (actual time=30.168..30.183 rows=5 loops=3)
              Index Cond: (small_table_id = small_table.id)
              Buffers: shared hit=16 read=4
Total runtime: 100.901 ms