Skip site navigation (1) Skip section navigation (2)

New style of hash join proposal

From: Gregory Stark <stark(at)enterprisedb(dot)com>
To: pgsql-hackers list <pgsql-hackers(at)postgresql(dot)org>
Subject: New style of hash join proposal
Date: 2007-12-13 13:13:33
Message-ID: 87y7by4u0y.fsf@oxford.xeocode.com (view raw or flat)
Thread:
Lists: pgsql-hackers

We currently execute a lot of joins as Nested Loops which would be more
efficient if we could batch together all the outer keys and execute a single
inner bitmap index scan for all of them together.

Essentially what I'm saying is that we're missing a trick with Hash Joins
which currently require that we can execute the inner side once without any
parameters from the outer side.

Instead what we could do is build up the hash table, then scan the hash table
building up an array of keys and pass them as a parameter to the inner side.
The inner side could do a bitmap index scan to fetch them all at once and
start returning them just as normal to the hash join.

There are a couple details:

1) Batched hash joins. Actually I think this would be fairly straightforward.
   You want to rescan the inner side once for each batch. That would actually
   be easier than what we currently do with saving tuples to files and all
   that.

2) How to pass the keys. This could be a bit tricky especially for
   multi-column keys. My first thought was to build up an actually Array node
   but that only really works for single-column keys I think. Besides it would
   be more efficient to somehow arrange to pass over a reference to the whole
   hash.

I fear the real complexity would be (as always) in the planner rather than the
executor. I haven't really looked into what it would take to arrange this or
how to decide when to do it.

-- 
  Gregory Stark
  EnterpriseDB          http://www.enterprisedb.com
  Ask me about EnterpriseDB's RemoteDBA services!

Responses

pgsql-hackers by date

Next:From: Alvaro HerreraDate: 2007-12-13 13:18:04
Subject: Re: Slow PITR restore
Previous:From: Alvaro HerreraDate: 2007-12-13 12:55:33
Subject: Re: pgwin32_open returning EINVAL

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group