public inbox for [email protected]
help / color / mirror / Atom feedFrom: Tomas Vondra <[email protected]>
Subject: [PATCH 5/8] bloom fixes and tweaks
Date: Wed, 13 Jan 2021 00:59:02 +0100
---
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"
view thread (23+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected]
Subject: Re: [PATCH 5/8] bloom fixes and tweaks
In-Reply-To: <no-message-id-1874476@localhost>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox