Creating multicolumn index for WHERE and ORDER BY

Question

I am trying to create an index to be used in WHERE and ORDER BY clauses at the same time. Reading Postgres 14 documentation (11.4. Indexes and ORDER BY - https://www.postgresql.org/docs/14/indexes-ordering.html) led me to believe that:

In addition to simply finding the rows to be returned by a query, an index may be able to deliver them in a specific sorted order. This allows a query's ORDER BY specification to be honoured without a separate sorting step.

Wow, sound awesome, let's try it! I created a test table, an index that includes both WHERE and ORDER BY columns and populated it with data:

DROP TABLE IF EXISTS testdata;
CREATE TABLE testdata
(
    question_id   TEXT        NOT NULL UNIQUE PRIMARY KEY,
    answerer_id   TEXT        NOT NULL,
    question_date TIMESTAMPTZ NOT NULL,
    answer_date   TIMESTAMPTZ NOT NULL
);

DROP INDEX IF EXISTS idx1;
CREATE INDEX idx1 ON testdata (answerer_id, answer_date, question_date);

TRUNCATE testdata;
INSERT INTO testdata(question_id, answerer_id, question_date, answer_date)
SELECT CONCAT('question_', LPAD(i::TEXT, 4, '0')),
       CONCAT('answerer_', LPAD(FLOOR(RANDOM() * (99 - 1 + 1) + 1)::TEXT, 2, '0')),
       TIMESTAMPTZ '2021-01-01' + RANDOM() * INTERVAL '365 days',
       TIMESTAMPTZ '2022-01-01' + RANDOM() * INTERVAL '365 days'
FROM GENERATE_SERIES(1, 9999) AS t(i);

VACUUM (FULL, ANALYZE) testdata;

EXPLAIN ANALYSE
SELECT *
FROM testdata
WHERE answerer_id = 'answerer_09'
ORDER BY answer_date,
         question_date;

Here is an example of the data. Since the answerer_id is a random number from 1 to 99, then ~100 rows out of 10K rows (~10% of all rows) should be returned for this query:

EXPLAIN ANALYSE of the query gives me the following:

Sort  (cost=108.49..108.75 rows=106 width=42) (actual time=2.194..3.555 rows=106 loops=1)
  Sort Key: answer_date, question_date"
  Sort Method: quicksort  Memory: 33kB
  ->  Bitmap Heap Scan on testdata  (cost=5.11..104.92 rows=106 width=42) (actual time=0.057..1.188 rows=106 loops=1)
        Recheck Cond: (answerer_id = 'answerer_09'::text)
        Heap Blocks: exact=67
        ->  Bitmap Index Scan on idx1  (cost=0.00..5.08 rows=106 width=0) (actual time=0.032..0.040 rows=106 loops=1)
              Index Cond: (answerer_id = 'answerer_09'::text)
Planning Time: 0.154 ms
Execution Time: 4.856 ms

So the DB used the index to find the rows that satisfied WHERE clause, and then... sorted them with quicksort? Why not return the rows exactly like they are in the index, already sorted?

Am I missing something? Maybe I need to create the index in some other way for it to be used in both WHERE and ORDER BY?

UPDATE:

Changing the query to:

EXPLAIN ANALYSE
SELECT *
FROM testdata
WHERE answerer_id = 'answerer_09'
ORDER BY answer_date,
         question_date
LIMIT 30; -- NEW!

Changes the result drastically:

Limit  (cost=0.29..83.88 rows=30 width=42) (actual time=0.064..1.599 rows=30 loops=1)
  ->  Index Scan using idx1 on testdata  (cost=0.29..253.87 rows=91 width=42) (actual time=0.044..0.676 rows=30 loops=1)
        Index Cond: (answerer_id = 'answerer_09'::text)
Planning Time: 0.125 ms
Execution Time: 1.967 ms

If I change the limit to 40+, it reverts back to using sorting (although a different type: top-N heapsort):

Limit  (cost=105.95..106.05 rows=40 width=42) (actual time=1.853..3.205 rows=40 loops=1)
  ->  Sort  (cost=105.95..106.17 rows=91 width=42) (actual time=1.837..2.321 rows=40 loops=1)
        Sort Key: answer_date, question_date"
        Sort Method: top-N heapsort  Memory: 30kB
        ->  Bitmap Heap Scan on testdata  (cost=4.99..103.07 rows=91 width=42) (actual time=0.054..1.037 rows=91 loops=1)
              Recheck Cond: (answerer_id = 'answerer_09'::text)
              Heap Blocks: exact=57
              ->  Bitmap Index Scan on idx1  (cost=0.00..4.97 rows=91 width=0) (actual time=0.034..0.042 rows=91 loops=1)
                    Index Cond: (answerer_id = 'answerer_09'::text)
Planning Time: 0.093 ms
Execution Time: 3.618 ms

So the index is correct, and the DB is aware of it, but ignores it when it expects to have undefined (no limit) or rather large limit.

What is the reason for that? Is it because somehow sorting and not using the index is faster?

Answer 1

For ~ 10 % of all rows it's typically not efficient to run an index scan. (Many factors in play here ...) What you see is a bitmap index scan. Why? See:

• Postgres not using index when index scan is much better option

Bitmap index scans cannot carry over the index sort order into the result. So a final sort step is required.

You can "disable" alternative query plans to "force" your index scan (only for testing purposes!):

SET enable_bitmapscan = off;
SET enable_seqscan = off;

Or you can lower the expected cost for random access with:

SET random_page_cost = 1;  -- or similar

Or you can LIMIT to only few result rows like you added.

Either of these can convince the query planner to switch to an index scan with no additional sort step:

Index Scan using idx1 on testdata  (cost=0.29..274.08 rows=104 width=42) (actual time=0.014..0.050 rows=104 loops=1)
  Index Cond: (answerer_id = 'answerer_09'::text)
Planning Time: 0.052 ms
Execution Time: 0.064 ms

db<>fiddle here

For your test case with only few rows and a mildly selective predicate, it's hard to tell whether sequential scan, bitmap index scan or index scan will be faster. Tests with bigger tables are more revealing.

Either way, the query planner strictly bases its decision on the estimated cost (Setting SET enable_seqscan = off just makes sequential scans seem very expensive.) The plan expected to be cheapest wins. Table and column statistics, server configuration and cost settings should be as valid as possible to get valid estimates - and good query plans.