Re: Should Oracle outperform PostgreSQL on a complex

Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:

> Simon Riggs <simon(at)2ndquadrant(dot)com> writes:
> > On Fri, 2005-12-16 at 23:28 -0500, Bruce Momjian wrote:
> >> How are star joins different from what we do now?
>
> > Methods:
> > 1. join all N small tables together in a cartesian product, then join to
> > main Large table once (rather than N times)
>
> Of course, the reason the current planner does not think of this is that
> it does not consider clauseless joins unless there is no alternative.
>
> However, I submit that it wouldn't pick such a plan anyway, and should
> not, because the idea is utterly stupid. The plan you currently get for
> this sort of scenario is typically a nest of hash joins:
>
> QUERY PLAN
> ------------------------------------------------------------------------
> Hash Join (cost=2.25..4652.25 rows=102400 width=16)
> Hash Cond: ("outer".f1 = "inner".f1)
> -> Hash Join (cost=1.12..3115.12 rows=102400 width=12)
> Hash Cond: ("outer".f2 = "inner".f1)
> -> Seq Scan on fact (cost=0.00..1578.00 rows=102400 width=8)
> -> Hash (cost=1.10..1.10 rows=10 width=4)
> -> Seq Scan on d2 (cost=0.00..1.10 rows=10 width=4)
> -> Hash (cost=1.10..1.10 rows=10 width=4)
> -> Seq Scan on d1 (cost=0.00..1.10 rows=10 width=4)
> (9 rows)

I realize DSS systems often expect to run queries using sequential scans but
perhaps the point of this particular plan is to exploit indexes? (I think
particularly bitmap indexes but ...)

So in this case, you would expect an index scan of d1 to pull out just the
records that d1 says should be included, and an index scan of d2 to pull out
just the records that d2 says should be included, then finally a nested loop
index lookup of f1 for the primary keys that show up in both the d1 scan and
the d2 scan.

So in the following it would be nice if the index scan on f didn't have to
appear until *after* all the hashes were checked for the dimenions, not after
only one of them. This would be even nicer if instead of hashes a bitmap data
structure could be built and bitmap operations used to do the joins, since no
other columns from these dimension tables need to be preserved to be included
in the select list.

It would be even better if there were an on-disk representation of these
bitmap data structures but I don't see how to do that with MVCC at all.

slo=> explain select * from fact as f where fact_id in (select fact_id from d d1 where dim_id = 4) and fact_id in (select fact_id from d d2 where dim_id = 29) and fact_id in (select fact_id from d d3 where dim_id = 57);
QUERY PLAN
------------------------------------------------------------------------------------------------
Hash IN Join (cost=15.77..21.86 rows=1 width=110)
Hash Cond: ("outer".fact_id = "inner".fact_id)
-> Hash IN Join (cost=10.51..16.59 rows=1 width=118)
Hash Cond: ("outer".fact_id = "inner".fact_id)
-> Nested Loop (cost=5.26..11.31 rows=2 width=114)
-> HashAggregate (cost=5.26..5.26 rows=2 width=4)
-> Index Scan using di on d d2 (cost=0.00..5.25 rows=3 width=4)
Index Cond: (dim_id = 29)
-> Index Scan using fact_pkey on fact f (cost=0.00..3.01 rows=1 width=110)
Index Cond: (f.fact_id = "outer".fact_id)
-> Hash (cost=5.25..5.25 rows=3 width=4)
-> Index Scan using di on d d1 (cost=0.00..5.25 rows=3 width=4)
Index Cond: (dim_id = 4)
-> Hash (cost=5.25..5.25 rows=3 width=4)
-> Index Scan using di on d d3 (cost=0.00..5.25 rows=3 width=4)
Index Cond: (dim_id = 57)
(16 rows)

> > 2. transform joins into subselects, then return subselect rows via an
> > index bitmap. Joins are performed via a bitmap addition process.
>
> This one might be interesting but it's not clear what you are talking
> about. "Bitmap addition"?

Well "transform joins into subselects" is a red herring. Joins and subselects
are two ways of spelling special cases of the same thing and internally they
ought to go through the same codepaths. They don't in Postgres but judging by
the plans it produces I believe they do at least in a lot of cases in Oracle.

That's sort of the whole point of the phrase "star join". What the user really
wants is a single table joined to a bunch of small tables. There's no way to
write that in SQL due to the limitations of the language but a bunch of
subqueries expresses precisely the same concept (albeit with another set of
language limitations which luckily don't impact this particular application).

--
greg