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

WIP: Hash Join-Filter Pruning using Bloom Filters

From: "Jonah H(dot) Harris" <jonah(dot)harris(at)gmail(dot)com>
To: "Pg Hackers" <pgsql-hackers(at)postgresql(dot)org>
Subject: WIP: Hash Join-Filter Pruning using Bloom Filters
Date: 2008-11-02 21:49:24
Message-ID: 36e682920811021349h7202bdecpd7a45c8a8038465e@mail.gmail.com (view raw or flat)
Thread:
Lists: pgsql-hackers
All,

Attached is an initial patch I've been playing with which uses Bloom
filters to reduce unnecessary processing of outer tuples in hash
joins.  In short, this works by creating a Bloom filter, adding all
relevant tuples for the inner relation, and querying the filter (for
existence) when retrieving tuples from the outer relation.  This
avoids unnecessary tuple movement and bucket searches for matches we
already know can't exist.  Currently it works only for JOIN_INNER, but
could be modified to optimize anti/semi joins as well.  Similarly, I
created a GUC to enable pruning, named bloom_pruning.

Rather than performing k hash functions, this implementation simply
sets a bit based on the already-computed hash value.  I wanted to send
this around for reviews and comments before working on it further.  As
this isn't overly intrusive, if someone can commit to reviewing and
providing input, I'll commit to having this ready for 8.4.

-- 
Jonah H. Harris, Senior DBA
myYearbook.com

Attachment: bloompruning_v1.patch
Description: application/octet-stream (9.3 KB)

Responses

pgsql-hackers by date

Next:From: Hannes EderDate: 2008-11-02 22:36:53
Subject: Re: WIP: Hash Join-Filter Pruning using Bloom Filters
Previous:From: Tom LaneDate: 2008-11-02 21:27:19
Subject: Re: don't use MAKE_PTR/OFFSET for shmem pointers

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