From: Mark Kirkwood <markir@paradise.net.nz>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Simon Riggs <simon@2ndquadrant.com>
Cc: Bruce Momjian <pgman@candle.pha.pa.us>
Cc: Pål Stenslet <paal.stenslet@exie.com>
Cc: pgsql-performance@postgresql.org
Subject: Re: Should Oracle outperform PostgreSQL on a complex
Date: Sun, 18 Dec 2005 15:02:48 +1300
Message-ID: <43A4C348.7050703@paradise.net.nz> (raw)
In-Reply-To: <8627.1134843222@sss.pgh.pa.us>
References: <200512170428.jBH4S2W23715@candle.pha.pa.us>
<1134810953.2964.117.camel@localhost.localdomain>
<8627.1134843222@sss.pgh.pa.us>
Tom Lane wrote:
> Simon Riggs <simon@2ndquadrant.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)
>
> This involves only one scan of the fact table. As each row is pulled up
> through the nest of hash joins, we hash one dimension key and join to
> one small table at each level. This is at worst the same amount of work
> as hashing all the keys at once and probing a single cartesian-product
> hashtable, probably less work (fewer wasted key-comparisons). And
> definitely less memory. You do have to keep your eye on the ball that
> you don't waste a lot of overhead propagating the row up through
> multiple join levels, but we got rid of most of the problem there in
> 8.1 via the introduction of "virtual tuple slots". If this isn't fast
> enough yet, it'd make more sense to invest effort in further cutting the
> executor's join overhead (which of course benefits *all* plan types)
> than in trying to make the planner choose a star join.
>
>
>>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"?
Yeah - the quoted method of "make a cartesian product of the dimensions
and then join to the fact all at once" is not actually used (as written)
in many implementations - probably for the reasons you are pointing out.
I found these two papers whilst browsing:
http://www.cs.brown.edu/courses/cs227/Papers/Indexing/O'NeilGraefe.pdfhttp://www.dama.upc.edu/downloads/jaguilar-2005-4.pdf
They seem to be describing a more subtle method making use of join
indexes and bitmapped indexes.
If I understand it correctly, the idea is to successively build up a
list (hash / bitmap) of fact RIDS that will satisfy the query, and when
complete actually perform the join and construct tuples. The goal being
similar in intent to the star join method (i.e. access the fact table
as little and as "late" as possible), but avoiding the cost of actually
constructing the dimension cartesian product.
cheers
Mark
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: markir@paradise.net.nz, tgl@sss.pgh.pa.us, simon@2ndquadrant.com, pgman@candle.pha.pa.us, paal.stenslet@exie.com
Subject: Re: Should Oracle outperform PostgreSQL on a complex
In-Reply-To: <43A4C348.7050703@paradise.net.nz>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox