4

I already posted this question on stackoverflow but I thought that I might get a better answer here.
I have a table storing millions of events occurring to users:

                                       Table "public.events"
   Column   |           Type           |                         Modifiers                         
------------+--------------------------+-----------------------------------------------------------
 event_id   | integer                  | not null default nextval('events_event_id_seq'::regclass)
 user_id    | bigint                   | 
 event_type | integer                  | 
 ts         | timestamp with time zone | 

There are 5 different values for event_type, millions of users, and varying number of events per user per event_type usually ranging from 1 to 50.

A sample of the data:

+-----------+----------+-------------+----------------------------+
| event_id  | user_id  | event_type  |         timestamp          |
+-----------+----------+-------------+----------------------------+
|        1  |       1  |          1  | January, 01 2015 00:00:00  |
|        2  |       1  |          1  | January, 10 2015 00:00:00  |
|        3  |       1  |          1  | January, 20 2015 00:00:00  |
|        4  |       1  |          1  | January, 30 2015 00:00:00  |
|        5  |       1  |          1  | February, 10 2015 00:00:00 |
|        6  |       1  |          1  | February, 21 2015 00:00:00 |
|        7  |       1  |          1  | February, 22 2015 00:00:00 |
+-----------+----------+-------------+----------------------------+

I would like to get, for each event, the number of events of the same user and the same event_type that occurred within 30 days before the event.

It should look like the following:

+-----------+----------+-------------+-----------------------------+-------+
| event_id  | user_id  | event_type  |         timestamp           | count |
+-----------+----------+-------------+-----------------------------+-------+
|        1  |       1  |          1  | January, 01 2015 00:00:00   |     1 |
|        2  |       1  |          1  | January, 10 2015 00:00:00   |     2 |
|        3  |       1  |          1  | January, 20 2015 00:00:00   |     3 |
|        4  |       1  |          1  | January, 30 2015 00:00:00   |     4 |
|        5  |       1  |          1  | February, 10 2015 00:00:00  |     3 |
|        6  |       1  |          1  | February, 21 2015 00:00:00  |     3 |
|        7  |       1  |          1  | February, 22 2015 00:00:00  |     4 |
+-----------+----------+-------------+-----------------------------+-------+

So far I managed to succeed with two different queries (tests on a 1000 rows generated sample on PostgreSQL 9.4.1):

SELECT 
  event_id, user_id,event_type,"timestamp", 
  (
    SELECT count(*) 
    FROM events 
    WHERE timestamp >= e.timestamp - interval '30 days'
    AND timestamp <= e.timestamp
    AND user_id = e.user_id 
    AND event_type = e.event_type
    GROUP BY event_type, user_id
  ) as "count"
FROM events e;

SQL Fiddle for first query

It works quite well, especially since I have an index on the timestamps:

Index Scan using pk_event_id on events e  (cost=0.28..12018.74 rows=1000 width=24)
SubPlan 1
  ->  GroupAggregate  (cost=4.33..11.97 rows=1 width=20)
        Group Key: events.event_type, events.user_id
        ->  Bitmap Heap Scan on events  (cost=4.33..11.95 rows=1 width=20)
              Recheck Cond: ((""timestamp"" >= (e."timestamp" - '30 days'::interval)) AND ("timestamp" <= e."timestamp"))
              Filter: ((user_id = e.user_id) AND (event_type = e.event_type))
              ->  Bitmap Index Scan on idx_events_timestamp  (cost=0.00..4.33 rows=5 width=0)
                    Index Cond: ((""timestamp"" >= (e."timestamp" - '30 days'::interval)) AND ("timestamp" <= e."timestamp"))

Still, it does not scale well and I thought that using window functions might improve the performance:

SELECT toto.event_id,toto.user_id,toto.event_type,toto.lv as time,COUNT(*)
FROM(
    SELECT e.event_id, e.user_id,e.event_type,"timestamp",
    last_value("timestamp") OVER w as lv,
    unnest(array_agg(e."timestamp") OVER w) as agg
    FROM events e
    WINDOW w AS (PARTITION BY e.user_id,e.event_type ORDER BY e."timestamp"
    ROWS UNBOUNDED PRECEDING)) AS toto
WHERE toto.agg >= toto.lv - interval '30 days'
GROUP by event_id,user_id,event_type,lv;

SQL Fiddle for second query

Since I have to use unnest and a sub-query, the performance actually gets worse:

Sort  (cost=5344.41..5427.74 rows=33333 width=24)
  Sort Key: toto.event_id
  ->  HashAggregate  (cost=2506.99..2840.32 rows=33333 width=24)
        Group Key: toto.event_id, toto.user_id, toto.event_type, toto.lv
        ->  Subquery Scan on toto  (cost=67.83..2090.33 rows=33333 width=24)
              Filter: (toto.agg >= (toto.lv - '30 days'::interval))
              ->  WindowAgg  (cost=67.83..590.33 rows=100000 width=24)
                    ->  Sort  (cost=67.83..70.33 rows=1000 width=24)
                          Sort Key: e.user_id, e.event_type, e."timestamp"
                          ->  Seq Scan on events e  (cost=0.00..18.00 rows=1000 width=24)

I was wondering if I could modify if I could only keep my sub-query and somehow modify the window frame to keep only timestamp that are 30 days or less before the row timestamp. Do you think it is possible to scale this query for a very big table without switching to a MapReduce framework?

In a second time, I would like to exclude duplicate events, i.e. same event_type and same timestamp.

  • 1
    Please, as always, provide your Postgres version. Is it timestamp with or without time zone? You have timestamptz in the fiddle but timestamp literals as data; also timestamp in the question. Please post your actual table definition instead of the freehand description: what you get with \d tbl in psql. And some info on data distribution: how many different event types, how many different users, typically how many events per (user_id, event_type) (per month)? Consider the tag info of [postgesql-performance]. – Erwin Brandstetter Apr 5 '15 at 21:15
  • 1
    event_type is int in the question and text in the fiddle. Please be consistent. Do you need the count for every row in the table or just for a particular time frame or a given user or whatever? It's rarely useful to return thousands of rows like this ... One more thing: please post the output of EXPLAIN (BUFFERS, ANALYZE), not just EXPLAIN. – Erwin Brandstetter Apr 5 '15 at 21:30
  • Dear @ErwinBrandstetter, thanks for the comments, it was my first question on dba.SE and yeah the fiddle and my original data differ. Actually, I am preparing this query for Redshift and I just to have my own sample to play with at the moment. I will edit my question to get the information correct. Thanks for the tips. – Julien Bourdon Apr 6 '15 at 15:59
  • And yeah, I need the count for every row as it is fed in dataming algorithms further on. – Julien Bourdon Apr 6 '15 at 16:00
4

Assuming this sanitized table definition

CREATE TABLE events (
  event_id   serial PRIMARY KEY
, user_id    int
, event_type int
, ts         timestamp  -- don't use reserved word as identifier
);

Your comparison seems unfair, the first query has ORDER BY event_id, but the second hasn't. The EXPLAIN output does not fit the first query (no sort step). Be sure to run all tests with the same ORDER BY clause to get valid results. Best run a couple of times and compare the best of 5 to eliminate caching effects.

Index

The key to performance is this multicolumn index:

CREATE INDEX events_fast_idx ON events (user_id, event_type, ts);

The sequence of columns matters! Why?

Queries

Each of your queries can be improved:

Query 1

Remove group by event_type, user_id without substitution:

SELECT event_id, user_id, event_type, ts
    , (SELECT count(*) 
       FROM   events 
       WHERE  user_id    = e.user_id 
       AND    event_type = e.event_type
       AND    ts >= e.ts - interval '30 days'
       AND    ts <= e.ts
      ) AS  ct
FROM   events e
ORDER  BY event_id;

Equivalent with more modern LATERAL join (Postgres 9.3+):

SELECT *
FROM   events e
    ,  LATERAL (
   SELECT count(*) AS ct
   FROM   events 
   WHERE  user_id    = e.user_id 
   AND    event_type = e.event_type
   AND    ts >= e.ts - interval '30 days'
   AND    ts <= e.ts
   ) ct
ORDER  BY event_id;

Which might also be the fastest query in combination with above index.
Related answer with more explanation:

Query 2

  • last_value(ts) OVER w as lv is just an expensive copy of ts.
  • ROWS UNBOUNDED PRECEDING is the default and hence just noise.

SELECT event_id, user_id, event_type, ts, count(*) AS ct
FROM  (
   SELECT event_id, user_id, event_type, ts
        , unnest(array_agg(ts) OVER (PARTITION BY user_id, event_type
                                     ORDER BY ts)) AS agg
   FROM   events   
   ) e
WHERE  agg >= ts - interval '30 days'
GROUP  BY event_id, user_id, event_type, ts
ORDER  BY event_id;

But this is needlessly complex. The same logic can be had much cheaper with a join instead of the subquery with window function:

SELECT e.*, count(*) AS ct
FROM   events e
JOIN   events x USING (user_id, event_type)
WHERE  x.ts >= e.ts - interval '30 days'
AND    x.ts <= e.ts
GROUP  BY e.event_id
ORDER  BY e.event_id;

Which is my other favorite for top performance. Again with the above index.

Other query

Here is another idea, but I doubt it can compete. Give it a go, though:

WITH cte AS (
   SELECT event_id, user_id, event_type, ts
        , row_number(*) OVER (PARTITION BY user_id, event_type
                              ORDER BY ts) AS rn
   FROM   events
   )
SELECT e.event_id, e.user_id, e.event_type, e.ts, e.rn - min(x.rn) + 1 AS ct
FROM   cte e
JOIN   cte x USING (user_id, event_type)
WHERE  x.ts >= e.ts - interval '30 days'
AND    x.ts <= e.ts
GROUP  BY e.event_id, e.user_id, e.event_type, e.ts, e.rn
ORDER  BY e.event_id;

SQL Fiddle demonstrating all in Postgres 9.3.

  • Maybe you can post the results of a fair benchmark as another answer. – Erwin Brandstetter Apr 6 '15 at 1:25
  • Thank you very much for your answer, it was very clear. I posted the resuts of my benchmarks as an answer. Then again, even if I'm quite confident about the data distribution, since I do not have access to the actual data yet, the results may vary. – Julien Bourdon Apr 6 '15 at 17:36
3

I accepted @Erwin's answer but here are the benchmarks on generated data (10000 rows, best of 5 executions) using the corrected queries. I run it with the multi-colmun index.

As expected, queries 1 (26.324 ms) and 2 (23.264 ms) are rather similar in terms of performance while query 3 is the slowest (32.775 ms).

CREATE INDEX events_fast_idx ON events (user_id, event_type, ts);

Query 1

SELECT *
FROM   events e
    ,  LATERAL (
   SELECT count(*) AS ct
   FROM   events 
   WHERE  user_id    = e.user_id 
   AND    event_type = e.event_type
   AND    ts >= e.ts - interval '30 days'
   AND    ts <= e.ts
   ) ct
ORDER  BY event_id;

EXPLAIN (BUFFERS,ANALYZE)

Nested Loop  (cost=8.60..83797.29 rows=10000 width=32) (actual time=0.036..25.775 rows=10000 loops=1)
  Buffers: shared hit=31964
  ->  Index Scan using pk_event_id on events e  (cost=0.29..347.29 rows=10000 width=24) (actual time=0.016..1.786 rows=10000 loops=1)
        Buffers: shared hit=103
  ->  Aggregate  (cost=8.31..8.32 rows=1 width=0) (actual time=0.002..0.002 rows=1 loops=10000)
        Buffers: shared hit=31861
        ->  Index Only Scan using events_fast_idx on events  (cost=0.29..8.31 rows=1 width=0) (actual time=0.001..0.001 rows=1 loops=10000)
              Index Cond: ((user_id = e.user_id) AND (event_type = e.event_type) AND (ts >= (e.ts - '30 days'::interval)) AND (ts <= e.ts))
              Heap Fetches: 11780
              Buffers: shared hit=31861
Planning time: 0.136 ms
Execution time: 26.324 ms

Query 2

SELECT e.*, count(*) AS ct
FROM   events e
JOIN   events x USING (user_id, event_type)
WHERE  x.ts >= e.ts - interval '30 days'
AND    x.ts <= e.ts
GROUP  BY e.event_id
ORDER  BY e.event_id;

EXPLAIN (BUFFERS,ANALYZE)

GroupAggregate  (cost=1597.56..1613.57 rows=915 width=24) (actual time=18.638..22.797 rows=10000 loops=1)
  Group Key: e.event_id
  Buffers: shared hit=26236
  ->  Sort  (cost=1597.56..1599.85 rows=915 width=24) (actual time=18.631..19.974 rows=11780 loops=1)
        Sort Key: e.event_id
        Sort Method: quicksort  Memory: 1305kB
        Buffers: shared hit=26236
        ->  Merge Join  (cost=0.57..1552.55 rows=915 width=24) (actual time=0.018..15.403 rows=11780 loops=1)
              Merge Cond: ((e.user_id = x.user_id) AND (e.event_type = x.event_type))
              Join Filter: ((x.ts <= e.ts) AND (x.ts >= (e.ts - '30 days'::interval)))
              Rows Removed by Join Filter: 4710
              Buffers: shared hit=26236
              ->  Index Scan using events_fast_idx on events e  (cost=0.29..654.26 rows=10000 width=24) (actual time=0.003..2.503 rows=10000 loops=1)
                    Buffers: shared hit=9909
              ->  Index Only Scan using events_fast_idx on events x  (cost=0.29..654.26 rows=10000 width=20) (actual time=0.005..5.111 rows=16490 loops=1)
                    Heap Fetches: 16490
                    Buffers: shared hit=16327
Planning time: 0.216 ms
Execution time: 23.264 ms

Query 3

WITH cte AS (
   SELECT event_id, user_id, event_type, ts
        , row_number(*) OVER (PARTITION BY user_id, event_type
                              ORDER BY ts) AS rn
   FROM   events
   )
SELECT e.event_id, e.user_id, e.event_type, e.ts, e.rn - min(x.rn) + 1 AS ct
FROM   cte e
JOIN   cte x USING (user_id, event_type)
WHERE  x.ts >= e.ts - interval '30 days'
AND    x.ts <= e.ts
GROUP  BY e.event_id, e.user_id, e.event_type, e.ts, e.rn
ORDER  BY e.event_id;

EXPLAIN (BUFFERS,ANALYZE)

GroupAggregate  (cost=2788.06..2797.10 rows=278 width=40) (actual time=27.711..32.004 rows=10000 loops=1)
  Group Key: e.event_id, e.user_id, e.event_type, e.ts, e.rn
  Buffers: shared hit=9909
  CTE cte
    ->  WindowAgg  (cost=0.29..854.26 rows=10000 width=24) (actual time=0.015..8.340 rows=10000 loops=1)
          Buffers: shared hit=9909
          ->  Index Scan using events_fast_idx on events  (cost=0.29..654.26 rows=10000 width=24) (actual time=0.012..3.743 rows=10000 loops=1)
                Buffers: shared hit=9909
  ->  Sort  (cost=1933.81..1934.50 rows=278 width=40) (actual time=27.696..28.470 rows=11780 loops=1)
        Sort Key: e.event_id, e.user_id, e.event_type, e.ts, e.rn
        Sort Method: quicksort  Memory: 1305kB
        Buffers: shared hit=9909
        ->  Merge Join  (cost=1728.77..1922.52 rows=278 width=40) (actual time=14.463..23.720 rows=11780 loops=1)
              Merge Cond: ((e.user_id = x.user_id) AND (e.event_type = x.event_type))
              Join Filter: ((x.ts <= e.ts) AND (x.ts >= (e.ts - '30 days'::interval)))
              Rows Removed by Join Filter: 4710
              Buffers: shared hit=9909
              ->  Sort  (cost=864.39..889.39 rows=10000 width=32) (actual time=11.840..12.296 rows=10000 loops=1)
                    Sort Key: e.user_id, e.event_type
                    Sort Method: quicksort  Memory: 1166kB
                    Buffers: shared hit=9909
                    ->  CTE Scan on cte e  (cost=0.00..200.00 rows=10000 width=32) (actual time=0.017..10.536 rows=10000 loops=1)
                          Buffers: shared hit=9909
              ->  Sort  (cost=864.39..889.39 rows=10000 width=28) (actual time=2.610..3.299 rows=16490 loops=1)
                    Sort Key: x.user_id, x.event_type
                    Sort Method: quicksort  Memory: 1166kB
                    ->  CTE Scan on cte x  (cost=0.00..200.00 rows=10000 width=28) (actual time=0.001..1.183 rows=10000 loops=1)
Planning time: 0.151 ms
Execution time: 32.775 ms
  • Thanks for coming back with results. It's great to see some verification (or falsification). Very good job for a first question. – Erwin Brandstetter Apr 6 '15 at 23:16
1

I don't expect this to be better than the already provided alternatives but it may be worth testing and adding to the options:

with t as
  ( select 
        event_id, user_id, event_type, ts,
        row_number() over w as rn
    from events
    window w as (partition by user_id, event_type 
                 order by ts)
  ) 
select t.event_id, t.user_id, t.event_type, t.ts,
       1 + t.rn - c.rn as cnt
from t, lateral
     ( select tt.rn 
       from t as tt
       where tt.user_id = t.user_id
         and tt.event_type = t.event_type
         and tt.ts >= t.ts - interval '30 days'
       order by tt.ts                        -- option b:  order by tt.rn
       limit 1
     ) c
order by t.user_id, t.event_type, t.ts ;
  • It does work but is twice slower than the other answers (~7500 ms) I guess using a window aggregation was not a good idea for my problem to start with. Thanks for the answer ! – Julien Bourdon Apr 6 '15 at 22:28
  • 7500 ms or 75 ms? – ypercubeᵀᴹ Apr 6 '15 at 22:29
  • nope 7500 ms on a 10000 rows test set. – Julien Bourdon Apr 7 '15 at 6:50
  • Then it is much, much slower than the 26 or 32 ms the other queries achieved. (I assume you did run this with the same multi-column index.) – ypercubeᵀᴹ Apr 7 '15 at 6:53
  • Yes I did -> here is the execution plan pastebin.com/NmztjFgS – Julien Bourdon Apr 7 '15 at 6:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.