Counting distinct rows using recursive cte over non-distinct index

Question

Given the following schema:

CREATE TABLE identifiers (
  id TEXT PRIMARY KEY
);

CREATE TABLE days (
  day DATE PRIMARY KEY
);

CREATE TABLE data (
  id TEXT REFERENCES identifiers
  , day DATE REFERENCES days
  , values NUMERIC[] 
); 
CREATE INDEX ON data (id, day);

What is the best way to count all distinct days between two timestamps? I've tried the following two methods:

EXPLAIN ANALYZE
SELECT COUNT(DISTINCT day) 
FROM data 
WHERE day BETWEEN '2010-01-01' AND '2011-01-01';
                                                                        QUERY PLAN                                                                        
----------------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=200331.32..200331.33 rows=1 width=4) (actual time=1647.574..1647.575 rows=1 loops=1)
   ->  Index Only Scan using data_day_sid_idx on data  (cost=0.56..196942.12 rows=1355678 width=4) (actual time=0.348..1180.566 rows=1362532 loops=1)
         Index Cond: ((day >= '2010-01-01'::date) AND (day <= '2011-01-01'::date))
         Heap Fetches: 0
 Total runtime: 1647.865 ms
(5 rows)

EXPLAIN ANALYZE
SELECT COUNT(DISTINCT day) 
FROM days
WHERE day BETWEEN '2010-01-01' AND '2011-01-01';
                                                           QUERY PLAN                                                           
--------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=18.95..18.96 rows=1 width=4) (actual time=0.481..0.481 rows=1 loops=1)
   ->  Index Only Scan using days_pkey on days  (cost=0.28..18.32 rows=252 width=4) (actual time=0.093..0.275 rows=252 loops=1)
         Index Cond: ((day >= '2010-01-01'::date) AND (day <= '2011-01-01'::date))
         Heap Fetches: 252
 Total runtime: 0.582 ms
(5 rows)

The COUNT(DISTINCT day) against days runs well, but it requires me to keep a secondary table (days) to keep the performance reasonable. In a general sense, I'd like to test if a recursive cte will allow me to achieve similar performance without maintaining a secondary table. My query looks like this, but doesn't run yet:

EXPLAIN ANALYZE
WITH RECURSIVE cte AS (
   (SELECT day FROM data ORDER BY 1 LIMIT 1)
   UNION ALL
   (  -- parentheses required
   SELECT d.day
   FROM   cte  c
   JOIN   data d ON d.day > c.day
   ORDER  BY 1 LIMIT 1
   )
)
SELECT day 
FROM cte
WHERE day BETWEEN '2010-01-01' AND '2011-01-01';

Updates

Thanks to everyone for the ideas. Looks like maintaining a trigger-based table of distinct days is the best way to go, both storage and performance-wise. Thanks to @Erwin's update, the recursive CTE is back in the running. Very useful.

WITH RECURSIVE cte AS (
   (  -- parentheses required because of LIMIT
   SELECT day
   FROM   data
   WHERE  day >= '2010-01-01'::date  -- exclude irrelevant rows early
   ORDER  BY 1
   LIMIT  1
   )

   UNION ALL
   SELECT (SELECT day FROM data
           WHERE  day > c.day
           AND    day < '2011-01-01'::date  -- see comments below
           ORDER  BY 1
           LIMIT  1)
   FROM   cte c
   WHERE  day IS NOT NULL  -- necessary because corr. subq. always returns row
   )
SELECT count(*) AS ct
FROM   cte
WHERE  day IS NOT NULL;

                                                                             QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=53.35..53.36 rows=1 width=0) (actual time=18.217..18.217 rows=1 loops=1)
   CTE cte
     ->  Recursive Union  (cost=0.43..51.08 rows=101 width=4) (actual time=0.194..17.594 rows=253 loops=1)
           ->  Limit  (cost=0.43..0.46 rows=1 width=4) (actual time=0.191..0.192 rows=1 loops=1)
                 ->  Index Only Scan using data_day_idx on data data_1  (cost=0.43..235042.00 rows=8255861 width=4) (actual time=0.189..0.189 rows=1 loops=1)
                       Index Cond: (day >= '2010-01-01'::date)
                       Heap Fetches: 0
           ->  WorkTable Scan on cte c  (cost=0.00..4.86 rows=10 width=4) (actual time=0.066..0.066 rows=1 loops=253)
                 Filter: (day IS NOT NULL)
                 Rows Removed by Filter: 0
                 SubPlan 1
                   ->  Limit  (cost=0.43..0.47 rows=1 width=4) (actual time=0.062..0.063 rows=1 loops=252)
                         ->  Index Only Scan using data_day_idx on data  (cost=0.43..1625.59 rows=52458 width=4) (actual time=0.060..0.060 rows=1 loops=252)
                               Index Cond: ((day > c.day) AND (day < '2011-01-01'::date))
                               Heap Fetches: 0
   ->  CTE Scan on cte  (cost=0.00..2.02 rows=100 width=0) (actual time=0.199..18.066 rows=252 loops=1)
         Filter: (day IS NOT NULL)
         Rows Removed by Filter: 1
 Total runtime: 19.355 ms
