2

I have a table of events that each take place during a time range, and I'm trying to create a template for a query which can find events that take place within a specified time period of correlated events which can in turn be specified to take place within a time period of other events. I also need to be able apply a boolean expression to these constraints.

I figure the best way to do this is to use nested exist statements, one for each event in the graph of events. This at least works better than doing inner joins with DISTINCT.

I've read that the Postgres optimizer is quite smart, so rather than trying to parse and optimize the boolean expression myself I was hoping to be able to throw all the constraints into the bottom of the nested queries and have the optimizer do most of the heavy lifting. While simple, disjoint, logic would be easy to parse more complex logic would essentially require writing a mini optimizer or arbitrarily choosing between different logical forms and the corresponding queries.

Unfortunately, the optimizer doesn't seem to optimize in the way I hoped it would. Even in the simplest form with straight AND statements and relatively few conditions, the conditions aren't getting pulled up.

Here is an example of how i'm generating the query and the explain. The CTE provided a substantial performance boost for this particular query, and as far as I know with this type of query the index on the timerange column is unlikely to be used anyways:

EXPLAIN ANALYZE
WITH event AS (
  SELECT *,
  int4range(
    lower(event.tickrange),
    upper(event.tickrange) + 500
  ) AS newrange
  FROM event
)
SELECT event_1.id AS event_1_id
FROM event AS event_1
WHERE EXISTS (
  SELECT 1
  FROM event AS event_2
  WHERE EXISTS (
    SELECT 1
    FROM event AS event_3
    WHERE event_1.a_id = 189
    AND event_3.tickrange <@ event_2.newrange
    AND event_1.id != event_3.id
    AND event_2.id != event_3.id
    AND event_2.tickrange <@ event_1.newrange
    AND event_1.id != event_2.id
  )
)

Nested Loop Semi Join  (cost=117.64..51683659.30 rows=2141 width=4) (actual time=0.075..11060.537 rows=158 loops=1)
  Join Filter: (SubPlan 2)
  Rows Removed by Join Filter: 17782972
  CTE event
    ->  Seq Scan on event  (cost=0.00..117.64 rows=4282 width=30) (actual time=0.033..9.446 rows=4282 loops=1)
  ->  CTE Scan on event event_1  (cost=0.00..85.64 rows=4282 width=40) (actual time=0.039..0.992 rows=4282 loops=1)
  ->  CTE Scan on event event_2  (cost=0.00..85.64 rows=4282 width=68) (actual time=0.000..0.541 rows=4153 loops=4282)
  SubPlan 2
    ->  Result  (cost=0.01..117.76 rows=21 width=0) (actual time=0.000..0.000 rows=0 loops=17783130)
          One-Time Filter: ((event_1.a_id = 189) AND (event_2.tickrange <@ event_1.newrange) AND (event_1.id <> event_2.id))
          ->  CTE Scan on event event_3  (cost=0.01..117.76 rows=21 width=0) (actual time=0.173..0.173 rows=1 loops=160)
                Filter: ((tickrange <@ event_2.newrange) AND (event_1.id <> id) AND (event_2.id <> id))
                Rows Removed by Filter: 830
Planning time: 0.322 ms
Execution time: 11060.848 ms

And here's the same query properly specified with the WHERE conditions where they should be. You'll notice that along with a massive performance difference, the filters are applied sequentially as they should be.

EXPLAIN ANALYZE
WITH event AS (
  SELECT *,
    int4range(
      lower(event.tickrange),
      upper(event.tickrange) + 500
    ) AS newrange
  FROM event
)
SELECT event_1.id AS event_1_id
FROM event AS event_1
WHERE event_1.a_id = 189
AND EXISTS (
  SELECT 1
  FROM event AS event_2
  WHERE EXISTS (
    SELECT 1
    FROM event AS event_3
    WHERE (event_3.tickrange <@ event_2.newrange)
    AND event_1.id != event_3.id
    AND event_2.id != event_3.id
  )
  AND (event_2.tickrange <@ event_1.newrange)
  AND event_1.id != event_2.id
)


