Re: Implementing a new Join Algorithm

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

Tom> Anagh Lal <anaghlal2001(at)yahoo(dot)com> writes:
>> I am trying to test a new join algorithm by implementing it on
>> Postgresql. It would be great if you could give me some start
>> off pointers so as to where all in the source code I will have
>> to make changes.

Tom> Lots of places ;-).

Tom> You will find that a full-text indexing tool is an essential
Tom> aid for working with the Postgres source code. I am partial

I've had great success with cscope. Especially with the XEmacs
interfaces.

I think in fact the easy part is the executor stuff because it's
nicely localized. Getting the planner to choose a new option is a
little messier.

As part of the TelegraphCQ project we've implemented what smells like
a symmetric hash join. Actually it's more like an N-way symmetric hash
join. This is done using the new SteM operator which can work in a
classical iterator model plan. With the Eddy operator we can avoid
static dataflows.

Since we were a bit chary of jumping headlong into the optimizer, we
"cheated". What we do is let the postgres optimizer do its thing and
produce a plan with Hash Joins. Then we walk the plan and replace Hash
Join nodes with our new SteM nodes. We call our conversion code in
pg_exec_query_string() right after pg_plan_query()

It's more complicated than that because we're actually implementing
the Eddy operator. But if your goal is just to try out your nice new
join algorithm, this would probably work and be a quick fix to get you
started.

--
Pip-pip
Sailesh
http://www.cs.berkeley.edu/~sailesh