Counting Distinct Rows Using Recursive Cte Over Non-distinct Index

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

Solution 1:

Several notes:

Simple query on table day

SELECTCOUNT(DISTINCTday) 
FROM   days
WHEREdayBETWEEN'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:

WITHRECURSIVE cte AS (
   (  -- parentheses required because of LIMITSELECTdayFROM   data
   WHEREday>='2010-01-01'-- exclude irrelevant rows earlyORDERBY1
   LIMIT  1
   )
  
   UNIONALLSELECT (SELECTdayFROM data
           WHEREday> c.day
           ANDday<'2011-01-01'-- see belowORDERBY1
           LIMIT  1)
   FROM   cte c
   WHEREdayISNOTNULL-- necessary because corr. subq. always returns row
   )
SELECTcount(*) AS ct
FROM   cte
WHEREdayISNOTNULL;

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:

SELECTcount(*) AS ct
FROM   generate_series(timestamp'2010-01-01'
                     , timestamp'2010-12-31'
                     , interval'1 day') AS d(day)
WHEREEXISTS (SELECTFROM data WHEREday= 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}

Solution 2:

Try creating an index on data(day) and then running the first query:

SELECTCOUNT(DISTINCTday) 
FROM data 
WHEREdayBETWEEN'2010-01-01'AND'2011-01-01';

You might find the performance sufficient for your purposes.

Solution 3:

I'm not really sure why the index on data(day) is slower, that would seem the simplest option. But if that's too slow, you could try creating a materialised view of your days. Basically just:

create materialized view days asselectdayfrom data 
groupbyday;

I don't believe postgres updates materialised views automatically, but at least then all the maintenance you need to do is periodically refresh it. Or perhaps create a trigger on data which refreshes the view. Bear in mind of course that refreshing this view might take some time depending on the size of the data table, you might only want to do it hourly or nightly if you can get away with it.

Alternatively if this table gets a lot of updates and you need the distinct day count to be consistent at all times, you could consider going back to your original separate days table, but reduce the maintenance overhead by creating a trigger on the data table to update it.