Re: [HACKERS] WIP: BRIN bloom indexes - Mailing list pgsql-hackers

On Fri, Oct 27, 2017 at 10:06:58PM +0200, Tomas Vondra wrote:
> > + * We use an optimisation that initially we store the uint32 values directly,
> > + * without the extra hashing step. And only later filling the bitmap space,
> > + * we switch to the regular bloom filter mode.
> > 
> > I don't think that optimization is worthwhile.  If I'm going to be using
> > a Bloom filter, it's because I expect to have a lot of rows.
> > 
> > (Granted, if I CREATE TABLE .. LIKE .. INCLUDING INDEXES, and the new
> > table just won't have lots of rows, then I might want this optimization,
> > but I can always just drop the Bloom filter index, or not include
> > indexes in the LIKE.)
> 
> I think you're confusing "rows" and "distinct values". Furthermore, it's
> rather irrelevant how many rows are in the table because BRIN indexes
> split the table into "ranges" that are 1MB by default. And you can only
> squash certain number of rows into such range.
> 
> The idea of the optimization is to efficiently support cases where each
> range contains only small number of distinct values - which is quite
> common in the cases I described in my initial message (with bursts of
> rows with the same IP / client identifier etc.).

What range?  It's just bits to set.

The point is that Bloom filters should ideally be about 50% full -- much
less than that and you are wasting space, much more than than and your
false positive rate becomes useless.

> > Filter compression is not worthwhile.  You want to have a fairly uniform
> > hash distribution, and you want to end up with a Bloom filter that's not
> > much more than 50% full.  That means that when near 50% full the filter
> > will not be very sparse at all.  Optimizing for the not common case
> > doesn't seem worthwhile, and adds complexity.
> 
> Properly sizing the bloom filter requires knowledge of many variables,
> in particular the number of distinct values expected to be added to the
> filter. But we don't really know that number, and we also don't even
> know many values useful for estimating that (how many rows will fit into
> a range, number of distinct values in the whole table, etc.)

This is why Scalable Bloom filters exist: so you can adapt.

> So the idea was to oversize the bloom filter, and then use the sparse
> representation to reduce the size.

A space-efficient representation of sparse bitmaps is not as simple as a
Scalable Bloom filter.

And a filter that requires user intervention to size correctly, or which
requires rebuilding when it gets too full, is also not as convenient as
a Scalable Bloom filter.

> > + * XXX We can also watch the number of bits set in the bloom filter, and
> > + * then stop using it (and not store the bitmap, to save space) when the
> > + * false positive rate gets too high.
> > 
> > Ah, right, what you want is a "Scalable Bloom Filter".
> 
> That's not what I had in mind. My idea was to size the bloom filter on
> "best effort" basis, and then if one range gets a bit too inaccurate
> then just get rid of the filter. If that happens for many ranges, we
> should probably allow specifying parameters as relopts for the index.

Scalable Bloom filters are way more convenient than that.  They're
always not-too-full, and only the open filter is less-than-full-enough.

And since you should grow them somewhat exponentially (but not quite as
much as a doubling in each generation), there should never be too many
filters to search.  But you can always "vacuum" (rebuild) the filter
starting with the size of the last filter added prior to the vacuum.

> I think this is really an over-engineering, and I certainly don't plan
> to extend the patch in this direction.

Whereas I think a sparse bitmap representation is overly complex and
"over-engineering".  Scalable Bloom filters are very well understood in
the literature -- there's nothing terribly complex to them.

> I do not expect these parameters (particularly the number of distinct
> values in a range) to significantly change over time, so the easiest
> solution is to provide a reloption to specify that number in
> CREATE/ALTER index.

Doesn't this depend on the use-case though?  I think a self-tuning
system is better than one that doesn't self-tune.  Call that
over-engineering if you like, but it doesn't make it not desirable :)

> Alternatively, we could allow the summarization process to gather some
> statistics (either on the whole range, or perhaps the whole table), and
> store them somewhere for later use. For example to compute the number of
> distinct values per range (in the existing data), and use that later.

Again, Scalable Bloom filters automatically adapt without needing a
statistics gathering exercise.  All you need is a good hash function
(that's another topic).

Scalable Bloom filters are a trivial extension of Bloom filters.

> > What I'm getting at is that the query planner really needs to understand
> > that a Bloom filter is a probabilistic data structure.
> 
> It does, and we never produce incorrect results. Which seems like the
> right thing to do.

OK, I saw your other response about this.  I didn't know that PG already
has support for probabilistic indexes.

Nico
-- 


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers