Re: [HACKERS] WIP: BRIN bloom indexes

[Tomas Vondra]

hi,

On 10/28/2017 02:41 AM, Nico Williams wrote:
> 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.

The range defined by BRIN indexes. BRIN indexes split the table into a
sequence of page ranges (128 pages by default, i.e. 1MB), and the bloom
filters are built on those table "chunks". So it's irrelevant how many
rows are in the table in total, what matters is just the page range.

> 
>>> 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.
> 

Maybe. For now I'm fine with the simple relopts-based approach and don't
plan to spend much time on these improvements. Which is not to say that
they may not be worthwhile, but it's not the only thing I'm working on.

I also suspect there are practical implications, as some things are only
possible with equally-sized bloom filters. I believe the "union"
(missing in the current patch) will rely on that when merging bloom filters.

>>> + * 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.
> 

That "sparse bitmap" is mentioned merely in an XXX comment as a thing to
consider, not something I plan to work right now. Perhaps it's not
really a good idea in general, or maybe it's addressing a non-issue. In
which case we don't need scalable bloom 

Re: [HACKERS] WIP: BRIN bloom indexes

[Nico Williams]

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 

Re: [HACKERS] WIP: BRIN bloom indexes

[Tomas Vondra]

Hi,

On 10/27/2017 05:22 PM, Sokolov Yura wrote:
> 
> Hi, Tomas
> 
> BRIN bloom index is a really cool feature, that definitely should be in
> core distribution (either in contrib or builtin)!!!
> 
> Small suggestion for algorithm:
> 
> It is well known practice not to calculate whole hash function for every
> point, but use double hashing approach.
> Example of proving double hashing approach for bloom filters:
> https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf
> 
> So, instead of:
> for (i = 0; i < filter->nhashes; i++)
> {
>     /* compute the hashes with a seed, used for the bloom filter */
>     uint32 h = ((uint32)DatumGetInt64(hash_uint32_extended(value,
> i))) % filter->nbits;
> 
>     /* set or check bit h */
> }
> 
> such construction could be used:
> /* compute the hashes, used for the bloom filter */
> uint32 big_h = ((uint32)DatumGetInt64(hash_uint32_extended(value, i)));
> uint32 h = big_h % filter->nbits;
> /* ensures d is never >= filter->nbits */
> uint32 d = big_h % (filter->nbits - 1);
> 
> for (i = 0; i < filter->nhashes; i++)
> {
>     /* set or check bit h */
> 
>     /* compute next bit h */
>     h += d++;
>     if (h >= filter->nbits) h -= filter->nbits;
>     if (d == filter->nbits) d = 0;
> }
> 
> Modulo of one 64bit result by two coprime numbers (`nbits` and `nbits-1`)
> gives two good-quality functions usable for double hashing.
> 

OK, thanks for the suggestion.


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

Re: [HACKERS] WIP: BRIN bloom indexes

[Tomas Vondra]

Hi,

On 10/27/2017 07:17 PM, Nico Williams wrote:
> On Thu, Oct 19, 2017 at 10:15:32PM +0200, Tomas Vondra wrote:
> 
> A bloom filter index would, indeed, be wonderful.
> 
> Comments:
> 
> + * 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.).

> + * XXX Perhaps we could save a few bytes by using different data types, but
> + * considering the size of the bitmap, the difference is negligible.
> 
> A bytea is all that's needed.  See below.
> 
> + * XXX We could also implement "sparse" bloom filters, keeping only the
> + * bytes that are not entirely 0. That might make the "sorted" phase
> + * mostly unnecessary.
> 
> 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.)

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

> + * 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.

> A Scalable Bloom filter is actually a series of Bloom filters where all
> but the newest filter are closed to additions, and the newest filter is
> where you do all the additions.  You generally want to make each new
> filter bigger than the preceding one because when searching a Scalable
> Bloom filter you have to search *all* of them, so you want to minimize
> the number of filters.
> 
> Eventually, when you have enough sub-filters, you may want to re-write
> the whole thing so that you start with a single sub-filter that is large
> enough.
> 
> The format of the bytea might then be something like:
> 
> [[[...]]
> 
> where the last bitmap is the filter that is open to additions.
>

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

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.

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.

> ...
> 
> Of course, for something like:
> 
>   SELECT a.*, b.* FROM a a JOIN b b USING (some_col);
> 
> a Bloom filter can only be used as an optimization to avoid using a
> slower index (or heap scan) on the inner table source.
> 
> 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.

regards

-- 
Tomas Vondra  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services


-- 
Sent via pgsql-hackers mailing list 

Re: [HACKERS] WIP: BRIN bloom indexes

[Sokolov Yura]

On 2017-10-27 20:17, Nico Williams wrote:

On Thu, Oct 19, 2017 at 10:15:32PM +0200, Tomas Vondra wrote:

A bloom filter index would, indeed, be wonderful.

Comments:

+ * 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.)

+ * XXX Perhaps we could save a few bytes by using different data 
types, but

+ * considering the size of the bitmap, the difference is negligible.

A bytea is all that's needed.  See below.

+ * XXX We could also implement "sparse" bloom filters, keeping only 
the

+ * bytes that are not entirely 0. That might make the "sorted" phase
+ * mostly unnecessary.

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.

+ * 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".

A Scalable Bloom filter is actually a series of Bloom filters where all
but the newest filter are closed to additions, and the newest filter is
where you do all the additions.  You generally want to make each new
filter bigger than the preceding one because when searching a Scalable
Bloom filter you have to search *all* of them, so you want to minimize
the number of filters.

Eventually, when you have enough sub-filters, you may want to re-write
the whole thing so that you start with a single sub-filter that is 
large

enough.

The format of the bytea might then be something like:

[[[...]]

where the last bitmap is the filter that is open to additions.

I wonder if there are write concurrency performance considerations
here...

It might be better to have a bytea value per-sub-filter so that there 
is

no lock contention for the closed filters.  The closed sub-filters are
constant, thus not even shared locks are needed for them, and 
especially

not exclusive locks.

Writing to the filter will necessitate locking the entire open filter,
or else byte-range locking on it.  Something to think about.


Now, what about query performance? Unlike the "minmax" indexes, the
"bloom" filter can only handle equality conditions.


A Bloom filter has non-zero false positives for existence, but zero
false positives for non-existence.

This means that a Bloom filter index can only be used for:

a) non-existence tests (with equality predicates, as you point out),

b) as an optimization to avoid slower index checks (or heap scans) when
   the Bloom filter indicates non-existence.

(b) is really just an internal application of (a).

There might be applications where false positives might be ok in a 
query

like:

  SELECT a.* FROM a a JOIN b b USING (some_col);

but for most real-world queries like that, allowing false positives by
default would be very bad.  An option in the index declaration could be
used to enable existence equality predicates, but I would not include
such an option initially -- let's see if anyone actually has a use case
for it first.

Of course, for something like:

  SELECT a.*, b.* FROM a a JOIN b b USING (some_col);

a Bloom filter can only be used as an optimization to avoid using a
slower index (or heap scan) on the inner table source.

What I'm getting at is that the query planner really needs to 
understand

that a Bloom filter is a probabilistic data structure.

Nico
--


PostgreSQL has a lot of probabilistic indexes.

Some GIST opclasses returns false positives and tells to executor to
recheck their results.
Bitmap-index-scan, when there are a lot of result tuples, falls back to
storing only page numbers, without actual tid's, and executer then scans
heap-pages to find necessary tuples.

BRIN index at all just "recommends executor to scan that heap page". 
Thus
BRIN index is at whole just an optimisation (regardless is it `minmax` 
or

`bloom`).
So that is ok.

--
Sokolov Yura
Postgres Professional: https://postgrespro.ru
The Russian Postgres Company


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

Re: [HACKERS] WIP: BRIN bloom indexes

[Nico Williams]

On Thu, Oct 19, 2017 at 10:15:32PM +0200, Tomas Vondra wrote:

A bloom filter index would, indeed, be wonderful.

Comments:

+ * 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.)

+ * XXX Perhaps we could save a few bytes by using different data types, but
+ * considering the size of the bitmap, the difference is negligible.

A bytea is all that's needed.  See below.

+ * XXX We could also implement "sparse" bloom filters, keeping only the
+ * bytes that are not entirely 0. That might make the "sorted" phase
+ * mostly unnecessary.

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.

+ * 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".

A Scalable Bloom filter is actually a series of Bloom filters where all
but the newest filter are closed to additions, and the newest filter is
where you do all the additions.  You generally want to make each new
filter bigger than the preceding one because when searching a Scalable
Bloom filter you have to search *all* of them, so you want to minimize
the number of filters.

Eventually, when you have enough sub-filters, you may want to re-write
the whole thing so that you start with a single sub-filter that is large
enough.

The format of the bytea might then be something like:

[[[...]]

where the last bitmap is the filter that is open to additions.

I wonder if there are write concurrency performance considerations
here...

It might be better to have a bytea value per-sub-filter so that there is
no lock contention for the closed filters.  The closed sub-filters are
constant, thus not even shared locks are needed for them, and especially
not exclusive locks.

Writing to the filter will necessitate locking the entire open filter,
or else byte-range locking on it.  Something to think about.

> Now, what about query performance? Unlike the "minmax" indexes, the
> "bloom" filter can only handle equality conditions.

A Bloom filter has non-zero false positives for existence, but zero
false positives for non-existence.

This means that a Bloom filter index can only be used for:

a) non-existence tests (with equality predicates, as you point out),

b) as an optimization to avoid slower index checks (or heap scans) when
   the Bloom filter indicates non-existence.

(b) is really just an internal application of (a).

There might be applications where false positives might be ok in a query
like:

  SELECT a.* FROM a a JOIN b b USING (some_col);

but for most real-world queries like that, allowing false positives by
default would be very bad.  An option in the index declaration could be
used to enable existence equality predicates, but I would not include
such an option initially -- let's see if anyone actually has a use case
for it first.

Of course, for something like:

  SELECT a.*, b.* FROM a a JOIN b b USING (some_col);

a Bloom filter can only be used as an optimization to avoid using a
slower index (or heap scan) on the inner table source.

What I'm getting at is that the query planner really needs to understand
that a Bloom filter is a probabilistic data structure.

Nico
-- 


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

Re: [HACKERS] WIP: BRIN bloom indexes

[Sokolov Yura]

On 2017-10-19 23:15, Tomas Vondra wrote:

Hi,

The BRIN minmax opclasses work well only for data where the column is
somewhat correlated to physical location in a table. So it works great
for timestamps in append-only log tables, for example. When that is not
the case (non-correlated columns) the minmax ranges get very "wide" and
we end up scanning large portions of the tables.

A typical example are columns with types that are inherently random (or
rather non-correlated) like for example UUIDs, IP or MAC addresses, and
so on. But it can just as easily happen even with simple IDs generated
from a sequence.

This WIP patch implements another type of BRIN index, with "summary"
being represented by a bloom filter. So instead of building [min,max]
range for each page range. The index is of course larger than the
regular "minmax" BRIN index, but it's still orders of magnitude smaller
than a btree index.

Note: This is different from the index type implemented in the "bloom"
extension. Those are not related to BRIN at all, and the index builds a
bloom filter on individual rows (values in different columns).

BTW kudos to everyone who worked on the BRIN infrastructure and API. I
found it very intuitive and well-documented. Adding the new opclass was
extremely straight-forward, and


To demonstrate this on a small example, consider this table:

CREATE TABLE bloom_test (id uuid, padding text);

INSERT INTO bloom_test
SELECT md5((mod(i,100)/100)::text)::uuid, md5(i::text)
  FROM generate_series(1,2) s(i);

VACUUM ANALYZE bloom_test;

 List of relations
 Schema |Name| Type  | Owner | Size  | Description
++---+---+---+-
 public | bloom_test | table | tomas | 16 GB |
(1 row)

The table was built so that each range contains relatively small number
of distinct UUID values - this is typical e.g. for user activity with
"bursts" of actions from a particular user separated by long periods of
inactivity (with actions from other users).

Now, let's build BRIN "minmax", BRIN "bloom" and BTREE indexes on the 
id

column.

create index test_brin_idx on bloom_test
 using brin (id);

create index test_bloom_idx on bloom_test
 using brin (id uuid_bloom_ops);

create index test_btree_idx on bloom_test (id);

which gives us this:

  List of relations
 Schema |  Name  | Type  | Owner |   Table|  Size
++---+---++-
 public | test_bloom_idx | index | tomas | bloom_test | 12 MB
 public | test_brin_idx  | index | tomas | bloom_test | 832 kB
 public | test_btree_idx | index | tomas | bloom_test | 6016 MB
(3 rows)

So yeah - the "bloom" index is larger than the default "minmax" index,
but it's still orders of magnitude smaller than the regular btree one.

Now, what about query performance? Unlike the "minmax" indexes, the
"bloom" filter can only handle equality conditions.

Let's see a query like this:

select * from bloom_test
 where id = '8db1d4a6-31a6-e9a2-4e2c-0e842e1f1772';

The minmax index produces this plan

QUERY PLAN

 Bitmap Heap Scan on bloom_test
 (cost=390.31..2130910.82 rows=20593 width=49)
 (actual time=197.974..22707.311 rows=2 loops=1)
   Recheck Cond: (id = '8db1d4a6-31a6-e9a2-4e2c-0e842e1f1772'::uuid)
   Rows Removed by Index Recheck: 19998
   Heap Blocks: lossy=2061856
   ->  Bitmap Index Scan on test_brin_idx
   (cost=0.00..385.16 rows=5493161 width=0)
   (actual time=133.463..133.463 rows=20619520 loops=1)
 Index Cond: (id = 
'8db1d4a6-31a6-e9a2-4e2c-0e842e1f1772'::uuid)

 Planning time: 0.165 ms
 Execution time: 22707.891 ms
(8 rows)

Which is not that great, and the long duration is a direct consequence
of "wide" ranges - the bitmap heap scan had to scan pretty much the
whole table. (A sequential scan takes only about 15 seconds.)

Now, the bloom index:

QUERY PLAN

 Bitmap Heap Scan on bloom_test
 (cost=5898.31..2136418.82 rows=20593 width=49)
 (actual time=24.229..338.324 rows=2 loops=1)
   Recheck Cond: (id = '8db1d4a6-31a6-e9a2-4e2c-0e842e1f1772'::uuid)
   Rows Removed by Index Recheck: 2500448
   Heap Blocks: lossy=25984
   ->  Bitmap Index Scan on test_bloom_idx
 (cost=0.00..5893.16 rows=5493161 width=0)
 (actual time=22.811..22.811 rows=259840 loops=1)
 Index Cond: (id = 
'8db1d4a6-31a6-e9a2-4e2c-0e842e1f1772'::uuid)

 Planning time: 0.201 ms
 Execution time: 338.946 ms
(8 rows)

So, way better.

For comparison, a simple index scan / bitmap index scan using the btree
take only about ~10ms in this case, but that's mostly thanks to the
whole dataset being entirely 

Re: [HACKERS] WIP: BRIN bloom indexes

[Robert Haas]

On Fri, Oct 27, 2017 at 2:55 PM, Alvaro Herrera  wrote:
> I was rather thinking that if we can make this very robust against the
> index growing out of proportion, we should consider ditching the
> original minmax and replace it with multirange minmax, which seems like
> it'd have much better behavior.

If the multirange stuff can be done in such a way that it's just an
updated version of the same opclass, and backward-compatible on disk,
then I think this would be OK.  But otherwise I don't think we ditch
what already exists.  That would break upgrades via both pg_upgrade
and pg_dump, which seems like too high a price to pay to get rid of
some arguably-worse code.  It's actually WORSE to drop an opclass
(which will make dumps not restore) than to do something like bump
HASH_VERSION (which doesn't affect pg_dump at all and for pg_upgrade
only requires post-upgrade steps rather than failing outright).

> I don't see any reason to put any of this in contrib.

Well, for one thing, it makes it easier to drop stuff later if we
decide we don't really want it.  I think that whichever BRIN opclasses
are thought to be high quality and of general utility can go into
core, just as we've done with other index AMs.  However, if we think
that something is useful-ish but maybe not something to which we want
to make a permanent commitment, putting it into contrib is good for
that.

Upgrades are easier for things in contrib, too, because there's a
built-in mechanism for people to try updating the SQL extensions
(ALTER EXTENSION .. UPDATE) and if it fails they can adjust things and
try again.  When you just make a hard change to SQL definitions in a
new release, any failures that result from those changes just turn
into upgrade failures, which is IMHO a lot more painful than a failure
to update an extension version while the database is still up and
usable the whole time.

For instance, if pg_stat_activity were bundled in an extension and we
made the C code backward-compatibility with old extension versions,
then some of the upgrade pain users have had with that over the years
could have been avoided.  People could update to the new version
without failures and then at their leisure try to update.  If the
update failed due to dependencies, then they would have time to figure
out what to do about it and try again later; in the meantime, they'd
be on the new version.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


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

Re: [HACKERS] WIP: BRIN bloom indexes

[Alvaro Herrera]

Tomas Vondra wrote:

> Not sure "a number of in-core opclasses" is a good reason to (not) add
> new ones. Also, we already have two built-in BRIN opclasses (minmax and
> inclusion).
>
> In general, "BRIN bloom" can be packed as a contrib module (at least I
> believe so). That's not the case for the "BRIN multi-range" which also
> requires some changes to some code in brin.c (but the rest can be moved
> to contrib module, of course).

I was rather thinking that if we can make this very robust against the
index growing out of proportion, we should consider ditching the
original minmax and replace it with multirange minmax, which seems like
it'd have much better behavior.

I don't see any reason to put any of this in contrib.

-- 
Álvaro Herrerahttps://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

Re: [HACKERS] WIP: BRIN bloom indexes

[Tomas Vondra]

hi,

On 10/27/2017 09:34 AM, Simon Riggs wrote:
> On 27 October 2017 at 07:20, Robert Haas  wrote:
>> On Thu, Oct 19, 2017 at 10:15 PM, Tomas Vondra
>>  wrote:
>>> Let's see a query like this:
>>>
>>> select * from bloom_test
>>>  where id = '8db1d4a6-31a6-e9a2-4e2c-0e842e1f1772';
>>>
>>> The minmax index produces this plan
>>>
>>>Heap Blocks: lossy=2061856
>>>  Execution time: 22707.891 ms
>>>
>>> Now, the bloom index:
>>>
>>>Heap Blocks: lossy=25984
>>>  Execution time: 338.946 ms
>>
>> It's neat to see BRIN being extended like this.  Possibly we could
>> consider making it a contrib module rather than including it in core,
>> although I don't have strong feelings about it.
> 
> I see that SP-GIST includes two operator classes in core, one default.
> 
> Makes sense to do the same thing with BRIN and add this new op class
> as a non-default option in core.
> 

Not sure "a number of in-core opclasses" is a good reason to (not) add
new ones. Also, we already have two built-in BRIN opclasses (minmax and
inclusion).

In general, "BRIN bloom" can be packed as a contrib module (at least I
believe so). That's not the case for the "BRIN multi-range" which also
requires some changes to some code in brin.c (but the rest can be moved
to contrib module, of course).


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

Re: [HACKERS] WIP: BRIN bloom indexes

[Simon Riggs]

On 27 October 2017 at 07:20, Robert Haas  wrote:
> On Thu, Oct 19, 2017 at 10:15 PM, Tomas Vondra
>  wrote:
>> Let's see a query like this:
>>
>> select * from bloom_test
>>  where id = '8db1d4a6-31a6-e9a2-4e2c-0e842e1f1772';
>>
>> The minmax index produces this plan
>>
>>Heap Blocks: lossy=2061856
>>  Execution time: 22707.891 ms
>>
>> Now, the bloom index:
>>
>>Heap Blocks: lossy=25984
>>  Execution time: 338.946 ms
>
> It's neat to see BRIN being extended like this.  Possibly we could
> consider making it a contrib module rather than including it in core,
> although I don't have strong feelings about it.

I see that SP-GIST includes two operator classes in core, one default.

Makes sense to do the same thing with BRIN and add this new op class
as a non-default option in core.

-- 
Simon Riggshttp://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

Re: [HACKERS] WIP: BRIN bloom indexes

[Robert Haas]

On Thu, Oct 19, 2017 at 10:15 PM, Tomas Vondra
 wrote:
> Let's see a query like this:
>
> select * from bloom_test
>  where id = '8db1d4a6-31a6-e9a2-4e2c-0e842e1f1772';
>
> The minmax index produces this plan
>
>Heap Blocks: lossy=2061856
>  Execution time: 22707.891 ms
>
> Now, the bloom index:
>
>Heap Blocks: lossy=25984
>  Execution time: 338.946 ms

It's neat to see BRIN being extended like this.  Possibly we could
consider making it a contrib module rather than including it in core,
although I don't have strong feelings about it.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


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

[HACKERS] WIP: BRIN bloom indexes

[Tomas Vondra]

Hi,

The BRIN minmax opclasses work well only for data where the column is
somewhat correlated to physical location in a table. So it works great
for timestamps in append-only log tables, for example. When that is not
the case (non-correlated columns) the minmax ranges get very "wide" and
we end up scanning large portions of the tables.

A typical example are columns with types that are inherently random (or
rather non-correlated) like for example UUIDs, IP or MAC addresses, and
so on. But it can just as easily happen even with simple IDs generated
from a sequence.

