Thread: Forcing filter/join order?

Folks,

Have an interesting issue with a complex query, where apparently I need to
twist the query planner's arm, and am looking for advice on how to do so.

The situation:  I have a table, events, with about 300,000 records.
It does an outer join to a second table, cases, with about 150,000 records.

A very simplified version query would be like

SELECT *
FROM events LEFT OUTER JOIN cases ON events.case_id = cases.case_id
WHERE events.event_date BETWEEN 'date1' AND 'date2'

This join is very expensive, as you can imagine.   Yet I can't seem to force
the query planner to apply the filter conditions to the events table *before*
attempting to join it to cases.  Here's the crucial explain lines:

                                 ->  Merge Left Join  (cost=0.00..11880.82
rows=15879 width=213) (actual time=5.777..901.899 rows=648 loops=1)
                                       Merge Cond: ("outer".case_id =
"inner".case_id)
                                       Join Filter: (("outer".link_type)::text
= 'case'::text)
                                       ->  Index Scan using idx_event_ends on
events  (cost=0.00..4546.15 rows=15879 width=80
) (actual time=4.144..333.769 rows=648 loops=1)
                                             Filter: ((status <> 0) AND
((event_date + duration) >= '2004-02-18 00:00:00'::timestamp without time
zone) AND (event_date <= '2004-03-05 23:59:00'::timestamp without time zone))
                                       ->  Index Scan using cases_pkey on
cases  (cost=0.00..6802.78 rows=117478 width=137) (
actual time=0.139..402.363 rows=116835 loops=1)

As you can see, part of the problem is a pretty drastic (20x) mis-estimation
of the selectivity of the date limits on events -- and results in 90% of the
execution time of my query on this one join.  I've tried raising the
statistics on event_date, duration, and case_id (to 1000), but this doesn't
seem to affect the estimate or the query plan.

In the above test, idx_event_ends indexes (case_id, status, event_date,
(event_date + duration)), but as you can see the planner uses only the first
column.  This was an attempt to circumvent the planner's tendency to
completely ignoring any index on (event_date, (event_date + duration))  --
even though that index is the most selective combination on the events table.

Is there anything I can do to force the query planner to filter on events
before joining cases, other than waiting for version 7.5?

--
-Josh Berkus
 Aglio Database Solutions
 San Francisco

Josh,
    I'm sure the big brains have a better suggestion, but in the mean time
could you do something as simple as:

SELECT *
FROM (select * from events where event_date BETWEEN 'date1' AND 'date2') e
LEFT OUTER JOIN cases ON e.case_id = cases.case_id;

Thanks,
Peter Darley

-----Original Message-----
From: pgsql-performance-owner@postgresql.org
[mailto:pgsql-performance-owner@postgresql.org]On Behalf Of Josh Berkus
Sent: Wednesday, February 18, 2004 4:11 PM
To: pgsql-performance
Subject: [PERFORM] Forcing filter/join order?


Folks,

Have an interesting issue with a complex query, where apparently I need to
twist the query planner's arm, and am looking for advice on how to do so.

The situation:  I have a table, events, with about 300,000 records.
It does an outer join to a second table, cases, with about 150,000 records.

A very simplified version query would be like

SELECT *
FROM events LEFT OUTER JOIN cases ON events.case_id = cases.case_id
WHERE events.event_date BETWEEN 'date1' AND 'date2'

This join is very expensive, as you can imagine.   Yet I can't seem to force
the query planner to apply the filter conditions to the events table
*before*
attempting to join it to cases.  Here's the crucial explain lines:

                                 ->  Merge Left Join  (cost=0.00..11880.82
rows=15879 width=213) (actual time=5.777..901.899 rows=648 loops=1)
                                       Merge Cond: ("outer".case_id =
"inner".case_id)
                                       Join Filter:
(("outer".link_type)::text
= 'case'::text)
                                       ->  Index Scan using idx_event_ends
on
events  (cost=0.00..4546.15 rows=15879 width=80
) (actual time=4.144..333.769 rows=648 loops=1)
                                             Filter: ((status <> 0) AND
((event_date + duration) >= '2004-02-18 00:00:00'::timestamp without time
zone) AND (event_date <= '2004-03-05 23:59:00'::timestamp without time
zone))
                                       ->  Index Scan using cases_pkey on
cases  (cost=0.00..6802.78 rows=117478 width=137) (
actual time=0.139..402.363 rows=116835 loops=1)

As you can see, part of the problem is a pretty drastic (20x) mis-estimation
of the selectivity of the date limits on events -- and results in 90% of the
execution time of my query on this one join.  I've tried raising the
statistics on event_date, duration, and case_id (to 1000), but this doesn't
seem to affect the estimate or the query plan.

In the above test, idx_event_ends indexes (case_id, status, event_date,
(event_date + duration)), but as you can see the planner uses only the first
column.  This was an attempt to circumvent the planner's tendency to
completely ignoring any index on (event_date, (event_date + duration))  --
even though that index is the most selective combination on the events
table.

