public inbox for [email protected]
help / color / mirror / Atom feed[PATCH 5/8] bloom fixes and tweaks
3+ messages / 3 participants
[nested] [flat]
* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 3+ 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] 3+ messages in thread
* Re: An incorrect check in get_memoize_path
@ 2025-04-07 12:54 Andrei Lepikhov <[email protected]>
2025-04-08 06:32 ` Re: An incorrect check in get_memoize_path Richard Guo <[email protected]>
0 siblings, 1 reply; 3+ messages in thread
From: Andrei Lepikhov @ 2025-04-07 12:54 UTC (permalink / raw)
To: Richard Guo <[email protected]>; +Cc: Pg Hackers <[email protected]>
On 4/7/25 09:50, Richard Guo wrote:
> Consider the join to t3. It is a unique join, and not all of its
> restriction clauses are parameterized. Despite this, the check still
> passes.
At least, this code looks more simple to understand, more 'armored' and
worth to change.
At the same time I think term 'Incorrect' is not good unless you show an
example where data returned is not consistent to the expected.
I think this inequality check has worked in couple with the
get_equal_hashops.
I think it may be pushed as is. But it worth to discover the
get_equal_hashops more deeply. Discovering your idea I wrote an example
(see attachment) which (with commented clause_sides_match_join) provides
an incorrect Memoize - that's why I ended up with support of your change
even when you can't show any buggy behaviour. But I've got an assertion
that is different from the error I expected to see (error on single_row
mode):
#0 0x00005583c45532ce in CheckVarSlotCompatibility
#1 0x00005583c4553244 in CheckExprStillValid
#2 0x00005583c45530ea in ExecInterpExprStillValid
#3 0x00005583c45a245c in ExecEvalExpr
#4 0x00005583c45a3985 in prepare_probe_slot
#5 0x00005583c45a3e52 in cache_lookup
#6 0x00005583c45a4313 in ExecMemoize
It looks strange.
--
regards, Andrei Lepikhov
Attachments:
[application/sql] example.sql (1.3K, ../../[email protected]/2-example.sql)
download
^ permalink raw reply [nested|flat] 3+ messages in thread
* Re: An incorrect check in get_memoize_path
2025-04-07 12:54 Re: An incorrect check in get_memoize_path Andrei Lepikhov <[email protected]>
@ 2025-04-08 06:32 ` Richard Guo <[email protected]>
0 siblings, 0 replies; 3+ messages in thread
From: Richard Guo @ 2025-04-08 06:32 UTC (permalink / raw)
To: Andrei Lepikhov <[email protected]>; +Cc: Pg Hackers <[email protected]>
On Mon, Apr 7, 2025 at 9:54 PM Andrei Lepikhov <[email protected]> wrote:
> On 4/7/25 09:50, Richard Guo wrote:
> > Consider the join to t3. It is a unique join, and not all of its
> > restriction clauses are parameterized. Despite this, the check still
> > passes.
> At the same time I think term 'Incorrect' is not good unless you show an
> example where data returned is not consistent to the expected.
> I think this inequality check has worked in couple with the
> get_equal_hashops.
Do you mean this check is designed to work in conjunction with the
clause_sides_match_join check in paraminfo_get_equal_hashops? I would
consider this a very poor design. The purpose of this check is simply
to verify whether all restriction clauses are parameterized. I don't
understand why it needs to depend on paraminfo_get_equal_hashops in
such an unexpected way to function correctly. I can't see any
advantage to this design, other than that it's prone to bugs.
Moreover, in the case where not all restriction clauses are
parameterized, why waste CPU cycles running all the code after the
check only for paraminfo_get_equal_hashops to catch it later?
Additionally, I couldn't find any comments explaining this unusual
behavior, either in the check itself or in paraminfo_get_equal_hashops.
Thanks
Richard
^ permalink raw reply [nested|flat] 3+ messages in thread
end of thread, other threads:[~2025-04-08 06:32 UTC | newest]
Thread overview: 3+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <[email protected]>
2025-04-07 12:54 Re: An incorrect check in get_memoize_path Andrei Lepikhov <[email protected]>
2025-04-08 06:32 ` Re: An incorrect check in get_memoize_path Richard Guo <[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