From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: David Rowley <david.rowley@2ndquadrant.com>
Cc: Shulgin, Oleksandr <oleksandr.shulgin@zalando.de>
Cc: PostgreSQL Hackers <pgsql-hackers@postgresql.org>
Subject: Re: WIP: bloom filter in Hash Joins with batches
Date: Mon, 28 Dec 2015 11:44:15 +0100
Message-ID: <5681127F.9080301@2ndquadrant.com> (raw)
In-Reply-To: <CAKJS1f_aefsMQ0REQELgCysm=oLBryOO1S_YVSZq-mfixUYHxw@mail.gmail.com>
References: <5670946E.8070705@2ndquadrant.com>
<CACACo5Q0z9vQE8pHc+b6rzHr_TOTNg4=nc4eiQodtD1poOBCCQ@mail.gmail.com>
<5672D617.9060601@2ndquadrant.com>
<CAKJS1f8qTxf2nqFLQ-koXeUWNxJX0b63ceaRcDz-F68hNzy9dA@mail.gmail.com>
<56810D8C.3020309@2ndquadrant.com>
<CAKJS1f_aefsMQ0REQELgCysm=oLBryOO1S_YVSZq-mfixUYHxw@mail.gmail.com>
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-hackers>
On 12/28/2015 11:38 AM, David Rowley wrote:
> On 28 December 2015 at 23:23, Tomas Vondra <tomas.vondra@2ndquadrant.com
> <mailto:tomas.vondra@2ndquadrant.com>> wrote:
>
> On 12/28/2015 03:15 AM, David Rowley wrote:
>
> Maybe it would be better to, once the filter is built, simply
> count the
>
> number of 1 bits and only use the filter if there's less than
> <threshold> 1 bits compared to the size of the filter in bits.
> There's
> functionality in bms_num_members() to do this, and there's
> also __builtin_popcount() in newer version of GCC, which we
> could have
> some wrapper around, perhaps.
>
>
> I don't really see how this is relevant with the previous point. The
> number of 1s in the bitmap can tell you the false positive rate for
> the bloom filter, not what fraction of lookups will be answered with
> "true".
>
> So while this needs to be watched, so that we stop using the bloom
> filter when it gets too full (e.g. due to under-estimate), it's
> completely unrelated to the previous issue.
>
>
> Why is it not related? this has got me confused. If a bloom filter has
> all of the bits set to 1, then it will never filter any Tuples right?
Because the false positive rate can be computed without having to look
at the lookups. So it's inherently independent on the ordering of outer
relation, and so on.
> If so, then a filter with all 1 bits set should be thrown away, as
> it'll never help us, and the filter should generally become more
> worthwhile as it contains a higher ratio of 0 bits vs 1 bits. Of
> course we don't have a count of how many Tuples matched each bit, so
> this is based on the assumption that each bit matches an equal number
> of Tuples. Are you saying this is not an assumption that we should
> make?
Sure we should check that. All I'm saying is it has nothing to do with
the first problem described in the first part of the e-mail.
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
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-hackers@postgresql.org
Cc: tomas.vondra@2ndquadrant.com, david.rowley@2ndquadrant.com, oleksandr.shulgin@zalando.de
Subject: Re: WIP: bloom filter in Hash Joins with batches
In-Reply-To: <5681127F.9080301@2ndquadrant.com>
* 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