agora inbox for [email protected]  

help / color / mirror / Atom feed

[PATCH] Do not allocate storage for partitioned tables.
23+ messages / 3 participants
[nested] [flat]

* [PATCH] Do not allocate storage for partitioned tables.
@ 2017-01-24 05:22 amit <[email protected]>
  0 siblings, 0 replies; 23+ messages in thread

From: amit @ 2017-01-24 05:22 UTC (permalink / raw)

Currently, it is not possible to insert any data into a partitioned
table.  So they're empty at all times, which means it is wasteful to
allocate relfilenode and related storage objects.

Also documented the fact that specifying storage options for partitioned
tables is ineffective at the moment.
---
 doc/src/sgml/ref/create_table.sgml |  6 ++++++
 src/backend/catalog/heap.c         | 17 ++++++++++-------
 2 files changed, 16 insertions(+), 7 deletions(-)

diff --git a/doc/src/sgml/ref/create_table.sgml b/doc/src/sgml/ref/create_table.sgml
index 9ed25c05da..7ac55b17fa 100644
--- a/doc/src/sgml/ref/create_table.sgml
+++ b/doc/src/sgml/ref/create_table.sgml
@@ -1040,6 +1040,12 @@ CREATE [ [ GLOBAL | LOCAL ] { TEMPORARY | TEMP } | UNLOGGED ] TABLE [ IF NOT EXI
     will use the table's parameter value.
    </para>
 
+   <para>
+    Note that specifying the following parameters for partitioned tables has
+    no effect at the moment.  You must specify them for individual leaf
+    partitions if necessary.
+   </para>
+
    <variablelist>
 
    <varlistentry>
diff --git a/src/backend/catalog/heap.c b/src/backend/catalog/heap.c
index 41c0056556..2f5090b183 100644
--- a/src/backend/catalog/heap.c
+++ b/src/backend/catalog/heap.c
@@ -291,6 +291,7 @@ heap_create(const char *relname,
 		case RELKIND_VIEW:
 		case RELKIND_COMPOSITE_TYPE:
 		case RELKIND_FOREIGN_TABLE:
+		case RELKIND_PARTITIONED_TABLE:
 			create_storage = false;
 
 			/*
@@ -1345,14 +1346,13 @@ heap_create_with_catalog(const char *relname,
 	if (oncommit != ONCOMMIT_NOOP)
 		register_on_commit_action(relid, oncommit);
 
-	if (relpersistence == RELPERSISTENCE_UNLOGGED)
-	{
-		Assert(relkind == RELKIND_RELATION || relkind == RELKIND_MATVIEW ||
-			   relkind == RELKIND_TOASTVALUE ||
-			   relkind == RELKIND_PARTITIONED_TABLE);
-
+	/*
+	 * We do not want to create any storage objects for a partitioned
+	 * table, including the init fork.
+	 */
+	if (relpersistence == RELPERSISTENCE_UNLOGGED &&
+		relkind != RELKIND_PARTITIONED_TABLE)
 		heap_create_init_fork(new_rel_desc);
-	}
 
 	/*
 	 * ok, the relation has been cataloged, so close our relations and return
@@ -1376,6 +1376,9 @@ heap_create_with_catalog(const char *relname,
 void
 heap_create_init_fork(Relation rel)
 {
+	Assert(rel->rd_rel->relkind == RELKIND_RELATION ||
+		   rel->rd_rel->relkind == RELKIND_MATVIEW ||
+		   rel->rd_rel->relkind == RELKIND_TOASTVALUE);
 	RelationOpenSmgr(rel);
 	smgrcreate(rel->rd_smgr, INIT_FORKNUM, false);
 	log_smgrcreate(&rel->rd_smgr->smgr_rnode.node, INIT_FORKNUM);
-- 
2.11.0


--------------FB43A8EFEDD9BFC7103E9A38
Content-Type: text/plain
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
MIME-Version: 1.0


-- 
Sent via pgsql-hackers mailing list ([email protected])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

--------------FB43A8EFEDD9BFC7103E9A38--






^ permalink  raw  reply  [nested|flat] 23+ messages in thread

* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
  0 siblings, 0 replies; 23+ 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] 23+ messages in thread

* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
  0 siblings, 0 replies; 23+ 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] 23+ messages in thread

* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
  0 siblings, 0 replies; 23+ 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] 23+ messages in thread

* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
  0 siblings, 0 replies; 23+ 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] 23+ messages in thread

* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
  0 siblings, 0 replies; 23+ 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] 23+ messages in thread

* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
  0 siblings, 0 replies; 23+ 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] 23+ messages in thread

* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
  0 siblings, 0 replies; 23+ 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] 23+ messages in thread

* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
  0 siblings, 0 replies; 23+ 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] 23+ messages in thread

* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
  0 siblings, 0 replies; 23+ 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] 23+ messages in thread

* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
  0 siblings, 0 replies; 23+ 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] 23+ messages in thread

* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
  0 siblings, 0 replies; 23+ 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] 23+ messages in thread

* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
  0 siblings, 0 replies; 23+ 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] 23+ messages in thread

* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
  0 siblings, 0 replies; 23+ 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] 23+ messages in thread

* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
  0 siblings, 0 replies; 23+ 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] 23+ messages in thread

* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
  0 siblings, 0 replies; 23+ 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] 23+ messages in thread

* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
  0 siblings, 0 replies; 23+ 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] 23+ messages in thread

* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
  0 siblings, 0 replies; 23+ 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] 23+ messages in thread

* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
  0 siblings, 0 replies; 23+ 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] 23+ messages in thread

* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
  0 siblings, 0 replies; 23+ 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] 23+ messages in thread

* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
  0 siblings, 0 replies; 23+ 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] 23+ messages in thread

* [PATCH 5/8] bloom fixes and tweaks
@ 2021-01-12 23:59 Tomas Vondra <[email protected]>
  0 siblings, 0 replies; 23+ 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] 23+ messages in thread

* Re: Is creating logical replication slots in template databases useful at all?
@ 2024-06-18 09:49 Ashutosh Bapat <[email protected]>
  0 siblings, 0 replies; 23+ messages in thread

From: Ashutosh Bapat @ 2024-06-18 09:49 UTC (permalink / raw)
  To: Bharath Rupireddy <[email protected]>; +Cc: PostgreSQL Hackers <[email protected]>

On Mon, Jun 17, 2024 at 5:50 PM Bharath Rupireddy <
[email protected]> wrote:

> Hi,
>
> While looking at the commit
>
> https://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=29d0a77fa6606f9c01ba17311fc452dab...
> ,
> I noticed that get_old_cluster_logical_slot_infos gets called for even
> template1 and template0 databases. Which means, pg_upgrade executes
> queries against the template databases to get replication slot
> information. I then realized that postgres allows one to connect to
> template1 database (or any other user-defined template databases for
> that matter), and create logical replication slots in it. If created,
> all the subsequent database creations will end up adding inactive
> logical replication slots in the postgres server. This might not be a
> problem in production servers as I assume the connections to template
> databases are typically restricted. Despite the connection
> restrictions, if at all one gets to connect to template databases in
> any way, it's pretty much possible to load the postgres server with
> inactive replication slots.
>

The replication slot names are unique across databases [1] Hence
replication slots created by connecting to template1 database should not
get copied over when creating a new database. Is that broken? A logical
replication slot is associated with a database but a physical replication
slot is not. The danger you mention above applies only to logical
replication slots I assume.


>
> This leads me to think why one would need logical replication slots in
> template databases at all. Can postgres restrict logical replication
> slots creation in template databases? If restricted, it may deviate
> from the fundamental principle of template databases in the sense that
> everything in the template database must be copied over to the new
> database created using it. Is it okay to do this? Am I missing
> something here?
>

If applications are using template1, they would want to keep the template1
on primary and replica in sync. Replication slot associated with template1
would be useful there.

[1]
https://www.postgresql.org/docs/current/logicaldecoding-explanation.html#LOGICALDECODING-REPLICATION...
-- 
Best Wishes,
Ashutosh Bapat


^ permalink  raw  reply  [nested|flat] 23+ messages in thread

end of thread, other threads:[~2024-06-18 09:49 UTC | newest]

Thread overview: 23+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2017-01-24 05:22 [PATCH] Do not allocate storage for partitioned tables. amit <[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]>
2024-06-18 09:49 Re: Is creating logical replication slots in template databases useful at all? Ashutosh Bapat <[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