Подсчет отдельных строк с использованием рекурсивного cte по нечеткому индексу

Учитывая следующую схему:

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);

Каков наилучший способ подсчета всех отдельных дней между двумя временными метками? Я пробовал следующие два метода:

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)

COUNT(DISTINCT day) против days работает хорошо, но для поддержания приемлемой производительности мне требуется дополнительная таблица (days). В общем, я хотел бы проверить, позволит ли рекурсивный cte добиться аналогичной производительности без поддержки вторичной таблицы. Мой запрос выглядит так, но еще не выполняется:

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';

Обновления

Спасибо всем за идеи. Похоже, что ведение таблицы отдельных дней на основе триггеров — лучший способ, как с точки зрения хранения, так и с точки зрения производительности. Благодаря обновлению @Erwin рекурсивный CTE снова в работе. Очень полезный.

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)

А также обсуждаемый EXISTS запрос

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)

postgresql sql count postgresql-9.3 unique-index
person Justin    schedule 21.03.2015    source источник
comment
Почему у вас есть первичный ключ text? Разве у вас не должно быть целого числа, которое ссылается на текст в другой таблице?   -  person Gordon Linoff    schedule 21.03.2015
comment
Они действительно должны быть, но они были реализованы как MD5 во всем коде обработки и, соответственно, оставлены как записи TEXT в db.   -  person Justin    schedule 21.03.2015
comment
Это продолжение предыдущего вопроса: stackoverflow.com/questions/29171623/   -  person Erwin Brandstetter    schedule 21.03.2015
comment
Я думаю, что вы случайно удалили результаты решения EXISTS.   -  person Erwin Brandstetter    schedule 22.03.2015
comment
Хороший улов. Повторно добавлено выше.   -  person Justin    schedule 22.03.2015
comment
Предыдущее время для варианта EXISTS составляло 3 мс. Теперь это 95 мс. Что изменилось?   -  person Erwin Brandstetter    schedule 22.03.2015
comment
Я предполагаю, что что-то было кэшировано. Просто повторил этот запрос несколько раз и увидел 87 мс, 7 мс и 4 мс. Нижняя граница примерно такая же, как и для рекурсивного запроса. Обычно я стараюсь запускать запросы такого типа несколько раз, прежде чем опубликовать объяснения, но в целом имеет ли смысл публиковать некэшированные или кешированные? В моем случае меня больше беспокоит кеширование, и я стараюсь размещать сообщения соответственно.   -  person Justin    schedule 23.03.2015
comment
Зависит от фактического варианта использования, конечно. Но обычно результат с теплым кешем более интересен. Я бы взял лучшее из 5, чтобы сравнить производительность.   -  person Erwin Brandstetter    schedule 23.03.2015

Ответы (3)


arrow_upward
2
arrow_downward

Несколько примечаний:

Простой запрос к таблице day

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

В то время как day определяется как PK, DISTINCT — это просто дорогой шум.

Рекурсивный CTE с коррелированным запросом

Это вариант, если нет day таблицы с уникальными записями. Этот метод окупается, если в день выполняется от нескольких до многих строк, так что эквивалент свободного сканирования индекса на самом деле быстрее, чем простое DISTINCT в базовой таблице:

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;

Показатель

Имеет смысл только в сочетании с соответствующим индексом на data:

CREATE INDEX data_day_idx ON data (day);

day должен быть ведущим столбцом. Индекс, который у вас есть в вопросе о (id, day), тоже можно использовать, но он гораздо менее эффективен:

Примечания

Гораздо дешевле заранее исключить нерелевантные строки. Я интегрировал ваш предикат в запрос.

Детальное объяснение:

Дело обстоит еще проще - на самом деле самое простое из возможных.

Ваш первоначальный временной интервал был day BETWEEN '2010-01-01' AND '2011-01-01'. Но BETWEEN .. AND .. включает верхнюю и нижнюю границы, так что вы получите весь 2010 год плюс 01 января 2011 года. Возможно, вы захотите исключить верхнюю границу. Используйте d.day < '2011-01-01' (не <=). Видеть:

EXISTS для этого особого случая

Поскольку вы тестируете диапазон перечислимых дней (в отличие от диапазона с бесконечным числом возможных значений), вы можете протестировать этот вариант с помощью EXISTS полусоединение:

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);

Почему эта форма generate_series() оптимальна?

Тот же самый простой индекс снова необходим.

db‹›fiddle здесь демонстрирует оба варианта с большой тестовой таблицей.
Старый sqlfiddle

person Erwin Brandstetter    schedule 21.03.2015
comment
Пытался запустить предоставленный рекурсивный cte безрезультатно (995 с). Случай с EXISTS работал очень хорошо (3 мс), но с точки зрения хранения простое обслуживание реляционной таблицы days выглядит как победитель. Размещенный запрос объясняет в вопросе как правки. Спасибо! - person Justin; 21.03.2015
comment
Поскольку вариант EXISTS работает так хорошо, я бы предпочел придерживаться его. Поддержка дополнительной таблицы с триггерами также обходится дорого. Если производительность этого запроса является первостепенным требованием, рассмотрите материализованное представление, подобное упомянутому EvilPuppetMaster в его ответе. Производительность rCTE была полностью неожиданной. Я изучил, нашел и исправил ошибку производительности в своем решении - благодаря вашим отзывам! Также обновил мой справочный ответ и добавил скрипку, чтобы доказать это. Пожалуйста, протестируйте новое решение rCTE. Вероятно, не так быстро, как EXISTS, но близко и более универсально. - person Erwin Brandstetter; 22.03.2015
comment
Работает как положено. Разместил объяснение в моем обновлении выше. Спасибо! - person Justin; 22.03.2015

arrow_upward
1
arrow_downward

Попробуйте создать индекс для data(day), а затем выполните первый запрос:

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

Вы можете найти производительность достаточной для ваших целей.

person Gordon Linoff    schedule 21.03.2015
comment
Чуть лучше производительность, но все же на три порядка медленнее, чем в отличие от дней. (Общее время выполнения: 1197,124 мс) - person Justin; 21.03.2015

arrow_upward
1
arrow_downward

Я не совсем уверен, почему индекс данных (день) работает медленнее, это может показаться самым простым вариантом. Но если это слишком медленно, вы можете попробовать создать материализованное представление о своих днях. В основном просто:

create materialized view days as
select day 
from data 
group by day;

Я не верю, что postgres автоматически обновляет материализованные представления, но, по крайней мере, тогда все, что вам нужно делать, это периодически обновлять его. Или, возможно, создайте триггер для данных, который обновляет представление. Имейте в виду, конечно, что обновление этого представления может занять некоторое время в зависимости от размера таблицы данных, вы можете делать это только ежечасно или каждую ночь, если вам это сойдет с рук.

В качестве альтернативы, если эта таблица получает много обновлений и вам нужно, чтобы число отдельных дней было постоянным, вы можете рассмотреть возможность возврата к исходной таблице отдельных дней, но уменьшить накладные расходы на обслуживание, создав триггер в таблице данных для обновления. Это.

person EvilPuppetMaster    schedule 21.03.2015