Nested Loop Semi Join  (cost=117.64..506774.59 rows=1 width=4) (actual time=0.070..111.936 rows=158 loops=1)
  Join Filter: ((event_2.tickrange <@ event_1.newrange) AND (event_1.id <> event_2.id) AND (SubPlan 2))
  Rows Removed by Join Filter: 136850
  CTE event
    ->  Seq Scan on event  (cost=0.00..117.64 rows=4282 width=30) (actual time=0.032..6.944 rows=4282 loops=1)
  ->  CTE Scan on event event_1  (cost=0.00..96.34 rows=21 width=36) (actual time=0.040..0.958 rows=161 loops=1)
        Filter: (a_id = 189)
        Rows Removed by Filter: 4121
  ->  CTE Scan on event event_2  (cost=0.00..85.64 rows=4282 width=68) (actual time=0.001..0.139 rows=851 loops=161)
  SubPlan 2
    ->  CTE Scan on event event_3  (cost=0.00..117.76 rows=21 width=0) (actual time=0.290..0.290 rows=1 loops=160)
          Filter: ((tickrange <@ event_2.newrange) AND (event_1.id <> id) AND (event_2.id <> id))
          Rows Removed by Filter: 830
Planning time: 0.446 ms
Execution time: 112.160 ms

So I have two (if I may be so bold) questions:

  1. Is there a better way to write the query other than nested exist statements?
  2. Is there a way I can convince the optimizer to do my work, i.e. pull up conditions so that the filters are applied as soon as possible.

I'm using Postgres 9.5

Edit: My admittedly long post could use some clarification it appears so here's the summary.

  • My goal is to create the query In such a way that I don't have to parse the logic and apply it at different levels of the statements. I'm thinking there might be something I'm not doing that would get the optimizer to do this.
  • The second query is a version of the first where I have parsed the logic and put the statements at the correct level. I showed this as a comparison for how the optimizer handles a more proper query.
  • The 500 added to the tickrange in my example is representative of the type of query I would like to run. Its value will change across queries and even across different events within the same query.
  • First when you submit these massive queries. Whitespace-format them. – Evan Carroll Jan 8 '17 at 21:34
  • Sorry about that, I'll do so in the future. – user3747260 Jan 8 '17 at 21:41
  • Is the 500 fixed or it can vary from query to query? – ypercubeᵀᴹ Jan 8 '17 at 22:44
1

You probably are not aware that CTEs in Postgres are optimization fences. In other words, they are evaluated. This is problem 1 of the query.

Problem 2 is that some of the conditions in the inner subquery can be pulled to the mid-subquery or to the main query. While Postgres optimizer is good, why rely on that? (I think it does this optimization with nested derived tables but I'm not sure for nested EXISTS).

Problem 3 is that the comparisons are based on calculated values (the +500). Without more info - whether this 500 is fixed or not), I'll leave that for later.

If we remove the CTEs and pul lout the conditions that can be pulled, the query becomes:

SELECT e1.id AS event_1_id
FROM event AS e1
WHERE e1.a_id = 189
  AND EXISTS (
    SELECT 
    FROM event AS e2
    WHERE e2.tickrange <@ int4range(lower(e1.tickrange), 
                                    upper(e1.tickrange) + 500)
      AND e2.id <> e1.id
      AND EXISTS (
        SELECT 
        FROM event AS e3
        WHERE e3.tickrange <@ int4range(lower(e2.tickrange), 
                                        upper(e2.tickrange) + 500)
          AND e3.id <> e2.id
          AND e3.id <> e1.id 
      )
  ) ;

I expect this to be more efficient that the previous, just by the removal of the CTEs.

If that 500 is fixed, adding an index on (int4range(lower(tickrange), upper(tickrange) + 500)) would likely help as well.


About other ways to write this, you could use LATERAL joins, which allows derived tables in the FROM to be correlated. The LIMIT 1 is needed to be equivalent with the EXISTS:

SELECT e1.id AS event_1_id
FROM event AS e1,
  LATERAL 
    ( SELECT 
      FROM event AS e2,
        LATERAL
          ( SELECT 
            FROM event AS e3
            WHERE e3.tickrange <@ int4range(lower(e2.tickrange), 
                                            upper(e2.tickrange) + 500)
              AND e3.id <> e2.id
              AND e3.id <> e1.id 
          ) 
      WHERE e2.tickrange <@ int4range(lower(e1.tickrange), 
                                      upper(e1.tickrange) + 500)
        AND e2.id <> e1.id
      LIMIT 1
    ) AS ex
WHERE e1.a_id = 189 ;

Both ways above have still nested subqueries. It isn't need though for nested EXISTS. You can have a single EXISTS (or LATERAL) subquery, like this:

SELECT e1.id AS event_1_id
FROM event AS e1
WHERE e1.a_id = 189
  AND EXISTS (
    SELECT
    FROM event AS e2,
         event AS e3
    WHERE e2.tickrange <@ int4range(lower(e1.tickrange), 
                                    upper(e1.tickrange) + 500)
      AND e2.id <> e1.id
      AND e3.tickrange <@ int4range(lower(e2.tickrange), 
                                        upper(e2.tickrange) + 500)
      AND e3.id <> e2.id
      AND e3.id <> e1.id 
  ) ;
  • Thanks for the response. Perhaps my post was a bit too verbose to get across some main points. I made an edit. My main goal is to be able to stuff the conditions in the bottom of the exist statement and have the optimizer work out where to apply them. The CTE is faster for this particular query, although you might be right that it's slower for a more general class of queries of this type. As I understand the optimization fence of CTEs, the filters aren't applied in the construction of the CTE, but once it has been materialized it will act as a normal table. Is this not correct? – user3747260 Jan 9 '17 at 0:33
  • So, you want to place the e1.a_id = 189 condition for example, in the most internal subquery? – ypercubeᵀᴹ Jan 9 '17 at 0:40
  • As for the CTE being more efficient, more efficient than what? Is it faster than my rewrite? And how many rows match the a_id=189 condition? 11 seconds doesn't sound very fast! – ypercubeᵀᴹ Jan 9 '17 at 0:41
  • Yes, I want to be able to put the condition in the most internal subquery. Other than the CTE, the query you posted is essentially the same as the second one I posted is it not? The CTE is about twice as fast for both the more properly formed query and the one with everything thrown into the most internal subquery. Roughly 5% of the rows match the a_id=189 condition. 11 seconds is slow, but the more proper query takes .1 second. It's the one I'm trying to optimize that's 11 seconds. – user3747260 Jan 9 '17 at 0:49
  • 1
    The unnested lateral query worked really well. It reduced the time to 2.5s, and seemed to apply the filters in a way that would scale much better. Interestingly, the unnested exists and lateral queries performed better than the nested versions when everything was thrown into the bottom subquery. I also figured out I was using the wrong index type on tickrange. So with LATERAL and the index it now runs at 42ms :). Big thanks. – user3747260 Jan 9 '17 at 10:39
1

I imagine you could get around the seq scans entirely if you avoided the CTE, and put a functional index on this.

CREATE INDEX myidx ON event int4range(
  lower(event.tickrange),upper(event.tickrange) + 500
);

And, then..

SELECT event_1.id AS event_1_id
FROM event AS event_1
WHERE EXISTS (
  SELECT 1
  FROM event AS event_2
  WHERE EXISTS (
    SELECT 1
    FROM event AS event_3
    WHERE event_1.a_id = 189
    AND event_3.tickrange <@ int4range(
      lower(event_2.tickrange), upper(event_2.tickrange) + 500
    )
    AND event_1.id != event_3.id
    AND event_2.id != event_3.id
    AND event_2.tickrange <@ int4range(
      lower(event_1.tickrange), upper(event_1.tickrange) + 500
    )
    AND event_1.id != event_2.id
  )
)

Also in your question you say,

events that take place within a specified time period of correlated events which can in turn be specified to take place within a time period of other events. I also need to be able apply a boolean expression to these constraints.

But, in you query you're not finding events. You're just checking that a specific event (id=189)

  1. has one range that contains it,
  2. which itself has one range that contains it.
  • They don't compare [x1,y1+500] @> [x2,y2+500]. They compare [x1,y1+500] @> [x2,y2] – ypercubeᵀᴹ Jan 8 '17 at 22:44
  • @TypoCubeᵀᴹ where do you see any comparison to anything that doesn't have the +500? Am I missing something doesn't the CTE event shadow all future references to event? – Evan Carroll Jan 8 '17 at 22:46
  • 1
    event_2. tickrange <@ event_1. newrange – ypercubeᵀᴹ Jan 8 '17 at 22:47
  • my bad, I was eating glue. – Evan Carroll Jan 8 '17 at 22:53
  • I just tried the indexed query. It sounds promising, but unfortunately a sequential scan was still used. I'll play around with it some more though. As for the number of events, 189 is the id of a foreign key so there are many rows in the event table that have that value. Sorry if that wasn't clear. – user3747260 Jan 9 '17 at 0:38

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.