This WIP patch implements another type of BRIN index, with "summary"
being represented by a bloom filter. So instead of building [min,max]
range for each page range. The index is of course larger than the
regular "minmax" BRIN index, but it's still orders of magnitude smaller
than a btree index.

Note: This is different from the index type implemented in the "bloom"
extension. Those are not related to BRIN at all, and the index builds a
bloom filter on individual rows (values in different columns).

BTW kudos to everyone who worked on the BRIN infrastructure and API. I
found it very intuitive and well-documented. Adding the new opclass was
extremely straight-forward, and


To demonstrate this on a small example, consider this table:

CREATE TABLE bloom_test (id uuid, padding text);

INSERT INTO bloom_test
SELECT md5((mod(i,100)/100)::text)::uuid, md5(i::text)
  FROM generate_series(1,2) s(i);

VACUUM ANALYZE bloom_test;

 List of relations
 Schema |Name| Type  | Owner | Size  | Description
++---+---+---+-
 public | bloom_test | table | tomas | 16 GB |
(1 row)

The table was built so that each range contains relatively small number
of distinct UUID values - this is typical e.g. for user activity with
"bursts" of actions from a particular user separated by long periods of
inactivity (with actions from other users).

Now, let's build BRIN "minmax", BRIN "bloom" and BTREE indexes on the id
column.

create index test_brin_idx on bloom_test
 using brin (id);

create index test_bloom_idx on bloom_test
 using brin (id uuid_bloom_ops);

create index test_btree_idx on bloom_test (id);

which gives us this:

  List of relations
 Schema |  Name  | Type  | Owner |   Table|  Size
++---+---++-
 public | test_bloom_idx | index | tomas | bloom_test | 12 MB
 public | test_brin_idx  | index | tomas | bloom_test | 832 kB
 public | test_btree_idx | index | tomas | bloom_test | 6016 MB
(3 rows)

So yeah - the "bloom" index is larger than the default "minmax" index,
but it's still orders of magnitude smaller than the regular btree one.

Now, what about query performance? Unlike the "minmax" indexes, the
"bloom" filter can only handle equality conditions.

Let's see a query like this:

select * from bloom_test
 where id = '8db1d4a6-31a6-e9a2-4e2c-0e842e1f1772';

The minmax index produces this plan

QUERY PLAN

 Bitmap Heap Scan on bloom_test
 (cost=390.31..2130910.82 rows=20593 width=49)
 (actual time=197.974..22707.311 rows=2 loops=1)
   Recheck Cond: (id = '8db1d4a6-31a6-e9a2-4e2c-0e842e1f1772'::uuid)
   Rows Removed by Index Recheck: 19998
   Heap Blocks: lossy=2061856
   ->  Bitmap Index Scan on test_brin_idx
   (cost=0.00..385.16 rows=5493161 width=0)
   (actual time=133.463..133.463 rows=20619520 loops=1)
 Index Cond: (id = '8db1d4a6-31a6-e9a2-4e2c-0e842e1f1772'::uuid)
 Planning time: 0.165 ms
 Execution time: 22707.891 ms
(8 rows)

Which is not that great, and the long duration is a direct consequence
of "wide" ranges - the bitmap heap scan had to scan pretty much the
whole table. (A sequential scan takes only about 15 seconds.)

Now, the bloom index:

QUERY PLAN

 Bitmap Heap Scan on bloom_test
 (cost=5898.31..2136418.82 rows=20593 width=49)
 (actual time=24.229..338.324 rows=2 loops=1)
   Recheck Cond: (id = '8db1d4a6-31a6-e9a2-4e2c-0e842e1f1772'::uuid)
   Rows Removed by Index Recheck: 2500448
   Heap Blocks: lossy=25984
   ->  Bitmap Index Scan on test_bloom_idx
 (cost=0.00..5893.16 rows=5493161 width=0)
 (actual time=22.811..22.811 rows=259840 loops=1)
 Index Cond: (id = '8db1d4a6-31a6-e9a2-4e2c-0e842e1f1772'::uuid)
 Planning time: 0.201 ms
 Execution time: 338.946 ms
(8 rows)

So, way better.

For comparison, a simple index scan / bitmap index scan using the btree
take only about ~10ms in this case, but that's mostly thanks to the
whole dataset being entirely in-memory.

There are some remaining open questions.

1)