From: Tomas Vondra Date: Wed, 13 Jan 2021 00:59:02 +0100 Subject: [PATCH 5/8] bloom fixes and tweaks --- 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 ] -0.1, and - the minimum number of distinct non-null values is 128. + the minimum number of distinct non-null values is 16. 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"