Subject: [PATCH 5/8] bloom fixes and tweaks

From: Tomas Vondra <[email-masked]>
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"