Postgres 14

By using db<>fiddle, you agree to license everything you submit by Creative Commons CC0.
CREATE TABLE test (
  id serial,
  some_integer INT
);

INSERT INTO test (some_integer)
SELECT trunc(random() * 100)  -- FEW distinct values, MANY dupes
FROM   generate_series(1,100000) s;

CREATE INDEX some_integer_idx ON test (some_integer);

CREATE TABLE

INSERT 0 100000

CREATE INDEX

VACUUM ANALYZE test;

VACUUM

EXPLAIN ANALYZE SELECT count(DISTINCT some_integer) FROM test;

QUERY PLAN

Aggregate  (cost=1693.00..1693.01 rows=1 width=8) (actual time=24.493..24.494 rows=1 loops=1)

  ->  Seq Scan on test  (cost=0.00..1443.00 rows=100000 width=4) (actual time=0.027..7.389 rows=100000 loops=1)

Planning Time: 0.444 ms

Execution Time: 24.690 ms

EXPLAIN

-- recursive CTE to emulate index skip scan
WITH RECURSIVE cte AS (
   (
   SELECT some_integer AS i
   FROM   test
   ORDER  BY 1
   LIMIT  1
   )
   
   UNION ALL
   SELECT (SELECT t.some_integer
           FROM   test t
           WHERE  t.some_integer > c.i
           ORDER  BY 1
           LIMIT  1)
   FROM   cte c
   WHERE  c.i IS NOT NULL
   )
SELECT count(i) FROM cte;

count

100

SELECT 1

-- performs excellently for many dupes
EXPLAIN ANALYZE
WITH RECURSIVE cte AS (
   (
   SELECT some_integer AS i
   FROM   test
   ORDER  BY 1
   LIMIT  1
   )
   
   UNION ALL
   SELECT (SELECT t.some_integer
           FROM   test t
           WHERE  t.some_integer > c.i
           ORDER  BY 1
           LIMIT  1)
   FROM   cte c
   WHERE  c.i IS NOT NULL
   )
SELECT count(i) FROM cte;

QUERY PLAN

Aggregate  (cost=37.96..37.97 rows=1 width=8) (actual time=0.517..0.518 rows=1 loops=1)

  CTE cte

    ->  Recursive Union  (cost=0.29..35.69 rows=101 width=4) (actual time=0.010..0.472 rows=101 loops=1)

          ->  Limit  (cost=0.29..0.31 rows=1 width=4) (actual time=0.010..0.010 rows=1 loops=1)

                ->  Index Only Scan using some_integer_idx on test  (cost=0.29..1860.29 rows=100000 width=4) (actual time=0.009..0.009 rows=1 loops=1)

                      Heap Fetches: 0

          ->  WorkTable Scan on cte c  (cost=0.00..3.34 rows=10 width=4) (actual time=0.004..0.004 rows=1 loops=101)

                Filter: (i IS NOT NULL)

                Rows Removed by Filter: 0

                SubPlan 1

                  ->  Limit  (cost=0.29..0.31 rows=1 width=4) (actual time=0.003..0.003 rows=1 loops=100)

                        ->  Index Only Scan using some_integer_idx on test t  (cost=0.29..703.62 rows=33333 width=4) (actual time=0.003..0.003 rows=1 loops=100)

                              Index Cond: (some_integer > c.i)

                              Heap Fetches: 0

  ->  CTE Scan on cte  (cost=0.00..2.02 rows=101 width=4) (actual time=0.011..0.500 rows=101 loops=1)

Planning Time: 0.133 ms

Execution Time: 0.549 ms

EXPLAIN