7

I'm using Postgres 9.5. I have a table that records page hits from several web sites. This table contains about 32 million rows spanning from Jan 1, 2016 to June 30, 2016.

CREATE TABLE event_pg (
   timestamp_        timestamp without time zone NOT NULL,
   person_id         character(24),
   location_host     varchar(256),
   location_path     varchar(256),
   location_query    varchar(256),
   location_fragment varchar(256)
);

I'm trying to tune a query that counts the number of people that performed a given sequence of page hits. The query is meant to answer questions like "how many people viewed the home-page, and then went to the help site and then viewed the thank-you page"? The result looks like this

╔════════════╦════════════╦═════════════╗
║  home-page ║ help site  ║ thankyou    ║
╠════════════╬════════════╬═════════════╣
║ 10000      ║ 9800       ║1500         ║
╚════════════╩════════════╩═════════════╝

Notice the numbers are decreasing which makes sense, because of the 10000 who viewed the home-page 9800 went on to the help site and of those 1500 went on to hit the thank you page.

The SQL for a 3 step sequence uses lateral joins as follows:

SELECT 
  sum(view_homepage) AS view_homepage,
  sum(use_help) AS use_help,
  sum(thank_you) AS thank_you
FROM (
  -- Get the first time each user viewed the homepage.
  SELECT X.person_id,
    1 AS view_homepage,
    min(timestamp_) AS view_homepage_time
  FROM event_pg X 
  WHERE X.timestamp_ between '2016-04-23 00:00:00.0' and timestamp '2016-04-30 23:59:59.999'
  AND X.location_host like '2015.testonline.ca'
  GROUP BY X.person_id
) e1 
LEFT JOIN LATERAL (
  SELECT
    Y.person_id,
    1 AS use_help,
    timestamp_ AS use_help_time
  FROM event_pg Y 
  WHERE 
    Y.person_id = e1.person_id AND
    location_host = 'helpcentre.testonline.ca' AND
    timestamp_ BETWEEN view_homepage_time AND timestamp '2016-04-30 23:59:59.999'
  ORDER BY timestamp_
  LIMIT 1
) e2 ON true 
LEFT JOIN LATERAL (
  SELECT
    1 AS thank_you,
    timestamp_ AS thank_you_time
  FROM event_pg Z 
  WHERE Z.person_id = e2.person_id AND
    location_fragment =  '/file/thank-you' AND
    timestamp_ BETWEEN use_help_time AND timestamp '2016-04-30 23:59:59.999'
  ORDER BY timestamp_
  LIMIT 1
) e3 ON true;

I have an index on timestamp_, person_id and the location columns. Queries on date ranges of a few days or weeks are very fast (1s to 10s). Where it gets slow is when I try to run the query for everything between Jan 1st & July 30. It takes over a minute. If you compare the two explains below you can see it no longer uses the timestamp_ index and instead does a Seq Scan because the index wouldn't buy us anything since we're querying "all time" hence pretty much all the records in the table.

Now I realise the nested loop nature of the lateral join is going to slow down the more records it has to loop through but is there any way I can speed up this query for huge date ranges so that it scales better?

7

Preliminary notes

  • You are using odd data types. character(24)? char(n) is an outdated type and almost always the wrong choice. You have indexes on person_id and join on it repeatedly. integer would be much more efficient for multiple reasons. (Or bigint, if you plan to burn more than 2 billion rows over the lifetime of the table.) Related:

  • LIKE is pointless without wildcards. Use = instead. Faster.
    x.location_host LIKE '2015.testonline.ca'
    x.location_host = '2015.testonline.ca'

  • Use count(e1.*) or count(*) instead of adding a dummy column with the value 1 for each subquery. (Except for the last (e3), where you don't need any actual data.)

  • You're inconsistent in sometimes casting the string literal to timestamp and sometimes not (timestamp '2016-04-30 23:59:59.999'). Either it makes sense, then do it all the time, or it doesn't, then don't do it.
    It doesn't. When compared to a timestamp column, a string literal is coerced to timestamp anyway. So you don't need an explicit cast.

  • The Postgres data type timestamp has up to 6 fractional digits. Your BETWEEN expressions leave corner cases. I replaced them with less error-prone expressions.

Indexes

Important: to optimize performance create multicolumn indexes.
For the first subquery hp:

CREATE INDEX event_pg_location_host_timestamp__idx
ON event_pg (location_host, timestamp_);

Or, if you can get index-only scans out of it, append person_id to the index:

CREATE INDEX event_pg_location_host_timestamp__person_id_idx
ON event_pg (location_host, timestamp_, person_id);

For very large time ranges spanning most or all of the table, this index should be preferable - it also supports the hlp subquery, so create it either way:

CREATE INDEX event_pg_location_host_person_id_timestamp__idx
ON event_pg (location_host, person_id, timestamp_);

For tnk:

CREATE INDEX event_pg_location_fragment_timestamp__idx
ON event_pg (location_fragment, person_id, timestamp_);

Optimized with partial indexes

If your predicates on location_host and location_fragment are constants, we can use much cheaper partial indexes instead, especially since your location_* columns seem big:

CREATE INDEX event_pg_hp_person_id_ts_idx ON event_pg (person_id, timestamp_)
WHERE  location_host = '2015.testonline.ca';

CREATE INDEX event_pg_hlp_person_id_ts_idx ON event_pg (person_id, timestamp_)
WHERE  location_host = 'helpcentre.testonline.ca';

CREATE INDEX event_pg_tnk_person_id_ts_idx ON event_pg (person_id, timestamp_)
WHERE  location_fragment = '/file/thank-you';

Consider:

Again, all of these indexes are substantially smaller and faster with integer or bigint for person_id.

Generally, you need to ANALYZE the table after creating a new index - or wait till autovacuum kicks in to do it for you.

To get index-only scans, your table has to be VACUUM'ed enough. Test immediately after VACUUM as proof of concept. Read the linked Postgres Wiki page for details if you are unfamiliar with index-only scans.

Basic Query

Implementing what I discussed. Query for small ranges (few rows per person_id):

SELECT count(*)::int           AS view_homepage
     , count(hlp.hlp_ts)::int AS use_help
     , count(tnk.yes)::int     AS thank_you
FROM  (
   SELECT DISTINCT ON (person_id)
          person_id, timestamp_ AS hp_ts
   FROM   event_pg
   WHERE  timestamp_ >= '2016-04-23'
   AND    timestamp_ <  '2016-05-01'
   AND    location_host = '2015.testonline.ca'
   ORDER  BY person_id, timestamp_
   ) hp
LEFT JOIN LATERAL (
   SELECT timestamp_ AS hlp_ts
   FROM   event_pg y 
   WHERE  y.person_id = hp.person_id
   AND    timestamp_ >= hp.hp_ts
   AND    timestamp_ <  '2016-05-01'
   AND    location_host = 'helpcentre.testonline.ca'
   ORDER  BY timestamp_
   LIMIT  1
   ) hlp ON true 
LEFT JOIN LATERAL (
   SELECT true AS yes                   -- we only need existence
   FROM   event_pg z
   WHERE  z.person_id = hp.person_id    -- we can use hp here
   AND    location_fragment = '/file/thank-you'
   AND    timestamp_ >= hlp.hlp_ts      -- this introduces dependency on hlp anyways.
   AND    timestamp_ <  '2016-05-01'
   ORDER  BY timestamp_
   LIMIT  1
   ) tnk ON true;

DISTINCT ON is often cheaper for few rows per person_id. Detailed explanation:

If you have many rows per person_id (more likely for bigger time ranges), the recursive CTE discussed in this answer in chapter 1a can be (much) faster:

See it integrated below.

Optimize & automate best query

It's the old conundrum: one query technique is best for a smaller set, another for a larger set. In your particular case we have a very good indicator from the start - the length of the given time period - which we can use to decide.

We wrap it all in a PL/pgSQL function. My implementation switches from DISTINCT ON to rCTE when the given time period is longer than a set threshold:

CREATE OR REPLACE FUNCTION f_my_counts(_ts_low_inc timestamp, _ts_hi_excl timestamp)
  RETURNS TABLE (view_homepage int, use_help int, thank_you int) AS
$func$
BEGIN

CASE
WHEN _ts_hi_excl <= _ts_low_inc THEN
   RAISE EXCEPTION 'Timestamp _ts_hi_excl (1st param) must be later than _ts_low_inc!';

WHEN _ts_hi_excl - _ts_low_inc < interval '10 days' THEN  -- example value !!!
-- DISTINCT ON for few rows per person_id
   RETURN QUERY
   WITH hp AS (
      SELECT DISTINCT ON (person_id)
             person_id, timestamp_ AS hp_ts
      FROM   event_pg
      WHERE  timestamp_ >= _ts_low_inc
      AND    timestamp_ <  _ts_hi_excl
      AND    location_host = '2015.testonline.ca'
      ORDER  BY person_id, timestamp_
      )
    , hlp AS (
      SELECT hp.person_id, hlp.hlp_ts
      FROM   hp
      CROSS  JOIN LATERAL (
         SELECT timestamp_ AS hlp_ts
         FROM   event_pg
         WHERE  person_id = hp.person_id
         AND    timestamp_ >= hp.hp_ts
         AND    timestamp_ < _ts_hi_excl
         AND    location_host = 'helpcentre.testonline.ca'  -- match partial idx
         ORDER  BY timestamp_
         LIMIT  1
         ) hlp
      )
   SELECT (SELECT count(*)::int FROM hp)   -- AS view_homepage
        , (SELECT count(*)::int FROM hlp)  -- AS use_help
        , (SELECT count(*)::int            -- AS thank_you
           FROM   hlp
           CROSS  JOIN LATERAL (
              SELECT 1                     -- we only care for existence
              FROM   event_pg
              WHERE  person_id = hlp.person_id
              AND    location_fragment = '/file/thank-you'
              AND    timestamp_ >= hlp.hlp_ts
              AND    timestamp_ < _ts_hi_excl
              ORDER  BY timestamp_
              LIMIT  1
              ) tnk
           );

ELSE
-- rCTE for many rows per person_id
   RETURN QUERY
   WITH RECURSIVE hp AS (
      (  -- parentheses required
      SELECT person_id, timestamp_ AS hp_ts
      FROM   event_pg
      WHERE  timestamp_ >= _ts_low_inc
      AND    timestamp_ <  _ts_hi_excl
      AND    location_host = '2015.testonline.ca'  -- match partial idx
      ORDER  BY person_id, timestamp_
      LIMIT  1
      )
      UNION ALL
      SELECT x.*
      FROM   hp, LATERAL (
         SELECT person_id, timestamp_ AS hp_ts
         FROM   event_pg
         WHERE  person_id  > hp.person_id  -- lateral reference
         AND    timestamp_ >= _ts_low_inc  -- repeat conditions
         AND    timestamp_ <  _ts_hi_excl
         AND    location_host = '2015.testonline.ca'  -- match partial idx
         ORDER  BY person_id, timestamp_
         LIMIT  1
         ) x
      )
    , hlp AS (
      SELECT hp.person_id, hlp.hlp_ts
      FROM   hp
      CROSS  JOIN LATERAL (
         SELECT timestamp_ AS hlp_ts
         FROM   event_pg y 
         WHERE  y.person_id = hp.person_id
         AND    location_host = 'helpcentre.testonline.ca'  -- match partial idx
         AND    timestamp_ >= hp.hp_ts
         AND    timestamp_ < _ts_hi_excl
         ORDER  BY timestamp_
         LIMIT  1
         ) hlp
      )
   SELECT (SELECT count(*)::int FROM hp)   -- AS view_homepage
        , (SELECT count(*)::int FROM hlp)  -- AS use_help
        , (SELECT count(*)::int            -- AS thank_you
           FROM   hlp
           CROSS  JOIN LATERAL (
              SELECT 1                     -- we only care for existence
              FROM   event_pg
              WHERE  person_id = hlp.person_id
              AND    location_fragment = '/file/thank-you'
              AND    timestamp_ >= hlp.hlp_ts
              AND    timestamp_ < _ts_hi_excl
              ORDER  BY timestamp_
              LIMIT  1
              ) tnk
           );
END CASE;

END
$func$  LANGUAGE plpgsql STABLE STRICT;

Call:

SELECT * FROM f_my_counts('2016-01-23', '2016-05-01');

The rCTE works with a CTE by definition. I also slipped in CTEs for the DISTINCT ON query (like I discussed with @Lennart in the comments), which allows us to use CROSS JOIN instead of LEFT JOIN to reduce the set with each step, since we can count each CTE separately. This has effects working in opposite directions:

  • On the one had we reduce the number of rows which should make the third join cheaper.
  • On the other hand we introduce overhead for the CTEs and need considerably more RAM, which may be particularly important for big queries like yours.

You'll have to test which outweighs the other.

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.