Loose indexscan

From PostgreSQL wiki

Revision as of 03:15, 4 August 2010 by Davidchristensen (Talk | contribs)

Jump to: navigation, search

Performance Snippets

Loose indexscan

Works with PostgreSQL

8.4

Written in

SQL

Depends on

Nothing


The term "loose indexscan" is used in some other databases for the operation of using a btree index to retrieve the distinct values of a column efficiently; rather than scanning all equal values of a key, as soon as a new value is found, restart the search by looking for a larger value. This is much faster when the index has many equal keys.

Postgres does not support loose indexscans natively, but they can be emulated using a recursive CTE as follows:

WITH RECURSIVE
     t AS (SELECT min(col) AS col FROM tablename
           UNION ALL
           SELECT (SELECT min(col) FROM tablename WHERE col > t.col) FROM t WHERE t.col IS NOT NULL)
SELECT col FROM t WHERE col IS NOT NULL
UNION ALL
SELECT NULL WHERE EXISTS(SELECT * FROM tablename WHERE col IS NULL);

The recursive part of the query processes one new row in each pass, finding the smallest column value greater than that on the previous pass; the main query adds in a single null result if needed. The above query is therefore equivalent to

SELECT DISTINCT col FROM tablename;

but runs orders of magnitude faster when "col" has only a proportionally small number of distinct values.

Personal tools