agora inbox for [email protected]
help / color / mirror / Atom feedRe: Crash when partition column specified twice
24+ messages / 4 participants
[nested] [flat]
* Re: Crash when partition column specified twice
@ 2017-05-01 00:13 Amit Langote <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Amit Langote @ 2017-05-01 00:13 UTC (permalink / raw)
To: Robert Haas <[email protected]>; Beena Emerson <[email protected]>; +Cc: pgsql-hackers
On 2017/04/29 2:53, Robert Haas wrote:
> On Fri, Apr 28, 2017 at 7:23 AM, Beena Emerson <[email protected]> wrote:
>> Hello Amit,
>>
>> The extra n->is_from_type = false; seems to be added by mistake?
>>
>> @@ -11888,6 +11891,8 @@ TableFuncElement: ColId Typename
>> opt_collate_clause
>> n->is_local = true;
>> n->is_not_null = false;
>> n->is_from_type = false;
>> + n->is_from_type = false;
>> + n->is_from_parent = false;
>> n->storage = 0;
>> n->raw_default = NULL;
>> n->cooked_default = NULL;
>
> Good catch. Committed after fixing that issue.
Thanks both.
Regards,
Amit
--
Sent via pgsql-hackers mailing list ([email protected])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
^ permalink raw reply [nested|flat] 24+ messages in thread
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw)
---
doc/src/sgml/ref/create_index.sgml | 2 +-
src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++----------
src/test/regress/expected/brin_bloom.out | 14 ++--
src/test/regress/sql/brin_bloom.sql | 6 +-
4 files changed, 60 insertions(+), 46 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 8db10b7b1e..244e5834d8 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class=
equal to -1, the number of distinct non-null is assumed linear with
the maximum possible number of tuples in the block range (about 290
rows per block). The default values is <literal>-0.1</literal>, and
- the minimum number of distinct non-null values is <literal>128</literal>.
+ the minimum number of distinct non-null values is <literal>16</literal>.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index b7aa6d9f11..ffeb459d3e 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -8,12 +8,12 @@
*
* A BRIN opclass summarizing page range into a bloom filter.
*
- * Bloom filters allow efficient test whether a given page range contains
+ * Bloom filters allow efficient testing whether a given page range contains
* a particular value. Therefore, if we summarize each page range into a
- * bloom filter, we can easily and cheaply test wheter it containst values
+ * bloom filter, we can easily and cheaply test wheter it contains values
* we get later.
*
- * The index only supports equality operator, similarly to hash indexes.
+ * The index only supports equality operators, similarly to hash indexes.
* BRIN bloom indexes are however much smaller, and support only bitmap
* scans.
*
@@ -51,9 +51,9 @@
* the bloom filter. On the other hand, we want to keep the index as small
* as possible - that's one of the basic advantages of BRIN indexes.
*
- * The number of distinct elements (in a page range) depends on the data,
- * we can consider it fixed. This simplifies the trade-off to just false
- * positive rate vs. size.
+ * Although the number of distinct elements (in a page range) depends on
+ * the data, we can consider it fixed. This simplifies the trade-off to
+ * just false positive rate vs. size.
*
* At the page range level, false positive rate is a probability the bloom
* filter matches a random value. For the whole index (with sufficiently
@@ -65,7 +65,7 @@
* the bitmap is inherently random, compression can't reliably help here.
* To reduce the size of a filter (to fit to a page), we have to either
* accept higher false positive rate (undesirable), or reduce the number
- * of distinct items to be stored in the filter. We can't quite the input
+ * of distinct items to be stored in the filter. We can't alter the input
* data, of course, but we may make the BRIN page ranges smaller - instead
* of the default 128 pages (1MB) we may build index with 16-page ranges,
* or something like that. This does help even for random data sets, as
@@ -87,7 +87,8 @@
* not entirely clear how to distrubute the space between those columns.
*
* The current logic, implemented in brin_bloom_get_ndistinct, attempts to
- * make some basic sizing decisions, based on the table ndistinct estimate.
+ * make some basic sizing decisions, based on the size of BRIN ranges, and
+ * the maximum number of rows per range.
*
*
* sort vs. hash
@@ -200,10 +201,20 @@ typedef struct BloomOptions
/*
* Allowed range and default value for the false positive range. The exact
- * values are somewhat arbitrary.
+ * values are somewhat arbitrary, but were chosen considering the various
+ * parameters (size of filter vs. page size, etc.).
+ *
+ * The lower the false-positive rate, the more accurate the filter is, but
+ * it also gets larger - at some point this eliminates the main advantage
+ * of BRIN indexes, which is the tiny size. At 0.01% the index is about
+ * 10% of the table (assuming 290 distinct values per 8kB page).
+ *
+ * On the other hand, as the false-positive rate increases, larger part of
+ * the table has to be scanned due to mismatches - at 25% we're probably
+ * close to sequential scan being cheaper.
*/
-#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */
-#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */
+#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
+#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
#define BloomGetNDistinctPerRange(opts) \
@@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate)
Assert(ndistinct > 0);
Assert((false_positive_rate > 0) && (false_positive_rate < 1.0));
- m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0)))));
+ /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
+ m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
/* round m to whole bytes */
m = ((m + 7) / 8) * 8;
+ /*
+ * Reject filters that are obviously too large to store on a page.
+ *
+ * We do expect the bloom filter to eventually switch to hashing mode,
+ * and it's bound to be almost perfectly random, so not compressible.
+ */
+ if ((m/8) > BLCKSZ)
+ elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ);
+
/*
* round(log(2.0) * m / ndistinct), but assume round() may not be
* available on Windows
@@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate)
k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
/*
- * Allocate the bloom filter with a minimum size 64B (about 40B in the
- * bitmap part). We require space at least for the header.
- *
- * XXX Maybe the 64B min size is not really needed?
+ * Allocate the bloom filter (initially it's just a header, we'll make
+ * it larger as needed).
*/
- len = Max(offsetof(BloomFilter, data), 64);
-
- /* Reject filters that are obviously too large to store on a page. */
- if (len > BLCKSZ)
- elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ);
+ len = offsetof(BloomFilter, data);
filter = (BloomFilter *) palloc0(len);
@@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* brin_bloom_get_ndistinct
* Determine the ndistinct value used to size bloom filter.
*
- * Tweak the ndistinct value based on the pagesPerRange value. First,
+ * Adjust the ndistinct value based on the pagesPerRange value. First,
* if it's negative, it's assumed to be relative to maximum number of
* tuples in the range (assuming each page gets MaxHeapTuplesPerPage
* tuples, which is likely a significant over-estimate). We also clamp
@@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* and compute the expected number of distinct values in a range. But
* that may be tricky due to data being sorted in various ways, so it
* seems better to rely on the upper estimate.
+ *
+ * XXX We might also calculate a better estimate of rows per BRIN range,
+ * instead of using MaxHeapTuplesPerPage (which probably produces values
+ * much higher than reality).
*/
static int
brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
@@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
return (int) ndistinct;
}
-static double
-brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts)
-{
- return BloomGetFalsePositiveRate(opts);
-}
/*
* Examine the given index tuple (which contains partial status of a certain
@@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS)
if (column->bv_allnulls)
{
filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
- brin_bloom_get_fp_rate(bdesc, opts));
+ BloomGetFalsePositiveRate(opts));
column->bv_values[0] = PointerGetDatum(filter);
column->bv_allnulls = false;
updated = true;
@@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS)
* Cache and return inclusion opclass support procedure
*
* Return the procedure corresponding to the given function support number
- * or null if it is not exists.
+ * or null if it does not exists.
*/
static FmgrInfo *
bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
@@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
initStringInfo(&str);
appendStringInfoChar(&str, '{');
- /*
- * XXX not sure the detoasting is necessary (probably not, this
- * can only be in an index).
- */
- filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0));
+ /* Detoasting not needed (this can only be in an index). */
+ filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0);
if (BLOOM_IS_HASHED(filter))
{
@@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
}
else
{
+ /*
+ * XXX Maybe include the sorted/unsorted values? Seems a bit too
+ * much useless detail (internal hash values).
+ */
appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u",
filter->nvalues, filter->nsorted);
- /* TODO include the sorted/unsorted values */
}
appendStringInfoChar(&str, '}');
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
index 19b866283a..24ea5f6e42 100644
--- a/src/test/regress/expected/brin_bloom.out
+++ b/src/test/regress/expected/brin_bloom.out
@@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
);
ERROR: value -1.1 out of bounds for option "n_distinct_per_range"
DETAIL: Valid values are between "-1.000000" and "2147483647.000000".
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
-ERROR: value 0.0009 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.00009 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
-ERROR: value 0.11 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.26 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops,
charcol char_bloom_ops,
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
index 3c2ef56316..d587f3962f 100644
--- a/src/test/regress/sql/brin_bloom.sql
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops(n_distinct_per_range = -1.1)
);
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
--
2.26.2
--------------CF71AF65F7C337C37C24B045
Content-Type: text/x-patch; charset=UTF-8;
name="0006-add-sort_mode-opclass-parameter-20210112.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0006-add-sort_mode-opclass-parameter-20210112.patch"
^ permalink raw reply [nested|flat] 24+ messages in thread
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw)
---
doc/src/sgml/ref/create_index.sgml | 2 +-
src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++----------
src/test/regress/expected/brin_bloom.out | 14 ++--
src/test/regress/sql/brin_bloom.sql | 6 +-
4 files changed, 60 insertions(+), 46 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 8db10b7b1e..244e5834d8 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class=
equal to -1, the number of distinct non-null is assumed linear with
the maximum possible number of tuples in the block range (about 290
rows per block). The default values is <literal>-0.1</literal>, and
- the minimum number of distinct non-null values is <literal>128</literal>.
+ the minimum number of distinct non-null values is <literal>16</literal>.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index b7aa6d9f11..ffeb459d3e 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -8,12 +8,12 @@
*
* A BRIN opclass summarizing page range into a bloom filter.
*
- * Bloom filters allow efficient test whether a given page range contains
+ * Bloom filters allow efficient testing whether a given page range contains
* a particular value. Therefore, if we summarize each page range into a
- * bloom filter, we can easily and cheaply test wheter it containst values
+ * bloom filter, we can easily and cheaply test wheter it contains values
* we get later.
*
- * The index only supports equality operator, similarly to hash indexes.
+ * The index only supports equality operators, similarly to hash indexes.
* BRIN bloom indexes are however much smaller, and support only bitmap
* scans.
*
@@ -51,9 +51,9 @@
* the bloom filter. On the other hand, we want to keep the index as small
* as possible - that's one of the basic advantages of BRIN indexes.
*
- * The number of distinct elements (in a page range) depends on the data,
- * we can consider it fixed. This simplifies the trade-off to just false
- * positive rate vs. size.
+ * Although the number of distinct elements (in a page range) depends on
+ * the data, we can consider it fixed. This simplifies the trade-off to
+ * just false positive rate vs. size.
*
* At the page range level, false positive rate is a probability the bloom
* filter matches a random value. For the whole index (with sufficiently
@@ -65,7 +65,7 @@
* the bitmap is inherently random, compression can't reliably help here.
* To reduce the size of a filter (to fit to a page), we have to either
* accept higher false positive rate (undesirable), or reduce the number
- * of distinct items to be stored in the filter. We can't quite the input
+ * of distinct items to be stored in the filter. We can't alter the input
* data, of course, but we may make the BRIN page ranges smaller - instead
* of the default 128 pages (1MB) we may build index with 16-page ranges,
* or something like that. This does help even for random data sets, as
@@ -87,7 +87,8 @@
* not entirely clear how to distrubute the space between those columns.
*
* The current logic, implemented in brin_bloom_get_ndistinct, attempts to
- * make some basic sizing decisions, based on the table ndistinct estimate.
+ * make some basic sizing decisions, based on the size of BRIN ranges, and
+ * the maximum number of rows per range.
*
*
* sort vs. hash
@@ -200,10 +201,20 @@ typedef struct BloomOptions
/*
* Allowed range and default value for the false positive range. The exact
- * values are somewhat arbitrary.
+ * values are somewhat arbitrary, but were chosen considering the various
+ * parameters (size of filter vs. page size, etc.).
+ *
+ * The lower the false-positive rate, the more accurate the filter is, but
+ * it also gets larger - at some point this eliminates the main advantage
+ * of BRIN indexes, which is the tiny size. At 0.01% the index is about
+ * 10% of the table (assuming 290 distinct values per 8kB page).
+ *
+ * On the other hand, as the false-positive rate increases, larger part of
+ * the table has to be scanned due to mismatches - at 25% we're probably
+ * close to sequential scan being cheaper.
*/
-#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */
-#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */
+#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
+#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
#define BloomGetNDistinctPerRange(opts) \
@@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate)
Assert(ndistinct > 0);
Assert((false_positive_rate > 0) && (false_positive_rate < 1.0));
- m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0)))));
+ /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
+ m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
/* round m to whole bytes */
m = ((m + 7) / 8) * 8;
+ /*
+ * Reject filters that are obviously too large to store on a page.
+ *
+ * We do expect the bloom filter to eventually switch to hashing mode,
+ * and it's bound to be almost perfectly random, so not compressible.
+ */
+ if ((m/8) > BLCKSZ)
+ elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ);
+
/*
* round(log(2.0) * m / ndistinct), but assume round() may not be
* available on Windows
@@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate)
k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
/*
- * Allocate the bloom filter with a minimum size 64B (about 40B in the
- * bitmap part). We require space at least for the header.
- *
- * XXX Maybe the 64B min size is not really needed?
+ * Allocate the bloom filter (initially it's just a header, we'll make
+ * it larger as needed).
*/
- len = Max(offsetof(BloomFilter, data), 64);
-
- /* Reject filters that are obviously too large to store on a page. */
- if (len > BLCKSZ)
- elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ);
+ len = offsetof(BloomFilter, data);
filter = (BloomFilter *) palloc0(len);
@@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* brin_bloom_get_ndistinct
* Determine the ndistinct value used to size bloom filter.
*
- * Tweak the ndistinct value based on the pagesPerRange value. First,
+ * Adjust the ndistinct value based on the pagesPerRange value. First,
* if it's negative, it's assumed to be relative to maximum number of
* tuples in the range (assuming each page gets MaxHeapTuplesPerPage
* tuples, which is likely a significant over-estimate). We also clamp
@@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* and compute the expected number of distinct values in a range. But
* that may be tricky due to data being sorted in various ways, so it
* seems better to rely on the upper estimate.
+ *
+ * XXX We might also calculate a better estimate of rows per BRIN range,
+ * instead of using MaxHeapTuplesPerPage (which probably produces values
+ * much higher than reality).
*/
static int
brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
@@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
return (int) ndistinct;
}
-static double
-brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts)
-{
- return BloomGetFalsePositiveRate(opts);
-}
/*
* Examine the given index tuple (which contains partial status of a certain
@@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS)
if (column->bv_allnulls)
{
filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
- brin_bloom_get_fp_rate(bdesc, opts));
+ BloomGetFalsePositiveRate(opts));
column->bv_values[0] = PointerGetDatum(filter);
column->bv_allnulls = false;
updated = true;
@@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS)
* Cache and return inclusion opclass support procedure
*
* Return the procedure corresponding to the given function support number
- * or null if it is not exists.
+ * or null if it does not exists.
*/
static FmgrInfo *
bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
@@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
initStringInfo(&str);
appendStringInfoChar(&str, '{');
- /*
- * XXX not sure the detoasting is necessary (probably not, this
- * can only be in an index).
- */
- filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0));
+ /* Detoasting not needed (this can only be in an index). */
+ filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0);
if (BLOOM_IS_HASHED(filter))
{
@@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
}
else
{
+ /*
+ * XXX Maybe include the sorted/unsorted values? Seems a bit too
+ * much useless detail (internal hash values).
+ */
appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u",
filter->nvalues, filter->nsorted);
- /* TODO include the sorted/unsorted values */
}
appendStringInfoChar(&str, '}');
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
index 19b866283a..24ea5f6e42 100644
--- a/src/test/regress/expected/brin_bloom.out
+++ b/src/test/regress/expected/brin_bloom.out
@@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
);
ERROR: value -1.1 out of bounds for option "n_distinct_per_range"
DETAIL: Valid values are between "-1.000000" and "2147483647.000000".
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
-ERROR: value 0.0009 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.00009 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
-ERROR: value 0.11 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.26 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops,
charcol char_bloom_ops,
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
index 3c2ef56316..d587f3962f 100644
--- a/src/test/regress/sql/brin_bloom.sql
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops(n_distinct_per_range = -1.1)
);
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
--
2.26.2
--------------CF71AF65F7C337C37C24B045
Content-Type: text/x-patch; charset=UTF-8;
name="0006-add-sort_mode-opclass-parameter-20210112.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0006-add-sort_mode-opclass-parameter-20210112.patch"
^ permalink raw reply [nested|flat] 24+ messages in thread
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw)
---
doc/src/sgml/ref/create_index.sgml | 2 +-
src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++----------
src/test/regress/expected/brin_bloom.out | 14 ++--
src/test/regress/sql/brin_bloom.sql | 6 +-
4 files changed, 60 insertions(+), 46 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 8db10b7b1e..244e5834d8 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class=
equal to -1, the number of distinct non-null is assumed linear with
the maximum possible number of tuples in the block range (about 290
rows per block). The default values is <literal>-0.1</literal>, and
- the minimum number of distinct non-null values is <literal>128</literal>.
+ the minimum number of distinct non-null values is <literal>16</literal>.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index b7aa6d9f11..ffeb459d3e 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -8,12 +8,12 @@
*
* A BRIN opclass summarizing page range into a bloom filter.
*
- * Bloom filters allow efficient test whether a given page range contains
+ * Bloom filters allow efficient testing whether a given page range contains
* a particular value. Therefore, if we summarize each page range into a
- * bloom filter, we can easily and cheaply test wheter it containst values
+ * bloom filter, we can easily and cheaply test wheter it contains values
* we get later.
*
- * The index only supports equality operator, similarly to hash indexes.
+ * The index only supports equality operators, similarly to hash indexes.
* BRIN bloom indexes are however much smaller, and support only bitmap
* scans.
*
@@ -51,9 +51,9 @@
* the bloom filter. On the other hand, we want to keep the index as small
* as possible - that's one of the basic advantages of BRIN indexes.
*
- * The number of distinct elements (in a page range) depends on the data,
- * we can consider it fixed. This simplifies the trade-off to just false
- * positive rate vs. size.
+ * Although the number of distinct elements (in a page range) depends on
+ * the data, we can consider it fixed. This simplifies the trade-off to
+ * just false positive rate vs. size.
*
* At the page range level, false positive rate is a probability the bloom
* filter matches a random value. For the whole index (with sufficiently
@@ -65,7 +65,7 @@
* the bitmap is inherently random, compression can't reliably help here.
* To reduce the size of a filter (to fit to a page), we have to either
* accept higher false positive rate (undesirable), or reduce the number
- * of distinct items to be stored in the filter. We can't quite the input
+ * of distinct items to be stored in the filter. We can't alter the input
* data, of course, but we may make the BRIN page ranges smaller - instead
* of the default 128 pages (1MB) we may build index with 16-page ranges,
* or something like that. This does help even for random data sets, as
@@ -87,7 +87,8 @@
* not entirely clear how to distrubute the space between those columns.
*
* The current logic, implemented in brin_bloom_get_ndistinct, attempts to
- * make some basic sizing decisions, based on the table ndistinct estimate.
+ * make some basic sizing decisions, based on the size of BRIN ranges, and
+ * the maximum number of rows per range.
*
*
* sort vs. hash
@@ -200,10 +201,20 @@ typedef struct BloomOptions
/*
* Allowed range and default value for the false positive range. The exact
- * values are somewhat arbitrary.
+ * values are somewhat arbitrary, but were chosen considering the various
+ * parameters (size of filter vs. page size, etc.).
+ *
+ * The lower the false-positive rate, the more accurate the filter is, but
+ * it also gets larger - at some point this eliminates the main advantage
+ * of BRIN indexes, which is the tiny size. At 0.01% the index is about
+ * 10% of the table (assuming 290 distinct values per 8kB page).
+ *
+ * On the other hand, as the false-positive rate increases, larger part of
+ * the table has to be scanned due to mismatches - at 25% we're probably
+ * close to sequential scan being cheaper.
*/
-#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */
-#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */
+#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
+#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
#define BloomGetNDistinctPerRange(opts) \
@@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate)
Assert(ndistinct > 0);
Assert((false_positive_rate > 0) && (false_positive_rate < 1.0));
- m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0)))));
+ /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
+ m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
/* round m to whole bytes */
m = ((m + 7) / 8) * 8;
+ /*
+ * Reject filters that are obviously too large to store on a page.
+ *
+ * We do expect the bloom filter to eventually switch to hashing mode,
+ * and it's bound to be almost perfectly random, so not compressible.
+ */
+ if ((m/8) > BLCKSZ)
+ elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ);
+
/*
* round(log(2.0) * m / ndistinct), but assume round() may not be
* available on Windows
@@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate)
k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
/*
- * Allocate the bloom filter with a minimum size 64B (about 40B in the
- * bitmap part). We require space at least for the header.
- *
- * XXX Maybe the 64B min size is not really needed?
+ * Allocate the bloom filter (initially it's just a header, we'll make
+ * it larger as needed).
*/
- len = Max(offsetof(BloomFilter, data), 64);
-
- /* Reject filters that are obviously too large to store on a page. */
- if (len > BLCKSZ)
- elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ);
+ len = offsetof(BloomFilter, data);
filter = (BloomFilter *) palloc0(len);
@@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* brin_bloom_get_ndistinct
* Determine the ndistinct value used to size bloom filter.
*
- * Tweak the ndistinct value based on the pagesPerRange value. First,
+ * Adjust the ndistinct value based on the pagesPerRange value. First,
* if it's negative, it's assumed to be relative to maximum number of
* tuples in the range (assuming each page gets MaxHeapTuplesPerPage
* tuples, which is likely a significant over-estimate). We also clamp
@@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* and compute the expected number of distinct values in a range. But
* that may be tricky due to data being sorted in various ways, so it
* seems better to rely on the upper estimate.
+ *
+ * XXX We might also calculate a better estimate of rows per BRIN range,
+ * instead of using MaxHeapTuplesPerPage (which probably produces values
+ * much higher than reality).
*/
static int
brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
@@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
return (int) ndistinct;
}
-static double
-brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts)
-{
- return BloomGetFalsePositiveRate(opts);
-}
/*
* Examine the given index tuple (which contains partial status of a certain
@@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS)
if (column->bv_allnulls)
{
filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
- brin_bloom_get_fp_rate(bdesc, opts));
+ BloomGetFalsePositiveRate(opts));
column->bv_values[0] = PointerGetDatum(filter);
column->bv_allnulls = false;
updated = true;
@@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS)
* Cache and return inclusion opclass support procedure
*
* Return the procedure corresponding to the given function support number
- * or null if it is not exists.
+ * or null if it does not exists.
*/
static FmgrInfo *
bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
@@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
initStringInfo(&str);
appendStringInfoChar(&str, '{');
- /*
- * XXX not sure the detoasting is necessary (probably not, this
- * can only be in an index).
- */
- filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0));
+ /* Detoasting not needed (this can only be in an index). */
+ filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0);
if (BLOOM_IS_HASHED(filter))
{
@@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
}
else
{
+ /*
+ * XXX Maybe include the sorted/unsorted values? Seems a bit too
+ * much useless detail (internal hash values).
+ */
appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u",
filter->nvalues, filter->nsorted);
- /* TODO include the sorted/unsorted values */
}
appendStringInfoChar(&str, '}');
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
index 19b866283a..24ea5f6e42 100644
--- a/src/test/regress/expected/brin_bloom.out
+++ b/src/test/regress/expected/brin_bloom.out
@@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
);
ERROR: value -1.1 out of bounds for option "n_distinct_per_range"
DETAIL: Valid values are between "-1.000000" and "2147483647.000000".
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
-ERROR: value 0.0009 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.00009 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
-ERROR: value 0.11 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.26 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops,
charcol char_bloom_ops,
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
index 3c2ef56316..d587f3962f 100644
--- a/src/test/regress/sql/brin_bloom.sql
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops(n_distinct_per_range = -1.1)
);
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
--
2.26.2
--------------CF71AF65F7C337C37C24B045
Content-Type: text/x-patch; charset=UTF-8;
name="0006-add-sort_mode-opclass-parameter-20210112.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0006-add-sort_mode-opclass-parameter-20210112.patch"
^ permalink raw reply [nested|flat] 24+ messages in thread
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw)
---
doc/src/sgml/ref/create_index.sgml | 2 +-
src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++----------
src/test/regress/expected/brin_bloom.out | 14 ++--
src/test/regress/sql/brin_bloom.sql | 6 +-
4 files changed, 60 insertions(+), 46 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 8db10b7b1e..244e5834d8 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class=
equal to -1, the number of distinct non-null is assumed linear with
the maximum possible number of tuples in the block range (about 290
rows per block). The default values is <literal>-0.1</literal>, and
- the minimum number of distinct non-null values is <literal>128</literal>.
+ the minimum number of distinct non-null values is <literal>16</literal>.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index b7aa6d9f11..ffeb459d3e 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -8,12 +8,12 @@
*
* A BRIN opclass summarizing page range into a bloom filter.
*
- * Bloom filters allow efficient test whether a given page range contains
+ * Bloom filters allow efficient testing whether a given page range contains
* a particular value. Therefore, if we summarize each page range into a
- * bloom filter, we can easily and cheaply test wheter it containst values
+ * bloom filter, we can easily and cheaply test wheter it contains values
* we get later.
*
- * The index only supports equality operator, similarly to hash indexes.
+ * The index only supports equality operators, similarly to hash indexes.
* BRIN bloom indexes are however much smaller, and support only bitmap
* scans.
*
@@ -51,9 +51,9 @@
* the bloom filter. On the other hand, we want to keep the index as small
* as possible - that's one of the basic advantages of BRIN indexes.
*
- * The number of distinct elements (in a page range) depends on the data,
- * we can consider it fixed. This simplifies the trade-off to just false
- * positive rate vs. size.
+ * Although the number of distinct elements (in a page range) depends on
+ * the data, we can consider it fixed. This simplifies the trade-off to
+ * just false positive rate vs. size.
*
* At the page range level, false positive rate is a probability the bloom
* filter matches a random value. For the whole index (with sufficiently
@@ -65,7 +65,7 @@
* the bitmap is inherently random, compression can't reliably help here.
* To reduce the size of a filter (to fit to a page), we have to either
* accept higher false positive rate (undesirable), or reduce the number
- * of distinct items to be stored in the filter. We can't quite the input
+ * of distinct items to be stored in the filter. We can't alter the input
* data, of course, but we may make the BRIN page ranges smaller - instead
* of the default 128 pages (1MB) we may build index with 16-page ranges,
* or something like that. This does help even for random data sets, as
@@ -87,7 +87,8 @@
* not entirely clear how to distrubute the space between those columns.
*
* The current logic, implemented in brin_bloom_get_ndistinct, attempts to
- * make some basic sizing decisions, based on the table ndistinct estimate.
+ * make some basic sizing decisions, based on the size of BRIN ranges, and
+ * the maximum number of rows per range.
*
*
* sort vs. hash
@@ -200,10 +201,20 @@ typedef struct BloomOptions
/*
* Allowed range and default value for the false positive range. The exact
- * values are somewhat arbitrary.
+ * values are somewhat arbitrary, but were chosen considering the various
+ * parameters (size of filter vs. page size, etc.).
+ *
+ * The lower the false-positive rate, the more accurate the filter is, but
+ * it also gets larger - at some point this eliminates the main advantage
+ * of BRIN indexes, which is the tiny size. At 0.01% the index is about
+ * 10% of the table (assuming 290 distinct values per 8kB page).
+ *
+ * On the other hand, as the false-positive rate increases, larger part of
+ * the table has to be scanned due to mismatches - at 25% we're probably
+ * close to sequential scan being cheaper.
*/
-#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */
-#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */
+#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
+#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
#define BloomGetNDistinctPerRange(opts) \
@@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate)
Assert(ndistinct > 0);
Assert((false_positive_rate > 0) && (false_positive_rate < 1.0));
- m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0)))));
+ /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
+ m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
/* round m to whole bytes */
m = ((m + 7) / 8) * 8;
+ /*
+ * Reject filters that are obviously too large to store on a page.
+ *
+ * We do expect the bloom filter to eventually switch to hashing mode,
+ * and it's bound to be almost perfectly random, so not compressible.
+ */
+ if ((m/8) > BLCKSZ)
+ elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ);
+
/*
* round(log(2.0) * m / ndistinct), but assume round() may not be
* available on Windows
@@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate)
k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
/*
- * Allocate the bloom filter with a minimum size 64B (about 40B in the
- * bitmap part). We require space at least for the header.
- *
- * XXX Maybe the 64B min size is not really needed?
+ * Allocate the bloom filter (initially it's just a header, we'll make
+ * it larger as needed).
*/
- len = Max(offsetof(BloomFilter, data), 64);
-
- /* Reject filters that are obviously too large to store on a page. */
- if (len > BLCKSZ)
- elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ);
+ len = offsetof(BloomFilter, data);
filter = (BloomFilter *) palloc0(len);
@@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* brin_bloom_get_ndistinct
* Determine the ndistinct value used to size bloom filter.
*
- * Tweak the ndistinct value based on the pagesPerRange value. First,
+ * Adjust the ndistinct value based on the pagesPerRange value. First,
* if it's negative, it's assumed to be relative to maximum number of
* tuples in the range (assuming each page gets MaxHeapTuplesPerPage
* tuples, which is likely a significant over-estimate). We also clamp
@@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* and compute the expected number of distinct values in a range. But
* that may be tricky due to data being sorted in various ways, so it
* seems better to rely on the upper estimate.
+ *
+ * XXX We might also calculate a better estimate of rows per BRIN range,
+ * instead of using MaxHeapTuplesPerPage (which probably produces values
+ * much higher than reality).
*/
static int
brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
@@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
return (int) ndistinct;
}
-static double
-brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts)
-{
- return BloomGetFalsePositiveRate(opts);
-}
/*
* Examine the given index tuple (which contains partial status of a certain
@@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS)
if (column->bv_allnulls)
{
filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
- brin_bloom_get_fp_rate(bdesc, opts));
+ BloomGetFalsePositiveRate(opts));
column->bv_values[0] = PointerGetDatum(filter);
column->bv_allnulls = false;
updated = true;
@@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS)
* Cache and return inclusion opclass support procedure
*
* Return the procedure corresponding to the given function support number
- * or null if it is not exists.
+ * or null if it does not exists.
*/
static FmgrInfo *
bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
@@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
initStringInfo(&str);
appendStringInfoChar(&str, '{');
- /*
- * XXX not sure the detoasting is necessary (probably not, this
- * can only be in an index).
- */
- filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0));
+ /* Detoasting not needed (this can only be in an index). */
+ filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0);
if (BLOOM_IS_HASHED(filter))
{
@@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
}
else
{
+ /*
+ * XXX Maybe include the sorted/unsorted values? Seems a bit too
+ * much useless detail (internal hash values).
+ */
appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u",
filter->nvalues, filter->nsorted);
- /* TODO include the sorted/unsorted values */
}
appendStringInfoChar(&str, '}');
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
index 19b866283a..24ea5f6e42 100644
--- a/src/test/regress/expected/brin_bloom.out
+++ b/src/test/regress/expected/brin_bloom.out
@@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
);
ERROR: value -1.1 out of bounds for option "n_distinct_per_range"
DETAIL: Valid values are between "-1.000000" and "2147483647.000000".
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
-ERROR: value 0.0009 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.00009 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
-ERROR: value 0.11 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.26 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops,
charcol char_bloom_ops,
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
index 3c2ef56316..d587f3962f 100644
--- a/src/test/regress/sql/brin_bloom.sql
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops(n_distinct_per_range = -1.1)
);
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
--
2.26.2
--------------CF71AF65F7C337C37C24B045
Content-Type: text/x-patch; charset=UTF-8;
name="0006-add-sort_mode-opclass-parameter-20210112.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0006-add-sort_mode-opclass-parameter-20210112.patch"
^ permalink raw reply [nested|flat] 24+ messages in thread
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw)
---
doc/src/sgml/ref/create_index.sgml | 2 +-
src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++----------
src/test/regress/expected/brin_bloom.out | 14 ++--
src/test/regress/sql/brin_bloom.sql | 6 +-
4 files changed, 60 insertions(+), 46 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 8db10b7b1e..244e5834d8 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class=
equal to -1, the number of distinct non-null is assumed linear with
the maximum possible number of tuples in the block range (about 290
rows per block). The default values is <literal>-0.1</literal>, and
- the minimum number of distinct non-null values is <literal>128</literal>.
+ the minimum number of distinct non-null values is <literal>16</literal>.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index b7aa6d9f11..ffeb459d3e 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -8,12 +8,12 @@
*
* A BRIN opclass summarizing page range into a bloom filter.
*
- * Bloom filters allow efficient test whether a given page range contains
+ * Bloom filters allow efficient testing whether a given page range contains
* a particular value. Therefore, if we summarize each page range into a
- * bloom filter, we can easily and cheaply test wheter it containst values
+ * bloom filter, we can easily and cheaply test wheter it contains values
* we get later.
*
- * The index only supports equality operator, similarly to hash indexes.
+ * The index only supports equality operators, similarly to hash indexes.
* BRIN bloom indexes are however much smaller, and support only bitmap
* scans.
*
@@ -51,9 +51,9 @@
* the bloom filter. On the other hand, we want to keep the index as small
* as possible - that's one of the basic advantages of BRIN indexes.
*
- * The number of distinct elements (in a page range) depends on the data,
- * we can consider it fixed. This simplifies the trade-off to just false
- * positive rate vs. size.
+ * Although the number of distinct elements (in a page range) depends on
+ * the data, we can consider it fixed. This simplifies the trade-off to
+ * just false positive rate vs. size.
*
* At the page range level, false positive rate is a probability the bloom
* filter matches a random value. For the whole index (with sufficiently
@@ -65,7 +65,7 @@
* the bitmap is inherently random, compression can't reliably help here.
* To reduce the size of a filter (to fit to a page), we have to either
* accept higher false positive rate (undesirable), or reduce the number
- * of distinct items to be stored in the filter. We can't quite the input
+ * of distinct items to be stored in the filter. We can't alter the input
* data, of course, but we may make the BRIN page ranges smaller - instead
* of the default 128 pages (1MB) we may build index with 16-page ranges,
* or something like that. This does help even for random data sets, as
@@ -87,7 +87,8 @@
* not entirely clear how to distrubute the space between those columns.
*
* The current logic, implemented in brin_bloom_get_ndistinct, attempts to
- * make some basic sizing decisions, based on the table ndistinct estimate.
+ * make some basic sizing decisions, based on the size of BRIN ranges, and
+ * the maximum number of rows per range.
*
*
* sort vs. hash
@@ -200,10 +201,20 @@ typedef struct BloomOptions
/*
* Allowed range and default value for the false positive range. The exact
- * values are somewhat arbitrary.
+ * values are somewhat arbitrary, but were chosen considering the various
+ * parameters (size of filter vs. page size, etc.).
+ *
+ * The lower the false-positive rate, the more accurate the filter is, but
+ * it also gets larger - at some point this eliminates the main advantage
+ * of BRIN indexes, which is the tiny size. At 0.01% the index is about
+ * 10% of the table (assuming 290 distinct values per 8kB page).
+ *
+ * On the other hand, as the false-positive rate increases, larger part of
+ * the table has to be scanned due to mismatches - at 25% we're probably
+ * close to sequential scan being cheaper.
*/
-#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */
-#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */
+#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
+#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
#define BloomGetNDistinctPerRange(opts) \
@@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate)
Assert(ndistinct > 0);
Assert((false_positive_rate > 0) && (false_positive_rate < 1.0));
- m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0)))));
+ /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
+ m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
/* round m to whole bytes */
m = ((m + 7) / 8) * 8;
+ /*
+ * Reject filters that are obviously too large to store on a page.
+ *
+ * We do expect the bloom filter to eventually switch to hashing mode,
+ * and it's bound to be almost perfectly random, so not compressible.
+ */
+ if ((m/8) > BLCKSZ)
+ elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ);
+
/*
* round(log(2.0) * m / ndistinct), but assume round() may not be
* available on Windows
@@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate)
k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
/*
- * Allocate the bloom filter with a minimum size 64B (about 40B in the
- * bitmap part). We require space at least for the header.
- *
- * XXX Maybe the 64B min size is not really needed?
+ * Allocate the bloom filter (initially it's just a header, we'll make
+ * it larger as needed).
*/
- len = Max(offsetof(BloomFilter, data), 64);
-
- /* Reject filters that are obviously too large to store on a page. */
- if (len > BLCKSZ)
- elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ);
+ len = offsetof(BloomFilter, data);
filter = (BloomFilter *) palloc0(len);
@@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* brin_bloom_get_ndistinct
* Determine the ndistinct value used to size bloom filter.
*
- * Tweak the ndistinct value based on the pagesPerRange value. First,
+ * Adjust the ndistinct value based on the pagesPerRange value. First,
* if it's negative, it's assumed to be relative to maximum number of
* tuples in the range (assuming each page gets MaxHeapTuplesPerPage
* tuples, which is likely a significant over-estimate). We also clamp
@@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* and compute the expected number of distinct values in a range. But
* that may be tricky due to data being sorted in various ways, so it
* seems better to rely on the upper estimate.
+ *
+ * XXX We might also calculate a better estimate of rows per BRIN range,
+ * instead of using MaxHeapTuplesPerPage (which probably produces values
+ * much higher than reality).
*/
static int
brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
@@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
return (int) ndistinct;
}
-static double
-brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts)
-{
- return BloomGetFalsePositiveRate(opts);
-}
/*
* Examine the given index tuple (which contains partial status of a certain
@@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS)
if (column->bv_allnulls)
{
filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
- brin_bloom_get_fp_rate(bdesc, opts));
+ BloomGetFalsePositiveRate(opts));
column->bv_values[0] = PointerGetDatum(filter);
column->bv_allnulls = false;
updated = true;
@@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS)
* Cache and return inclusion opclass support procedure
*
* Return the procedure corresponding to the given function support number
- * or null if it is not exists.
+ * or null if it does not exists.
*/
static FmgrInfo *
bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
@@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
initStringInfo(&str);
appendStringInfoChar(&str, '{');
- /*
- * XXX not sure the detoasting is necessary (probably not, this
- * can only be in an index).
- */
- filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0));
+ /* Detoasting not needed (this can only be in an index). */
+ filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0);
if (BLOOM_IS_HASHED(filter))
{
@@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
}
else
{
+ /*
+ * XXX Maybe include the sorted/unsorted values? Seems a bit too
+ * much useless detail (internal hash values).
+ */
appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u",
filter->nvalues, filter->nsorted);
- /* TODO include the sorted/unsorted values */
}
appendStringInfoChar(&str, '}');
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
index 19b866283a..24ea5f6e42 100644
--- a/src/test/regress/expected/brin_bloom.out
+++ b/src/test/regress/expected/brin_bloom.out
@@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
);
ERROR: value -1.1 out of bounds for option "n_distinct_per_range"
DETAIL: Valid values are between "-1.000000" and "2147483647.000000".
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
-ERROR: value 0.0009 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.00009 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
-ERROR: value 0.11 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.26 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops,
charcol char_bloom_ops,
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
index 3c2ef56316..d587f3962f 100644
--- a/src/test/regress/sql/brin_bloom.sql
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops(n_distinct_per_range = -1.1)
);
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
--
2.26.2
--------------CF71AF65F7C337C37C24B045
Content-Type: text/x-patch; charset=UTF-8;
name="0006-add-sort_mode-opclass-parameter-20210112.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0006-add-sort_mode-opclass-parameter-20210112.patch"
^ permalink raw reply [nested|flat] 24+ messages in thread
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw)
---
doc/src/sgml/ref/create_index.sgml | 2 +-
src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++----------
src/test/regress/expected/brin_bloom.out | 14 ++--
src/test/regress/sql/brin_bloom.sql | 6 +-
4 files changed, 60 insertions(+), 46 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 8db10b7b1e..244e5834d8 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class=
equal to -1, the number of distinct non-null is assumed linear with
the maximum possible number of tuples in the block range (about 290
rows per block). The default values is <literal>-0.1</literal>, and
- the minimum number of distinct non-null values is <literal>128</literal>.
+ the minimum number of distinct non-null values is <literal>16</literal>.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index b7aa6d9f11..ffeb459d3e 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -8,12 +8,12 @@
*
* A BRIN opclass summarizing page range into a bloom filter.
*
- * Bloom filters allow efficient test whether a given page range contains
+ * Bloom filters allow efficient testing whether a given page range contains
* a particular value. Therefore, if we summarize each page range into a
- * bloom filter, we can easily and cheaply test wheter it containst values
+ * bloom filter, we can easily and cheaply test wheter it contains values
* we get later.
*
- * The index only supports equality operator, similarly to hash indexes.
+ * The index only supports equality operators, similarly to hash indexes.
* BRIN bloom indexes are however much smaller, and support only bitmap
* scans.
*
@@ -51,9 +51,9 @@
* the bloom filter. On the other hand, we want to keep the index as small
* as possible - that's one of the basic advantages of BRIN indexes.
*
- * The number of distinct elements (in a page range) depends on the data,
- * we can consider it fixed. This simplifies the trade-off to just false
- * positive rate vs. size.
+ * Although the number of distinct elements (in a page range) depends on
+ * the data, we can consider it fixed. This simplifies the trade-off to
+ * just false positive rate vs. size.
*
* At the page range level, false positive rate is a probability the bloom
* filter matches a random value. For the whole index (with sufficiently
@@ -65,7 +65,7 @@
* the bitmap is inherently random, compression can't reliably help here.
* To reduce the size of a filter (to fit to a page), we have to either
* accept higher false positive rate (undesirable), or reduce the number
- * of distinct items to be stored in the filter. We can't quite the input
+ * of distinct items to be stored in the filter. We can't alter the input
* data, of course, but we may make the BRIN page ranges smaller - instead
* of the default 128 pages (1MB) we may build index with 16-page ranges,
* or something like that. This does help even for random data sets, as
@@ -87,7 +87,8 @@
* not entirely clear how to distrubute the space between those columns.
*
* The current logic, implemented in brin_bloom_get_ndistinct, attempts to
- * make some basic sizing decisions, based on the table ndistinct estimate.
+ * make some basic sizing decisions, based on the size of BRIN ranges, and
+ * the maximum number of rows per range.
*
*
* sort vs. hash
@@ -200,10 +201,20 @@ typedef struct BloomOptions
/*
* Allowed range and default value for the false positive range. The exact
- * values are somewhat arbitrary.
+ * values are somewhat arbitrary, but were chosen considering the various
+ * parameters (size of filter vs. page size, etc.).
+ *
+ * The lower the false-positive rate, the more accurate the filter is, but
+ * it also gets larger - at some point this eliminates the main advantage
+ * of BRIN indexes, which is the tiny size. At 0.01% the index is about
+ * 10% of the table (assuming 290 distinct values per 8kB page).
+ *
+ * On the other hand, as the false-positive rate increases, larger part of
+ * the table has to be scanned due to mismatches - at 25% we're probably
+ * close to sequential scan being cheaper.
*/
-#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */
-#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */
+#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
+#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
#define BloomGetNDistinctPerRange(opts) \
@@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate)
Assert(ndistinct > 0);
Assert((false_positive_rate > 0) && (false_positive_rate < 1.0));
- m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0)))));
+ /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
+ m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
/* round m to whole bytes */
m = ((m + 7) / 8) * 8;
+ /*
+ * Reject filters that are obviously too large to store on a page.
+ *
+ * We do expect the bloom filter to eventually switch to hashing mode,
+ * and it's bound to be almost perfectly random, so not compressible.
+ */
+ if ((m/8) > BLCKSZ)
+ elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ);
+
/*
* round(log(2.0) * m / ndistinct), but assume round() may not be
* available on Windows
@@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate)
k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
/*
- * Allocate the bloom filter with a minimum size 64B (about 40B in the
- * bitmap part). We require space at least for the header.
- *
- * XXX Maybe the 64B min size is not really needed?
+ * Allocate the bloom filter (initially it's just a header, we'll make
+ * it larger as needed).
*/
- len = Max(offsetof(BloomFilter, data), 64);
-
- /* Reject filters that are obviously too large to store on a page. */
- if (len > BLCKSZ)
- elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ);
+ len = offsetof(BloomFilter, data);
filter = (BloomFilter *) palloc0(len);
@@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* brin_bloom_get_ndistinct
* Determine the ndistinct value used to size bloom filter.
*
- * Tweak the ndistinct value based on the pagesPerRange value. First,
+ * Adjust the ndistinct value based on the pagesPerRange value. First,
* if it's negative, it's assumed to be relative to maximum number of
* tuples in the range (assuming each page gets MaxHeapTuplesPerPage
* tuples, which is likely a significant over-estimate). We also clamp
@@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* and compute the expected number of distinct values in a range. But
* that may be tricky due to data being sorted in various ways, so it
* seems better to rely on the upper estimate.
+ *
+ * XXX We might also calculate a better estimate of rows per BRIN range,
+ * instead of using MaxHeapTuplesPerPage (which probably produces values
+ * much higher than reality).
*/
static int
brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
@@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
return (int) ndistinct;
}
-static double
-brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts)
-{
- return BloomGetFalsePositiveRate(opts);
-}
/*
* Examine the given index tuple (which contains partial status of a certain
@@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS)
if (column->bv_allnulls)
{
filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
- brin_bloom_get_fp_rate(bdesc, opts));
+ BloomGetFalsePositiveRate(opts));
column->bv_values[0] = PointerGetDatum(filter);
column->bv_allnulls = false;
updated = true;
@@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS)
* Cache and return inclusion opclass support procedure
*
* Return the procedure corresponding to the given function support number
- * or null if it is not exists.
+ * or null if it does not exists.
*/
static FmgrInfo *
bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
@@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
initStringInfo(&str);
appendStringInfoChar(&str, '{');
- /*
- * XXX not sure the detoasting is necessary (probably not, this
- * can only be in an index).
- */
- filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0));
+ /* Detoasting not needed (this can only be in an index). */
+ filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0);
if (BLOOM_IS_HASHED(filter))
{
@@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
}
else
{
+ /*
+ * XXX Maybe include the sorted/unsorted values? Seems a bit too
+ * much useless detail (internal hash values).
+ */
appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u",
filter->nvalues, filter->nsorted);
- /* TODO include the sorted/unsorted values */
}
appendStringInfoChar(&str, '}');
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
index 19b866283a..24ea5f6e42 100644
--- a/src/test/regress/expected/brin_bloom.out
+++ b/src/test/regress/expected/brin_bloom.out
@@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
);
ERROR: value -1.1 out of bounds for option "n_distinct_per_range"
DETAIL: Valid values are between "-1.000000" and "2147483647.000000".
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
-ERROR: value 0.0009 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.00009 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
-ERROR: value 0.11 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.26 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops,
charcol char_bloom_ops,
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
index 3c2ef56316..d587f3962f 100644
--- a/src/test/regress/sql/brin_bloom.sql
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops(n_distinct_per_range = -1.1)
);
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
--
2.26.2
--------------CF71AF65F7C337C37C24B045
Content-Type: text/x-patch; charset=UTF-8;
name="0006-add-sort_mode-opclass-parameter-20210112.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0006-add-sort_mode-opclass-parameter-20210112.patch"
^ permalink raw reply [nested|flat] 24+ messages in thread
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw)
---
doc/src/sgml/ref/create_index.sgml | 2 +-
src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++----------
src/test/regress/expected/brin_bloom.out | 14 ++--
src/test/regress/sql/brin_bloom.sql | 6 +-
4 files changed, 60 insertions(+), 46 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 8db10b7b1e..244e5834d8 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class=
equal to -1, the number of distinct non-null is assumed linear with
the maximum possible number of tuples in the block range (about 290
rows per block). The default values is <literal>-0.1</literal>, and
- the minimum number of distinct non-null values is <literal>128</literal>.
+ the minimum number of distinct non-null values is <literal>16</literal>.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index b7aa6d9f11..ffeb459d3e 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -8,12 +8,12 @@
*
* A BRIN opclass summarizing page range into a bloom filter.
*
- * Bloom filters allow efficient test whether a given page range contains
+ * Bloom filters allow efficient testing whether a given page range contains
* a particular value. Therefore, if we summarize each page range into a
- * bloom filter, we can easily and cheaply test wheter it containst values
+ * bloom filter, we can easily and cheaply test wheter it contains values
* we get later.
*
- * The index only supports equality operator, similarly to hash indexes.
+ * The index only supports equality operators, similarly to hash indexes.
* BRIN bloom indexes are however much smaller, and support only bitmap
* scans.
*
@@ -51,9 +51,9 @@
* the bloom filter. On the other hand, we want to keep the index as small
* as possible - that's one of the basic advantages of BRIN indexes.
*
- * The number of distinct elements (in a page range) depends on the data,
- * we can consider it fixed. This simplifies the trade-off to just false
- * positive rate vs. size.
+ * Although the number of distinct elements (in a page range) depends on
+ * the data, we can consider it fixed. This simplifies the trade-off to
+ * just false positive rate vs. size.
*
* At the page range level, false positive rate is a probability the bloom
* filter matches a random value. For the whole index (with sufficiently
@@ -65,7 +65,7 @@
* the bitmap is inherently random, compression can't reliably help here.
* To reduce the size of a filter (to fit to a page), we have to either
* accept higher false positive rate (undesirable), or reduce the number
- * of distinct items to be stored in the filter. We can't quite the input
+ * of distinct items to be stored in the filter. We can't alter the input
* data, of course, but we may make the BRIN page ranges smaller - instead
* of the default 128 pages (1MB) we may build index with 16-page ranges,
* or something like that. This does help even for random data sets, as
@@ -87,7 +87,8 @@
* not entirely clear how to distrubute the space between those columns.
*
* The current logic, implemented in brin_bloom_get_ndistinct, attempts to
- * make some basic sizing decisions, based on the table ndistinct estimate.
+ * make some basic sizing decisions, based on the size of BRIN ranges, and
+ * the maximum number of rows per range.
*
*
* sort vs. hash
@@ -200,10 +201,20 @@ typedef struct BloomOptions
/*
* Allowed range and default value for the false positive range. The exact
- * values are somewhat arbitrary.
+ * values are somewhat arbitrary, but were chosen considering the various
+ * parameters (size of filter vs. page size, etc.).
+ *
+ * The lower the false-positive rate, the more accurate the filter is, but
+ * it also gets larger - at some point this eliminates the main advantage
+ * of BRIN indexes, which is the tiny size. At 0.01% the index is about
+ * 10% of the table (assuming 290 distinct values per 8kB page).
+ *
+ * On the other hand, as the false-positive rate increases, larger part of
+ * the table has to be scanned due to mismatches - at 25% we're probably
+ * close to sequential scan being cheaper.
*/
-#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */
-#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */
+#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
+#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
#define BloomGetNDistinctPerRange(opts) \
@@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate)
Assert(ndistinct > 0);
Assert((false_positive_rate > 0) && (false_positive_rate < 1.0));
- m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0)))));
+ /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
+ m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
/* round m to whole bytes */
m = ((m + 7) / 8) * 8;
+ /*
+ * Reject filters that are obviously too large to store on a page.
+ *
+ * We do expect the bloom filter to eventually switch to hashing mode,
+ * and it's bound to be almost perfectly random, so not compressible.
+ */
+ if ((m/8) > BLCKSZ)
+ elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ);
+
/*
* round(log(2.0) * m / ndistinct), but assume round() may not be
* available on Windows
@@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate)
k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
/*
- * Allocate the bloom filter with a minimum size 64B (about 40B in the
- * bitmap part). We require space at least for the header.
- *
- * XXX Maybe the 64B min size is not really needed?
+ * Allocate the bloom filter (initially it's just a header, we'll make
+ * it larger as needed).
*/
- len = Max(offsetof(BloomFilter, data), 64);
-
- /* Reject filters that are obviously too large to store on a page. */
- if (len > BLCKSZ)
- elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ);
+ len = offsetof(BloomFilter, data);
filter = (BloomFilter *) palloc0(len);
@@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* brin_bloom_get_ndistinct
* Determine the ndistinct value used to size bloom filter.
*
- * Tweak the ndistinct value based on the pagesPerRange value. First,
+ * Adjust the ndistinct value based on the pagesPerRange value. First,
* if it's negative, it's assumed to be relative to maximum number of
* tuples in the range (assuming each page gets MaxHeapTuplesPerPage
* tuples, which is likely a significant over-estimate). We also clamp
@@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* and compute the expected number of distinct values in a range. But
* that may be tricky due to data being sorted in various ways, so it
* seems better to rely on the upper estimate.
+ *
+ * XXX We might also calculate a better estimate of rows per BRIN range,
+ * instead of using MaxHeapTuplesPerPage (which probably produces values
+ * much higher than reality).
*/
static int
brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
@@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
return (int) ndistinct;
}
-static double
-brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts)
-{
- return BloomGetFalsePositiveRate(opts);
-}
/*
* Examine the given index tuple (which contains partial status of a certain
@@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS)
if (column->bv_allnulls)
{
filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
- brin_bloom_get_fp_rate(bdesc, opts));
+ BloomGetFalsePositiveRate(opts));
column->bv_values[0] = PointerGetDatum(filter);
column->bv_allnulls = false;
updated = true;
@@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS)
* Cache and return inclusion opclass support procedure
*
* Return the procedure corresponding to the given function support number
- * or null if it is not exists.
+ * or null if it does not exists.
*/
static FmgrInfo *
bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
@@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
initStringInfo(&str);
appendStringInfoChar(&str, '{');
- /*
- * XXX not sure the detoasting is necessary (probably not, this
- * can only be in an index).
- */
- filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0));
+ /* Detoasting not needed (this can only be in an index). */
+ filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0);
if (BLOOM_IS_HASHED(filter))
{
@@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
}
else
{
+ /*
+ * XXX Maybe include the sorted/unsorted values? Seems a bit too
+ * much useless detail (internal hash values).
+ */
appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u",
filter->nvalues, filter->nsorted);
- /* TODO include the sorted/unsorted values */
}
appendStringInfoChar(&str, '}');
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
index 19b866283a..24ea5f6e42 100644
--- a/src/test/regress/expected/brin_bloom.out
+++ b/src/test/regress/expected/brin_bloom.out
@@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
);
ERROR: value -1.1 out of bounds for option "n_distinct_per_range"
DETAIL: Valid values are between "-1.000000" and "2147483647.000000".
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
-ERROR: value 0.0009 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.00009 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
-ERROR: value 0.11 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.26 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops,
charcol char_bloom_ops,
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
index 3c2ef56316..d587f3962f 100644
--- a/src/test/regress/sql/brin_bloom.sql
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops(n_distinct_per_range = -1.1)
);
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
--
2.26.2
--------------CF71AF65F7C337C37C24B045
Content-Type: text/x-patch; charset=UTF-8;
name="0006-add-sort_mode-opclass-parameter-20210112.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0006-add-sort_mode-opclass-parameter-20210112.patch"
^ permalink raw reply [nested|flat] 24+ messages in thread
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw)
---
doc/src/sgml/ref/create_index.sgml | 2 +-
src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++----------
src/test/regress/expected/brin_bloom.out | 14 ++--
src/test/regress/sql/brin_bloom.sql | 6 +-
4 files changed, 60 insertions(+), 46 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 8db10b7b1e..244e5834d8 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class=
equal to -1, the number of distinct non-null is assumed linear with
the maximum possible number of tuples in the block range (about 290
rows per block). The default values is <literal>-0.1</literal>, and
- the minimum number of distinct non-null values is <literal>128</literal>.
+ the minimum number of distinct non-null values is <literal>16</literal>.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index b7aa6d9f11..ffeb459d3e 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -8,12 +8,12 @@
*
* A BRIN opclass summarizing page range into a bloom filter.
*
- * Bloom filters allow efficient test whether a given page range contains
+ * Bloom filters allow efficient testing whether a given page range contains
* a particular value. Therefore, if we summarize each page range into a
- * bloom filter, we can easily and cheaply test wheter it containst values
+ * bloom filter, we can easily and cheaply test wheter it contains values
* we get later.
*
- * The index only supports equality operator, similarly to hash indexes.
+ * The index only supports equality operators, similarly to hash indexes.
* BRIN bloom indexes are however much smaller, and support only bitmap
* scans.
*
@@ -51,9 +51,9 @@
* the bloom filter. On the other hand, we want to keep the index as small
* as possible - that's one of the basic advantages of BRIN indexes.
*
- * The number of distinct elements (in a page range) depends on the data,
- * we can consider it fixed. This simplifies the trade-off to just false
- * positive rate vs. size.
+ * Although the number of distinct elements (in a page range) depends on
+ * the data, we can consider it fixed. This simplifies the trade-off to
+ * just false positive rate vs. size.
*
* At the page range level, false positive rate is a probability the bloom
* filter matches a random value. For the whole index (with sufficiently
@@ -65,7 +65,7 @@
* the bitmap is inherently random, compression can't reliably help here.
* To reduce the size of a filter (to fit to a page), we have to either
* accept higher false positive rate (undesirable), or reduce the number
- * of distinct items to be stored in the filter. We can't quite the input
+ * of distinct items to be stored in the filter. We can't alter the input
* data, of course, but we may make the BRIN page ranges smaller - instead
* of the default 128 pages (1MB) we may build index with 16-page ranges,
* or something like that. This does help even for random data sets, as
@@ -87,7 +87,8 @@
* not entirely clear how to distrubute the space between those columns.
*
* The current logic, implemented in brin_bloom_get_ndistinct, attempts to
- * make some basic sizing decisions, based on the table ndistinct estimate.
+ * make some basic sizing decisions, based on the size of BRIN ranges, and
+ * the maximum number of rows per range.
*
*
* sort vs. hash
@@ -200,10 +201,20 @@ typedef struct BloomOptions
/*
* Allowed range and default value for the false positive range. The exact
- * values are somewhat arbitrary.
+ * values are somewhat arbitrary, but were chosen considering the various
+ * parameters (size of filter vs. page size, etc.).
+ *
+ * The lower the false-positive rate, the more accurate the filter is, but
+ * it also gets larger - at some point this eliminates the main advantage
+ * of BRIN indexes, which is the tiny size. At 0.01% the index is about
+ * 10% of the table (assuming 290 distinct values per 8kB page).
+ *
+ * On the other hand, as the false-positive rate increases, larger part of
+ * the table has to be scanned due to mismatches - at 25% we're probably
+ * close to sequential scan being cheaper.
*/
-#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */
-#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */
+#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
+#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
#define BloomGetNDistinctPerRange(opts) \
@@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate)
Assert(ndistinct > 0);
Assert((false_positive_rate > 0) && (false_positive_rate < 1.0));
- m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0)))));
+ /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
+ m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
/* round m to whole bytes */
m = ((m + 7) / 8) * 8;
+ /*
+ * Reject filters that are obviously too large to store on a page.
+ *
+ * We do expect the bloom filter to eventually switch to hashing mode,
+ * and it's bound to be almost perfectly random, so not compressible.
+ */
+ if ((m/8) > BLCKSZ)
+ elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ);
+
/*
* round(log(2.0) * m / ndistinct), but assume round() may not be
* available on Windows
@@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate)
k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
/*
- * Allocate the bloom filter with a minimum size 64B (about 40B in the
- * bitmap part). We require space at least for the header.
- *
- * XXX Maybe the 64B min size is not really needed?
+ * Allocate the bloom filter (initially it's just a header, we'll make
+ * it larger as needed).
*/
- len = Max(offsetof(BloomFilter, data), 64);
-
- /* Reject filters that are obviously too large to store on a page. */
- if (len > BLCKSZ)
- elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ);
+ len = offsetof(BloomFilter, data);
filter = (BloomFilter *) palloc0(len);
@@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* brin_bloom_get_ndistinct
* Determine the ndistinct value used to size bloom filter.
*
- * Tweak the ndistinct value based on the pagesPerRange value. First,
+ * Adjust the ndistinct value based on the pagesPerRange value. First,
* if it's negative, it's assumed to be relative to maximum number of
* tuples in the range (assuming each page gets MaxHeapTuplesPerPage
* tuples, which is likely a significant over-estimate). We also clamp
@@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* and compute the expected number of distinct values in a range. But
* that may be tricky due to data being sorted in various ways, so it
* seems better to rely on the upper estimate.
+ *
+ * XXX We might also calculate a better estimate of rows per BRIN range,
+ * instead of using MaxHeapTuplesPerPage (which probably produces values
+ * much higher than reality).
*/
static int
brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
@@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
return (int) ndistinct;
}
-static double
-brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts)
-{
- return BloomGetFalsePositiveRate(opts);
-}
/*
* Examine the given index tuple (which contains partial status of a certain
@@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS)
if (column->bv_allnulls)
{
filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
- brin_bloom_get_fp_rate(bdesc, opts));
+ BloomGetFalsePositiveRate(opts));
column->bv_values[0] = PointerGetDatum(filter);
column->bv_allnulls = false;
updated = true;
@@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS)
* Cache and return inclusion opclass support procedure
*
* Return the procedure corresponding to the given function support number
- * or null if it is not exists.
+ * or null if it does not exists.
*/
static FmgrInfo *
bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
@@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
initStringInfo(&str);
appendStringInfoChar(&str, '{');
- /*
- * XXX not sure the detoasting is necessary (probably not, this
- * can only be in an index).
- */
- filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0));
+ /* Detoasting not needed (this can only be in an index). */
+ filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0);
if (BLOOM_IS_HASHED(filter))
{
@@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
}
else
{
+ /*
+ * XXX Maybe include the sorted/unsorted values? Seems a bit too
+ * much useless detail (internal hash values).
+ */
appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u",
filter->nvalues, filter->nsorted);
- /* TODO include the sorted/unsorted values */
}
appendStringInfoChar(&str, '}');
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
index 19b866283a..24ea5f6e42 100644
--- a/src/test/regress/expected/brin_bloom.out
+++ b/src/test/regress/expected/brin_bloom.out
@@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
);
ERROR: value -1.1 out of bounds for option "n_distinct_per_range"
DETAIL: Valid values are between "-1.000000" and "2147483647.000000".
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
-ERROR: value 0.0009 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.00009 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
-ERROR: value 0.11 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.26 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops,
charcol char_bloom_ops,
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
index 3c2ef56316..d587f3962f 100644
--- a/src/test/regress/sql/brin_bloom.sql
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops(n_distinct_per_range = -1.1)
);
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
--
2.26.2
--------------CF71AF65F7C337C37C24B045
Content-Type: text/x-patch; charset=UTF-8;
name="0006-add-sort_mode-opclass-parameter-20210112.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0006-add-sort_mode-opclass-parameter-20210112.patch"
^ permalink raw reply [nested|flat] 24+ messages in thread
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw)
---
doc/src/sgml/ref/create_index.sgml | 2 +-
src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++----------
src/test/regress/expected/brin_bloom.out | 14 ++--
src/test/regress/sql/brin_bloom.sql | 6 +-
4 files changed, 60 insertions(+), 46 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 8db10b7b1e..244e5834d8 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class=
equal to -1, the number of distinct non-null is assumed linear with
the maximum possible number of tuples in the block range (about 290
rows per block). The default values is <literal>-0.1</literal>, and
- the minimum number of distinct non-null values is <literal>128</literal>.
+ the minimum number of distinct non-null values is <literal>16</literal>.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index b7aa6d9f11..ffeb459d3e 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -8,12 +8,12 @@
*
* A BRIN opclass summarizing page range into a bloom filter.
*
- * Bloom filters allow efficient test whether a given page range contains
+ * Bloom filters allow efficient testing whether a given page range contains
* a particular value. Therefore, if we summarize each page range into a
- * bloom filter, we can easily and cheaply test wheter it containst values
+ * bloom filter, we can easily and cheaply test wheter it contains values
* we get later.
*
- * The index only supports equality operator, similarly to hash indexes.
+ * The index only supports equality operators, similarly to hash indexes.
* BRIN bloom indexes are however much smaller, and support only bitmap
* scans.
*
@@ -51,9 +51,9 @@
* the bloom filter. On the other hand, we want to keep the index as small
* as possible - that's one of the basic advantages of BRIN indexes.
*
- * The number of distinct elements (in a page range) depends on the data,
- * we can consider it fixed. This simplifies the trade-off to just false
- * positive rate vs. size.
+ * Although the number of distinct elements (in a page range) depends on
+ * the data, we can consider it fixed. This simplifies the trade-off to
+ * just false positive rate vs. size.
*
* At the page range level, false positive rate is a probability the bloom
* filter matches a random value. For the whole index (with sufficiently
@@ -65,7 +65,7 @@
* the bitmap is inherently random, compression can't reliably help here.
* To reduce the size of a filter (to fit to a page), we have to either
* accept higher false positive rate (undesirable), or reduce the number
- * of distinct items to be stored in the filter. We can't quite the input
+ * of distinct items to be stored in the filter. We can't alter the input
* data, of course, but we may make the BRIN page ranges smaller - instead
* of the default 128 pages (1MB) we may build index with 16-page ranges,
* or something like that. This does help even for random data sets, as
@@ -87,7 +87,8 @@
* not entirely clear how to distrubute the space between those columns.
*
* The current logic, implemented in brin_bloom_get_ndistinct, attempts to
- * make some basic sizing decisions, based on the table ndistinct estimate.
+ * make some basic sizing decisions, based on the size of BRIN ranges, and
+ * the maximum number of rows per range.
*
*
* sort vs. hash
@@ -200,10 +201,20 @@ typedef struct BloomOptions
/*
* Allowed range and default value for the false positive range. The exact
- * values are somewhat arbitrary.
+ * values are somewhat arbitrary, but were chosen considering the various
+ * parameters (size of filter vs. page size, etc.).
+ *
+ * The lower the false-positive rate, the more accurate the filter is, but
+ * it also gets larger - at some point this eliminates the main advantage
+ * of BRIN indexes, which is the tiny size. At 0.01% the index is about
+ * 10% of the table (assuming 290 distinct values per 8kB page).
+ *
+ * On the other hand, as the false-positive rate increases, larger part of
+ * the table has to be scanned due to mismatches - at 25% we're probably
+ * close to sequential scan being cheaper.
*/
-#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */
-#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */
+#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
+#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
#define BloomGetNDistinctPerRange(opts) \
@@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate)
Assert(ndistinct > 0);
Assert((false_positive_rate > 0) && (false_positive_rate < 1.0));
- m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0)))));
+ /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
+ m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
/* round m to whole bytes */
m = ((m + 7) / 8) * 8;
+ /*
+ * Reject filters that are obviously too large to store on a page.
+ *
+ * We do expect the bloom filter to eventually switch to hashing mode,
+ * and it's bound to be almost perfectly random, so not compressible.
+ */
+ if ((m/8) > BLCKSZ)
+ elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ);
+
/*
* round(log(2.0) * m / ndistinct), but assume round() may not be
* available on Windows
@@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate)
k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
/*
- * Allocate the bloom filter with a minimum size 64B (about 40B in the
- * bitmap part). We require space at least for the header.
- *
- * XXX Maybe the 64B min size is not really needed?
+ * Allocate the bloom filter (initially it's just a header, we'll make
+ * it larger as needed).
*/
- len = Max(offsetof(BloomFilter, data), 64);
-
- /* Reject filters that are obviously too large to store on a page. */
- if (len > BLCKSZ)
- elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ);
+ len = offsetof(BloomFilter, data);
filter = (BloomFilter *) palloc0(len);
@@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* brin_bloom_get_ndistinct
* Determine the ndistinct value used to size bloom filter.
*
- * Tweak the ndistinct value based on the pagesPerRange value. First,
+ * Adjust the ndistinct value based on the pagesPerRange value. First,
* if it's negative, it's assumed to be relative to maximum number of
* tuples in the range (assuming each page gets MaxHeapTuplesPerPage
* tuples, which is likely a significant over-estimate). We also clamp
@@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* and compute the expected number of distinct values in a range. But
* that may be tricky due to data being sorted in various ways, so it
* seems better to rely on the upper estimate.
+ *
+ * XXX We might also calculate a better estimate of rows per BRIN range,
+ * instead of using MaxHeapTuplesPerPage (which probably produces values
+ * much higher than reality).
*/
static int
brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
@@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
return (int) ndistinct;
}
-static double
-brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts)
-{
- return BloomGetFalsePositiveRate(opts);
-}
/*
* Examine the given index tuple (which contains partial status of a certain
@@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS)
if (column->bv_allnulls)
{
filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
- brin_bloom_get_fp_rate(bdesc, opts));
+ BloomGetFalsePositiveRate(opts));
column->bv_values[0] = PointerGetDatum(filter);
column->bv_allnulls = false;
updated = true;
@@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS)
* Cache and return inclusion opclass support procedure
*
* Return the procedure corresponding to the given function support number
- * or null if it is not exists.
+ * or null if it does not exists.
*/
static FmgrInfo *
bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
@@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
initStringInfo(&str);
appendStringInfoChar(&str, '{');
- /*
- * XXX not sure the detoasting is necessary (probably not, this
- * can only be in an index).
- */
- filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0));
+ /* Detoasting not needed (this can only be in an index). */
+ filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0);
if (BLOOM_IS_HASHED(filter))
{
@@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
}
else
{
+ /*
+ * XXX Maybe include the sorted/unsorted values? Seems a bit too
+ * much useless detail (internal hash values).
+ */
appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u",
filter->nvalues, filter->nsorted);
- /* TODO include the sorted/unsorted values */
}
appendStringInfoChar(&str, '}');
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
index 19b866283a..24ea5f6e42 100644
--- a/src/test/regress/expected/brin_bloom.out
+++ b/src/test/regress/expected/brin_bloom.out
@@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
);
ERROR: value -1.1 out of bounds for option "n_distinct_per_range"
DETAIL: Valid values are between "-1.000000" and "2147483647.000000".
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
-ERROR: value 0.0009 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.00009 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
-ERROR: value 0.11 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.26 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops,
charcol char_bloom_ops,
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
index 3c2ef56316..d587f3962f 100644
--- a/src/test/regress/sql/brin_bloom.sql
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops(n_distinct_per_range = -1.1)
);
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
--
2.26.2
--------------CF71AF65F7C337C37C24B045
Content-Type: text/x-patch; charset=UTF-8;
name="0006-add-sort_mode-opclass-parameter-20210112.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0006-add-sort_mode-opclass-parameter-20210112.patch"
^ permalink raw reply [nested|flat] 24+ messages in thread
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw)
---
doc/src/sgml/ref/create_index.sgml | 2 +-
src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++----------
src/test/regress/expected/brin_bloom.out | 14 ++--
src/test/regress/sql/brin_bloom.sql | 6 +-
4 files changed, 60 insertions(+), 46 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 8db10b7b1e..244e5834d8 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class=
equal to -1, the number of distinct non-null is assumed linear with
the maximum possible number of tuples in the block range (about 290
rows per block). The default values is <literal>-0.1</literal>, and
- the minimum number of distinct non-null values is <literal>128</literal>.
+ the minimum number of distinct non-null values is <literal>16</literal>.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index b7aa6d9f11..ffeb459d3e 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -8,12 +8,12 @@
*
* A BRIN opclass summarizing page range into a bloom filter.
*
- * Bloom filters allow efficient test whether a given page range contains
+ * Bloom filters allow efficient testing whether a given page range contains
* a particular value. Therefore, if we summarize each page range into a
- * bloom filter, we can easily and cheaply test wheter it containst values
+ * bloom filter, we can easily and cheaply test wheter it contains values
* we get later.
*
- * The index only supports equality operator, similarly to hash indexes.
+ * The index only supports equality operators, similarly to hash indexes.
* BRIN bloom indexes are however much smaller, and support only bitmap
* scans.
*
@@ -51,9 +51,9 @@
* the bloom filter. On the other hand, we want to keep the index as small
* as possible - that's one of the basic advantages of BRIN indexes.
*
- * The number of distinct elements (in a page range) depends on the data,
- * we can consider it fixed. This simplifies the trade-off to just false
- * positive rate vs. size.
+ * Although the number of distinct elements (in a page range) depends on
+ * the data, we can consider it fixed. This simplifies the trade-off to
+ * just false positive rate vs. size.
*
* At the page range level, false positive rate is a probability the bloom
* filter matches a random value. For the whole index (with sufficiently
@@ -65,7 +65,7 @@
* the bitmap is inherently random, compression can't reliably help here.
* To reduce the size of a filter (to fit to a page), we have to either
* accept higher false positive rate (undesirable), or reduce the number
- * of distinct items to be stored in the filter. We can't quite the input
+ * of distinct items to be stored in the filter. We can't alter the input
* data, of course, but we may make the BRIN page ranges smaller - instead
* of the default 128 pages (1MB) we may build index with 16-page ranges,
* or something like that. This does help even for random data sets, as
@@ -87,7 +87,8 @@
* not entirely clear how to distrubute the space between those columns.
*
* The current logic, implemented in brin_bloom_get_ndistinct, attempts to
- * make some basic sizing decisions, based on the table ndistinct estimate.
+ * make some basic sizing decisions, based on the size of BRIN ranges, and
+ * the maximum number of rows per range.
*
*
* sort vs. hash
@@ -200,10 +201,20 @@ typedef struct BloomOptions
/*
* Allowed range and default value for the false positive range. The exact
- * values are somewhat arbitrary.
+ * values are somewhat arbitrary, but were chosen considering the various
+ * parameters (size of filter vs. page size, etc.).
+ *
+ * The lower the false-positive rate, the more accurate the filter is, but
+ * it also gets larger - at some point this eliminates the main advantage
+ * of BRIN indexes, which is the tiny size. At 0.01% the index is about
+ * 10% of the table (assuming 290 distinct values per 8kB page).
+ *
+ * On the other hand, as the false-positive rate increases, larger part of
+ * the table has to be scanned due to mismatches - at 25% we're probably
+ * close to sequential scan being cheaper.
*/
-#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */
-#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */
+#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
+#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
#define BloomGetNDistinctPerRange(opts) \
@@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate)
Assert(ndistinct > 0);
Assert((false_positive_rate > 0) && (false_positive_rate < 1.0));
- m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0)))));
+ /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
+ m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
/* round m to whole bytes */
m = ((m + 7) / 8) * 8;
+ /*
+ * Reject filters that are obviously too large to store on a page.
+ *
+ * We do expect the bloom filter to eventually switch to hashing mode,
+ * and it's bound to be almost perfectly random, so not compressible.
+ */
+ if ((m/8) > BLCKSZ)
+ elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ);
+
/*
* round(log(2.0) * m / ndistinct), but assume round() may not be
* available on Windows
@@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate)
k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
/*
- * Allocate the bloom filter with a minimum size 64B (about 40B in the
- * bitmap part). We require space at least for the header.
- *
- * XXX Maybe the 64B min size is not really needed?
+ * Allocate the bloom filter (initially it's just a header, we'll make
+ * it larger as needed).
*/
- len = Max(offsetof(BloomFilter, data), 64);
-
- /* Reject filters that are obviously too large to store on a page. */
- if (len > BLCKSZ)
- elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ);
+ len = offsetof(BloomFilter, data);
filter = (BloomFilter *) palloc0(len);
@@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* brin_bloom_get_ndistinct
* Determine the ndistinct value used to size bloom filter.
*
- * Tweak the ndistinct value based on the pagesPerRange value. First,
+ * Adjust the ndistinct value based on the pagesPerRange value. First,
* if it's negative, it's assumed to be relative to maximum number of
* tuples in the range (assuming each page gets MaxHeapTuplesPerPage
* tuples, which is likely a significant over-estimate). We also clamp
@@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* and compute the expected number of distinct values in a range. But
* that may be tricky due to data being sorted in various ways, so it
* seems better to rely on the upper estimate.
+ *
+ * XXX We might also calculate a better estimate of rows per BRIN range,
+ * instead of using MaxHeapTuplesPerPage (which probably produces values
+ * much higher than reality).
*/
static int
brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
@@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
return (int) ndistinct;
}
-static double
-brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts)
-{
- return BloomGetFalsePositiveRate(opts);
-}
/*
* Examine the given index tuple (which contains partial status of a certain
@@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS)
if (column->bv_allnulls)
{
filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
- brin_bloom_get_fp_rate(bdesc, opts));
+ BloomGetFalsePositiveRate(opts));
column->bv_values[0] = PointerGetDatum(filter);
column->bv_allnulls = false;
updated = true;
@@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS)
* Cache and return inclusion opclass support procedure
*
* Return the procedure corresponding to the given function support number
- * or null if it is not exists.
+ * or null if it does not exists.
*/
static FmgrInfo *
bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
@@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
initStringInfo(&str);
appendStringInfoChar(&str, '{');
- /*
- * XXX not sure the detoasting is necessary (probably not, this
- * can only be in an index).
- */
- filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0));
+ /* Detoasting not needed (this can only be in an index). */
+ filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0);
if (BLOOM_IS_HASHED(filter))
{
@@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
}
else
{
+ /*
+ * XXX Maybe include the sorted/unsorted values? Seems a bit too
+ * much useless detail (internal hash values).
+ */
appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u",
filter->nvalues, filter->nsorted);
- /* TODO include the sorted/unsorted values */
}
appendStringInfoChar(&str, '}');
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
index 19b866283a..24ea5f6e42 100644
--- a/src/test/regress/expected/brin_bloom.out
+++ b/src/test/regress/expected/brin_bloom.out
@@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
);
ERROR: value -1.1 out of bounds for option "n_distinct_per_range"
DETAIL: Valid values are between "-1.000000" and "2147483647.000000".
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
-ERROR: value 0.0009 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.00009 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
-ERROR: value 0.11 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.26 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops,
charcol char_bloom_ops,
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
index 3c2ef56316..d587f3962f 100644
--- a/src/test/regress/sql/brin_bloom.sql
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops(n_distinct_per_range = -1.1)
);
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
--
2.26.2
--------------CF71AF65F7C337C37C24B045
Content-Type: text/x-patch; charset=UTF-8;
name="0006-add-sort_mode-opclass-parameter-20210112.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0006-add-sort_mode-opclass-parameter-20210112.patch"
^ permalink raw reply [nested|flat] 24+ messages in thread
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw)
---
doc/src/sgml/ref/create_index.sgml | 2 +-
src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++----------
src/test/regress/expected/brin_bloom.out | 14 ++--
src/test/regress/sql/brin_bloom.sql | 6 +-
4 files changed, 60 insertions(+), 46 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 8db10b7b1e..244e5834d8 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class=
equal to -1, the number of distinct non-null is assumed linear with
the maximum possible number of tuples in the block range (about 290
rows per block). The default values is <literal>-0.1</literal>, and
- the minimum number of distinct non-null values is <literal>128</literal>.
+ the minimum number of distinct non-null values is <literal>16</literal>.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index b7aa6d9f11..ffeb459d3e 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -8,12 +8,12 @@
*
* A BRIN opclass summarizing page range into a bloom filter.
*
- * Bloom filters allow efficient test whether a given page range contains
+ * Bloom filters allow efficient testing whether a given page range contains
* a particular value. Therefore, if we summarize each page range into a
- * bloom filter, we can easily and cheaply test wheter it containst values
+ * bloom filter, we can easily and cheaply test wheter it contains values
* we get later.
*
- * The index only supports equality operator, similarly to hash indexes.
+ * The index only supports equality operators, similarly to hash indexes.
* BRIN bloom indexes are however much smaller, and support only bitmap
* scans.
*
@@ -51,9 +51,9 @@
* the bloom filter. On the other hand, we want to keep the index as small
* as possible - that's one of the basic advantages of BRIN indexes.
*
- * The number of distinct elements (in a page range) depends on the data,
- * we can consider it fixed. This simplifies the trade-off to just false
- * positive rate vs. size.
+ * Although the number of distinct elements (in a page range) depends on
+ * the data, we can consider it fixed. This simplifies the trade-off to
+ * just false positive rate vs. size.
*
* At the page range level, false positive rate is a probability the bloom
* filter matches a random value. For the whole index (with sufficiently
@@ -65,7 +65,7 @@
* the bitmap is inherently random, compression can't reliably help here.
* To reduce the size of a filter (to fit to a page), we have to either
* accept higher false positive rate (undesirable), or reduce the number
- * of distinct items to be stored in the filter. We can't quite the input
+ * of distinct items to be stored in the filter. We can't alter the input
* data, of course, but we may make the BRIN page ranges smaller - instead
* of the default 128 pages (1MB) we may build index with 16-page ranges,
* or something like that. This does help even for random data sets, as
@@ -87,7 +87,8 @@
* not entirely clear how to distrubute the space between those columns.
*
* The current logic, implemented in brin_bloom_get_ndistinct, attempts to
- * make some basic sizing decisions, based on the table ndistinct estimate.
+ * make some basic sizing decisions, based on the size of BRIN ranges, and
+ * the maximum number of rows per range.
*
*
* sort vs. hash
@@ -200,10 +201,20 @@ typedef struct BloomOptions
/*
* Allowed range and default value for the false positive range. The exact
- * values are somewhat arbitrary.
+ * values are somewhat arbitrary, but were chosen considering the various
+ * parameters (size of filter vs. page size, etc.).
+ *
+ * The lower the false-positive rate, the more accurate the filter is, but
+ * it also gets larger - at some point this eliminates the main advantage
+ * of BRIN indexes, which is the tiny size. At 0.01% the index is about
+ * 10% of the table (assuming 290 distinct values per 8kB page).
+ *
+ * On the other hand, as the false-positive rate increases, larger part of
+ * the table has to be scanned due to mismatches - at 25% we're probably
+ * close to sequential scan being cheaper.
*/
-#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */
-#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */
+#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
+#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
#define BloomGetNDistinctPerRange(opts) \
@@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate)
Assert(ndistinct > 0);
Assert((false_positive_rate > 0) && (false_positive_rate < 1.0));
- m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0)))));
+ /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
+ m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
/* round m to whole bytes */
m = ((m + 7) / 8) * 8;
+ /*
+ * Reject filters that are obviously too large to store on a page.
+ *
+ * We do expect the bloom filter to eventually switch to hashing mode,
+ * and it's bound to be almost perfectly random, so not compressible.
+ */
+ if ((m/8) > BLCKSZ)
+ elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ);
+
/*
* round(log(2.0) * m / ndistinct), but assume round() may not be
* available on Windows
@@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate)
k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
/*
- * Allocate the bloom filter with a minimum size 64B (about 40B in the
- * bitmap part). We require space at least for the header.
- *
- * XXX Maybe the 64B min size is not really needed?
+ * Allocate the bloom filter (initially it's just a header, we'll make
+ * it larger as needed).
*/
- len = Max(offsetof(BloomFilter, data), 64);
-
- /* Reject filters that are obviously too large to store on a page. */
- if (len > BLCKSZ)
- elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ);
+ len = offsetof(BloomFilter, data);
filter = (BloomFilter *) palloc0(len);
@@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* brin_bloom_get_ndistinct
* Determine the ndistinct value used to size bloom filter.
*
- * Tweak the ndistinct value based on the pagesPerRange value. First,
+ * Adjust the ndistinct value based on the pagesPerRange value. First,
* if it's negative, it's assumed to be relative to maximum number of
* tuples in the range (assuming each page gets MaxHeapTuplesPerPage
* tuples, which is likely a significant over-estimate). We also clamp
@@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* and compute the expected number of distinct values in a range. But
* that may be tricky due to data being sorted in various ways, so it
* seems better to rely on the upper estimate.
+ *
+ * XXX We might also calculate a better estimate of rows per BRIN range,
+ * instead of using MaxHeapTuplesPerPage (which probably produces values
+ * much higher than reality).
*/
static int
brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
@@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
return (int) ndistinct;
}
-static double
-brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts)
-{
- return BloomGetFalsePositiveRate(opts);
-}
/*
* Examine the given index tuple (which contains partial status of a certain
@@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS)
if (column->bv_allnulls)
{
filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
- brin_bloom_get_fp_rate(bdesc, opts));
+ BloomGetFalsePositiveRate(opts));
column->bv_values[0] = PointerGetDatum(filter);
column->bv_allnulls = false;
updated = true;
@@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS)
* Cache and return inclusion opclass support procedure
*
* Return the procedure corresponding to the given function support number
- * or null if it is not exists.
+ * or null if it does not exists.
*/
static FmgrInfo *
bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
@@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
initStringInfo(&str);
appendStringInfoChar(&str, '{');
- /*
- * XXX not sure the detoasting is necessary (probably not, this
- * can only be in an index).
- */
- filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0));
+ /* Detoasting not needed (this can only be in an index). */
+ filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0);
if (BLOOM_IS_HASHED(filter))
{
@@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
}
else
{
+ /*
+ * XXX Maybe include the sorted/unsorted values? Seems a bit too
+ * much useless detail (internal hash values).
+ */
appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u",
filter->nvalues, filter->nsorted);
- /* TODO include the sorted/unsorted values */
}
appendStringInfoChar(&str, '}');
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
index 19b866283a..24ea5f6e42 100644
--- a/src/test/regress/expected/brin_bloom.out
+++ b/src/test/regress/expected/brin_bloom.out
@@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
);
ERROR: value -1.1 out of bounds for option "n_distinct_per_range"
DETAIL: Valid values are between "-1.000000" and "2147483647.000000".
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
-ERROR: value 0.0009 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.00009 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
-ERROR: value 0.11 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.26 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops,
charcol char_bloom_ops,
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
index 3c2ef56316..d587f3962f 100644
--- a/src/test/regress/sql/brin_bloom.sql
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops(n_distinct_per_range = -1.1)
);
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
--
2.26.2
--------------CF71AF65F7C337C37C24B045
Content-Type: text/x-patch; charset=UTF-8;
name="0006-add-sort_mode-opclass-parameter-20210112.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0006-add-sort_mode-opclass-parameter-20210112.patch"
^ permalink raw reply [nested|flat] 24+ messages in thread
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw)
---
doc/src/sgml/ref/create_index.sgml | 2 +-
src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++----------
src/test/regress/expected/brin_bloom.out | 14 ++--
src/test/regress/sql/brin_bloom.sql | 6 +-
4 files changed, 60 insertions(+), 46 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 8db10b7b1e..244e5834d8 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class=
equal to -1, the number of distinct non-null is assumed linear with
the maximum possible number of tuples in the block range (about 290
rows per block). The default values is <literal>-0.1</literal>, and
- the minimum number of distinct non-null values is <literal>128</literal>.
+ the minimum number of distinct non-null values is <literal>16</literal>.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index b7aa6d9f11..ffeb459d3e 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -8,12 +8,12 @@
*
* A BRIN opclass summarizing page range into a bloom filter.
*
- * Bloom filters allow efficient test whether a given page range contains
+ * Bloom filters allow efficient testing whether a given page range contains
* a particular value. Therefore, if we summarize each page range into a
- * bloom filter, we can easily and cheaply test wheter it containst values
+ * bloom filter, we can easily and cheaply test wheter it contains values
* we get later.
*
- * The index only supports equality operator, similarly to hash indexes.
+ * The index only supports equality operators, similarly to hash indexes.
* BRIN bloom indexes are however much smaller, and support only bitmap
* scans.
*
@@ -51,9 +51,9 @@
* the bloom filter. On the other hand, we want to keep the index as small
* as possible - that's one of the basic advantages of BRIN indexes.
*
- * The number of distinct elements (in a page range) depends on the data,
- * we can consider it fixed. This simplifies the trade-off to just false
- * positive rate vs. size.
+ * Although the number of distinct elements (in a page range) depends on
+ * the data, we can consider it fixed. This simplifies the trade-off to
+ * just false positive rate vs. size.
*
* At the page range level, false positive rate is a probability the bloom
* filter matches a random value. For the whole index (with sufficiently
@@ -65,7 +65,7 @@
* the bitmap is inherently random, compression can't reliably help here.
* To reduce the size of a filter (to fit to a page), we have to either
* accept higher false positive rate (undesirable), or reduce the number
- * of distinct items to be stored in the filter. We can't quite the input
+ * of distinct items to be stored in the filter. We can't alter the input
* data, of course, but we may make the BRIN page ranges smaller - instead
* of the default 128 pages (1MB) we may build index with 16-page ranges,
* or something like that. This does help even for random data sets, as
@@ -87,7 +87,8 @@
* not entirely clear how to distrubute the space between those columns.
*
* The current logic, implemented in brin_bloom_get_ndistinct, attempts to
- * make some basic sizing decisions, based on the table ndistinct estimate.
+ * make some basic sizing decisions, based on the size of BRIN ranges, and
+ * the maximum number of rows per range.
*
*
* sort vs. hash
@@ -200,10 +201,20 @@ typedef struct BloomOptions
/*
* Allowed range and default value for the false positive range. The exact
- * values are somewhat arbitrary.
+ * values are somewhat arbitrary, but were chosen considering the various
+ * parameters (size of filter vs. page size, etc.).
+ *
+ * The lower the false-positive rate, the more accurate the filter is, but
+ * it also gets larger - at some point this eliminates the main advantage
+ * of BRIN indexes, which is the tiny size. At 0.01% the index is about
+ * 10% of the table (assuming 290 distinct values per 8kB page).
+ *
+ * On the other hand, as the false-positive rate increases, larger part of
+ * the table has to be scanned due to mismatches - at 25% we're probably
+ * close to sequential scan being cheaper.
*/
-#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */
-#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */
+#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
+#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
#define BloomGetNDistinctPerRange(opts) \
@@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate)
Assert(ndistinct > 0);
Assert((false_positive_rate > 0) && (false_positive_rate < 1.0));
- m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0)))));
+ /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
+ m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
/* round m to whole bytes */
m = ((m + 7) / 8) * 8;
+ /*
+ * Reject filters that are obviously too large to store on a page.
+ *
+ * We do expect the bloom filter to eventually switch to hashing mode,
+ * and it's bound to be almost perfectly random, so not compressible.
+ */
+ if ((m/8) > BLCKSZ)
+ elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ);
+
/*
* round(log(2.0) * m / ndistinct), but assume round() may not be
* available on Windows
@@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate)
k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
/*
- * Allocate the bloom filter with a minimum size 64B (about 40B in the
- * bitmap part). We require space at least for the header.
- *
- * XXX Maybe the 64B min size is not really needed?
+ * Allocate the bloom filter (initially it's just a header, we'll make
+ * it larger as needed).
*/
- len = Max(offsetof(BloomFilter, data), 64);
-
- /* Reject filters that are obviously too large to store on a page. */
- if (len > BLCKSZ)
- elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ);
+ len = offsetof(BloomFilter, data);
filter = (BloomFilter *) palloc0(len);
@@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* brin_bloom_get_ndistinct
* Determine the ndistinct value used to size bloom filter.
*
- * Tweak the ndistinct value based on the pagesPerRange value. First,
+ * Adjust the ndistinct value based on the pagesPerRange value. First,
* if it's negative, it's assumed to be relative to maximum number of
* tuples in the range (assuming each page gets MaxHeapTuplesPerPage
* tuples, which is likely a significant over-estimate). We also clamp
@@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* and compute the expected number of distinct values in a range. But
* that may be tricky due to data being sorted in various ways, so it
* seems better to rely on the upper estimate.
+ *
+ * XXX We might also calculate a better estimate of rows per BRIN range,
+ * instead of using MaxHeapTuplesPerPage (which probably produces values
+ * much higher than reality).
*/
static int
brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
@@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
return (int) ndistinct;
}
-static double
-brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts)
-{
- return BloomGetFalsePositiveRate(opts);
-}
/*
* Examine the given index tuple (which contains partial status of a certain
@@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS)
if (column->bv_allnulls)
{
filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
- brin_bloom_get_fp_rate(bdesc, opts));
+ BloomGetFalsePositiveRate(opts));
column->bv_values[0] = PointerGetDatum(filter);
column->bv_allnulls = false;
updated = true;
@@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS)
* Cache and return inclusion opclass support procedure
*
* Return the procedure corresponding to the given function support number
- * or null if it is not exists.
+ * or null if it does not exists.
*/
static FmgrInfo *
bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
@@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
initStringInfo(&str);
appendStringInfoChar(&str, '{');
- /*
- * XXX not sure the detoasting is necessary (probably not, this
- * can only be in an index).
- */
- filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0));
+ /* Detoasting not needed (this can only be in an index). */
+ filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0);
if (BLOOM_IS_HASHED(filter))
{
@@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
}
else
{
+ /*
+ * XXX Maybe include the sorted/unsorted values? Seems a bit too
+ * much useless detail (internal hash values).
+ */
appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u",
filter->nvalues, filter->nsorted);
- /* TODO include the sorted/unsorted values */
}
appendStringInfoChar(&str, '}');
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
index 19b866283a..24ea5f6e42 100644
--- a/src/test/regress/expected/brin_bloom.out
+++ b/src/test/regress/expected/brin_bloom.out
@@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
);
ERROR: value -1.1 out of bounds for option "n_distinct_per_range"
DETAIL: Valid values are between "-1.000000" and "2147483647.000000".
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
-ERROR: value 0.0009 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.00009 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
-ERROR: value 0.11 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.26 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops,
charcol char_bloom_ops,
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
index 3c2ef56316..d587f3962f 100644
--- a/src/test/regress/sql/brin_bloom.sql
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops(n_distinct_per_range = -1.1)
);
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
--
2.26.2
--------------CF71AF65F7C337C37C24B045
Content-Type: text/x-patch; charset=UTF-8;
name="0006-add-sort_mode-opclass-parameter-20210112.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0006-add-sort_mode-opclass-parameter-20210112.patch"
^ permalink raw reply [nested|flat] 24+ messages in thread
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw)
---
doc/src/sgml/ref/create_index.sgml | 2 +-
src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++----------
src/test/regress/expected/brin_bloom.out | 14 ++--
src/test/regress/sql/brin_bloom.sql | 6 +-
4 files changed, 60 insertions(+), 46 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 8db10b7b1e..244e5834d8 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class=
equal to -1, the number of distinct non-null is assumed linear with
the maximum possible number of tuples in the block range (about 290
rows per block). The default values is <literal>-0.1</literal>, and
- the minimum number of distinct non-null values is <literal>128</literal>.
+ the minimum number of distinct non-null values is <literal>16</literal>.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index b7aa6d9f11..ffeb459d3e 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -8,12 +8,12 @@
*
* A BRIN opclass summarizing page range into a bloom filter.
*
- * Bloom filters allow efficient test whether a given page range contains
+ * Bloom filters allow efficient testing whether a given page range contains
* a particular value. Therefore, if we summarize each page range into a
- * bloom filter, we can easily and cheaply test wheter it containst values
+ * bloom filter, we can easily and cheaply test wheter it contains values
* we get later.
*
- * The index only supports equality operator, similarly to hash indexes.
+ * The index only supports equality operators, similarly to hash indexes.
* BRIN bloom indexes are however much smaller, and support only bitmap
* scans.
*
@@ -51,9 +51,9 @@
* the bloom filter. On the other hand, we want to keep the index as small
* as possible - that's one of the basic advantages of BRIN indexes.
*
- * The number of distinct elements (in a page range) depends on the data,
- * we can consider it fixed. This simplifies the trade-off to just false
- * positive rate vs. size.
+ * Although the number of distinct elements (in a page range) depends on
+ * the data, we can consider it fixed. This simplifies the trade-off to
+ * just false positive rate vs. size.
*
* At the page range level, false positive rate is a probability the bloom
* filter matches a random value. For the whole index (with sufficiently
@@ -65,7 +65,7 @@
* the bitmap is inherently random, compression can't reliably help here.
* To reduce the size of a filter (to fit to a page), we have to either
* accept higher false positive rate (undesirable), or reduce the number
- * of distinct items to be stored in the filter. We can't quite the input
+ * of distinct items to be stored in the filter. We can't alter the input
* data, of course, but we may make the BRIN page ranges smaller - instead
* of the default 128 pages (1MB) we may build index with 16-page ranges,
* or something like that. This does help even for random data sets, as
@@ -87,7 +87,8 @@
* not entirely clear how to distrubute the space between those columns.
*
* The current logic, implemented in brin_bloom_get_ndistinct, attempts to
- * make some basic sizing decisions, based on the table ndistinct estimate.
+ * make some basic sizing decisions, based on the size of BRIN ranges, and
+ * the maximum number of rows per range.
*
*
* sort vs. hash
@@ -200,10 +201,20 @@ typedef struct BloomOptions
/*
* Allowed range and default value for the false positive range. The exact
- * values are somewhat arbitrary.
+ * values are somewhat arbitrary, but were chosen considering the various
+ * parameters (size of filter vs. page size, etc.).
+ *
+ * The lower the false-positive rate, the more accurate the filter is, but
+ * it also gets larger - at some point this eliminates the main advantage
+ * of BRIN indexes, which is the tiny size. At 0.01% the index is about
+ * 10% of the table (assuming 290 distinct values per 8kB page).
+ *
+ * On the other hand, as the false-positive rate increases, larger part of
+ * the table has to be scanned due to mismatches - at 25% we're probably
+ * close to sequential scan being cheaper.
*/
-#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */
-#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */
+#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
+#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
#define BloomGetNDistinctPerRange(opts) \
@@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate)
Assert(ndistinct > 0);
Assert((false_positive_rate > 0) && (false_positive_rate < 1.0));
- m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0)))));
+ /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
+ m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
/* round m to whole bytes */
m = ((m + 7) / 8) * 8;
+ /*
+ * Reject filters that are obviously too large to store on a page.
+ *
+ * We do expect the bloom filter to eventually switch to hashing mode,
+ * and it's bound to be almost perfectly random, so not compressible.
+ */
+ if ((m/8) > BLCKSZ)
+ elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ);
+
/*
* round(log(2.0) * m / ndistinct), but assume round() may not be
* available on Windows
@@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate)
k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
/*
- * Allocate the bloom filter with a minimum size 64B (about 40B in the
- * bitmap part). We require space at least for the header.
- *
- * XXX Maybe the 64B min size is not really needed?
+ * Allocate the bloom filter (initially it's just a header, we'll make
+ * it larger as needed).
*/
- len = Max(offsetof(BloomFilter, data), 64);
-
- /* Reject filters that are obviously too large to store on a page. */
- if (len > BLCKSZ)
- elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ);
+ len = offsetof(BloomFilter, data);
filter = (BloomFilter *) palloc0(len);
@@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* brin_bloom_get_ndistinct
* Determine the ndistinct value used to size bloom filter.
*
- * Tweak the ndistinct value based on the pagesPerRange value. First,
+ * Adjust the ndistinct value based on the pagesPerRange value. First,
* if it's negative, it's assumed to be relative to maximum number of
* tuples in the range (assuming each page gets MaxHeapTuplesPerPage
* tuples, which is likely a significant over-estimate). We also clamp
@@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* and compute the expected number of distinct values in a range. But
* that may be tricky due to data being sorted in various ways, so it
* seems better to rely on the upper estimate.
+ *
+ * XXX We might also calculate a better estimate of rows per BRIN range,
+ * instead of using MaxHeapTuplesPerPage (which probably produces values
+ * much higher than reality).
*/
static int
brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
@@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
return (int) ndistinct;
}
-static double
-brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts)
-{
- return BloomGetFalsePositiveRate(opts);
-}
/*
* Examine the given index tuple (which contains partial status of a certain
@@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS)
if (column->bv_allnulls)
{
filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
- brin_bloom_get_fp_rate(bdesc, opts));
+ BloomGetFalsePositiveRate(opts));
column->bv_values[0] = PointerGetDatum(filter);
column->bv_allnulls = false;
updated = true;
@@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS)
* Cache and return inclusion opclass support procedure
*
* Return the procedure corresponding to the given function support number
- * or null if it is not exists.
+ * or null if it does not exists.
*/
static FmgrInfo *
bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
@@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
initStringInfo(&str);
appendStringInfoChar(&str, '{');
- /*
- * XXX not sure the detoasting is necessary (probably not, this
- * can only be in an index).
- */
- filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0));
+ /* Detoasting not needed (this can only be in an index). */
+ filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0);
if (BLOOM_IS_HASHED(filter))
{
@@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
}
else
{
+ /*
+ * XXX Maybe include the sorted/unsorted values? Seems a bit too
+ * much useless detail (internal hash values).
+ */
appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u",
filter->nvalues, filter->nsorted);
- /* TODO include the sorted/unsorted values */
}
appendStringInfoChar(&str, '}');
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
index 19b866283a..24ea5f6e42 100644
--- a/src/test/regress/expected/brin_bloom.out
+++ b/src/test/regress/expected/brin_bloom.out
@@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
);
ERROR: value -1.1 out of bounds for option "n_distinct_per_range"
DETAIL: Valid values are between "-1.000000" and "2147483647.000000".
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
-ERROR: value 0.0009 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.00009 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
-ERROR: value 0.11 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.26 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops,
charcol char_bloom_ops,
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
index 3c2ef56316..d587f3962f 100644
--- a/src/test/regress/sql/brin_bloom.sql
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops(n_distinct_per_range = -1.1)
);
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
--
2.26.2
--------------CF71AF65F7C337C37C24B045
Content-Type: text/x-patch; charset=UTF-8;
name="0006-add-sort_mode-opclass-parameter-20210112.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0006-add-sort_mode-opclass-parameter-20210112.patch"
^ permalink raw reply [nested|flat] 24+ messages in thread
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw)
---
doc/src/sgml/ref/create_index.sgml | 2 +-
src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++----------
src/test/regress/expected/brin_bloom.out | 14 ++--
src/test/regress/sql/brin_bloom.sql | 6 +-
4 files changed, 60 insertions(+), 46 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 8db10b7b1e..244e5834d8 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class=
equal to -1, the number of distinct non-null is assumed linear with
the maximum possible number of tuples in the block range (about 290
rows per block). The default values is <literal>-0.1</literal>, and
- the minimum number of distinct non-null values is <literal>128</literal>.
+ the minimum number of distinct non-null values is <literal>16</literal>.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index b7aa6d9f11..ffeb459d3e 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -8,12 +8,12 @@
*
* A BRIN opclass summarizing page range into a bloom filter.
*
- * Bloom filters allow efficient test whether a given page range contains
+ * Bloom filters allow efficient testing whether a given page range contains
* a particular value. Therefore, if we summarize each page range into a
- * bloom filter, we can easily and cheaply test wheter it containst values
+ * bloom filter, we can easily and cheaply test wheter it contains values
* we get later.
*
- * The index only supports equality operator, similarly to hash indexes.
+ * The index only supports equality operators, similarly to hash indexes.
* BRIN bloom indexes are however much smaller, and support only bitmap
* scans.
*
@@ -51,9 +51,9 @@
* the bloom filter. On the other hand, we want to keep the index as small
* as possible - that's one of the basic advantages of BRIN indexes.
*
- * The number of distinct elements (in a page range) depends on the data,
- * we can consider it fixed. This simplifies the trade-off to just false
- * positive rate vs. size.
+ * Although the number of distinct elements (in a page range) depends on
+ * the data, we can consider it fixed. This simplifies the trade-off to
+ * just false positive rate vs. size.
*
* At the page range level, false positive rate is a probability the bloom
* filter matches a random value. For the whole index (with sufficiently
@@ -65,7 +65,7 @@
* the bitmap is inherently random, compression can't reliably help here.
* To reduce the size of a filter (to fit to a page), we have to either
* accept higher false positive rate (undesirable), or reduce the number
- * of distinct items to be stored in the filter. We can't quite the input
+ * of distinct items to be stored in the filter. We can't alter the input
* data, of course, but we may make the BRIN page ranges smaller - instead
* of the default 128 pages (1MB) we may build index with 16-page ranges,
* or something like that. This does help even for random data sets, as
@@ -87,7 +87,8 @@
* not entirely clear how to distrubute the space between those columns.
*
* The current logic, implemented in brin_bloom_get_ndistinct, attempts to
- * make some basic sizing decisions, based on the table ndistinct estimate.
+ * make some basic sizing decisions, based on the size of BRIN ranges, and
+ * the maximum number of rows per range.
*
*
* sort vs. hash
@@ -200,10 +201,20 @@ typedef struct BloomOptions
/*
* Allowed range and default value for the false positive range. The exact
- * values are somewhat arbitrary.
+ * values are somewhat arbitrary, but were chosen considering the various
+ * parameters (size of filter vs. page size, etc.).
+ *
+ * The lower the false-positive rate, the more accurate the filter is, but
+ * it also gets larger - at some point this eliminates the main advantage
+ * of BRIN indexes, which is the tiny size. At 0.01% the index is about
+ * 10% of the table (assuming 290 distinct values per 8kB page).
+ *
+ * On the other hand, as the false-positive rate increases, larger part of
+ * the table has to be scanned due to mismatches - at 25% we're probably
+ * close to sequential scan being cheaper.
*/
-#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */
-#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */
+#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
+#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
#define BloomGetNDistinctPerRange(opts) \
@@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate)
Assert(ndistinct > 0);
Assert((false_positive_rate > 0) && (false_positive_rate < 1.0));
- m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0)))));
+ /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
+ m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
/* round m to whole bytes */
m = ((m + 7) / 8) * 8;
+ /*
+ * Reject filters that are obviously too large to store on a page.
+ *
+ * We do expect the bloom filter to eventually switch to hashing mode,
+ * and it's bound to be almost perfectly random, so not compressible.
+ */
+ if ((m/8) > BLCKSZ)
+ elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ);
+
/*
* round(log(2.0) * m / ndistinct), but assume round() may not be
* available on Windows
@@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate)
k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
/*
- * Allocate the bloom filter with a minimum size 64B (about 40B in the
- * bitmap part). We require space at least for the header.
- *
- * XXX Maybe the 64B min size is not really needed?
+ * Allocate the bloom filter (initially it's just a header, we'll make
+ * it larger as needed).
*/
- len = Max(offsetof(BloomFilter, data), 64);
-
- /* Reject filters that are obviously too large to store on a page. */
- if (len > BLCKSZ)
- elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ);
+ len = offsetof(BloomFilter, data);
filter = (BloomFilter *) palloc0(len);
@@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* brin_bloom_get_ndistinct
* Determine the ndistinct value used to size bloom filter.
*
- * Tweak the ndistinct value based on the pagesPerRange value. First,
+ * Adjust the ndistinct value based on the pagesPerRange value. First,
* if it's negative, it's assumed to be relative to maximum number of
* tuples in the range (assuming each page gets MaxHeapTuplesPerPage
* tuples, which is likely a significant over-estimate). We also clamp
@@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* and compute the expected number of distinct values in a range. But
* that may be tricky due to data being sorted in various ways, so it
* seems better to rely on the upper estimate.
+ *
+ * XXX We might also calculate a better estimate of rows per BRIN range,
+ * instead of using MaxHeapTuplesPerPage (which probably produces values
+ * much higher than reality).
*/
static int
brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
@@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
return (int) ndistinct;
}
-static double
-brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts)
-{
- return BloomGetFalsePositiveRate(opts);
-}
/*
* Examine the given index tuple (which contains partial status of a certain
@@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS)
if (column->bv_allnulls)
{
filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
- brin_bloom_get_fp_rate(bdesc, opts));
+ BloomGetFalsePositiveRate(opts));
column->bv_values[0] = PointerGetDatum(filter);
column->bv_allnulls = false;
updated = true;
@@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS)
* Cache and return inclusion opclass support procedure
*
* Return the procedure corresponding to the given function support number
- * or null if it is not exists.
+ * or null if it does not exists.
*/
static FmgrInfo *
bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
@@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
initStringInfo(&str);
appendStringInfoChar(&str, '{');
- /*
- * XXX not sure the detoasting is necessary (probably not, this
- * can only be in an index).
- */
- filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0));
+ /* Detoasting not needed (this can only be in an index). */
+ filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0);
if (BLOOM_IS_HASHED(filter))
{
@@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
}
else
{
+ /*
+ * XXX Maybe include the sorted/unsorted values? Seems a bit too
+ * much useless detail (internal hash values).
+ */
appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u",
filter->nvalues, filter->nsorted);
- /* TODO include the sorted/unsorted values */
}
appendStringInfoChar(&str, '}');
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
index 19b866283a..24ea5f6e42 100644
--- a/src/test/regress/expected/brin_bloom.out
+++ b/src/test/regress/expected/brin_bloom.out
@@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
);
ERROR: value -1.1 out of bounds for option "n_distinct_per_range"
DETAIL: Valid values are between "-1.000000" and "2147483647.000000".
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
-ERROR: value 0.0009 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.00009 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
-ERROR: value 0.11 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.26 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops,
charcol char_bloom_ops,
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
index 3c2ef56316..d587f3962f 100644
--- a/src/test/regress/sql/brin_bloom.sql
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops(n_distinct_per_range = -1.1)
);
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
--
2.26.2
--------------CF71AF65F7C337C37C24B045
Content-Type: text/x-patch; charset=UTF-8;
name="0006-add-sort_mode-opclass-parameter-20210112.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0006-add-sort_mode-opclass-parameter-20210112.patch"
^ permalink raw reply [nested|flat] 24+ messages in thread
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw)
---
doc/src/sgml/ref/create_index.sgml | 2 +-
src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++----------
src/test/regress/expected/brin_bloom.out | 14 ++--
src/test/regress/sql/brin_bloom.sql | 6 +-
4 files changed, 60 insertions(+), 46 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 8db10b7b1e..244e5834d8 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class=
equal to -1, the number of distinct non-null is assumed linear with
the maximum possible number of tuples in the block range (about 290
rows per block). The default values is <literal>-0.1</literal>, and
- the minimum number of distinct non-null values is <literal>128</literal>.
+ the minimum number of distinct non-null values is <literal>16</literal>.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index b7aa6d9f11..ffeb459d3e 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -8,12 +8,12 @@
*
* A BRIN opclass summarizing page range into a bloom filter.
*
- * Bloom filters allow efficient test whether a given page range contains
+ * Bloom filters allow efficient testing whether a given page range contains
* a particular value. Therefore, if we summarize each page range into a
- * bloom filter, we can easily and cheaply test wheter it containst values
+ * bloom filter, we can easily and cheaply test wheter it contains values
* we get later.
*
- * The index only supports equality operator, similarly to hash indexes.
+ * The index only supports equality operators, similarly to hash indexes.
* BRIN bloom indexes are however much smaller, and support only bitmap
* scans.
*
@@ -51,9 +51,9 @@
* the bloom filter. On the other hand, we want to keep the index as small
* as possible - that's one of the basic advantages of BRIN indexes.
*
- * The number of distinct elements (in a page range) depends on the data,
- * we can consider it fixed. This simplifies the trade-off to just false
- * positive rate vs. size.
+ * Although the number of distinct elements (in a page range) depends on
+ * the data, we can consider it fixed. This simplifies the trade-off to
+ * just false positive rate vs. size.
*
* At the page range level, false positive rate is a probability the bloom
* filter matches a random value. For the whole index (with sufficiently
@@ -65,7 +65,7 @@
* the bitmap is inherently random, compression can't reliably help here.
* To reduce the size of a filter (to fit to a page), we have to either
* accept higher false positive rate (undesirable), or reduce the number
- * of distinct items to be stored in the filter. We can't quite the input
+ * of distinct items to be stored in the filter. We can't alter the input
* data, of course, but we may make the BRIN page ranges smaller - instead
* of the default 128 pages (1MB) we may build index with 16-page ranges,
* or something like that. This does help even for random data sets, as
@@ -87,7 +87,8 @@
* not entirely clear how to distrubute the space between those columns.
*
* The current logic, implemented in brin_bloom_get_ndistinct, attempts to
- * make some basic sizing decisions, based on the table ndistinct estimate.
+ * make some basic sizing decisions, based on the size of BRIN ranges, and
+ * the maximum number of rows per range.
*
*
* sort vs. hash
@@ -200,10 +201,20 @@ typedef struct BloomOptions
/*
* Allowed range and default value for the false positive range. The exact
- * values are somewhat arbitrary.
+ * values are somewhat arbitrary, but were chosen considering the various
+ * parameters (size of filter vs. page size, etc.).
+ *
+ * The lower the false-positive rate, the more accurate the filter is, but
+ * it also gets larger - at some point this eliminates the main advantage
+ * of BRIN indexes, which is the tiny size. At 0.01% the index is about
+ * 10% of the table (assuming 290 distinct values per 8kB page).
+ *
+ * On the other hand, as the false-positive rate increases, larger part of
+ * the table has to be scanned due to mismatches - at 25% we're probably
+ * close to sequential scan being cheaper.
*/
-#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */
-#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */
+#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
+#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
#define BloomGetNDistinctPerRange(opts) \
@@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate)
Assert(ndistinct > 0);
Assert((false_positive_rate > 0) && (false_positive_rate < 1.0));
- m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0)))));
+ /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
+ m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
/* round m to whole bytes */
m = ((m + 7) / 8) * 8;
+ /*
+ * Reject filters that are obviously too large to store on a page.
+ *
+ * We do expect the bloom filter to eventually switch to hashing mode,
+ * and it's bound to be almost perfectly random, so not compressible.
+ */
+ if ((m/8) > BLCKSZ)
+ elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ);
+
/*
* round(log(2.0) * m / ndistinct), but assume round() may not be
* available on Windows
@@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate)
k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
/*
- * Allocate the bloom filter with a minimum size 64B (about 40B in the
- * bitmap part). We require space at least for the header.
- *
- * XXX Maybe the 64B min size is not really needed?
+ * Allocate the bloom filter (initially it's just a header, we'll make
+ * it larger as needed).
*/
- len = Max(offsetof(BloomFilter, data), 64);
-
- /* Reject filters that are obviously too large to store on a page. */
- if (len > BLCKSZ)
- elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ);
+ len = offsetof(BloomFilter, data);
filter = (BloomFilter *) palloc0(len);
@@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* brin_bloom_get_ndistinct
* Determine the ndistinct value used to size bloom filter.
*
- * Tweak the ndistinct value based on the pagesPerRange value. First,
+ * Adjust the ndistinct value based on the pagesPerRange value. First,
* if it's negative, it's assumed to be relative to maximum number of
* tuples in the range (assuming each page gets MaxHeapTuplesPerPage
* tuples, which is likely a significant over-estimate). We also clamp
@@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* and compute the expected number of distinct values in a range. But
* that may be tricky due to data being sorted in various ways, so it
* seems better to rely on the upper estimate.
+ *
+ * XXX We might also calculate a better estimate of rows per BRIN range,
+ * instead of using MaxHeapTuplesPerPage (which probably produces values
+ * much higher than reality).
*/
static int
brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
@@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
return (int) ndistinct;
}
-static double
-brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts)
-{
- return BloomGetFalsePositiveRate(opts);
-}
/*
* Examine the given index tuple (which contains partial status of a certain
@@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS)
if (column->bv_allnulls)
{
filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
- brin_bloom_get_fp_rate(bdesc, opts));
+ BloomGetFalsePositiveRate(opts));
column->bv_values[0] = PointerGetDatum(filter);
column->bv_allnulls = false;
updated = true;
@@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS)
* Cache and return inclusion opclass support procedure
*
* Return the procedure corresponding to the given function support number
- * or null if it is not exists.
+ * or null if it does not exists.
*/
static FmgrInfo *
bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
@@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
initStringInfo(&str);
appendStringInfoChar(&str, '{');
- /*
- * XXX not sure the detoasting is necessary (probably not, this
- * can only be in an index).
- */
- filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0));
+ /* Detoasting not needed (this can only be in an index). */
+ filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0);
if (BLOOM_IS_HASHED(filter))
{
@@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
}
else
{
+ /*
+ * XXX Maybe include the sorted/unsorted values? Seems a bit too
+ * much useless detail (internal hash values).
+ */
appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u",
filter->nvalues, filter->nsorted);
- /* TODO include the sorted/unsorted values */
}
appendStringInfoChar(&str, '}');
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
index 19b866283a..24ea5f6e42 100644
--- a/src/test/regress/expected/brin_bloom.out
+++ b/src/test/regress/expected/brin_bloom.out
@@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
);
ERROR: value -1.1 out of bounds for option "n_distinct_per_range"
DETAIL: Valid values are between "-1.000000" and "2147483647.000000".
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
-ERROR: value 0.0009 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.00009 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
-ERROR: value 0.11 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.26 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops,
charcol char_bloom_ops,
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
index 3c2ef56316..d587f3962f 100644
--- a/src/test/regress/sql/brin_bloom.sql
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops(n_distinct_per_range = -1.1)
);
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
--
2.26.2
--------------CF71AF65F7C337C37C24B045
Content-Type: text/x-patch; charset=UTF-8;
name="0006-add-sort_mode-opclass-parameter-20210112.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0006-add-sort_mode-opclass-parameter-20210112.patch"
^ permalink raw reply [nested|flat] 24+ messages in thread
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw)
---
doc/src/sgml/ref/create_index.sgml | 2 +-
src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++----------
src/test/regress/expected/brin_bloom.out | 14 ++--
src/test/regress/sql/brin_bloom.sql | 6 +-
4 files changed, 60 insertions(+), 46 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 8db10b7b1e..244e5834d8 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class=
equal to -1, the number of distinct non-null is assumed linear with
the maximum possible number of tuples in the block range (about 290
rows per block). The default values is <literal>-0.1</literal>, and
- the minimum number of distinct non-null values is <literal>128</literal>.
+ the minimum number of distinct non-null values is <literal>16</literal>.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index b7aa6d9f11..ffeb459d3e 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -8,12 +8,12 @@
*
* A BRIN opclass summarizing page range into a bloom filter.
*
- * Bloom filters allow efficient test whether a given page range contains
+ * Bloom filters allow efficient testing whether a given page range contains
* a particular value. Therefore, if we summarize each page range into a
- * bloom filter, we can easily and cheaply test wheter it containst values
+ * bloom filter, we can easily and cheaply test wheter it contains values
* we get later.
*
- * The index only supports equality operator, similarly to hash indexes.
+ * The index only supports equality operators, similarly to hash indexes.
* BRIN bloom indexes are however much smaller, and support only bitmap
* scans.
*
@@ -51,9 +51,9 @@
* the bloom filter. On the other hand, we want to keep the index as small
* as possible - that's one of the basic advantages of BRIN indexes.
*
- * The number of distinct elements (in a page range) depends on the data,
- * we can consider it fixed. This simplifies the trade-off to just false
- * positive rate vs. size.
+ * Although the number of distinct elements (in a page range) depends on
+ * the data, we can consider it fixed. This simplifies the trade-off to
+ * just false positive rate vs. size.
*
* At the page range level, false positive rate is a probability the bloom
* filter matches a random value. For the whole index (with sufficiently
@@ -65,7 +65,7 @@
* the bitmap is inherently random, compression can't reliably help here.
* To reduce the size of a filter (to fit to a page), we have to either
* accept higher false positive rate (undesirable), or reduce the number
- * of distinct items to be stored in the filter. We can't quite the input
+ * of distinct items to be stored in the filter. We can't alter the input
* data, of course, but we may make the BRIN page ranges smaller - instead
* of the default 128 pages (1MB) we may build index with 16-page ranges,
* or something like that. This does help even for random data sets, as
@@ -87,7 +87,8 @@
* not entirely clear how to distrubute the space between those columns.
*
* The current logic, implemented in brin_bloom_get_ndistinct, attempts to
- * make some basic sizing decisions, based on the table ndistinct estimate.
+ * make some basic sizing decisions, based on the size of BRIN ranges, and
+ * the maximum number of rows per range.
*
*
* sort vs. hash
@@ -200,10 +201,20 @@ typedef struct BloomOptions
/*
* Allowed range and default value for the false positive range. The exact
- * values are somewhat arbitrary.
+ * values are somewhat arbitrary, but were chosen considering the various
+ * parameters (size of filter vs. page size, etc.).
+ *
+ * The lower the false-positive rate, the more accurate the filter is, but
+ * it also gets larger - at some point this eliminates the main advantage
+ * of BRIN indexes, which is the tiny size. At 0.01% the index is about
+ * 10% of the table (assuming 290 distinct values per 8kB page).
+ *
+ * On the other hand, as the false-positive rate increases, larger part of
+ * the table has to be scanned due to mismatches - at 25% we're probably
+ * close to sequential scan being cheaper.
*/
-#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */
-#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */
+#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
+#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
#define BloomGetNDistinctPerRange(opts) \
@@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate)
Assert(ndistinct > 0);
Assert((false_positive_rate > 0) && (false_positive_rate < 1.0));
- m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0)))));
+ /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
+ m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
/* round m to whole bytes */
m = ((m + 7) / 8) * 8;
+ /*
+ * Reject filters that are obviously too large to store on a page.
+ *
+ * We do expect the bloom filter to eventually switch to hashing mode,
+ * and it's bound to be almost perfectly random, so not compressible.
+ */
+ if ((m/8) > BLCKSZ)
+ elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ);
+
/*
* round(log(2.0) * m / ndistinct), but assume round() may not be
* available on Windows
@@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate)
k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
/*
- * Allocate the bloom filter with a minimum size 64B (about 40B in the
- * bitmap part). We require space at least for the header.
- *
- * XXX Maybe the 64B min size is not really needed?
+ * Allocate the bloom filter (initially it's just a header, we'll make
+ * it larger as needed).
*/
- len = Max(offsetof(BloomFilter, data), 64);
-
- /* Reject filters that are obviously too large to store on a page. */
- if (len > BLCKSZ)
- elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ);
+ len = offsetof(BloomFilter, data);
filter = (BloomFilter *) palloc0(len);
@@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* brin_bloom_get_ndistinct
* Determine the ndistinct value used to size bloom filter.
*
- * Tweak the ndistinct value based on the pagesPerRange value. First,
+ * Adjust the ndistinct value based on the pagesPerRange value. First,
* if it's negative, it's assumed to be relative to maximum number of
* tuples in the range (assuming each page gets MaxHeapTuplesPerPage
* tuples, which is likely a significant over-estimate). We also clamp
@@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* and compute the expected number of distinct values in a range. But
* that may be tricky due to data being sorted in various ways, so it
* seems better to rely on the upper estimate.
+ *
+ * XXX We might also calculate a better estimate of rows per BRIN range,
+ * instead of using MaxHeapTuplesPerPage (which probably produces values
+ * much higher than reality).
*/
static int
brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
@@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
return (int) ndistinct;
}
-static double
-brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts)
-{
- return BloomGetFalsePositiveRate(opts);
-}
/*
* Examine the given index tuple (which contains partial status of a certain
@@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS)
if (column->bv_allnulls)
{
filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
- brin_bloom_get_fp_rate(bdesc, opts));
+ BloomGetFalsePositiveRate(opts));
column->bv_values[0] = PointerGetDatum(filter);
column->bv_allnulls = false;
updated = true;
@@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS)
* Cache and return inclusion opclass support procedure
*
* Return the procedure corresponding to the given function support number
- * or null if it is not exists.
+ * or null if it does not exists.
*/
static FmgrInfo *
bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
@@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
initStringInfo(&str);
appendStringInfoChar(&str, '{');
- /*
- * XXX not sure the detoasting is necessary (probably not, this
- * can only be in an index).
- */
- filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0));
+ /* Detoasting not needed (this can only be in an index). */
+ filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0);
if (BLOOM_IS_HASHED(filter))
{
@@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
}
else
{
+ /*
+ * XXX Maybe include the sorted/unsorted values? Seems a bit too
+ * much useless detail (internal hash values).
+ */
appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u",
filter->nvalues, filter->nsorted);
- /* TODO include the sorted/unsorted values */
}
appendStringInfoChar(&str, '}');
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
index 19b866283a..24ea5f6e42 100644
--- a/src/test/regress/expected/brin_bloom.out
+++ b/src/test/regress/expected/brin_bloom.out
@@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
);
ERROR: value -1.1 out of bounds for option "n_distinct_per_range"
DETAIL: Valid values are between "-1.000000" and "2147483647.000000".
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
-ERROR: value 0.0009 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.00009 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
-ERROR: value 0.11 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.26 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops,
charcol char_bloom_ops,
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
index 3c2ef56316..d587f3962f 100644
--- a/src/test/regress/sql/brin_bloom.sql
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops(n_distinct_per_range = -1.1)
);
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
--
2.26.2
--------------CF71AF65F7C337C37C24B045
Content-Type: text/x-patch; charset=UTF-8;
name="0006-add-sort_mode-opclass-parameter-20210112.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0006-add-sort_mode-opclass-parameter-20210112.patch"
^ permalink raw reply [nested|flat] 24+ messages in thread
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw)
---
doc/src/sgml/ref/create_index.sgml | 2 +-
src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++----------
src/test/regress/expected/brin_bloom.out | 14 ++--
src/test/regress/sql/brin_bloom.sql | 6 +-
4 files changed, 60 insertions(+), 46 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 8db10b7b1e..244e5834d8 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class=
equal to -1, the number of distinct non-null is assumed linear with
the maximum possible number of tuples in the block range (about 290
rows per block). The default values is <literal>-0.1</literal>, and
- the minimum number of distinct non-null values is <literal>128</literal>.
+ the minimum number of distinct non-null values is <literal>16</literal>.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index b7aa6d9f11..ffeb459d3e 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -8,12 +8,12 @@
*
* A BRIN opclass summarizing page range into a bloom filter.
*
- * Bloom filters allow efficient test whether a given page range contains
+ * Bloom filters allow efficient testing whether a given page range contains
* a particular value. Therefore, if we summarize each page range into a
- * bloom filter, we can easily and cheaply test wheter it containst values
+ * bloom filter, we can easily and cheaply test wheter it contains values
* we get later.
*
- * The index only supports equality operator, similarly to hash indexes.
+ * The index only supports equality operators, similarly to hash indexes.
* BRIN bloom indexes are however much smaller, and support only bitmap
* scans.
*
@@ -51,9 +51,9 @@
* the bloom filter. On the other hand, we want to keep the index as small
* as possible - that's one of the basic advantages of BRIN indexes.
*
- * The number of distinct elements (in a page range) depends on the data,
- * we can consider it fixed. This simplifies the trade-off to just false
- * positive rate vs. size.
+ * Although the number of distinct elements (in a page range) depends on
+ * the data, we can consider it fixed. This simplifies the trade-off to
+ * just false positive rate vs. size.
*
* At the page range level, false positive rate is a probability the bloom
* filter matches a random value. For the whole index (with sufficiently
@@ -65,7 +65,7 @@
* the bitmap is inherently random, compression can't reliably help here.
* To reduce the size of a filter (to fit to a page), we have to either
* accept higher false positive rate (undesirable), or reduce the number
- * of distinct items to be stored in the filter. We can't quite the input
+ * of distinct items to be stored in the filter. We can't alter the input
* data, of course, but we may make the BRIN page ranges smaller - instead
* of the default 128 pages (1MB) we may build index with 16-page ranges,
* or something like that. This does help even for random data sets, as
@@ -87,7 +87,8 @@
* not entirely clear how to distrubute the space between those columns.
*
* The current logic, implemented in brin_bloom_get_ndistinct, attempts to
- * make some basic sizing decisions, based on the table ndistinct estimate.
+ * make some basic sizing decisions, based on the size of BRIN ranges, and
+ * the maximum number of rows per range.
*
*
* sort vs. hash
@@ -200,10 +201,20 @@ typedef struct BloomOptions
/*
* Allowed range and default value for the false positive range. The exact
- * values are somewhat arbitrary.
+ * values are somewhat arbitrary, but were chosen considering the various
+ * parameters (size of filter vs. page size, etc.).
+ *
+ * The lower the false-positive rate, the more accurate the filter is, but
+ * it also gets larger - at some point this eliminates the main advantage
+ * of BRIN indexes, which is the tiny size. At 0.01% the index is about
+ * 10% of the table (assuming 290 distinct values per 8kB page).
+ *
+ * On the other hand, as the false-positive rate increases, larger part of
+ * the table has to be scanned due to mismatches - at 25% we're probably
+ * close to sequential scan being cheaper.
*/
-#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */
-#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */
+#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
+#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
#define BloomGetNDistinctPerRange(opts) \
@@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate)
Assert(ndistinct > 0);
Assert((false_positive_rate > 0) && (false_positive_rate < 1.0));
- m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0)))));
+ /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
+ m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
/* round m to whole bytes */
m = ((m + 7) / 8) * 8;
+ /*
+ * Reject filters that are obviously too large to store on a page.
+ *
+ * We do expect the bloom filter to eventually switch to hashing mode,
+ * and it's bound to be almost perfectly random, so not compressible.
+ */
+ if ((m/8) > BLCKSZ)
+ elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ);
+
/*
* round(log(2.0) * m / ndistinct), but assume round() may not be
* available on Windows
@@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate)
k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
/*
- * Allocate the bloom filter with a minimum size 64B (about 40B in the
- * bitmap part). We require space at least for the header.
- *
- * XXX Maybe the 64B min size is not really needed?
+ * Allocate the bloom filter (initially it's just a header, we'll make
+ * it larger as needed).
*/
- len = Max(offsetof(BloomFilter, data), 64);
-
- /* Reject filters that are obviously too large to store on a page. */
- if (len > BLCKSZ)
- elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ);
+ len = offsetof(BloomFilter, data);
filter = (BloomFilter *) palloc0(len);
@@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* brin_bloom_get_ndistinct
* Determine the ndistinct value used to size bloom filter.
*
- * Tweak the ndistinct value based on the pagesPerRange value. First,
+ * Adjust the ndistinct value based on the pagesPerRange value. First,
* if it's negative, it's assumed to be relative to maximum number of
* tuples in the range (assuming each page gets MaxHeapTuplesPerPage
* tuples, which is likely a significant over-estimate). We also clamp
@@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* and compute the expected number of distinct values in a range. But
* that may be tricky due to data being sorted in various ways, so it
* seems better to rely on the upper estimate.
+ *
+ * XXX We might also calculate a better estimate of rows per BRIN range,
+ * instead of using MaxHeapTuplesPerPage (which probably produces values
+ * much higher than reality).
*/
static int
brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
@@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
return (int) ndistinct;
}
-static double
-brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts)
-{
- return BloomGetFalsePositiveRate(opts);
-}
/*
* Examine the given index tuple (which contains partial status of a certain
@@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS)
if (column->bv_allnulls)
{
filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
- brin_bloom_get_fp_rate(bdesc, opts));
+ BloomGetFalsePositiveRate(opts));
column->bv_values[0] = PointerGetDatum(filter);
column->bv_allnulls = false;
updated = true;
@@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS)
* Cache and return inclusion opclass support procedure
*
* Return the procedure corresponding to the given function support number
- * or null if it is not exists.
+ * or null if it does not exists.
*/
static FmgrInfo *
bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
@@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
initStringInfo(&str);
appendStringInfoChar(&str, '{');
- /*
- * XXX not sure the detoasting is necessary (probably not, this
- * can only be in an index).
- */
- filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0));
+ /* Detoasting not needed (this can only be in an index). */
+ filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0);
if (BLOOM_IS_HASHED(filter))
{
@@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
}
else
{
+ /*
+ * XXX Maybe include the sorted/unsorted values? Seems a bit too
+ * much useless detail (internal hash values).
+ */
appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u",
filter->nvalues, filter->nsorted);
- /* TODO include the sorted/unsorted values */
}
appendStringInfoChar(&str, '}');
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
index 19b866283a..24ea5f6e42 100644
--- a/src/test/regress/expected/brin_bloom.out
+++ b/src/test/regress/expected/brin_bloom.out
@@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
);
ERROR: value -1.1 out of bounds for option "n_distinct_per_range"
DETAIL: Valid values are between "-1.000000" and "2147483647.000000".
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
-ERROR: value 0.0009 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.00009 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
-ERROR: value 0.11 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.26 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops,
charcol char_bloom_ops,
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
index 3c2ef56316..d587f3962f 100644
--- a/src/test/regress/sql/brin_bloom.sql
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops(n_distinct_per_range = -1.1)
);
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
--
2.26.2
--------------CF71AF65F7C337C37C24B045
Content-Type: text/x-patch; charset=UTF-8;
name="0006-add-sort_mode-opclass-parameter-20210112.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0006-add-sort_mode-opclass-parameter-20210112.patch"
^ permalink raw reply [nested|flat] 24+ messages in thread
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw)
---
doc/src/sgml/ref/create_index.sgml | 2 +-
src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++----------
src/test/regress/expected/brin_bloom.out | 14 ++--
src/test/regress/sql/brin_bloom.sql | 6 +-
4 files changed, 60 insertions(+), 46 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 8db10b7b1e..244e5834d8 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class=
equal to -1, the number of distinct non-null is assumed linear with
the maximum possible number of tuples in the block range (about 290
rows per block). The default values is <literal>-0.1</literal>, and
- the minimum number of distinct non-null values is <literal>128</literal>.
+ the minimum number of distinct non-null values is <literal>16</literal>.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index b7aa6d9f11..ffeb459d3e 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -8,12 +8,12 @@
*
* A BRIN opclass summarizing page range into a bloom filter.
*
- * Bloom filters allow efficient test whether a given page range contains
+ * Bloom filters allow efficient testing whether a given page range contains
* a particular value. Therefore, if we summarize each page range into a
- * bloom filter, we can easily and cheaply test wheter it containst values
+ * bloom filter, we can easily and cheaply test wheter it contains values
* we get later.
*
- * The index only supports equality operator, similarly to hash indexes.
+ * The index only supports equality operators, similarly to hash indexes.
* BRIN bloom indexes are however much smaller, and support only bitmap
* scans.
*
@@ -51,9 +51,9 @@
* the bloom filter. On the other hand, we want to keep the index as small
* as possible - that's one of the basic advantages of BRIN indexes.
*
- * The number of distinct elements (in a page range) depends on the data,
- * we can consider it fixed. This simplifies the trade-off to just false
- * positive rate vs. size.
+ * Although the number of distinct elements (in a page range) depends on
+ * the data, we can consider it fixed. This simplifies the trade-off to
+ * just false positive rate vs. size.
*
* At the page range level, false positive rate is a probability the bloom
* filter matches a random value. For the whole index (with sufficiently
@@ -65,7 +65,7 @@
* the bitmap is inherently random, compression can't reliably help here.
* To reduce the size of a filter (to fit to a page), we have to either
* accept higher false positive rate (undesirable), or reduce the number
- * of distinct items to be stored in the filter. We can't quite the input
+ * of distinct items to be stored in the filter. We can't alter the input
* data, of course, but we may make the BRIN page ranges smaller - instead
* of the default 128 pages (1MB) we may build index with 16-page ranges,
* or something like that. This does help even for random data sets, as
@@ -87,7 +87,8 @@
* not entirely clear how to distrubute the space between those columns.
*
* The current logic, implemented in brin_bloom_get_ndistinct, attempts to
- * make some basic sizing decisions, based on the table ndistinct estimate.
+ * make some basic sizing decisions, based on the size of BRIN ranges, and
+ * the maximum number of rows per range.
*
*
* sort vs. hash
@@ -200,10 +201,20 @@ typedef struct BloomOptions
/*
* Allowed range and default value for the false positive range. The exact
- * values are somewhat arbitrary.
+ * values are somewhat arbitrary, but were chosen considering the various
+ * parameters (size of filter vs. page size, etc.).
+ *
+ * The lower the false-positive rate, the more accurate the filter is, but
+ * it also gets larger - at some point this eliminates the main advantage
+ * of BRIN indexes, which is the tiny size. At 0.01% the index is about
+ * 10% of the table (assuming 290 distinct values per 8kB page).
+ *
+ * On the other hand, as the false-positive rate increases, larger part of
+ * the table has to be scanned due to mismatches - at 25% we're probably
+ * close to sequential scan being cheaper.
*/
-#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */
-#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */
+#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
+#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
#define BloomGetNDistinctPerRange(opts) \
@@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate)
Assert(ndistinct > 0);
Assert((false_positive_rate > 0) && (false_positive_rate < 1.0));
- m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0)))));
+ /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
+ m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
/* round m to whole bytes */
m = ((m + 7) / 8) * 8;
+ /*
+ * Reject filters that are obviously too large to store on a page.
+ *
+ * We do expect the bloom filter to eventually switch to hashing mode,
+ * and it's bound to be almost perfectly random, so not compressible.
+ */
+ if ((m/8) > BLCKSZ)
+ elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ);
+
/*
* round(log(2.0) * m / ndistinct), but assume round() may not be
* available on Windows
@@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate)
k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
/*
- * Allocate the bloom filter with a minimum size 64B (about 40B in the
- * bitmap part). We require space at least for the header.
- *
- * XXX Maybe the 64B min size is not really needed?
+ * Allocate the bloom filter (initially it's just a header, we'll make
+ * it larger as needed).
*/
- len = Max(offsetof(BloomFilter, data), 64);
-
- /* Reject filters that are obviously too large to store on a page. */
- if (len > BLCKSZ)
- elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ);
+ len = offsetof(BloomFilter, data);
filter = (BloomFilter *) palloc0(len);
@@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* brin_bloom_get_ndistinct
* Determine the ndistinct value used to size bloom filter.
*
- * Tweak the ndistinct value based on the pagesPerRange value. First,
+ * Adjust the ndistinct value based on the pagesPerRange value. First,
* if it's negative, it's assumed to be relative to maximum number of
* tuples in the range (assuming each page gets MaxHeapTuplesPerPage
* tuples, which is likely a significant over-estimate). We also clamp
@@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* and compute the expected number of distinct values in a range. But
* that may be tricky due to data being sorted in various ways, so it
* seems better to rely on the upper estimate.
+ *
+ * XXX We might also calculate a better estimate of rows per BRIN range,
+ * instead of using MaxHeapTuplesPerPage (which probably produces values
+ * much higher than reality).
*/
static int
brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
@@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
return (int) ndistinct;
}
-static double
-brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts)
-{
- return BloomGetFalsePositiveRate(opts);
-}
/*
* Examine the given index tuple (which contains partial status of a certain
@@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS)
if (column->bv_allnulls)
{
filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
- brin_bloom_get_fp_rate(bdesc, opts));
+ BloomGetFalsePositiveRate(opts));
column->bv_values[0] = PointerGetDatum(filter);
column->bv_allnulls = false;
updated = true;
@@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS)
* Cache and return inclusion opclass support procedure
*
* Return the procedure corresponding to the given function support number
- * or null if it is not exists.
+ * or null if it does not exists.
*/
static FmgrInfo *
bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
@@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
initStringInfo(&str);
appendStringInfoChar(&str, '{');
- /*
- * XXX not sure the detoasting is necessary (probably not, this
- * can only be in an index).
- */
- filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0));
+ /* Detoasting not needed (this can only be in an index). */
+ filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0);
if (BLOOM_IS_HASHED(filter))
{
@@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
}
else
{
+ /*
+ * XXX Maybe include the sorted/unsorted values? Seems a bit too
+ * much useless detail (internal hash values).
+ */
appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u",
filter->nvalues, filter->nsorted);
- /* TODO include the sorted/unsorted values */
}
appendStringInfoChar(&str, '}');
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
index 19b866283a..24ea5f6e42 100644
--- a/src/test/regress/expected/brin_bloom.out
+++ b/src/test/regress/expected/brin_bloom.out
@@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
);
ERROR: value -1.1 out of bounds for option "n_distinct_per_range"
DETAIL: Valid values are between "-1.000000" and "2147483647.000000".
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
-ERROR: value 0.0009 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.00009 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
-ERROR: value 0.11 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.26 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops,
charcol char_bloom_ops,
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
index 3c2ef56316..d587f3962f 100644
--- a/src/test/regress/sql/brin_bloom.sql
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops(n_distinct_per_range = -1.1)
);
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
--
2.26.2
--------------CF71AF65F7C337C37C24B045
Content-Type: text/x-patch; charset=UTF-8;
name="0006-add-sort_mode-opclass-parameter-20210112.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0006-add-sort_mode-opclass-parameter-20210112.patch"
^ permalink raw reply [nested|flat] 24+ messages in thread
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw)
---
doc/src/sgml/ref/create_index.sgml | 2 +-
src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++----------
src/test/regress/expected/brin_bloom.out | 14 ++--
src/test/regress/sql/brin_bloom.sql | 6 +-
4 files changed, 60 insertions(+), 46 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 8db10b7b1e..244e5834d8 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class=
equal to -1, the number of distinct non-null is assumed linear with
the maximum possible number of tuples in the block range (about 290
rows per block). The default values is <literal>-0.1</literal>, and
- the minimum number of distinct non-null values is <literal>128</literal>.
+ the minimum number of distinct non-null values is <literal>16</literal>.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index b7aa6d9f11..ffeb459d3e 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -8,12 +8,12 @@
*
* A BRIN opclass summarizing page range into a bloom filter.
*
- * Bloom filters allow efficient test whether a given page range contains
+ * Bloom filters allow efficient testing whether a given page range contains
* a particular value. Therefore, if we summarize each page range into a
- * bloom filter, we can easily and cheaply test wheter it containst values
+ * bloom filter, we can easily and cheaply test wheter it contains values
* we get later.
*
- * The index only supports equality operator, similarly to hash indexes.
+ * The index only supports equality operators, similarly to hash indexes.
* BRIN bloom indexes are however much smaller, and support only bitmap
* scans.
*
@@ -51,9 +51,9 @@
* the bloom filter. On the other hand, we want to keep the index as small
* as possible - that's one of the basic advantages of BRIN indexes.
*
- * The number of distinct elements (in a page range) depends on the data,
- * we can consider it fixed. This simplifies the trade-off to just false
- * positive rate vs. size.
+ * Although the number of distinct elements (in a page range) depends on
+ * the data, we can consider it fixed. This simplifies the trade-off to
+ * just false positive rate vs. size.
*
* At the page range level, false positive rate is a probability the bloom
* filter matches a random value. For the whole index (with sufficiently
@@ -65,7 +65,7 @@
* the bitmap is inherently random, compression can't reliably help here.
* To reduce the size of a filter (to fit to a page), we have to either
* accept higher false positive rate (undesirable), or reduce the number
- * of distinct items to be stored in the filter. We can't quite the input
+ * of distinct items to be stored in the filter. We can't alter the input
* data, of course, but we may make the BRIN page ranges smaller - instead
* of the default 128 pages (1MB) we may build index with 16-page ranges,
* or something like that. This does help even for random data sets, as
@@ -87,7 +87,8 @@
* not entirely clear how to distrubute the space between those columns.
*
* The current logic, implemented in brin_bloom_get_ndistinct, attempts to
- * make some basic sizing decisions, based on the table ndistinct estimate.
+ * make some basic sizing decisions, based on the size of BRIN ranges, and
+ * the maximum number of rows per range.
*
*
* sort vs. hash
@@ -200,10 +201,20 @@ typedef struct BloomOptions
/*
* Allowed range and default value for the false positive range. The exact
- * values are somewhat arbitrary.
+ * values are somewhat arbitrary, but were chosen considering the various
+ * parameters (size of filter vs. page size, etc.).
+ *
+ * The lower the false-positive rate, the more accurate the filter is, but
+ * it also gets larger - at some point this eliminates the main advantage
+ * of BRIN indexes, which is the tiny size. At 0.01% the index is about
+ * 10% of the table (assuming 290 distinct values per 8kB page).
+ *
+ * On the other hand, as the false-positive rate increases, larger part of
+ * the table has to be scanned due to mismatches - at 25% we're probably
+ * close to sequential scan being cheaper.
*/
-#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */
-#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */
+#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
+#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
#define BloomGetNDistinctPerRange(opts) \
@@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate)
Assert(ndistinct > 0);
Assert((false_positive_rate > 0) && (false_positive_rate < 1.0));
- m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0)))));
+ /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
+ m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
/* round m to whole bytes */
m = ((m + 7) / 8) * 8;
+ /*
+ * Reject filters that are obviously too large to store on a page.
+ *
+ * We do expect the bloom filter to eventually switch to hashing mode,
+ * and it's bound to be almost perfectly random, so not compressible.
+ */
+ if ((m/8) > BLCKSZ)
+ elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ);
+
/*
* round(log(2.0) * m / ndistinct), but assume round() may not be
* available on Windows
@@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate)
k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
/*
- * Allocate the bloom filter with a minimum size 64B (about 40B in the
- * bitmap part). We require space at least for the header.
- *
- * XXX Maybe the 64B min size is not really needed?
+ * Allocate the bloom filter (initially it's just a header, we'll make
+ * it larger as needed).
*/
- len = Max(offsetof(BloomFilter, data), 64);
-
- /* Reject filters that are obviously too large to store on a page. */
- if (len > BLCKSZ)
- elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ);
+ len = offsetof(BloomFilter, data);
filter = (BloomFilter *) palloc0(len);
@@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* brin_bloom_get_ndistinct
* Determine the ndistinct value used to size bloom filter.
*
- * Tweak the ndistinct value based on the pagesPerRange value. First,
+ * Adjust the ndistinct value based on the pagesPerRange value. First,
* if it's negative, it's assumed to be relative to maximum number of
* tuples in the range (assuming each page gets MaxHeapTuplesPerPage
* tuples, which is likely a significant over-estimate). We also clamp
@@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* and compute the expected number of distinct values in a range. But
* that may be tricky due to data being sorted in various ways, so it
* seems better to rely on the upper estimate.
+ *
+ * XXX We might also calculate a better estimate of rows per BRIN range,
+ * instead of using MaxHeapTuplesPerPage (which probably produces values
+ * much higher than reality).
*/
static int
brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
@@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
return (int) ndistinct;
}
-static double
-brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts)
-{
- return BloomGetFalsePositiveRate(opts);
-}
/*
* Examine the given index tuple (which contains partial status of a certain
@@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS)
if (column->bv_allnulls)
{
filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
- brin_bloom_get_fp_rate(bdesc, opts));
+ BloomGetFalsePositiveRate(opts));
column->bv_values[0] = PointerGetDatum(filter);
column->bv_allnulls = false;
updated = true;
@@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS)
* Cache and return inclusion opclass support procedure
*
* Return the procedure corresponding to the given function support number
- * or null if it is not exists.
+ * or null if it does not exists.
*/
static FmgrInfo *
bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
@@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
initStringInfo(&str);
appendStringInfoChar(&str, '{');
- /*
- * XXX not sure the detoasting is necessary (probably not, this
- * can only be in an index).
- */
- filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0));
+ /* Detoasting not needed (this can only be in an index). */
+ filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0);
if (BLOOM_IS_HASHED(filter))
{
@@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
}
else
{
+ /*
+ * XXX Maybe include the sorted/unsorted values? Seems a bit too
+ * much useless detail (internal hash values).
+ */
appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u",
filter->nvalues, filter->nsorted);
- /* TODO include the sorted/unsorted values */
}
appendStringInfoChar(&str, '}');
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
index 19b866283a..24ea5f6e42 100644
--- a/src/test/regress/expected/brin_bloom.out
+++ b/src/test/regress/expected/brin_bloom.out
@@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
);
ERROR: value -1.1 out of bounds for option "n_distinct_per_range"
DETAIL: Valid values are between "-1.000000" and "2147483647.000000".
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
-ERROR: value 0.0009 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.00009 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
-ERROR: value 0.11 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.26 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops,
charcol char_bloom_ops,
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
index 3c2ef56316..d587f3962f 100644
--- a/src/test/regress/sql/brin_bloom.sql
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops(n_distinct_per_range = -1.1)
);
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
--
2.26.2
--------------CF71AF65F7C337C37C24B045
Content-Type: text/x-patch; charset=UTF-8;
name="0006-add-sort_mode-opclass-parameter-20210112.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0006-add-sort_mode-opclass-parameter-20210112.patch"
^ permalink raw reply [nested|flat] 24+ messages in thread
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw)
---
doc/src/sgml/ref/create_index.sgml | 2 +-
src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++----------
src/test/regress/expected/brin_bloom.out | 14 ++--
src/test/regress/sql/brin_bloom.sql | 6 +-
4 files changed, 60 insertions(+), 46 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 8db10b7b1e..244e5834d8 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class=
equal to -1, the number of distinct non-null is assumed linear with
the maximum possible number of tuples in the block range (about 290
rows per block). The default values is <literal>-0.1</literal>, and
- the minimum number of distinct non-null values is <literal>128</literal>.
+ the minimum number of distinct non-null values is <literal>16</literal>.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index b7aa6d9f11..ffeb459d3e 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -8,12 +8,12 @@
*
* A BRIN opclass summarizing page range into a bloom filter.
*
- * Bloom filters allow efficient test whether a given page range contains
+ * Bloom filters allow efficient testing whether a given page range contains
* a particular value. Therefore, if we summarize each page range into a
- * bloom filter, we can easily and cheaply test wheter it containst values
+ * bloom filter, we can easily and cheaply test wheter it contains values
* we get later.
*
- * The index only supports equality operator, similarly to hash indexes.
+ * The index only supports equality operators, similarly to hash indexes.
* BRIN bloom indexes are however much smaller, and support only bitmap
* scans.
*
@@ -51,9 +51,9 @@
* the bloom filter. On the other hand, we want to keep the index as small
* as possible - that's one of the basic advantages of BRIN indexes.
*
- * The number of distinct elements (in a page range) depends on the data,
- * we can consider it fixed. This simplifies the trade-off to just false
- * positive rate vs. size.
+ * Although the number of distinct elements (in a page range) depends on
+ * the data, we can consider it fixed. This simplifies the trade-off to
+ * just false positive rate vs. size.
*
* At the page range level, false positive rate is a probability the bloom
* filter matches a random value. For the whole index (with sufficiently
@@ -65,7 +65,7 @@
* the bitmap is inherently random, compression can't reliably help here.
* To reduce the size of a filter (to fit to a page), we have to either
* accept higher false positive rate (undesirable), or reduce the number
- * of distinct items to be stored in the filter. We can't quite the input
+ * of distinct items to be stored in the filter. We can't alter the input
* data, of course, but we may make the BRIN page ranges smaller - instead
* of the default 128 pages (1MB) we may build index with 16-page ranges,
* or something like that. This does help even for random data sets, as
@@ -87,7 +87,8 @@
* not entirely clear how to distrubute the space between those columns.
*
* The current logic, implemented in brin_bloom_get_ndistinct, attempts to
- * make some basic sizing decisions, based on the table ndistinct estimate.
+ * make some basic sizing decisions, based on the size of BRIN ranges, and
+ * the maximum number of rows per range.
*
*
* sort vs. hash
@@ -200,10 +201,20 @@ typedef struct BloomOptions
/*
* Allowed range and default value for the false positive range. The exact
- * values are somewhat arbitrary.
+ * values are somewhat arbitrary, but were chosen considering the various
+ * parameters (size of filter vs. page size, etc.).
+ *
+ * The lower the false-positive rate, the more accurate the filter is, but
+ * it also gets larger - at some point this eliminates the main advantage
+ * of BRIN indexes, which is the tiny size. At 0.01% the index is about
+ * 10% of the table (assuming 290 distinct values per 8kB page).
+ *
+ * On the other hand, as the false-positive rate increases, larger part of
+ * the table has to be scanned due to mismatches - at 25% we're probably
+ * close to sequential scan being cheaper.
*/
-#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */
-#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */
+#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
+#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
#define BloomGetNDistinctPerRange(opts) \
@@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate)
Assert(ndistinct > 0);
Assert((false_positive_rate > 0) && (false_positive_rate < 1.0));
- m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0)))));
+ /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
+ m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
/* round m to whole bytes */
m = ((m + 7) / 8) * 8;
+ /*
+ * Reject filters that are obviously too large to store on a page.
+ *
+ * We do expect the bloom filter to eventually switch to hashing mode,
+ * and it's bound to be almost perfectly random, so not compressible.
+ */
+ if ((m/8) > BLCKSZ)
+ elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ);
+
/*
* round(log(2.0) * m / ndistinct), but assume round() may not be
* available on Windows
@@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate)
k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
/*
- * Allocate the bloom filter with a minimum size 64B (about 40B in the
- * bitmap part). We require space at least for the header.
- *
- * XXX Maybe the 64B min size is not really needed?
+ * Allocate the bloom filter (initially it's just a header, we'll make
+ * it larger as needed).
*/
- len = Max(offsetof(BloomFilter, data), 64);
-
- /* Reject filters that are obviously too large to store on a page. */
- if (len > BLCKSZ)
- elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ);
+ len = offsetof(BloomFilter, data);
filter = (BloomFilter *) palloc0(len);
@@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* brin_bloom_get_ndistinct
* Determine the ndistinct value used to size bloom filter.
*
- * Tweak the ndistinct value based on the pagesPerRange value. First,
+ * Adjust the ndistinct value based on the pagesPerRange value. First,
* if it's negative, it's assumed to be relative to maximum number of
* tuples in the range (assuming each page gets MaxHeapTuplesPerPage
* tuples, which is likely a significant over-estimate). We also clamp
@@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* and compute the expected number of distinct values in a range. But
* that may be tricky due to data being sorted in various ways, so it
* seems better to rely on the upper estimate.
+ *
+ * XXX We might also calculate a better estimate of rows per BRIN range,
+ * instead of using MaxHeapTuplesPerPage (which probably produces values
+ * much higher than reality).
*/
static int
brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
@@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
return (int) ndistinct;
}
-static double
-brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts)
-{
- return BloomGetFalsePositiveRate(opts);
-}
/*
* Examine the given index tuple (which contains partial status of a certain
@@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS)
if (column->bv_allnulls)
{
filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
- brin_bloom_get_fp_rate(bdesc, opts));
+ BloomGetFalsePositiveRate(opts));
column->bv_values[0] = PointerGetDatum(filter);
column->bv_allnulls = false;
updated = true;
@@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS)
* Cache and return inclusion opclass support procedure
*
* Return the procedure corresponding to the given function support number
- * or null if it is not exists.
+ * or null if it does not exists.
*/
static FmgrInfo *
bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
@@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
initStringInfo(&str);
appendStringInfoChar(&str, '{');
- /*
- * XXX not sure the detoasting is necessary (probably not, this
- * can only be in an index).
- */
- filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0));
+ /* Detoasting not needed (this can only be in an index). */
+ filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0);
if (BLOOM_IS_HASHED(filter))
{
@@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
}
else
{
+ /*
+ * XXX Maybe include the sorted/unsorted values? Seems a bit too
+ * much useless detail (internal hash values).
+ */
appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u",
filter->nvalues, filter->nsorted);
- /* TODO include the sorted/unsorted values */
}
appendStringInfoChar(&str, '}');
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
index 19b866283a..24ea5f6e42 100644
--- a/src/test/regress/expected/brin_bloom.out
+++ b/src/test/regress/expected/brin_bloom.out
@@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
);
ERROR: value -1.1 out of bounds for option "n_distinct_per_range"
DETAIL: Valid values are between "-1.000000" and "2147483647.000000".
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
-ERROR: value 0.0009 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.00009 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
-ERROR: value 0.11 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.26 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops,
charcol char_bloom_ops,
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
index 3c2ef56316..d587f3962f 100644
--- a/src/test/regress/sql/brin_bloom.sql
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops(n_distinct_per_range = -1.1)
);
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
--
2.26.2
--------------CF71AF65F7C337C37C24B045
Content-Type: text/x-patch; charset=UTF-8;
name="0006-add-sort_mode-opclass-parameter-20210112.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0006-add-sort_mode-opclass-parameter-20210112.patch"
^ permalink raw reply [nested|flat] 24+ messages in thread
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw)
---
doc/src/sgml/ref/create_index.sgml | 2 +-
src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++----------
src/test/regress/expected/brin_bloom.out | 14 ++--
src/test/regress/sql/brin_bloom.sql | 6 +-
4 files changed, 60 insertions(+), 46 deletions(-)
diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml
index 8db10b7b1e..244e5834d8 100644
--- a/doc/src/sgml/ref/create_index.sgml
+++ b/doc/src/sgml/ref/create_index.sgml
@@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class=
equal to -1, the number of distinct non-null is assumed linear with
the maximum possible number of tuples in the block range (about 290
rows per block). The default values is <literal>-0.1</literal>, and
- the minimum number of distinct non-null values is <literal>128</literal>.
+ the minimum number of distinct non-null values is <literal>16</literal>.
</para>
</listitem>
</varlistentry>
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index b7aa6d9f11..ffeb459d3e 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -8,12 +8,12 @@
*
* A BRIN opclass summarizing page range into a bloom filter.
*
- * Bloom filters allow efficient test whether a given page range contains
+ * Bloom filters allow efficient testing whether a given page range contains
* a particular value. Therefore, if we summarize each page range into a
- * bloom filter, we can easily and cheaply test wheter it containst values
+ * bloom filter, we can easily and cheaply test wheter it contains values
* we get later.
*
- * The index only supports equality operator, similarly to hash indexes.
+ * The index only supports equality operators, similarly to hash indexes.
* BRIN bloom indexes are however much smaller, and support only bitmap
* scans.
*
@@ -51,9 +51,9 @@
* the bloom filter. On the other hand, we want to keep the index as small
* as possible - that's one of the basic advantages of BRIN indexes.
*
- * The number of distinct elements (in a page range) depends on the data,
- * we can consider it fixed. This simplifies the trade-off to just false
- * positive rate vs. size.
+ * Although the number of distinct elements (in a page range) depends on
+ * the data, we can consider it fixed. This simplifies the trade-off to
+ * just false positive rate vs. size.
*
* At the page range level, false positive rate is a probability the bloom
* filter matches a random value. For the whole index (with sufficiently
@@ -65,7 +65,7 @@
* the bitmap is inherently random, compression can't reliably help here.
* To reduce the size of a filter (to fit to a page), we have to either
* accept higher false positive rate (undesirable), or reduce the number
- * of distinct items to be stored in the filter. We can't quite the input
+ * of distinct items to be stored in the filter. We can't alter the input
* data, of course, but we may make the BRIN page ranges smaller - instead
* of the default 128 pages (1MB) we may build index with 16-page ranges,
* or something like that. This does help even for random data sets, as
@@ -87,7 +87,8 @@
* not entirely clear how to distrubute the space between those columns.
*
* The current logic, implemented in brin_bloom_get_ndistinct, attempts to
- * make some basic sizing decisions, based on the table ndistinct estimate.
+ * make some basic sizing decisions, based on the size of BRIN ranges, and
+ * the maximum number of rows per range.
*
*
* sort vs. hash
@@ -200,10 +201,20 @@ typedef struct BloomOptions
/*
* Allowed range and default value for the false positive range. The exact
- * values are somewhat arbitrary.
+ * values are somewhat arbitrary, but were chosen considering the various
+ * parameters (size of filter vs. page size, etc.).
+ *
+ * The lower the false-positive rate, the more accurate the filter is, but
+ * it also gets larger - at some point this eliminates the main advantage
+ * of BRIN indexes, which is the tiny size. At 0.01% the index is about
+ * 10% of the table (assuming 290 distinct values per 8kB page).
+ *
+ * On the other hand, as the false-positive rate increases, larger part of
+ * the table has to be scanned due to mismatches - at 25% we're probably
+ * close to sequential scan being cheaper.
*/
-#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */
-#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */
+#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
+#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
#define BloomGetNDistinctPerRange(opts) \
@@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate)
Assert(ndistinct > 0);
Assert((false_positive_rate > 0) && (false_positive_rate < 1.0));
- m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0)))));
+ /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
+ m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
/* round m to whole bytes */
m = ((m + 7) / 8) * 8;
+ /*
+ * Reject filters that are obviously too large to store on a page.
+ *
+ * We do expect the bloom filter to eventually switch to hashing mode,
+ * and it's bound to be almost perfectly random, so not compressible.
+ */
+ if ((m/8) > BLCKSZ)
+ elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ);
+
/*
* round(log(2.0) * m / ndistinct), but assume round() may not be
* available on Windows
@@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate)
k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
/*
- * Allocate the bloom filter with a minimum size 64B (about 40B in the
- * bitmap part). We require space at least for the header.
- *
- * XXX Maybe the 64B min size is not really needed?
+ * Allocate the bloom filter (initially it's just a header, we'll make
+ * it larger as needed).
*/
- len = Max(offsetof(BloomFilter, data), 64);
-
- /* Reject filters that are obviously too large to store on a page. */
- if (len > BLCKSZ)
- elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ);
+ len = offsetof(BloomFilter, data);
filter = (BloomFilter *) palloc0(len);
@@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* brin_bloom_get_ndistinct
* Determine the ndistinct value used to size bloom filter.
*
- * Tweak the ndistinct value based on the pagesPerRange value. First,
+ * Adjust the ndistinct value based on the pagesPerRange value. First,
* if it's negative, it's assumed to be relative to maximum number of
* tuples in the range (assuming each page gets MaxHeapTuplesPerPage
* tuples, which is likely a significant over-estimate). We also clamp
@@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS)
* and compute the expected number of distinct values in a range. But
* that may be tricky due to data being sorted in various ways, so it
* seems better to rely on the upper estimate.
+ *
+ * XXX We might also calculate a better estimate of rows per BRIN range,
+ * instead of using MaxHeapTuplesPerPage (which probably produces values
+ * much higher than reality).
*/
static int
brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
@@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
return (int) ndistinct;
}
-static double
-brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts)
-{
- return BloomGetFalsePositiveRate(opts);
-}
/*
* Examine the given index tuple (which contains partial status of a certain
@@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS)
if (column->bv_allnulls)
{
filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
- brin_bloom_get_fp_rate(bdesc, opts));
+ BloomGetFalsePositiveRate(opts));
column->bv_values[0] = PointerGetDatum(filter);
column->bv_allnulls = false;
updated = true;
@@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS)
* Cache and return inclusion opclass support procedure
*
* Return the procedure corresponding to the given function support number
- * or null if it is not exists.
+ * or null if it does not exists.
*/
static FmgrInfo *
bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
@@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
initStringInfo(&str);
appendStringInfoChar(&str, '{');
- /*
- * XXX not sure the detoasting is necessary (probably not, this
- * can only be in an index).
- */
- filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0));
+ /* Detoasting not needed (this can only be in an index). */
+ filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0);
if (BLOOM_IS_HASHED(filter))
{
@@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
}
else
{
+ /*
+ * XXX Maybe include the sorted/unsorted values? Seems a bit too
+ * much useless detail (internal hash values).
+ */
appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u",
filter->nvalues, filter->nsorted);
- /* TODO include the sorted/unsorted values */
}
appendStringInfoChar(&str, '}');
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
index 19b866283a..24ea5f6e42 100644
--- a/src/test/regress/expected/brin_bloom.out
+++ b/src/test/regress/expected/brin_bloom.out
@@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
);
ERROR: value -1.1 out of bounds for option "n_distinct_per_range"
DETAIL: Valid values are between "-1.000000" and "2147483647.000000".
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
-ERROR: value 0.0009 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.00009 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
-ERROR: value 0.11 out of bounds for option "false_positive_rate"
-DETAIL: Valid values are between "0.001000" and "0.100000".
+ERROR: value 0.26 out of bounds for option "false_positive_rate"
+DETAIL: Valid values are between "0.000100" and "0.250000".
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops,
charcol char_bloom_ops,
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
index 3c2ef56316..d587f3962f 100644
--- a/src/test/regress/sql/brin_bloom.sql
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
byteacol bytea_bloom_ops(n_distinct_per_range = -1.1)
);
--- false_positive_rate must be between 0.001 and 1.0
+-- false_positive_rate must be between 0.0001 and 0.25
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.0009)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.00009)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
- byteacol bytea_bloom_ops(false_positive_rate = 0.11)
+ byteacol bytea_bloom_ops(false_positive_rate = 0.26)
);
CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
--
2.26.2
--------------CF71AF65F7C337C37C24B045
Content-Type: text/x-patch; charset=UTF-8;
name="0006-add-sort_mode-opclass-parameter-20210112.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0006-add-sort_mode-opclass-parameter-20210112.patch"
^ permalink raw reply [nested|flat] 24+ messages in thread
* Re: Wrong results from Parallel Hash Full Join
@ 2023-04-19 19:20 Andres Freund <[email protected]>
2023-04-20 00:41 ` Re: Wrong results from Parallel Hash Full Join Justin Pryzby <[email protected]>
0 siblings, 1 reply; 24+ messages in thread
From: Andres Freund @ 2023-04-19 19:20 UTC (permalink / raw)
To: Justin Pryzby <[email protected]>; +Cc: Melanie Plageman <[email protected]>; Thomas Munro <[email protected]>; Richard Guo <[email protected]>; pgsql-hackers
Hi,
On 2023-04-19 12:16:24 -0500, Justin Pryzby wrote:
> On Wed, Apr 19, 2023 at 11:17:04AM -0400, Melanie Plageman wrote:
> > Ultimately this is probably fine. If we wanted to modify one of the
> > existing tests to cover the multi-batch case, changing the select
> > count(*) to a select * would do the trick. I imagine we wouldn't want to
> > do this because of the excessive output this would produce. I wondered
> > if there was a pattern in the tests for getting around this.
>
> You could use explain (ANALYZE). But the output is machine-dependant in
> various ways (which is why the tests use "explain analyze so rarely).
I think with sufficient options it's not machine specific. We have a bunch of
EXPLAIN (ANALYZE, COSTS OFF, SUMMARY OFF, TIMING OFF) ..
in our tests.
Greetings,
Andres Freund
^ permalink raw reply [nested|flat] 24+ messages in thread
* Re: Wrong results from Parallel Hash Full Join
2023-04-19 19:20 Re: Wrong results from Parallel Hash Full Join Andres Freund <[email protected]>
@ 2023-04-20 00:41 ` Justin Pryzby <[email protected]>
0 siblings, 0 replies; 24+ messages in thread
From: Justin Pryzby @ 2023-04-20 00:41 UTC (permalink / raw)
To: Andres Freund <[email protected]>; +Cc: Melanie Plageman <[email protected]>; Thomas Munro <[email protected]>; Richard Guo <[email protected]>; pgsql-hackers
On Wed, Apr 19, 2023 at 12:20:51PM -0700, Andres Freund wrote:
> On 2023-04-19 12:16:24 -0500, Justin Pryzby wrote:
> > On Wed, Apr 19, 2023 at 11:17:04AM -0400, Melanie Plageman wrote:
> > > Ultimately this is probably fine. If we wanted to modify one of the
> > > existing tests to cover the multi-batch case, changing the select
> > > count(*) to a select * would do the trick. I imagine we wouldn't want to
> > > do this because of the excessive output this would produce. I wondered
> > > if there was a pattern in the tests for getting around this.
> >
> > You could use explain (ANALYZE). But the output is machine-dependant in
> > various ways (which is why the tests use "explain analyze so rarely).
>
> I think with sufficient options it's not machine specific.
It *can* be machine specific depending on the node type..
In particular, for parallel workers, it shows "Workers Launched: ..",
which can vary even across executions on the same machine. And don't
forget about "loops=".
Plus:
src/backend/commands/explain.c: "Buckets: %d Batches: %d Memory Usage: %ldkB\n",
> We have a bunch of
> EXPLAIN (ANALYZE, COSTS OFF, SUMMARY OFF, TIMING OFF) ..
> in our tests.
There's 81 uses of "timing off", out of a total of ~1600 explains. Most
of them are in partition_prune.sql. explain analyze is barely used.
I sent a patch to elide the machine-specific parts, which would make it
easier to use. But there was no interest.
--
Justin
^ permalink raw reply [nested|flat] 24+ messages in thread
end of thread, other threads:[~2023-04-20 00:41 UTC | newest]
Thread overview: 24+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2017-05-01 00:13 Re: Crash when partition column specified twice Amit Langote <[email protected]>
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2023-04-19 19:20 Re: Wrong results from Parallel Hash Full Join Andres Freund <[email protected]>
2023-04-20 00:41 ` Re: Wrong results from Parallel Hash Full Join Justin Pryzby <[email protected]>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox