Re: Project proposal/comments please - query optimization

I have noticed a deficiency in the current query optimizer related to
"full outer joins". Tom Lane has confirmed to me that it will not be 8.1
material. I am not able to wait for 8.2

I am in the lucky situation that my project has money to hire
consultants, so I would be very interested in hearing about any who
feels able to work on this, with estimates to costs. The sw developed
shall be freely available and will be given back into PostgreSQL, if the
project wants it. I actually think it should be a requirement that the
sw is accepted into PostgreSQL, but I do not know how to phrase it so
that it is acceptable to all parties.

The specific problem can be illustrated with two example queries.
Query1:

SELECT x, y, av, bv
FROM at a
FULL OUTER JOIN bt b
USING (x, y)
WHERE x = 52981
AND y = '2004-1-1 0:0:0';

Query2:

SELECT x, y, av, bv
FROM
(SELECT x, y, av
FROM at
WHERE x = 52981 AND y = '2004-1-1 0:0:0') a
FULL OUTER JOIN
(SELECT x, y, bv
FROM bt
WHERE x = 52981 AND y = '2004-1-1 0:0:0') b
USING (x, y);

Both queries select the same set of data (one record), but query2 is
able to use the indexes in doing so. By looking at the "explain analyze"
output it is clear that this is because the current PostgreSQL query
optimizer is not able to push the conditions (x = 52981 AND y =
'2004-1-1 0:0:0') down into the sub-queries, thus forcing the fetching
of all data from the tables, and then lastly filtering out the few
records (zero to one row from each table).

The reason why I say it is related to "full outer joins" it that if I
take Query1 and substitute "full" with "left", the optimizer is capable
of pushing the conditions out in the sub-selects, and is thus able to
use indices.

Looking forward for any comments. I am aware that there are workarounds
(like query2, union of two left-joins, hand coding the join from a
series of simple selects, ...) but I do not feel they are practical for
my use.

Regards,

--
Kim Bisgaard

Computer Department Phone: +45 3915 7562 (direct)
Danish Meteorological Institute Fax: +45 3915 7460 (division)

Kim Bisgaard <kib+pg(at)dmi(dot)dk> writes:
> I have noticed a deficiency in the current query optimizer related to
> "full outer joins". Tom Lane has confirmed to me that it will not be 8.1
> material.

The particular case you are complaining of is fixed in CVS tip. There
are related issues involving N-way joins that we're still not very
good at.

regression=# create table at (x int, y timestamp, av text);
CREATE TABLE
regression=# create table bt (x int, y timestamp, bv text);
CREATE TABLE
regression=# create index ati on at(x,y);
CREATE INDEX
regression=# create index bti on bt(x,y);
CREATE INDEX
regression=# explain SELECT x, y, av, bv FROM at a FULL OUTER JOIN bt b USING (x, y) WHERE x = 52981 AND y = '2004-1-1 0:0:0';
QUERY PLAN
------------------------------------------------------------------------------------------------
Merge Full Join (cost=0.00..9.66 rows=1 width=88)
-> Index Scan using ati on "at" a (cost=0.00..4.83 rows=1 width=44)
Index Cond: ((x = 52981) AND (y = '2004-01-01 00:00:00'::timestamp without time zone))
-> Index Scan using bti on bt b (cost=0.00..4.83 rows=1 width=44)
Index Cond: ((x = 52981) AND (y = '2004-01-01 00:00:00'::timestamp without time zone))
(5 rows)

regression=#

This only works for WHERE clauses that equate join alias variables to
pseudoconstants. I have this in my notes:

Consider this version of Kim Bisgaard's example:
SELECT FROM a join (b full join c using (id)) using (id)
If A is small and B,C have indexes on ID then it is interesting to consider
a plan like
Nest Loop
Scan A
Merge Full Join
Indexscan B using id = outer.id
Indexscan C using id = outer.id
We are fairly far from being able to do this. generate_outer_join_implications
could easily be modified to generate derived equalities (I think it works to
allow a deduction against any clause not overlapping the outerjoin itself)
but the planner would want to evaluate them at the wrong level, and the
executor doesn't have support for passing the outer variable down more than
one level of join. This is why the existing hack works only for equalities
to pseudoconstants. We could maybe mark join RestrictInfos as "valid only
below xxx" and ignore them when processing a join that includes all of the
indicated rels? Still not clear how you get the planner to recognize the
above as an inner indexscan situation though.

regards, tom lane

Tom Lane wrote:

>Kim Bisgaard <kib+pg(at)dmi(dot)dk> writes:
>
>
>>I have noticed a deficiency in the current query optimizer related to
>>"full outer joins". Tom Lane has confirmed to me that it will not be 8.1
>>material.
>>
>>
>
>... There
>are related issues involving N-way joins that we're still not very
>good at.
>...
>
>Consider this version of Kim Bisgaard's example:
> SELECT FROM a join (b full join c using (id)) using (id)
>If A is small and B,C have indexes on ID then it is interesting to consider
>a plan like
> Nest Loop
> Scan A
> Merge Full Join
> Indexscan B using id = outer.id
> Indexscan C using id = outer.id
>We are fairly far from being able to do this. generate_outer_join_implications
>could easily be modified to generate derived equalities (I think it works to
>allow a deduction against any clause not overlapping the outerjoin itself)
>but the planner would want to evaluate them at the wrong level, and the
>executor doesn't have support for passing the outer variable down more than
>one level of join. This is why the existing hack works only for equalities
>to pseudoconstants. We could maybe mark join RestrictInfos as "valid only
>below xxx" and ignore them when processing a join that includes all of the
>indicated rels? Still not clear how you get the planner to recognize the
>above as an inner indexscan situation though.
>
The query samples I gave was the smallest test I could find to provoke
the behavior. Tom is right in that the full case I am ideally want
solved is of the form above with lots (below 20) of full outer joined
tables.

I am still a little intrigued by the effect of substituting "full" with
"left" in my examples; maybe an alternative to Toms idea could be to
work in the direction of treating "full" more like "left/right"

There are some examples of my problems (on nightly builds of yesterday)
at the bottom of the mail.

Regards,
Kim.

obsdb=> explain analyse select wmo_id,timeobs,temp_dry_at_2m,temp_grass
from station
join (temp_grass
full join temp_dry_at_2m using (station_id, timeobs)
) using (station_id)
where wmo_id=6065 and '2004-1-2 6:0' between startdate and enddate
and timeobs = '2004-1-2 06:0:0';

QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Hash Join (cost=5.04..372928.92 rows=1349 width=28) (actual
time=23986.480..46301.966 rows=1 loops=1)
Hash Cond: (COALESCE("outer".station_id, "outer".station_id) =
"inner".station_id)
-> Merge Full Join (cost=0.00..338124.90 rows=6957100 width=32)
(actual time=23965.761..46281.380 rows=76 loops=1)
Merge Cond: (("outer".timeobs = "inner".timeobs) AND
("outer".station_id = "inner".station_id))
Filter: (COALESCE("outer".timeobs, "inner".timeobs) =
'2004-01-02 06:00:00'::timestamp without time zone)
-> Index Scan using temp_grass_idx on temp_grass
(cost=0.00..75312.59 rows=2406292 width=16) (actual
time=12.436..4916.043 rows=2406292 loops=1)
-> Index Scan using temp_dry_at_2m_idx on temp_dry_at_2m
(cost=0.00..210390.85 rows=6957100 width=16) (actual
time=13.696..21363.054 rows=6956994 loops=1)
-> Hash (cost=5.03..5.03 rows=1 width=8) (actual
time=19.612..19.612 rows=0 loops=1)
-> Index Scan using wmo_idx on station (cost=0.00..5.03
rows=1 width=8) (actual time=19.586..19.591 rows=1 loops=1)
Index Cond: ((wmo_id = 6065) AND ('2004-01-02
06:00:00'::timestamp without time zone >= startdate) AND ('2004-01-02
06:00:00'::timestamp without time zone <= enddate))
Total runtime: 46302.208 ms
(11 rows)

obsdb=> explain analyse select
wmo_id,timeobs,wind_dir_10m,temp_dry_at_2m,temp_grass
from station
join (temp_grass
full join temp_dry_at_2m using (station_id, timeobs)
full join wind_dir_10m using (station_id, timeobs)
) using (station_id)
where wmo_id=6065 and '2004-1-2 6:0' between startdate and enddate
and timeobs = '2004-1-2 06:0:0';

QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Hash Join (cost=1249443.54..1700082.70 rows=1392 width=40) (actual
time=331437.803..384389.174 rows=1 loops=1)
Hash Cond: (COALESCE(COALESCE("outer".station_id,
"outer".station_id), "outer".station_id) = "inner".station_id)
-> Merge Full Join (cost=1249438.51..1664170.44 rows=7178660
width=48) (actual time=291406.613..384359.322 rows=82 loops=1)
Merge Cond: (("outer".station_id = "inner"."?column7?") AND
("outer".timeobs = "inner"."?column8?"))
Filter: (COALESCE("inner"."?column8?", "outer".timeobs) =
'2004-01-02 06:00:00'::timestamp without time zone)
-> Index Scan using wind_dir_10m_idx on wind_dir_10m
(cost=0.00..299534.38 rows=7178660 width=16) (actual
time=15.194..52605.785 rows=7178639 loops=1)
-> Sort (cost=1249438.51..1266831.26 rows=6957100 width=32)
(actual time=290255.163..302211.520 rows=8743745 loops=1)
Sort Key: COALESCE(temp_grass.station_id,
temp_dry_at_2m.station_id), COALESCE(temp_grass.timeobs,
temp_dry_at_2m.timeobs)
-> Merge Full Join (cost=0.00..337004.00 rows=6957100
width=32) (actual time=28.909..73512.533 rows=8743745 loops=1)
Merge Cond: (("outer".timeobs = "inner".timeobs)
AND ("outer".station_id = "inner".station_id))
-> Index Scan using temp_grass_idx on temp_grass
(cost=0.00..75312.59 rows=2406292 width=16) (actual
time=15.178..6088.732 rows=2406292 loops=1)
-> Index Scan using temp_dry_at_2m_idx on
temp_dry_at_2m (cost=0.00..210390.85 rows=6957100 width=16) (actual
time=13.694..25573.509 rows=6956994 loops=1)
-> Hash (cost=5.03..5.03 rows=1 width=8) (actual
time=28.609..28.609 rows=0 loops=1)
-> Index Scan using wmo_idx on station (cost=0.00..5.03
rows=1 width=8) (actual time=28.581..28.585 rows=1 loops=1)
Index Cond: ((wmo_id = 6065) AND ('2004-01-02
06:00:00'::timestamp without time zone >= startdate) AND ('2004-01-02
06:00:00'::timestamp without time zone <= enddate))
Total runtime: 384979.287 ms
(16 rows)