Is there anything I can do to force the query planner to filter on events
before joining cases, other than waiting for version 7.5?

--
-Josh Berkus
 Aglio Database Solutions
 San Francisco


---------------------------(end of broadcast)---------------------------
TIP 7: don't forget to increase your free space map settings

Folks,

Hmmm posted too soon.  Figured out the problem:

The planner can't, or doesn't want to, use an index on (event_date,
(event_date + duration)) where the first column is an ascending sort and the
second a descending sort.    So I've coded a workaround that's quite
inelegant but does get the correct results in 0.3 seconds (as opposed to the
2.2 seconds taken by the example plan).

Is this the sort of thing which is ever likely to get fixed, or just a
fundamental limitation of index algorithms?   Would using a non B-Tree index
allow me to work around this?

--
-Josh Berkus
 Aglio Database Solutions
 San Francisco

Peter,

>     I'm sure the big brains have a better suggestion, but in the mean time
> could you do something as simple as:
>
> SELECT *
> FROM (select * from events where event_date BETWEEN 'date1' AND 'date2') e
> LEFT OUTER JOIN cases ON e.case_id = cases.case_id;

Thanks, but that doens't work; the planner will collapse the subquery into the
main query, which most of the time is the right thing to do.

--
-Josh Berkus
 Aglio Database Solutions
 San Francisco

On Wed, 18 Feb 2004, Josh Berkus wrote:

> The planner can't, or doesn't want to, use an index on (event_date,
> (event_date + duration)) where the first column is an ascending sort and the
> second a descending sort.    So I've coded a workaround that's quite
> inelegant but does get the correct results in 0.3 seconds (as opposed to the
> 2.2 seconds taken by the example plan).

Can you give more information?  I know that I'm not exactly certain what
the situation is from the above and the original query/explain piece.

Stephan,

> Can you give more information?  I know that I'm not exactly certain what
> the situation is from the above and the original query/explain piece.
>

Believe me, if I posted the query it wouldn't help.    Heck, I'd have trouble
following it without my notes.

a simplifed version:

SELECT events.*, cases.case_name
FROM events LEFT OUTER JOIN cases ON events.case_id = cases.case_id
WHERE (event_date >= '2004-03-05' OR (event_date + duration) <= '2004-02-18')
    AND events.status <> 0;

... this is to get me all vaild events which overlap with the range
'2004-02-18' to '2004-03-05'.

I had thought, in 7.4, that adding an index on (event_date, (event_date +
duration)) would improve the execution of this query.   It doesn't,
presumably because the multi-column index can't be used for both ascending
and descending sorts at the same time, and event_date >= '2004-03-05' isn't
selective enough.

There was a workaround for this posted on hackers about a year ago as I
recally, that involved creating custom operators for indexing.  Too much
trouble when there's a hackish workaround (due to the fact that events have
to be less than a month long).

--
-Josh Berkus
 Aglio Database Solutions
 San Francisco

On Wed, 18 Feb 2004, Josh Berkus wrote:

> Stephan,
>
> > Can you give more information?  I know that I'm not exactly certain what
> > the situation is from the above and the original query/explain piece.
> >
>
> Believe me, if I posted the query it wouldn't help.    Heck, I'd have trouble
> following it without my notes.
>
> a simplifed version:
>
> SELECT events.*, cases.case_name
> FROM events LEFT OUTER JOIN cases ON events.case_id = cases.case_id
> WHERE (event_date >= '2004-03-05' OR (event_date + duration) <= '2004-02-18')
>     AND events.status <> 0;
>
> ... this is to get me all vaild events which overlap with the range
> '2004-02-18' to '2004-03-05'.
>
> I had thought, in 7.4, that adding an index on (event_date, (event_date +
> duration)) would improve the execution of this query.   It doesn't,
> presumably because the multi-column index can't be used for both ascending
> and descending sorts at the same time, and event_date >= '2004-03-05' isn't
> selective enough.

I don't think the direction issue is the problem in the above.  I think
the problem is that given a condition like:
  a>value or b<othervalue
an index on (a,b) doesn't appear to be considered probably since the
b<othervalue wouldn't be indexable by that index and you can't use the
a>value alone since that'd do the wrong thing.

Testing on a two column table, I see behavior like the following (with
seqscan off)

sszabo=# create table q2(a int, b int);
CREATE TABLE
sszabo=# create index q2ind on q2(a,b);
CREATE INDEX
sszabo=# set enable_seqscan=off;
SET
sszabo=# explain select * from q2 where a>3 and b<5;
                            QUERY PLAN
-------------------------------------------------------------------
 Index Scan using q2ind on q2  (cost=0.00..42.79 rows=112 width=8)
   Index Cond: ((a > 3) AND (b < 5))
(2 rows)

sszabo=# explain select * from q2 where a>3 or b<5;
                             QUERY PLAN
--------------------------------------------------------------------
 Seq Scan on q2  (cost=100000000.00..100000025.00 rows=556 width=8)
   Filter: ((a > 3) OR (b < 5))
(2 rows)

sszabo=# create index q2ind2 on q2(b);
CREATE INDEX
sszabo=# explain select * from q2 where a>3 or b<5;
                                QUERY PLAN
---------------------------------------------------------------------------
 Index Scan using q2ind, q2ind2 on q2  (cost=0.00..92.68 rows=556 width=8)
   Index Cond: ((a > 3) OR (b < 5))
(2 rows)

Josh Berkus <josh@agliodbs.com> writes:
> SELECT events.*, cases.case_name
> FROM events LEFT OUTER JOIN cases ON events.case_id = cases.case_id
> WHERE (event_date >= '2004-03-05' OR (event_date + duration) <= '2004-02-18')
>     AND events.status <> 0;

> ... this is to get me all vaild events which overlap with the range
> '2004-02-18' to '2004-03-05'.

Did you mean events that *don't* overlap with the range?  Seems like
what you say you want should be expressed as

event_date <= 'end-date' AND (event_date + duration) >= 'start-date'

This assumes duration is never negative of course.

I think you could make this btree-indexable by negating the second
clause.  Imagine

create index evi on events (event_date, (-(event_date+duration)))

and then transforming the query to

event_date <= 'end-date' AND -(event_date + duration) <= -'start-date'

but that doesn't quite work because there's no unary minus for date or
timestamp types.  Is this too ugly for you?

create index evi on events (event_date, ('ref-date'-event_date-duration))

event_date <= 'end-date'
AND ('ref-date'-event_date-duration) <= 'ref-date'-'start-date'

where 'ref-date' is any convenient fixed reference date, say 1-1-2000.

Now, what this will look like to the planner is a one-sided two-column
restriction, and I'm not certain that the planner will assign a
sufficiently small selectivity estimate.  But in theory it could work.

            regards, tom lane

Tom,

First off, you are correct, I swapped the dates when typing the simplified
query into e-mail.

> create index evi on events (event_date, ('ref-date'-event_date-duration))
>
> event_date <= 'end-date'
> AND ('ref-date'-event_date-duration) <= 'ref-date'-'start-date'
>
> where 'ref-date' is any convenient fixed reference date, say 1-1-2000.
>
> Now, what this will look like to the planner is a one-sided two-column
> restriction, and I'm not certain that the planner will assign a
> sufficiently small selectivity estimate.  But in theory it could work.

Interesting idea.   I'll try it just to see if it works when I have a chance.

In the meantime, for production, I'll stick with the hackish solution I was
using under 7.2.

Knowing that events are never more than one month long for this application, I
can do:

"WHERE event.event_date >= (begin_date - '1 month) AND event.event_date <=
end_date"

... which works because I have a child table which has event information by
day:

AND events.event_id IN (SELECT event_id FROM event_day
    WHERE calendar_day BETWEEN begin_date AND end_date);

Note that this subselect isn't sufficent on its own, because once again the
query planner is unable to correctly estimate the selectivity of the
subselect.   It needs the "help" of the filter against events.event_date.

This is the workaround I was using with 7.2.   I had just hoped that some of
the improvements that Tom has made over the last two versions would cure the
problem, but no dice.

--
-Josh Berkus
 Aglio Database Solutions
 San Francisco

Josh Berkus <josh@agliodbs.com> writes:
> Knowing that events are never more than one month long for this
> application, I can do:

> "WHERE event.event_date >= (begin_date - '1 month) AND event.event_date <=
> end_date"

> ... which works because I have a child table which has event information by
> day:

Uh, why do you need the child table?  Seems like the correct incantation
given an assumption about maximum duration is

event_date <= 'end-date' AND (event_date + duration) >= 'start-date'
AND event_date >= 'start-date' - 'max-duration'

The last clause is redundant with the one involving the duration field,
but it provides a lower bound for the index scan on event_date.  The
only index you really need here is one on event_date, but possibly one
on (event_date, (event_date + duration)) would be marginally faster.

            regards, tom lane

Tom,

> Uh, why do you need the child table?

Because there's linked information which needs to be kept by day for multi-day
events.   Also, it makes calendar reports easier, where one wants each day of
a multi-day event to appear on each day of the calendar.

>Seems like the correct incantation
> given an assumption about maximum duration is
>
> event_date <= 'end-date' AND (event_date + duration) >= 'start-date'
> AND event_date >= 'start-date' - 'max-duration'

Hmmmm ... so the same as what I have, only with the extra condition for
event_date+duration and without the IN clause.   I'll try it, thanks!

--
-Josh Berkus
 Aglio Database Solutions
 San Francisco

Tom,

> event_date <= 'end-date' AND (event_date + duration) >= 'start-date'
> AND event_date >= 'start-date' - 'max-duration'

Great suggestion!   We're down to 160ms, from about 370ms with my subselect
workaround.   Thanks!

--
-Josh Berkus
 Aglio Database Solutions
 San Francisco