(19 rows)

And the also discussed EXISTS query

EXPLAIN ANALYZE
SELECT count(*) AS ct
FROM   generate_series('2010-01-01'::date, '2010-12-31'::date, '1d'::interval) d(day)
WHERE  EXISTS (SELECT 1 FROM data WHERE day = d.day::date);

                                                                  QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=674.32..674.33 rows=1 width=0) (actual time=95.049..95.049 rows=1 loops=1)
   ->  Nested Loop Semi Join  (cost=0.45..673.07 rows=500 width=0) (actual time=12.438..94.749 rows=252 loops=1)
         ->  Function Scan on generate_series d  (cost=0.01..10.01 rows=1000 width=8) (actual time=9.248..9.669 rows=365 loops=1)
         ->  Index Only Scan using data_day_idx on data  (cost=0.44..189.62 rows=6023 width=4) (actual time=0.227..0.227 rows=1 loops=365)
               Index Cond: (day = (d.day)::date)
               Heap Fetches: 0
 Total runtime: 95.620 ms
(7 rows)

Answer 1

Several notes:

Simple query on table day

SELECT COUNT(DISTINCT day) 
FROM   days
WHERE  day BETWEEN '2010-01-01' AND '2011-01-01';

While day is defined as PK, DISTINCT is just expensive noise.

Recursive CTE with correlated suquery

This is the alternative if there is no day table with unique entries. The technique pays if there are multiple to many rows per day, so that the equivalent of a loose index scan is actually faster than a simple DISTINCT on the base table:

WITH RECURSIVE cte AS (
   (  -- parentheses required because of LIMIT
   SELECT day
   FROM   data
   WHERE  day >= '2010-01-01'  -- exclude irrelevant rows early
   ORDER  BY 1
   LIMIT  1
   )
  
   UNION ALL
   SELECT (SELECT day FROM data
           WHERE  day > c.day
           AND    day < '2011-01-01'  -- see below
           ORDER  BY 1
           LIMIT  1)
   FROM   cte c
   WHERE  day IS NOT NULL  -- necessary because corr. subq. always returns row
   )
SELECT count(*) AS ct
FROM   cte
WHERE  day IS NOT NULL;

Index

Only makes sense in combination with a matching index on data:

CREATE INDEX data_day_idx ON data (day);

day must be the leading column. The index you have in the question on (id, day) can be used too, but is far less efficient:

• Working of indexes in PostgreSQL
• Is a composite index also good for queries on the first field?

Notes

It is much cheaper to exclude irrelevant rows early. I integrated your predicate into the query.

Detailed explanation:

• Optimize GROUP BY query to retrieve latest row per user

The case at hand is even simpler - the simplest possible actually.

Your original time frame was day BETWEEN '2010-01-01' AND '2011-01-01'. But BETWEEN .. AND .. includes upper and lower bound, so you'd get all of 2010 plus 2011-01-01. You probably want to exclude the upper bound. Use d.day < '2011-01-01' (not <=). See:

• How to add a day/night indicator to a timestamp column?

EXISTS for this special case

Since you are testing for a range of enumerable days (as opposed to a range with an infinite number of possible values), you can test this alternative with an EXISTS semi-join:

SELECT count(*) AS ct
FROM   generate_series(timestamp '2010-01-01'
                     , timestamp '2010-12-31'
                     , interval  '1 day') AS d(day)
WHERE  EXISTS (SELECT FROM data WHERE day = d.day::date);

Why is this form of generate_series() optimal?

• Generating time series between two dates in PostgreSQL

The same simple index is essential again.

db<>fiddle here demonstrating both with big test table.
_{Old sqlfiddle}