No merge sort?

I tried general, but no response. Anyone here can shed some light on the
issue? Do I need to code merge sort into postgresql?

----- Forwarded message from Taral <taral(at)taral(dot)net> -----

From: Taral <taral(at)taral(dot)net>
To: pgsql-general(at)postgresql(dot)org
Date: Wed, 12 Mar 2003 17:54:35 -0600
Subject: [GENERAL] No merge sort?
Message-ID: <20030312235435(dot)GA3007(at)taral(dot)net>

I have a table "test" that looks like this:

CREATE TABLE test (
id BIGINT,
time INTEGER
);

There is an index:

CREATE INDEX idx ON test(id, time);

The table has been loaded with 2M rows, where time ranges sequentially
from 0 to 1999999 and id is random values from 0 to 49999.

This query:

SELECT * FROM idx WHERE id IN (...) AND time > 198000 AND time < 199800
ORDER BY time DESC LIMIT 20;

has an EXPLAIN ANALYZE of:

Limit (cost=3635.28..3635.28 rows=20 width=12) (actual time=22.94...22.96 rows=14 loops=1)
-> Sort (cost=3635.28..3635.28 rows=23 width=12) (actual time=22.93..22.93 rows=14 loops=1)
-> Index Scan using idx, idx, ..., idx, idx on test (cost=0.00...3634.77 rows=23 width=12) (actual time=1.01..22.10 rows=14 loops=1)
Total runtime: 29.12 msec

This query:

SELECT * FROM idx WHERE id IN (...) AND time < 199800 ORDER BY time DESC
LIMIT 20;

has an EXPLAIN ANALYZE of:

Limit (cost=14516.46..14516.46 rows=20 width=12) (actual time=1448..83..1448.86 rows=20 loops=1)
-> Sort (cost=14516.46..14516.46 rows=2527 width=12) (actual time=1448.82..1448.83 rows=21 loops=1)
-> Index Scan using idx, idx, ..., idx, idx on test (cost=0.00...14373.67 rows=2527 width=12) (actual time=0.14..1437.33 rows=2048 loops=1)
Total runtime: 1454.62 msec

Since the index will output 'time' sorted data for each 'id', why isn't
a merge sort being used here? A merge sort would reduce the execution
time back to 30 ms.

--
Taral <taral(at)taral(dot)net>
This message is digitally signed. Please PGP encrypt mail to me.
"Most parents have better things to do with their time than take care of
their children." -- Me