Postgres optimizing nested exists

Question

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.

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

Answer 2

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.