Why index is not used in SELECT COUNT(DISTINCT)?

Question

This is what I'm doing in PostgreSQL 10.9 (x is VARCHAR(100)):

SELECT COUNT(DISTINCT x) FROM t

The table has over 1.5M records and it has an index:

CREA­TE INDE­X idx_1 ON t­ USIN­G btre­e (x)

The request takes over 7 seconds. This is what EXPLAIN says:

Aggr­egat­e (cos­t=23­675.­97..­2367­5.97­ rows­=1 widt­h=8)­
->­; Seq Scan­ on t (cos­t=0.­00..­2293­0.97­ rows­=148­9990­ widt­h=23­)

What's wrong? Why index is not used?

Answer 1

It depends on two factors:

1. if the table has “wide rows” or not
2. if the table was vacuumed or not

At any rate, the query will have to scan either the whole index or the whole table, because there is no index skip scan in PostgreSQL.

PostgreSQL can either scan the index or the table.

• If the table hasn't been vacuumed recently, an index scan will always have to visit the table to determine if the row is visible or not. In that case, a sequential scan will always be faster.

• If the table has been vacuumed recently, and the visibility map has most blocks marked “all visible”, you could get an index only scan.

  • If the table rows are narrow, you are less likely to get an index only scan, because then reading the index won't be cheaper than reading the table (sequential reads are faster).

  • For tables with wide rows, you will get an index only scan.

Answer 2

The issue here is that while you do have a B-tree index on column t, it won't necessarily help in finding the distinct count. Let's say the index conceptually looks something like this:

1 - 1 - 2 - 2 - 2 - 2 - 4 - 4 - 9

If you only wanted the smallest and largest value, the index in theory could be used, because the first and last value contains this information, and a scan would not be required. But, to find all distinct values, an index scan is necessary. Note that it does not really help to have the index, because Postgres will still have to touch every value in the t column to get the answer.

COUNT is an aggregate function which tends to be index un-friendly (unlike MIN and MAX, which can be index friendly).

Answer 3

To upcomers:

This issue has an interesting solution.

Thanks to these two questions Q1 and Q2, and also the keen questioners and especially genius answerer Erwin Brandstetter, we can use RECURSIVE CTE to achieve partly index skip scan.

As for your example, here is the SQL:

WITH RECURSIVE mid_cte AS (
    (   -- parentheses required
        SELECT x
        FROM   t
        ORDER  BY 1
        LIMIT  1
    )
    UNION ALL
    SELECT n.*
    FROM   mid_cte o
    CROSS JOIN LATERAL (
        SELECT next_t.x
        FROM   t next_t
        WHERE  next_t.x > o.x
        ORDER  BY 1
        LIMIT  1
    ) n
)
SELECT MIN(x),MAX(x),COUNT(DISTINCT x)
FROM   mid_cte

But there is something we have to be aware of: The performance of this index skip scan emulation deeply depends on the cardinality of indexed columns, while table scan only depends on the table size. Here is my experiment and result within:

1st part. 1k cardinality -- 2.67s table scan vs 0.03s emulated index skip scan

-- all test table t has 1.5million rows and run on a ssd.
-- ################# 1) 1k cardinality of column x #################
DROP TABLE IF EXISTS t;
CREATE TABLE t AS SELECT MD5(LEFT (RANDOM()::TEXT,5)) AS x FROM GENERATE_SERIES(1,1500000);
CREATE INDEX t_x_idx ON t USING btree(x);

-- table scan
SELECT MIN(x),MAX(x),COUNT(DISTINCT x) FROM t;
/*
### result set ###
min max count
... ... 1,161  
### use time ###
2.67s
*/

-- emulate index skip scan
WITH RECURSIVE mid_cte AS (
    (   -- parentheses required
        SELECT x
        FROM   t
        ORDER  BY 1
        LIMIT  1
    )
    UNION ALL
    SELECT n.*
    FROM   mid_cte o
    CROSS JOIN LATERAL (
        SELECT next_t.x
        FROM   t next_t
        WHERE  next_t.x > o.x
        ORDER  BY 1
        LIMIT  1
    ) n
)
SELECT MIN(x),MAX(x),COUNT(DISTINCT x)
FROM   mid_cte
;
/*
### result set ###
min max count
... ... 1,161
### use time ###
0.03s
*/

2nd part. 10k cardinality -- 3.44s table scan vs 0.09s emulated index skip scan

-- ################# 2) 10k cardinality of column x #################
-- other SQLs omitted here. the other SQLs are the same as above.
......
CREATE TABLE t AS SELECT MD5(LEFT (RANDOM()::TEXT,6)) AS x FROM GENERATE_SERIES(1,1500000);
......

-- table scan
/*
### result set ###
min max count
... ... 10,146  
### use time ###
3.44s
*/

-- emulate index skip scan
;
/*
### result set ###
min max count
... ... 10,146  
### use time ###
0.09s
*/

3rd part. 100k cardinality -- 4.27s table scan vs 0.89s emulated index skip scan

-- ################# 3) 100k cardinality of column x #################
-- other SQLs omitted here. the other SQLs are the same as above.
......
CREATE TABLE t AS SELECT MD5(LEFT (RANDOM()::TEXT,7)) AS x FROM GENERATE_SERIES(1,1500000);
......

-- table scan
/*
### result set ###
min max count
... ... 100,134  
### use time ###
4.27s
*/

-- emulate index skip scan
;
/*
### result set ###
min max count
... ... 100,134  
### use time ###
0.89s
*/

4th part. 776k cardinality (50% total rows) -- 5.16s table scan vs 10.38s emulated index skip scan

-- ################# 4) 776k cardinality of column x #################
-- other SQLs omitted here. the other SQLs are the same as above.
......
CREATE TABLE t AS SELECT MD5(LEFT (RANDOM()::TEXT,8)) AS x FROM GENERATE_SERIES(1,1500000);
......

-- table scan
/*
### result set ###
min max count
... ... 776,864  
### use time ###
5.16s
*/

-- emulate index skip scan
;
/*
### result set ###
min max count
... ... 776,864  
### use time ###
10.38s
*/

You can see when the cardinality increases, the table scan time increase much slower than emulated index skip scan. So when to use this method is important and has to be under consider.