agora inbox for [email protected]
help / color / mirror / Atom feedFrom: Tomas Vondra <[email protected]>
Subject: [PATCH 3/4] BRIN bloom indexes
Date: Tue, 9 Jan 2018 01:00:39 +0100
An opclass implementing BRIN indexes with bloom filter summary.
Naturally, this opclass only supports equality searches, but that
is fine for many use cases (e.g. it's uncommon to do range queries
on identifiers or labels).
It's not quite clear how to size the bloom filter, or what to do
if it gets too full (more than 50% of bits set). The patch picks
some reasonable defaults, but perhaps we can improve this based on
more information (ndistinct from pg_stats, pages_per_range, ...).
Or make it configurable when creating the index.
Another option would be to implement scalable bloom filters, i.e.
instead of creating one filter and stop using it when it gets too
full, create another (larger) one and use it for new additions.
But considering we can only see very limited number of distinct
values per range, that seems like an overkill, and it might make
certain operations (particularly "union" support procedure) more
complicated.
The patch also implements an optimization that we initially keep
the values "raw", and only switch to the actual bloom filter once
we use the same space. This somewhat reduces the space usage when
the column is low-cardinality (at least within a page range), so
that the bloom filter defaults would be too high.
---
doc/src/sgml/brin.sgml | 229 ++++++++++
src/backend/access/brin/Makefile | 2 +-
src/backend/access/brin/brin_bloom.c | 755 +++++++++++++++++++++++++++++++
src/include/catalog/pg_amop.h | 59 +++
src/include/catalog/pg_amproc.h | 153 +++++++
src/include/catalog/pg_opclass.h | 25 +
src/include/catalog/pg_opfamily.h | 20 +
src/include/catalog/pg_proc.h | 10 +
src/test/regress/expected/brin_bloom.out | 438 ++++++++++++++++++
src/test/regress/expected/opr_sanity.out | 3 +-
src/test/regress/parallel_schedule | 2 +-
src/test/regress/serial_schedule | 1 +
src/test/regress/sql/brin_bloom.sql | 391 ++++++++++++++++
13 files changed, 2085 insertions(+), 3 deletions(-)
create mode 100644 src/backend/access/brin/brin_bloom.c
create mode 100644 src/test/regress/expected/brin_bloom.out
create mode 100644 src/test/regress/sql/brin_bloom.sql
diff --git a/doc/src/sgml/brin.sgml b/doc/src/sgml/brin.sgml
index 23c0e05..434538e 100644
--- a/doc/src/sgml/brin.sgml
+++ b/doc/src/sgml/brin.sgml
@@ -118,6 +118,13 @@
</thead>
<tbody>
<row>
+ <entry><literal>abstime_bloom_ops</literal></entry>
+ <entry><type>abstime</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>abstime_minmax_ops</literal></entry>
<entry><type>abstime</type></entry>
<entry>
@@ -129,6 +136,13 @@
</entry>
</row>
<row>
+ <entry><literal>int8_bloom_ops</literal></entry>
+ <entry><type>bigint</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>int8_minmax_ops</literal></entry>
<entry><type>bigint</type></entry>
<entry>
@@ -180,6 +194,13 @@
</entry>
</row>
<row>
+ <entry><literal>bytea_bloom_ops</literal></entry>
+ <entry><type>bytea</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>bytea_minmax_ops</literal></entry>
<entry><type>bytea</type></entry>
<entry>
@@ -191,6 +212,13 @@
</entry>
</row>
<row>
+ <entry><literal>bpchar_bloom_ops</literal></entry>
+ <entry><type>character</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>bpchar_minmax_ops</literal></entry>
<entry><type>character</type></entry>
<entry>
@@ -202,6 +230,13 @@
</entry>
</row>
<row>
+ <entry><literal>char_bloom_ops</literal></entry>
+ <entry><type>"char"</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>char_minmax_ops</literal></entry>
<entry><type>"char"</type></entry>
<entry>
@@ -213,6 +248,13 @@
</entry>
</row>
<row>
+ <entry><literal>date_bloom_ops</literal></entry>
+ <entry><type>date</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>date_minmax_ops</literal></entry>
<entry><type>date</type></entry>
<entry>
@@ -224,6 +266,13 @@
</entry>
</row>
<row>
+ <entry><literal>float8_bloom_ops</literal></entry>
+ <entry><type>double precision</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>float8_minmax_ops</literal></entry>
<entry><type>double precision</type></entry>
<entry>
@@ -235,6 +284,13 @@
</entry>
</row>
<row>
+ <entry><literal>inet_bloom_ops</literal></entry>
+ <entry><type>inet</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>inet_minmax_ops</literal></entry>
<entry><type>inet</type></entry>
<entry>
@@ -258,6 +314,13 @@
</entry>
</row>
<row>
+ <entry><literal>int4_bloom_ops</literal></entry>
+ <entry><type>integer</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>int4_minmax_ops</literal></entry>
<entry><type>integer</type></entry>
<entry>
@@ -269,6 +332,13 @@
</entry>
</row>
<row>
+ <entry><literal>interval_bloom_ops</literal></entry>
+ <entry><type>interval</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>interval_minmax_ops</literal></entry>
<entry><type>interval</type></entry>
<entry>
@@ -280,6 +350,13 @@
</entry>
</row>
<row>
+ <entry><literal>macaddr_bloom_ops</literal></entry>
+ <entry><type>macaddr</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>macaddr_minmax_ops</literal></entry>
<entry><type>macaddr</type></entry>
<entry>
@@ -291,6 +368,13 @@
</entry>
</row>
<row>
+ <entry><literal>macaddr8_bloom_ops</literal></entry>
+ <entry><type>macaddr8</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>macaddr8_minmax_ops</literal></entry>
<entry><type>macaddr8</type></entry>
<entry>
@@ -302,6 +386,13 @@
</entry>
</row>
<row>
+ <entry><literal>name_bloom_ops</literal></entry>
+ <entry><type>name</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>name_minmax_ops</literal></entry>
<entry><type>name</type></entry>
<entry>
@@ -313,6 +404,13 @@
</entry>
</row>
<row>
+ <entry><literal>numeric_bloom_ops</literal></entry>
+ <entry><type>numeric</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>numeric_minmax_ops</literal></entry>
<entry><type>numeric</type></entry>
<entry>
@@ -324,6 +422,13 @@
</entry>
</row>
<row>
+ <entry><literal>pg_lsn_bloom_ops</literal></entry>
+ <entry><type>pg_lsn</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>pg_lsn_minmax_ops</literal></entry>
<entry><type>pg_lsn</type></entry>
<entry>
@@ -335,6 +440,13 @@
</entry>
</row>
<row>
+ <entry><literal>oid_bloom_ops</literal></entry>
+ <entry><type>oid</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>oid_minmax_ops</literal></entry>
<entry><type>oid</type></entry>
<entry>
@@ -366,6 +478,13 @@
</entry>
</row>
<row>
+ <entry><literal>float4_bloom_ops</literal></entry>
+ <entry><type>real</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>float4_minmax_ops</literal></entry>
<entry><type>real</type></entry>
<entry>
@@ -377,6 +496,13 @@
</entry>
</row>
<row>
+ <entry><literal>reltime_bloom_ops</literal></entry>
+ <entry><type>reltime</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>reltime_minmax_ops</literal></entry>
<entry><type>reltime</type></entry>
<entry>
@@ -388,6 +514,13 @@
</entry>
</row>
<row>
+ <entry><literal>int2_bloom_ops</literal></entry>
+ <entry><type>smallint</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>int2_minmax_ops</literal></entry>
<entry><type>smallint</type></entry>
<entry>
@@ -399,6 +532,13 @@
</entry>
</row>
<row>
+ <entry><literal>text_bloom_ops</literal></entry>
+ <entry><type>text</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>text_minmax_ops</literal></entry>
<entry><type>text</type></entry>
<entry>
@@ -421,6 +561,13 @@
</entry>
</row>
<row>
+ <entry><literal>timestamp_bloom_ops</literal></entry>
+ <entry><type>timestamp without time zone</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>timestamp_minmax_ops</literal></entry>
<entry><type>timestamp without time zone</type></entry>
<entry>
@@ -432,6 +579,13 @@
</entry>
</row>
<row>
+ <entry><literal>timestamptz_bloom_ops</literal></entry>
+ <entry><type>timestamp with time zone</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>timestamptz_minmax_ops</literal></entry>
<entry><type>timestamp with time zone</type></entry>
<entry>
@@ -443,6 +597,13 @@
</entry>
</row>
<row>
+ <entry><literal>time_bloom_ops</literal></entry>
+ <entry><type>time without time zone</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>time_minmax_ops</literal></entry>
<entry><type>time without time zone</type></entry>
<entry>
@@ -454,6 +615,13 @@
</entry>
</row>
<row>
+ <entry><literal>timetz_bloom_ops</literal></entry>
+ <entry><type>time with time zone</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>timetz_minmax_ops</literal></entry>
<entry><type>time with time zone</type></entry>
<entry>
@@ -465,6 +633,13 @@
</entry>
</row>
<row>
+ <entry><literal>uuid_bloom_ops</literal></entry>
+ <entry><type>uuid</type></entry>
+ <entry>
+ <literal>=</literal>
+ </entry>
+ </row>
+ <row>
<entry><literal>uuid_minmax_ops</literal></entry>
<entry><type>uuid</type></entry>
<entry>
@@ -814,6 +989,60 @@ typedef struct BrinOpcInfo
</para>
<para>
+ To write an operator class for a data type that implements only an equality
+ operator and supports hashing, it is possible to use the bloom support procedures
+ alongside the corresponding operators, as shown in
+ <xref linkend="brin-extensibility-bloom-table"/>.
+ All operator class members (procedures and operators) are mandatory.
+ </para>
+
+ <table id="brin-extensibility-bloom-table">
+ <title>Procedure and Support Numbers for Bloom Operator Classes</title>
+ <tgroup cols="2">
+ <thead>
+ <row>
+ <entry>Operator class member</entry>
+ <entry>Object</entry>
+ </row>
+ </thead>
+ <tbody>
+ <row>
+ <entry>Support Procedure 1</entry>
+ <entry>internal function <function>brin_bloom_opcinfo()</function></entry>
+ </row>
+ <row>
+ <entry>Support Procedure 2</entry>
+ <entry>internal function <function>brin_bloom_add_value()</function></entry>
+ </row>
+ <row>
+ <entry>Support Procedure 3</entry>
+ <entry>internal function <function>brin_bloom_consistent()</function></entry>
+ </row>
+ <row>
+ <entry>Support Procedure 4</entry>
+ <entry>internal function <function>brin_bloom_union()</function></entry>
+ </row>
+ <row>
+ <entry>Support Procedure 11</entry>
+ <entry>function to compute hash of an element</entry>
+ </row>
+ <row>
+ <entry>Operator Strategy 1</entry>
+ <entry>operator equal-to</entry>
+ </row>
+ </tbody>
+ </tgroup>
+ </table>
+
+ <para>
+ Support procedure numbers 1-10 are reserved for the BRIN internal
+ functions, so the SQL level functions start with number 11. Support
+ function number 11 is the main function required to build the index.
+ It should accept one argument with the same data type as the operator class,
+ and return a hash of the value.
+ </para>
+
+ <para>
Both minmax and inclusion operator classes support cross-data-type
operators, though with these the dependencies become more complicated.
The minmax operator class requires a full set of operators to be
diff --git a/src/backend/access/brin/Makefile b/src/backend/access/brin/Makefile
index 5aef925..a76d927 100644
--- a/src/backend/access/brin/Makefile
+++ b/src/backend/access/brin/Makefile
@@ -13,6 +13,6 @@ top_builddir = ../../../..
include $(top_builddir)/src/Makefile.global
OBJS = brin.o brin_pageops.o brin_revmap.o brin_tuple.o brin_xlog.o \
- brin_minmax.o brin_inclusion.o brin_validate.o
+ brin_minmax.o brin_inclusion.o brin_validate.o brin_bloom.o
include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
new file mode 100644
index 0000000..461bfce
--- /dev/null
+++ b/src/backend/access/brin/brin_bloom.c
@@ -0,0 +1,755 @@
+/*
+ * brin_bloom.c
+ * Implementation of Bloom opclass for BRIN
+ *
+ * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * IDENTIFICATION
+ * src/backend/access/brin/brin_bloom.c
+ */
+#include "postgres.h"
+
+#include "access/genam.h"
+#include "access/brin_internal.h"
+#include "access/brin_tuple.h"
+#include "access/hash.h"
+#include "access/stratnum.h"
+#include "catalog/pg_type.h"
+#include "catalog/pg_amop.h"
+#include "utils/builtins.h"
+#include "utils/datum.h"
+#include "utils/lsyscache.h"
+#include "utils/rel.h"
+#include "utils/syscache.h"
+
+#include <math.h>
+
+#define BloomEqualStrategyNumber 1
+
+/*
+ * Additional SQL level support functions
+ *
+ * Procedure numbers must not use values reserved for BRIN itself; see
+ * brin_internal.h.
+ */
+#define BLOOM_MAX_PROCNUMS 4 /* maximum support procs we need */
+#define PROCNUM_HASH 11 /* required */
+
+/*
+ * Subtract this from procnum to obtain index in BloomOpaque arrays
+ * (Must be equal to minimum of private procnums).
+ */
+#define PROCNUM_BASE 11
+
+
+#define BLOOM_PHASE_SORTED 1
+#define BLOOM_PHASE_HASH 2
+
+/* how many hashes to accumulate before hashing */
+#define BLOOM_MAX_UNSORTED 32
+#define BLOOM_GROW_BYTES 32
+#define BLOOM_NDISTINCT 1000 /* number of distinct values */
+#define BLOOM_ERROR_RATE 0.05 /* 2% false positive rate */
+
+/*
+ * Bloom Filter
+ *
+ * Represents a bloom filter, built on hashes of the indexed values. That is,
+ * we compute a uint32 hash of the value, and then store this hash into the
+ * bloom filter (and compute additional hashes on it).
+ *
+ * We use an optimisation that initially we store the uint32 values directly,
+ * without the extra hashing step. And only later filling the bitmap space,
+ * we switch to the regular bloom filter mode.
+ *
+ * PHASE_SORTED
+ *
+ * Initially we copy the uint32 hash into the bitmap, regularly sorting the
+ * hash values for fast lookup (we keep at most BLOOM_MAX_UNSORTED unsorted
+ * values).
+ *
+ * The idea is that if we only see very few distinct values, we can store
+ * them in less space compared to the (sparse) bloom filter bitmap. It also
+ * stores them exactly, although that's not a big advantage as almost-empty
+ * bloom filter has false positive rate close to zero anyway.
+ *
+ * PHASE_HASH
+ *
+ * Once we fill the bitmap space in the sorted phase, we switch to the hash
+ * phase, where we actually use the bloom filter. We treat the uint32 hashes
+ * as input values, and hash them again with different seeds (to get the k
+ * hash functions needed for bloom filter).
+ *
+ *
+ * XXX Maybe instead of explicitly limiting the number of unsorted values
+ * by BLOOM_MAX_UNSORTED, we should cap them by (filter size / 4B), i.e.
+ * allow up to the whole filter size.
+ *
+ * XXX Perhaps we could save a few bytes by using different data types, but
+ * considering the size of the bitmap, the difference is negligible.
+ *
+ * XXX We could also implement "sparse" bloom filters, keeping only the
+ * bytes that are not entirely 0. That might make the "sorted" phase
+ * mostly unnecessary.
+ *
+ * XXX We can also watch the number of bits set in the bloom filter, and
+ * then stop using it (and not store the bitmap, to save space) when the
+ * false positive rate gets too high.
+ */
+typedef struct BloomFilter
+{
+ /* varlena header (do not touch directly!) */
+ int32 vl_len_;
+
+ /* global bloom filter parameters */
+ uint32 phase; /* phase (initially SORTED, then HASH) */
+ uint32 nhashes; /* number of hash functions */
+ uint32 nbits; /* number of bits in the bitmap (optimal) */
+ uint32 nbits_set; /* number of bits set to 1 */
+
+ /* fields used only in the EXACT phase */
+ uint32 nvalues; /* number of hashes stored (sorted + extra) */
+ uint32 nsorted; /* number of uint32 hashes in sorted part */
+
+ /* bitmap of the bloom filter */
+ char bitmap[FLEXIBLE_ARRAY_MEMBER];
+
+} BloomFilter;
+
+/*
+ * bloom_init
+ * Initialize the Bloom Filter, allocate all the memory.
+ *
+ * The filter is initialized with optimal size for ndistinct expected
+ * values, and requested false positive rate. The filter is stored as
+ * varlena.
+ */
+static BloomFilter *
+bloom_init(int ndistinct, double false_positive_rate)
+{
+ Size len;
+ BloomFilter *filter;
+
+ /* https://en.wikipedia.org/wiki/Bloom_filter */
+ int m; /* number of bits */
+ int k; /* number of hash functions */
+
+ Assert((ndistinct > 0) && (ndistinct < 10000)); /* 10k is mostly arbitrary limit */
+ 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)))));
+
+ /* round m to whole bytes */
+ m = ((m + 7) / 8) * 8;
+
+ k = round(log(2.0) * m / ndistinct);
+
+ /*
+ * Allocate the bloom filter with a minimum size 64B (about 40B in the
+ * bitmap part). We require space at least for the header.
+ */
+ len = Max(offsetof(BloomFilter, bitmap), 64);
+
+ filter = (BloomFilter *) palloc0(len);
+
+ filter->phase = BLOOM_PHASE_SORTED;
+ filter->nhashes = k;
+ filter->nbits = m;
+
+ SET_VARSIZE(filter, len);
+
+ return filter;
+}
+
+/* simple uint32 comparator, for pg_qsort and bsearch */
+static int
+cmp_uint32(const void *a, const void *b)
+{
+ uint32 *ia = (uint32 *) a;
+ uint32 *ib = (uint32 *) b;
+
+ if (*ia == *ib)
+ return 0;
+ else if (*ia < *ib)
+ return -1;
+ else
+ return 1;
+}
+
+/*
+ * bloom_compact
+ * Compact the filter during the 'sorted' phase.
+ *
+ * We sort the uint32 hashes and remove duplicates, for two main reasons.
+ * Firstly, to keep most of the data sorted for bsearch lookups. Secondly,
+ * we try to save space by removing the duplicates, allowing us to stay
+ * in the sorted phase a bit longer.
+ *
+ * We currently don't repalloc the bitmap, i.e. we don't free the memory
+ * here - in the worst case we waste space for up to 32 unsorted hashes
+ * (if all of them are already in the sorted part), so about 128B. We can
+ * either reduce the number of unsorted items (e.g. to 8 hashes, which
+ * would mean 32B), or start doing the repalloc.
+ *
+ * XXX Actually, we don't need to do repalloc - we just need to set the
+ * varlena header length!
+ */
+static void
+bloom_compact(BloomFilter *filter)
+{
+ int i,
+ nvalues;
+ uint32 *values;
+
+ /* never call compact on filters in HASH phase */
+ Assert(filter->phase == BLOOM_PHASE_SORTED);
+
+ /* no chance to compact anything */
+ if (filter->nvalues == filter->nsorted)
+ return;
+
+ values = (uint32 *) palloc(filter->nvalues * sizeof(uint32));
+
+ /* copy the data, then reset the bitmap */
+ memcpy(values, filter->bitmap, filter->nvalues * sizeof(uint32));
+ memset(filter->bitmap, 0, filter->nvalues * sizeof(uint32));
+
+ /* FIXME optimization: sort only the unsorted part, then merge */
+ pg_qsort(values, filter->nvalues, sizeof(uint32), cmp_uint32);
+
+ nvalues = 1;
+ for (i = 1; i < filter->nvalues; i++)
+ {
+ /* if a new value, keep it */
+ if (values[i] != values[i-1])
+ {
+ values[nvalues] = values[i];
+ nvalues++;
+ }
+ }
+
+ filter->nvalues = nvalues;
+ filter->nsorted = nvalues;
+
+ memcpy(filter->bitmap, values, nvalues * sizeof(uint32));
+
+ pfree(values);
+}
+
+static BloomFilter *
+bloom_switch_to_hashing(BloomFilter *filter);
+
+/*
+ * bloom_add_value
+ * Add value to the bloom filter.
+ */
+static BloomFilter *
+bloom_add_value(BloomFilter *filter, uint32 value, bool *updated)
+{
+ int i;
+ uint32 big_h, h, d;
+
+ /* assume 'not updated' by default */
+ Assert(filter);
+
+ /* if we're in the sorted phase, we store the hashes directly */
+ if (filter->phase == BLOOM_PHASE_SORTED)
+ {
+ /* how many uint32 hashes can we fit into the bitmap */
+ int maxvalues = filter->nbits / (8 * sizeof(uint32));
+
+ /* do not overflow the bitmap space or number of unsorted items */
+ Assert(filter->nvalues <= maxvalues);
+ Assert(filter->nvalues - filter->nsorted <= BLOOM_MAX_UNSORTED);
+
+ /*
+ * In this branch we always update the filter - we either add the
+ * hash to the unsorted part, or switch the filter to hashing.
+ */
+ if (updated)
+ *updated = true;
+
+ /*
+ * If the array is full, or if we reached the limit on unsorted
+ * items, try to compact the filter first, before attempting to
+ * add the new value.
+ */
+ if ((filter->nvalues == maxvalues) ||
+ (filter->nvalues - filter->nsorted == BLOOM_MAX_UNSORTED))
+ bloom_compact(filter);
+
+ /*
+ * Can we squeeze one more uint32 hash into the bitmap? Also make
+ * sure there's enough space in the bytea value first.
+ */
+ if (filter->nvalues < maxvalues)
+ {
+ Size len = VARSIZE_ANY(filter);
+ Size need = offsetof(BloomFilter,bitmap) + (filter->nvalues+1) * sizeof(uint32);
+
+ if (len < need)
+ {
+ /*
+ * We don't double the size here, as in the first place we care about
+ * reducing storage requirements, and the doubling happens automatically
+ * in memory contexts anyway.
+ *
+ * XXX Zero the newly allocated part. Maybe not really needed?
+ */
+ filter = (BloomFilter *) repalloc(filter, len + BLOOM_GROW_BYTES);
+ memset((char *)filter + len, 0, BLOOM_GROW_BYTES);
+ SET_VARSIZE(filter, len + BLOOM_GROW_BYTES);
+ }
+
+ /* copy the data into the bitmap */
+ memcpy(&filter->bitmap[filter->nvalues * sizeof(uint32)],
+ &value, sizeof(uint32));
+
+ filter->nvalues++;
+
+ /* we're done */
+ return filter;
+ }
+
+ /* can't add any more exact hashes, so switch to hashing */
+ filter = bloom_switch_to_hashing(filter);
+ }
+
+ /* we better be in the hashing phase */
+ Assert(filter->phase == BLOOM_PHASE_HASH);
+
+ /* compute the hashes, used for the bloom filter */
+ big_h = ((uint32)DatumGetInt64(hash_uint32(value)));
+
+ h = big_h % filter->nbits;
+ d = big_h % (filter->nbits - 1);
+
+ /* compute the requested number of hashes */
+ for (i = 0; i < filter->nhashes; i++)
+ {
+ int byte = (h / 8);
+ int bit = (h % 8);
+
+ /* if the bit is not set, set it and remember we did that */
+ if (! (filter->bitmap[byte] & (0x01 << bit)))
+ {
+ filter->bitmap[byte] |= (0x01 << bit);
+ filter->nbits_set++;
+ if (updated)
+ *updated = true;
+ }
+
+ /* next bit */
+ h += d++;
+ if (h >= filter->nbits) h -= filter->nbits;
+ if (d == filter->nbits) d = 0;
+ }
+
+ return filter;
+}
+
+/*
+ * bloom_switch_to_hashing
+ * Switch the bloom filter from sorted to hashing mode.
+ */
+static BloomFilter *
+bloom_switch_to_hashing(BloomFilter *filter)
+{
+ int i;
+ uint32 *values;
+ Size len;
+ BloomFilter *newfilter;
+
+ /*
+ * The new filter is allocated with all the memory, directly into
+ * the HASH phase.
+ */
+ len = offsetof(BloomFilter, bitmap) + (filter->nbits / 8);
+
+ newfilter = (BloomFilter *) palloc0(len);
+
+ newfilter->nhashes = filter->nhashes;
+ newfilter->nbits = filter->nbits;
+ newfilter->phase = BLOOM_PHASE_HASH;
+
+ SET_VARSIZE(newfilter, len);
+
+ values = (uint32 *) filter->bitmap;
+
+ for (i = 0; i < filter->nvalues; i++)
+ /* ignore the return value here, re don't repalloc in hashing mode */
+ bloom_add_value(newfilter, values[i], NULL);
+
+ /* free the original filter, return the newly allocated one */
+ pfree(filter);
+
+ return newfilter;
+}
+
+/*
+ * bloom_contains_value
+ * Check if the bloom filter contains a particular value.
+ */
+static bool
+bloom_contains_value(BloomFilter *filter, uint32 value)
+{
+ int i;
+ uint32 big_h, h, d;
+
+ Assert(filter);
+
+ /* in sorted mode we simply search the two arrays (sorted, unsorted) */
+ if (filter->phase == BLOOM_PHASE_SORTED)
+ {
+ int i;
+ uint32 *values = (uint32 *)filter->bitmap;
+
+ /* first search through the sorted part */
+ if ((filter->nsorted > 0) &&
+ (bsearch(&value, values, filter->nsorted, sizeof(uint32), cmp_uint32) != NULL))
+ return true;
+
+ /* now search through the unsorted part - linear search */
+ for (i = filter->nsorted; i < filter->nvalues; i++)
+ if (value == values[i])
+ return true;
+
+ /* nothing found */
+ return false;
+ }
+
+ /* now the regular hashing mode */
+ Assert(filter->phase == BLOOM_PHASE_HASH);
+
+ big_h = ((uint32)DatumGetInt64(hash_uint32(value)));
+
+ h = big_h % filter->nbits;
+ d = big_h % (filter->nbits - 1);
+
+ /* compute the requested number of hashes */
+ for (i = 0; i < filter->nhashes; i++)
+ {
+ int byte = (h / 8);
+ int bit = (h % 8);
+
+ /* if the bit is not set, the value is not there */
+ if (! (filter->bitmap[byte] & (0x01 << bit)))
+ return false;
+
+ /* next bit */
+ h += d++;
+ if (h >= filter->nbits) h -= filter->nbits;
+ if (d == filter->nbits) d = 0;
+ }
+
+ /* all hashes found in bloom filter */
+ return true;
+}
+
+typedef struct BloomOpaque
+{
+ /*
+ * XXX At this point we only need a single proc (to compute the hash),
+ * but let's keep the array just like inclusion and minman opclasses,
+ * for consistency. We may need additional procs in the future.
+ */
+ FmgrInfo extra_procinfos[BLOOM_MAX_PROCNUMS];
+ bool extra_proc_missing[BLOOM_MAX_PROCNUMS];
+} BloomOpaque;
+
+static FmgrInfo *bloom_get_procinfo(BrinDesc *bdesc, uint16 attno,
+ uint16 procnum);
+
+
+Datum
+brin_bloom_opcinfo(PG_FUNCTION_ARGS)
+{
+ BrinOpcInfo *result;
+
+ /*
+ * opaque->strategy_procinfos is initialized lazily; here it is set to
+ * all-uninitialized by palloc0 which sets fn_oid to InvalidOid.
+ *
+ * bloom indexes only store a the filter as a single BYTEA column
+ */
+
+ result = palloc0(MAXALIGN(SizeofBrinOpcInfo(1)) +
+ sizeof(BloomOpaque));
+ result->oi_nstored = 1;
+ result->oi_opaque = (BloomOpaque *)
+ MAXALIGN((char *) result + SizeofBrinOpcInfo(1));
+ result->oi_typcache[0] = lookup_type_cache(BYTEAOID, 0);
+
+ PG_RETURN_POINTER(result);
+}
+
+/*
+ * Examine the given index tuple (which contains partial status of a certain
+ * page range) by comparing it to the given value that comes from another heap
+ * tuple. If the new value is outside the bloom filter specified by the
+ * existing tuple values, update the index tuple and return true. Otherwise,
+ * return false and do not modify in this case.
+ */
+Datum
+brin_bloom_add_value(PG_FUNCTION_ARGS)
+{
+ BrinDesc *bdesc = (BrinDesc *) PG_GETARG_POINTER(0);
+ BrinValues *column = (BrinValues *) PG_GETARG_POINTER(1);
+ Datum newval = PG_GETARG_DATUM(2);
+ bool isnull = PG_GETARG_DATUM(3);
+ Oid colloid = PG_GET_COLLATION();
+ FmgrInfo *hashFn;
+ uint32 hashValue;
+ bool updated = false;
+ AttrNumber attno;
+ BloomFilter *filter;
+
+ /*
+ * If the new value is null, we record that we saw it if it's the first
+ * one; otherwise, there's nothing to do.
+ */
+ if (isnull)
+ {
+ if (column->bv_hasnulls)
+ PG_RETURN_BOOL(false);
+
+ column->bv_hasnulls = true;
+ PG_RETURN_BOOL(true);
+ }
+
+ attno = column->bv_attno;
+
+ /*
+ * If this is the first non-null value, we need to initialize the bloom
+ * filter. Otherwise just extract the existing bloom filter from BrinValues.
+ */
+ if (column->bv_allnulls)
+ {
+ filter = bloom_init(BLOOM_NDISTINCT, BLOOM_ERROR_RATE);
+ column->bv_values[0] = PointerGetDatum(filter);
+ column->bv_allnulls = false;
+ updated = true;
+ }
+ else
+ filter = (BloomFilter *) PG_DETOAST_DATUM(column->bv_values[0]);
+
+ /*
+ * Compute the hash of the new value, using the supplied hash function,
+ * and then add the hash value to the bloom filter.
+ */
+ hashFn = bloom_get_procinfo(bdesc, attno, PROCNUM_HASH);
+
+ hashValue = DatumGetUInt32(FunctionCall1Coll(hashFn, colloid, newval));
+
+ filter = bloom_add_value(filter, hashValue, &updated);
+
+ column->bv_values[0] = PointerGetDatum(filter);
+
+ PG_RETURN_BOOL(updated);
+}
+
+/*
+ * Given an index tuple corresponding to a certain page range and a scan key,
+ * return whether the scan key is consistent with the index tuple's bloom
+ * filter. Return true if so, false otherwise.
+ */
+Datum
+brin_bloom_consistent(PG_FUNCTION_ARGS)
+{
+ BrinDesc *bdesc = (BrinDesc *) PG_GETARG_POINTER(0);
+ BrinValues *column = (BrinValues *) PG_GETARG_POINTER(1);
+ ScanKey *keys = (ScanKey *) PG_GETARG_POINTER(2);
+ int nkeys = PG_GETARG_INT32(3);
+ Oid colloid = PG_GET_COLLATION();
+ AttrNumber attno;
+ Datum value;
+ Datum matches;
+ FmgrInfo *finfo;
+ uint32 hashValue;
+ BloomFilter *filter;
+ int keyno;
+
+ filter = (BloomFilter *) PG_DETOAST_DATUM(column->bv_values[0]);
+
+ Assert(filter);
+
+ matches = true;
+
+ for (keyno = 0; keyno < nkeys; keyno++)
+ {
+ ScanKey key = keys[keyno];
+
+ /* NULL keys are handled and filtered-out in bringetbitmap */
+ Assert(!(key->sk_flags & SK_ISNULL));
+
+ attno = key->sk_attno;
+ value = key->sk_argument;
+
+ switch (key->sk_strategy)
+ {
+ case BloomEqualStrategyNumber:
+
+ /*
+ * In the equality case (WHERE col = someval), we want to return
+ * the current page range if the minimum value in the range <=
+ * scan key, and the maximum value >= scan key.
+ */
+ finfo = bloom_get_procinfo(bdesc, attno, PROCNUM_HASH);
+
+ hashValue = DatumGetUInt32(FunctionCall1Coll(finfo, colloid, value));
+ matches &= bloom_contains_value(filter, hashValue);
+
+ break;
+ default:
+ /* shouldn't happen */
+ elog(ERROR, "invalid strategy number %d", key->sk_strategy);
+ matches = 0;
+ break;
+ }
+
+ if (!matches)
+ break;
+ }
+
+ PG_RETURN_DATUM(matches);
+}
+
+/*
+ * Given two BrinValues, update the first of them as a union of the summary
+ * values contained in both. The second one is untouched.
+ *
+ * XXX We assume the bloom filters have the same parameters fow now. In the
+ * future we should have 'can union' function, to decide if we can combine
+ * two particular bloom filters.
+ */
+Datum
+brin_bloom_union(PG_FUNCTION_ARGS)
+{
+ BrinValues *col_a = (BrinValues *) PG_GETARG_POINTER(1);
+ BrinValues *col_b = (BrinValues *) PG_GETARG_POINTER(2);
+ BloomFilter *filter_a;
+ BloomFilter *filter_b;
+
+ Assert(col_a->bv_attno == col_b->bv_attno);
+
+ /* Adjust "hasnulls" */
+ if (!col_a->bv_hasnulls && col_b->bv_hasnulls)
+ col_a->bv_hasnulls = true;
+
+ /* If there are no values in B, there's nothing left to do */
+ if (col_b->bv_allnulls)
+ PG_RETURN_VOID();
+
+ /*
+ * Adjust "allnulls". If A doesn't have values, just copy the values from
+ * B into A, and we're done. We cannot run the operators in this case,
+ * because values in A might contain garbage. Note we already established
+ * that B contains values.
+ */
+ if (col_a->bv_allnulls)
+ {
+ col_a->bv_allnulls = false;
+ col_a->bv_values[0] = datumCopy(col_b->bv_values[0], false, -1);
+ PG_RETURN_VOID();
+ }
+
+ filter_a = (BloomFilter *) PG_DETOAST_DATUM(col_a->bv_values[0]);
+ filter_b = (BloomFilter *) PG_DETOAST_DATUM(col_b->bv_values[0]);
+
+ /* make sure neither of the bloom filters is NULL */
+ Assert(filter_a && filter_b);
+ Assert(filter_a->nbits == filter_b->nbits);
+
+ /*
+ * Merging of the filters depends on the phase of both filters.
+ */
+ if (filter_b->phase == BLOOM_PHASE_SORTED)
+ {
+ /*
+ * Simply read all items from 'b' and add them to 'a' (the phase of
+ * 'a' does not really matter).
+ */
+ int i;
+ uint32 *values = (uint32 *) filter_b->bitmap;
+
+ for (i = 0; i < filter_b->nvalues; i++)
+ filter_a = bloom_add_value(filter_a, values[i], NULL);
+
+ col_a->bv_values[0] = PointerGetDatum(filter_a);
+ }
+ else if (filter_a->phase == BLOOM_PHASE_SORTED)
+ {
+ /*
+ * 'b' hashed, 'a' sorted - copy 'b' into 'a' and then add all values
+ * from 'a' into the new copy.
+ */
+ int i;
+ BloomFilter *filter_c;
+ uint32 *values = (uint32 *) filter_a->bitmap;
+
+ filter_c = (BloomFilter *) PG_DETOAST_DATUM(datumCopy(PointerGetDatum(filter_b), false, -1));
+
+ for (i = 0; i < filter_a->nvalues; i++)
+ filter_c = bloom_add_value(filter_c, values[i], NULL);
+
+ col_a->bv_values[0] = PointerGetDatum(filter_c);
+ }
+ else if (filter_a->phase == BLOOM_PHASE_HASH)
+ {
+ /*
+ * 'b' hashed, 'a' hashed - merge the bitmaps by OR
+ */
+ int i;
+ int nbytes = (filter_a->nbits + 7) / 8;
+
+ for (i = 0; i < nbytes; i++)
+ filter_a->bitmap[i] |= filter_b->bitmap[i];
+ }
+
+ PG_RETURN_VOID();
+}
+
+/*
+ * Cache and return inclusion opclass support procedure
+ *
+ * Return the procedure corresponding to the given function support number
+ * or null if it is not exists.
+ */
+static FmgrInfo *
+bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
+{
+ BloomOpaque *opaque;
+ uint16 basenum = procnum - PROCNUM_BASE;
+
+ /*
+ * We cache these in the opaque struct, to avoid repetitive syscache
+ * lookups.
+ */
+ opaque = (BloomOpaque *) bdesc->bd_info[attno - 1]->oi_opaque;
+
+ /*
+ * If we already searched for this proc and didn't find it, don't bother
+ * searching again.
+ */
+ if (opaque->extra_proc_missing[basenum])
+ return NULL;
+
+ if (opaque->extra_procinfos[basenum].fn_oid == InvalidOid)
+ {
+ if (RegProcedureIsValid(index_getprocid(bdesc->bd_index, attno,
+ procnum)))
+ {
+ fmgr_info_copy(&opaque->extra_procinfos[basenum],
+ index_getprocinfo(bdesc->bd_index, attno, procnum),
+ bdesc->bd_context);
+ }
+ else
+ {
+ opaque->extra_proc_missing[basenum] = true;
+ return NULL;
+ }
+ }
+
+ return &opaque->extra_procinfos[basenum];
+}
diff --git a/src/include/catalog/pg_amop.h b/src/include/catalog/pg_amop.h
index 03af581..84dc6e3 100644
--- a/src/include/catalog/pg_amop.h
+++ b/src/include/catalog/pg_amop.h
@@ -910,18 +910,24 @@ DATA(insert ( 4064 17 17 2 s 1958 3580 0 ));
DATA(insert ( 4064 17 17 3 s 1955 3580 0 ));
DATA(insert ( 4064 17 17 4 s 1960 3580 0 ));
DATA(insert ( 4064 17 17 5 s 1959 3580 0 ));
+/* bloom bytea */
+DATA(insert ( 5021 17 17 1 s 1955 3580 0 ));
/* minmax "char" */
DATA(insert ( 4062 18 18 1 s 631 3580 0 ));
DATA(insert ( 4062 18 18 2 s 632 3580 0 ));
DATA(insert ( 4062 18 18 3 s 92 3580 0 ));
DATA(insert ( 4062 18 18 4 s 634 3580 0 ));
DATA(insert ( 4062 18 18 5 s 633 3580 0 ));
+/* bloom "char" */
+DATA(insert ( 5022 18 18 1 s 92 3580 0 ));
/* minmax name */
DATA(insert ( 4065 19 19 1 s 660 3580 0 ));
DATA(insert ( 4065 19 19 2 s 661 3580 0 ));
DATA(insert ( 4065 19 19 3 s 93 3580 0 ));
DATA(insert ( 4065 19 19 4 s 663 3580 0 ));
DATA(insert ( 4065 19 19 5 s 662 3580 0 ));
+/* bloom name */
+DATA(insert ( 5023 19 19 1 s 93 3580 0 ));
/* minmax integer */
DATA(insert ( 4054 20 20 1 s 412 3580 0 ));
DATA(insert ( 4054 20 20 2 s 414 3580 0 ));
@@ -968,6 +974,16 @@ DATA(insert ( 4054 23 20 2 s 80 3580 0 ));
DATA(insert ( 4054 23 20 3 s 15 3580 0 ));
DATA(insert ( 4054 23 20 4 s 82 3580 0 ));
DATA(insert ( 4054 23 20 5 s 76 3580 0 ));
+/* bloom integer */
+DATA(insert ( 5024 20 20 1 s 410 3580 0 ));
+DATA(insert ( 5024 20 21 1 s 1868 3580 0 ));
+DATA(insert ( 5024 20 23 1 s 416 3580 0 ));
+DATA(insert ( 5024 21 21 1 s 94 3580 0 ));
+DATA(insert ( 5024 21 20 1 s 1862 3580 0 ));
+DATA(insert ( 5024 21 23 1 s 532 3580 0 ));
+DATA(insert ( 5024 23 23 1 s 96 3580 0 ));
+DATA(insert ( 5024 23 21 1 s 533 3580 0 ));
+DATA(insert ( 5024 23 20 1 s 15 3580 0 ));
/* minmax text */
DATA(insert ( 4056 25 25 1 s 664 3580 0 ));
@@ -975,12 +991,16 @@ DATA(insert ( 4056 25 25 2 s 665 3580 0 ));
DATA(insert ( 4056 25 25 3 s 98 3580 0 ));
DATA(insert ( 4056 25 25 4 s 667 3580 0 ));
DATA(insert ( 4056 25 25 5 s 666 3580 0 ));
+/* bloom text */
+DATA(insert ( 5027 25 25 1 s 98 3580 0 ));
/* minmax oid */
DATA(insert ( 4068 26 26 1 s 609 3580 0 ));
DATA(insert ( 4068 26 26 2 s 611 3580 0 ));
DATA(insert ( 4068 26 26 3 s 607 3580 0 ));
DATA(insert ( 4068 26 26 4 s 612 3580 0 ));
DATA(insert ( 4068 26 26 5 s 610 3580 0 ));
+/* bloom oid */
+DATA(insert ( 5029 26 26 1 s 607 3580 0 ));
/* minmax tid */
DATA(insert ( 4069 27 27 1 s 2799 3580 0 ));
DATA(insert ( 4069 27 27 2 s 2801 3580 0 ));
@@ -1008,6 +1028,11 @@ DATA(insert ( 4070 701 701 2 s 673 3580 0 ));
DATA(insert ( 4070 701 701 3 s 670 3580 0 ));
DATA(insert ( 4070 701 701 4 s 675 3580 0 ));
DATA(insert ( 4070 701 701 5 s 674 3580 0 ));
+/* bloom float (float4, float8) */
+DATA(insert ( 5030 700 700 1 s 620 3580 0 ));
+DATA(insert ( 5030 700 701 1 s 1120 3580 0 ));
+DATA(insert ( 5030 701 700 1 s 1130 3580 0 ));
+DATA(insert ( 5030 701 701 1 s 670 3580 0 ));
/* minmax abstime */
DATA(insert ( 4072 702 702 1 s 562 3580 0 ));
@@ -1015,24 +1040,32 @@ DATA(insert ( 4072 702 702 2 s 564 3580 0 ));
DATA(insert ( 4072 702 702 3 s 560 3580 0 ));
DATA(insert ( 4072 702 702 4 s 565 3580 0 ));
DATA(insert ( 4072 702 702 5 s 563 3580 0 ));
+/* bloom abstime */
+DATA(insert ( 5031 702 702 1 s 560 3580 0 ));
/* minmax reltime */
DATA(insert ( 4073 703 703 1 s 568 3580 0 ));
DATA(insert ( 4073 703 703 2 s 570 3580 0 ));
DATA(insert ( 4073 703 703 3 s 566 3580 0 ));
DATA(insert ( 4073 703 703 4 s 571 3580 0 ));
DATA(insert ( 4073 703 703 5 s 569 3580 0 ));
+/* bloom reltime */
+DATA(insert ( 5032 703 703 1 s 566 3580 0 ));
/* minmax macaddr */
DATA(insert ( 4074 829 829 1 s 1222 3580 0 ));
DATA(insert ( 4074 829 829 2 s 1223 3580 0 ));
DATA(insert ( 4074 829 829 3 s 1220 3580 0 ));
DATA(insert ( 4074 829 829 4 s 1225 3580 0 ));
DATA(insert ( 4074 829 829 5 s 1224 3580 0 ));
+/* bloom macaddr */
+DATA(insert ( 5033 829 829 1 s 1220 3580 0 ));
/* minmax macaddr8 */
DATA(insert ( 4109 774 774 1 s 3364 3580 0 ));
DATA(insert ( 4109 774 774 2 s 3365 3580 0 ));
DATA(insert ( 4109 774 774 3 s 3362 3580 0 ));
DATA(insert ( 4109 774 774 4 s 3367 3580 0 ));
DATA(insert ( 4109 774 774 5 s 3366 3580 0 ));
+/* bloom macaddr8 */
+DATA(insert ( 5034 774 774 1 s 3362 3580 0 ));
/* minmax inet */
DATA(insert ( 4075 869 869 1 s 1203 3580 0 ));
DATA(insert ( 4075 869 869 2 s 1204 3580 0 ));
@@ -1046,18 +1079,24 @@ DATA(insert ( 4102 869 869 8 s 932 3580 0 ));
DATA(insert ( 4102 869 869 18 s 1201 3580 0 ));
DATA(insert ( 4102 869 869 24 s 933 3580 0 ));
DATA(insert ( 4102 869 869 26 s 931 3580 0 ));
+/* bloom inet */
+DATA(insert ( 5035 869 869 1 s 1201 3580 0 ));
/* minmax character */
DATA(insert ( 4076 1042 1042 1 s 1058 3580 0 ));
DATA(insert ( 4076 1042 1042 2 s 1059 3580 0 ));
DATA(insert ( 4076 1042 1042 3 s 1054 3580 0 ));
DATA(insert ( 4076 1042 1042 4 s 1061 3580 0 ));
DATA(insert ( 4076 1042 1042 5 s 1060 3580 0 ));
+/* bloom character */
+DATA(insert ( 5036 1042 1042 1 s 1054 3580 0 ));
/* minmax time without time zone */
DATA(insert ( 4077 1083 1083 1 s 1110 3580 0 ));
DATA(insert ( 4077 1083 1083 2 s 1111 3580 0 ));
DATA(insert ( 4077 1083 1083 3 s 1108 3580 0 ));
DATA(insert ( 4077 1083 1083 4 s 1113 3580 0 ));
DATA(insert ( 4077 1083 1083 5 s 1112 3580 0 ));
+/* bloom time without time zone */
+DATA(insert ( 5037 1083 1083 1 s 1108 3580 0 ));
/* minmax datetime (date, timestamp, timestamptz) */
DATA(insert ( 4059 1114 1114 1 s 2062 3580 0 ));
DATA(insert ( 4059 1114 1114 2 s 2063 3580 0 ));
@@ -1104,6 +1143,16 @@ DATA(insert ( 4059 1184 1184 2 s 1323 3580 0 ));
DATA(insert ( 4059 1184 1184 3 s 1320 3580 0 ));
DATA(insert ( 4059 1184 1184 4 s 1325 3580 0 ));
DATA(insert ( 4059 1184 1184 5 s 1324 3580 0 ));
+/* bloom datetime (date, timestamp, timestamptz) */
+DATA(insert ( 5038 1114 1114 1 s 2060 3580 0 ));
+DATA(insert ( 5038 1114 1082 1 s 2373 3580 0 ));
+DATA(insert ( 5038 1114 1184 1 s 2536 3580 0 ));
+DATA(insert ( 5038 1082 1082 1 s 1093 3580 0 ));
+DATA(insert ( 5038 1082 1114 1 s 2347 3580 0 ));
+DATA(insert ( 5038 1082 1184 1 s 2360 3580 0 ));
+DATA(insert ( 5038 1184 1082 1 s 2386 3580 0 ));
+DATA(insert ( 5038 1184 1114 1 s 2542 3580 0 ));
+DATA(insert ( 5038 1184 1184 1 s 1320 3580 0 ));
/* minmax interval */
DATA(insert ( 4078 1186 1186 1 s 1332 3580 0 ));
@@ -1111,12 +1160,16 @@ DATA(insert ( 4078 1186 1186 2 s 1333 3580 0 ));
DATA(insert ( 4078 1186 1186 3 s 1330 3580 0 ));
DATA(insert ( 4078 1186 1186 4 s 1335 3580 0 ));
DATA(insert ( 4078 1186 1186 5 s 1334 3580 0 ));
+/* bloom interval */
+DATA(insert ( 5041 1186 1186 1 s 1330 3580 0 ));
/* minmax time with time zone */
DATA(insert ( 4058 1266 1266 1 s 1552 3580 0 ));
DATA(insert ( 4058 1266 1266 2 s 1553 3580 0 ));
DATA(insert ( 4058 1266 1266 3 s 1550 3580 0 ));
DATA(insert ( 4058 1266 1266 4 s 1555 3580 0 ));
DATA(insert ( 4058 1266 1266 5 s 1554 3580 0 ));
+/* bloom time with time zone */
+DATA(insert ( 5042 1266 1266 1 s 1550 3580 0 ));
/* minmax bit */
DATA(insert ( 4079 1560 1560 1 s 1786 3580 0 ));
DATA(insert ( 4079 1560 1560 2 s 1788 3580 0 ));
@@ -1135,12 +1188,16 @@ DATA(insert ( 4055 1700 1700 2 s 1755 3580 0 ));
DATA(insert ( 4055 1700 1700 3 s 1752 3580 0 ));
DATA(insert ( 4055 1700 1700 4 s 1757 3580 0 ));
DATA(insert ( 4055 1700 1700 5 s 1756 3580 0 ));
+/* bloom numeric */
+DATA(insert ( 5045 1700 1700 1 s 1752 3580 0 ));
/* minmax uuid */
DATA(insert ( 4081 2950 2950 1 s 2974 3580 0 ));
DATA(insert ( 4081 2950 2950 2 s 2976 3580 0 ));
DATA(insert ( 4081 2950 2950 3 s 2972 3580 0 ));
DATA(insert ( 4081 2950 2950 4 s 2977 3580 0 ));
DATA(insert ( 4081 2950 2950 5 s 2975 3580 0 ));
+/* bloom uuid */
+DATA(insert ( 5046 2950 2950 1 s 2972 3580 0 ));
/* inclusion range types */
DATA(insert ( 4103 3831 3831 1 s 3893 3580 0 ));
DATA(insert ( 4103 3831 3831 2 s 3895 3580 0 ));
@@ -1162,6 +1219,8 @@ DATA(insert ( 4082 3220 3220 2 s 3226 3580 0 ));
DATA(insert ( 4082 3220 3220 3 s 3222 3580 0 ));
DATA(insert ( 4082 3220 3220 4 s 3227 3580 0 ));
DATA(insert ( 4082 3220 3220 5 s 3225 3580 0 ));
+/* bloom pg_lsn */
+DATA(insert ( 5047 3220 3220 1 s 3222 3580 0 ));
/* inclusion box */
DATA(insert ( 4104 603 603 1 s 493 3580 0 ));
DATA(insert ( 4104 603 603 2 s 494 3580 0 ));
diff --git a/src/include/catalog/pg_amproc.h b/src/include/catalog/pg_amproc.h
index f545a058..4871836 100644
--- a/src/include/catalog/pg_amproc.h
+++ b/src/include/catalog/pg_amproc.h
@@ -347,16 +347,34 @@ DATA(insert ( 4064 17 17 1 3383 ));
DATA(insert ( 4064 17 17 2 3384 ));
DATA(insert ( 4064 17 17 3 3385 ));
DATA(insert ( 4064 17 17 4 3386 ));
+/* bloom bytea */
+DATA(insert ( 5021 17 17 1 5017 ));
+DATA(insert ( 5021 17 17 2 5018 ));
+DATA(insert ( 5021 17 17 3 5019 ));
+DATA(insert ( 5021 17 17 4 5020 ));
+DATA(insert ( 5021 17 17 11 456 ));
/* minmax "char" */
DATA(insert ( 4062 18 18 1 3383 ));
DATA(insert ( 4062 18 18 2 3384 ));
DATA(insert ( 4062 18 18 3 3385 ));
DATA(insert ( 4062 18 18 4 3386 ));
+/* bloom "char" */
+DATA(insert ( 5022 18 18 1 5017 ));
+DATA(insert ( 5022 18 18 2 5018 ));
+DATA(insert ( 5022 18 18 3 5019 ));
+DATA(insert ( 5022 18 18 4 5020 ));
+DATA(insert ( 5022 18 18 11 454 ));
/* minmax name */
DATA(insert ( 4065 19 19 1 3383 ));
DATA(insert ( 4065 19 19 2 3384 ));
DATA(insert ( 4065 19 19 3 3385 ));
DATA(insert ( 4065 19 19 4 3386 ));
+/* bloom name */
+DATA(insert ( 5023 19 19 1 5017 ));
+DATA(insert ( 5023 19 19 2 5018 ));
+DATA(insert ( 5023 19 19 3 5019 ));
+DATA(insert ( 5023 19 19 4 5020 ));
+DATA(insert ( 5023 19 19 11 455 ));
/* minmax integer: int2, int4, int8 */
DATA(insert ( 4054 20 20 1 3383 ));
DATA(insert ( 4054 20 20 2 3384 ));
@@ -397,16 +415,47 @@ DATA(insert ( 4054 23 21 2 3384 ));
DATA(insert ( 4054 23 21 3 3385 ));
DATA(insert ( 4054 23 21 4 3386 ));
+/* bloom integer: int2, int4, int8 */
+DATA(insert ( 5024 20 20 1 5017 ));
+DATA(insert ( 5024 20 20 2 5018 ));
+DATA(insert ( 5024 20 20 3 5019 ));
+DATA(insert ( 5024 20 20 4 5020 ));
+DATA(insert ( 5024 20 20 11 949 ));
+
+DATA(insert ( 5024 21 21 1 5017 ));
+DATA(insert ( 5024 21 21 2 5018 ));
+DATA(insert ( 5024 21 21 3 5019 ));
+DATA(insert ( 5024 21 21 4 5020 ));
+DATA(insert ( 5024 21 21 11 449 ));
+
+DATA(insert ( 5024 23 23 1 5017 ));
+DATA(insert ( 5024 23 23 2 5018 ));
+DATA(insert ( 5024 23 23 3 5019 ));
+DATA(insert ( 5024 23 23 4 5020 ));
+DATA(insert ( 5024 23 23 11 450 ));
+
/* minmax text */
DATA(insert ( 4056 25 25 1 3383 ));
DATA(insert ( 4056 25 25 2 3384 ));
DATA(insert ( 4056 25 25 3 3385 ));
DATA(insert ( 4056 25 25 4 3386 ));
+/* bloom text */
+DATA(insert ( 5027 25 25 1 5017 ));
+DATA(insert ( 5027 25 25 2 5018 ));
+DATA(insert ( 5027 25 25 3 5019 ));
+DATA(insert ( 5027 25 25 4 5020 ));
+DATA(insert ( 5027 25 25 11 400 ));
/* minmax oid */
DATA(insert ( 4068 26 26 1 3383 ));
DATA(insert ( 4068 26 26 2 3384 ));
DATA(insert ( 4068 26 26 3 3385 ));
DATA(insert ( 4068 26 26 4 3386 ));
+/* bloom oid */
+DATA(insert ( 5029 26 26 1 5017 ));
+DATA(insert ( 5029 26 26 2 5018 ));
+DATA(insert ( 5029 26 26 3 5019 ));
+DATA(insert ( 5029 26 26 4 5020 ));
+DATA(insert ( 5029 26 26 11 453 ));
/* minmax tid */
DATA(insert ( 4069 27 27 1 3383 ));
DATA(insert ( 4069 27 27 2 3384 ));
@@ -433,26 +482,63 @@ DATA(insert ( 4070 701 700 2 3384 ));
DATA(insert ( 4070 701 700 3 3385 ));
DATA(insert ( 4070 701 700 4 3386 ));
+/* bloom float */
+DATA(insert ( 5030 700 700 1 5017 ));
+DATA(insert ( 5030 700 700 2 5018 ));
+DATA(insert ( 5030 700 700 3 5019 ));
+DATA(insert ( 5030 700 700 4 5020 ));
+DATA(insert ( 5030 700 700 11 451 ));
+
+DATA(insert ( 5030 701 701 1 5017 ));
+DATA(insert ( 5030 701 701 2 5018 ));
+DATA(insert ( 5030 701 701 3 5019 ));
+DATA(insert ( 5030 701 701 4 5020 ));
+DATA(insert ( 5030 701 701 11 452 ));
+
/* minmax abstime */
DATA(insert ( 4072 702 702 1 3383 ));
DATA(insert ( 4072 702 702 2 3384 ));
DATA(insert ( 4072 702 702 3 3385 ));
DATA(insert ( 4072 702 702 4 3386 ));
+/* bloom abstime */
+DATA(insert ( 5031 702 702 1 5017 ));
+DATA(insert ( 5031 702 702 2 5018 ));
+DATA(insert ( 5031 702 702 3 5019 ));
+DATA(insert ( 5031 702 702 4 5020 ));
+DATA(insert ( 5031 702 702 11 450 ));
/* minmax reltime */
DATA(insert ( 4073 703 703 1 3383 ));
DATA(insert ( 4073 703 703 2 3384 ));
DATA(insert ( 4073 703 703 3 3385 ));
DATA(insert ( 4073 703 703 4 3386 ));
+/* bloom reltime */
+DATA(insert ( 5032 703 703 1 5017 ));
+DATA(insert ( 5032 703 703 2 5018 ));
+DATA(insert ( 5032 703 703 3 5019 ));
+DATA(insert ( 5032 703 703 4 5020 ));
+DATA(insert ( 5032 703 703 11 450 ));
/* minmax macaddr */
DATA(insert ( 4074 829 829 1 3383 ));
DATA(insert ( 4074 829 829 2 3384 ));
DATA(insert ( 4074 829 829 3 3385 ));
DATA(insert ( 4074 829 829 4 3386 ));
+/* bloom macaddr */
+DATA(insert ( 5033 829 829 1 5017 ));
+DATA(insert ( 5033 829 829 2 5018 ));
+DATA(insert ( 5033 829 829 3 5019 ));
+DATA(insert ( 5033 829 829 4 5020 ));
+DATA(insert ( 5033 829 829 11 399 ));
/* minmax macaddr8 */
DATA(insert ( 4109 774 774 1 3383 ));
DATA(insert ( 4109 774 774 2 3384 ));
DATA(insert ( 4109 774 774 3 3385 ));
DATA(insert ( 4109 774 774 4 3386 ));
+/* bloom macaddr8 */
+DATA(insert ( 5034 774 774 1 5017 ));
+DATA(insert ( 5034 774 774 2 5018 ));
+DATA(insert ( 5034 774 774 3 5019 ));
+DATA(insert ( 5034 774 774 4 5020 ));
+DATA(insert ( 5034 774 774 11 328 ));
/* minmax inet */
DATA(insert ( 4075 869 869 1 3383 ));
DATA(insert ( 4075 869 869 2 3384 ));
@@ -466,16 +552,34 @@ DATA(insert ( 4102 869 869 4 4108 ));
DATA(insert ( 4102 869 869 11 4063 ));
DATA(insert ( 4102 869 869 12 4071 ));
DATA(insert ( 4102 869 869 13 930 ));
+/* bloom inet */
+DATA(insert ( 5035 869 869 1 5017 ));
+DATA(insert ( 5035 869 869 2 5018 ));
+DATA(insert ( 5035 869 869 3 5019 ));
+DATA(insert ( 5035 869 869 4 5020 ));
+DATA(insert ( 5035 869 869 11 422 ));
/* minmax character */
DATA(insert ( 4076 1042 1042 1 3383 ));
DATA(insert ( 4076 1042 1042 2 3384 ));
DATA(insert ( 4076 1042 1042 3 3385 ));
DATA(insert ( 4076 1042 1042 4 3386 ));
+/* bloom character */
+DATA(insert ( 5036 1042 1042 1 5017 ));
+DATA(insert ( 5036 1042 1042 2 5018 ));
+DATA(insert ( 5036 1042 1042 3 5019 ));
+DATA(insert ( 5036 1042 1042 4 5020 ));
+DATA(insert ( 5036 1042 1042 11 454 ));
/* minmax time without time zone */
DATA(insert ( 4077 1083 1083 1 3383 ));
DATA(insert ( 4077 1083 1083 2 3384 ));
DATA(insert ( 4077 1083 1083 3 3385 ));
DATA(insert ( 4077 1083 1083 4 3386 ));
+/* bloom time without time zone */
+DATA(insert ( 5037 1083 1083 1 5017 ));
+DATA(insert ( 5037 1083 1083 2 5018 ));
+DATA(insert ( 5037 1083 1083 3 5019 ));
+DATA(insert ( 5037 1083 1083 4 5020 ));
+DATA(insert ( 5037 1083 1083 11 1688 ));
/* minmax datetime (date, timestamp, timestamptz) */
DATA(insert ( 4059 1114 1114 1 3383 ));
DATA(insert ( 4059 1114 1114 2 3384 ));
@@ -516,16 +620,47 @@ DATA(insert ( 4059 1082 1184 2 3384 ));
DATA(insert ( 4059 1082 1184 3 3385 ));
DATA(insert ( 4059 1082 1184 4 3386 ));
+/* bloom datetime (date, timestamp, timestamptz) */
+DATA(insert ( 5038 1114 1114 1 5017 ));
+DATA(insert ( 5038 1114 1114 2 5018 ));
+DATA(insert ( 5038 1114 1114 3 5019 ));
+DATA(insert ( 5038 1114 1114 4 5020 ));
+DATA(insert ( 5038 1114 1114 11 2039 ));
+
+DATA(insert ( 5038 1184 1184 1 5017 ));
+DATA(insert ( 5038 1184 1184 2 5018 ));
+DATA(insert ( 5038 1184 1184 3 5019 ));
+DATA(insert ( 5038 1184 1184 4 5020 ));
+DATA(insert ( 5038 1184 1184 11 2039 ));
+
+DATA(insert ( 5038 1082 1082 1 5017 ));
+DATA(insert ( 5038 1082 1082 2 5018 ));
+DATA(insert ( 5038 1082 1082 3 5019 ));
+DATA(insert ( 5038 1082 1082 4 5020 ));
+DATA(insert ( 5038 1082 1082 11 450 ));
+
/* minmax interval */
DATA(insert ( 4078 1186 1186 1 3383 ));
DATA(insert ( 4078 1186 1186 2 3384 ));
DATA(insert ( 4078 1186 1186 3 3385 ));
DATA(insert ( 4078 1186 1186 4 3386 ));
+/* bloom interval */
+DATA(insert ( 5041 1186 1186 1 5017 ));
+DATA(insert ( 5041 1186 1186 2 5018 ));
+DATA(insert ( 5041 1186 1186 3 5019 ));
+DATA(insert ( 5041 1186 1186 4 5020 ));
+DATA(insert ( 5041 1186 1186 11 1697 ));
/* minmax time with time zone */
DATA(insert ( 4058 1266 1266 1 3383 ));
DATA(insert ( 4058 1266 1266 2 3384 ));
DATA(insert ( 4058 1266 1266 3 3385 ));
DATA(insert ( 4058 1266 1266 4 3386 ));
+/* bloom time with time zone */
+DATA(insert ( 5042 1266 1266 1 5017 ));
+DATA(insert ( 5042 1266 1266 2 5018 ));
+DATA(insert ( 5042 1266 1266 3 5019 ));
+DATA(insert ( 5042 1266 1266 4 5020 ));
+DATA(insert ( 5042 1266 1266 11 1696 ));
/* minmax bit */
DATA(insert ( 4079 1560 1560 1 3383 ));
DATA(insert ( 4079 1560 1560 2 3384 ));
@@ -541,11 +676,23 @@ DATA(insert ( 4055 1700 1700 1 3383 ));
DATA(insert ( 4055 1700 1700 2 3384 ));
DATA(insert ( 4055 1700 1700 3 3385 ));
DATA(insert ( 4055 1700 1700 4 3386 ));
+/* bloom numeric */
+DATA(insert ( 5045 1700 1700 1 5017 ));
+DATA(insert ( 5045 1700 1700 2 5018 ));
+DATA(insert ( 5045 1700 1700 3 5019 ));
+DATA(insert ( 5045 1700 1700 4 5020 ));
+DATA(insert ( 5045 1700 1700 11 432 ));
/* minmax uuid */
DATA(insert ( 4081 2950 2950 1 3383 ));
DATA(insert ( 4081 2950 2950 2 3384 ));
DATA(insert ( 4081 2950 2950 3 3385 ));
DATA(insert ( 4081 2950 2950 4 3386 ));
+/* bloom uuid */
+DATA(insert ( 5046 2950 2950 1 5017 ));
+DATA(insert ( 5046 2950 2950 2 5018 ));
+DATA(insert ( 5046 2950 2950 3 5019 ));
+DATA(insert ( 5046 2950 2950 4 5020 ));
+DATA(insert ( 5046 2950 2950 11 2963 ));
/* inclusion range types */
DATA(insert ( 4103 3831 3831 1 4105 ));
DATA(insert ( 4103 3831 3831 2 4106 ));
@@ -559,6 +706,12 @@ DATA(insert ( 4082 3220 3220 1 3383 ));
DATA(insert ( 4082 3220 3220 2 3384 ));
DATA(insert ( 4082 3220 3220 3 3385 ));
DATA(insert ( 4082 3220 3220 4 3386 ));
+/* bloom pg_lsn */
+DATA(insert ( 5047 3220 3220 1 5017 ));
+DATA(insert ( 5047 3220 3220 2 5018 ));
+DATA(insert ( 5047 3220 3220 3 5019 ));
+DATA(insert ( 5047 3220 3220 4 5020 ));
+DATA(insert ( 5047 3220 3220 11 3252 ));
/* inclusion box */
DATA(insert ( 4104 603 603 1 4105 ));
DATA(insert ( 4104 603 603 2 4106 ));
diff --git a/src/include/catalog/pg_opclass.h b/src/include/catalog/pg_opclass.h
index e11d52e..7dbd4ff 100644
--- a/src/include/catalog/pg_opclass.h
+++ b/src/include/catalog/pg_opclass.h
@@ -214,36 +214,61 @@ DATA(insert ( 2742 jsonb_path_ops PGNSP PGUID 4037 3802 f 23 ));
/* BRIN operator classes */
/* no brin opclass for bool */
DATA(insert ( 3580 bytea_minmax_ops PGNSP PGUID 4064 17 t 17 ));
+DATA(insert ( 3580 bytea_bloom_ops PGNSP PGUID 5021 17 f 17 ));
DATA(insert ( 3580 char_minmax_ops PGNSP PGUID 4062 18 t 18 ));
+DATA(insert ( 3580 char_bloom_ops PGNSP PGUID 5022 18 f 18 ));
DATA(insert ( 3580 name_minmax_ops PGNSP PGUID 4065 19 t 19 ));
+DATA(insert ( 3580 name_bloom_ops PGNSP PGUID 5023 19 f 19 ));
DATA(insert ( 3580 int8_minmax_ops PGNSP PGUID 4054 20 t 20 ));
+DATA(insert ( 3580 int8_bloom_ops PGNSP PGUID 5024 20 f 20 ));
DATA(insert ( 3580 int2_minmax_ops PGNSP PGUID 4054 21 t 21 ));
+DATA(insert ( 3580 int2_bloom_ops PGNSP PGUID 5024 21 f 21 ));
DATA(insert ( 3580 int4_minmax_ops PGNSP PGUID 4054 23 t 23 ));
+DATA(insert ( 3580 int4_bloom_ops PGNSP PGUID 5024 23 f 23 ));
DATA(insert ( 3580 text_minmax_ops PGNSP PGUID 4056 25 t 25 ));
+DATA(insert ( 3580 text_bloom_ops PGNSP PGUID 5027 25 f 25 ));
DATA(insert ( 3580 oid_minmax_ops PGNSP PGUID 4068 26 t 26 ));
+DATA(insert ( 3580 oid_bloom_ops PGNSP PGUID 5029 26 f 26 ));
DATA(insert ( 3580 tid_minmax_ops PGNSP PGUID 4069 27 t 27 ));
DATA(insert ( 3580 float4_minmax_ops PGNSP PGUID 4070 700 t 700 ));
+DATA(insert ( 3580 float4_bloom_ops PGNSP PGUID 5030 700 f 700 ));
DATA(insert ( 3580 float8_minmax_ops PGNSP PGUID 4070 701 t 701 ));
+DATA(insert ( 3580 float8_bloom_ops PGNSP PGUID 5030 701 f 701 ));
DATA(insert ( 3580 abstime_minmax_ops PGNSP PGUID 4072 702 t 702 ));
+DATA(insert ( 3580 abstime_bloom_ops PGNSP PGUID 5031 702 f 702 ));
DATA(insert ( 3580 reltime_minmax_ops PGNSP PGUID 4073 703 t 703 ));
+DATA(insert ( 3580 reltime_bloom_ops PGNSP PGUID 5032 703 f 703 ));
DATA(insert ( 3580 macaddr_minmax_ops PGNSP PGUID 4074 829 t 829 ));
+DATA(insert ( 3580 macaddr_bloom_ops PGNSP PGUID 5033 829 f 829 ));
DATA(insert ( 3580 macaddr8_minmax_ops PGNSP PGUID 4109 774 t 774 ));
+DATA(insert ( 3580 macaddr8_bloom_ops PGNSP PGUID 5034 774 f 774 ));
DATA(insert ( 3580 inet_minmax_ops PGNSP PGUID 4075 869 f 869 ));
DATA(insert ( 3580 inet_inclusion_ops PGNSP PGUID 4102 869 t 869 ));
+DATA(insert ( 3580 inet_bloom_ops PGNSP PGUID 5035 869 f 869 ));
DATA(insert ( 3580 bpchar_minmax_ops PGNSP PGUID 4076 1042 t 1042 ));
+DATA(insert ( 3580 bpchar_bloom_ops PGNSP PGUID 5036 1042 f 1042 ));
DATA(insert ( 3580 time_minmax_ops PGNSP PGUID 4077 1083 t 1083 ));
+DATA(insert ( 3580 time_bloom_ops PGNSP PGUID 5037 1083 f 1083 ));
DATA(insert ( 3580 date_minmax_ops PGNSP PGUID 4059 1082 t 1082 ));
+DATA(insert ( 3580 date_bloom_ops PGNSP PGUID 5038 1082 f 1082 ));
DATA(insert ( 3580 timestamp_minmax_ops PGNSP PGUID 4059 1114 t 1114 ));
+DATA(insert ( 3580 timestamp_bloom_ops PGNSP PGUID 5038 1114 f 1114 ));
DATA(insert ( 3580 timestamptz_minmax_ops PGNSP PGUID 4059 1184 t 1184 ));
+DATA(insert ( 3580 timestamptz_bloom_ops PGNSP PGUID 5038 1184 f 1184 ));
DATA(insert ( 3580 interval_minmax_ops PGNSP PGUID 4078 1186 t 1186 ));
+DATA(insert ( 3580 interval_bloom_ops PGNSP PGUID 5041 1186 f 1186 ));
DATA(insert ( 3580 timetz_minmax_ops PGNSP PGUID 4058 1266 t 1266 ));
+DATA(insert ( 3580 timetz_bloom_ops PGNSP PGUID 5042 1266 f 1266 ));
DATA(insert ( 3580 bit_minmax_ops PGNSP PGUID 4079 1560 t 1560 ));
DATA(insert ( 3580 varbit_minmax_ops PGNSP PGUID 4080 1562 t 1562 ));
DATA(insert ( 3580 numeric_minmax_ops PGNSP PGUID 4055 1700 t 1700 ));
+DATA(insert ( 3580 numeric_bloom_ops PGNSP PGUID 5045 1700 f 1700 ));
/* no brin opclass for record, anyarray */
DATA(insert ( 3580 uuid_minmax_ops PGNSP PGUID 4081 2950 t 2950 ));
+DATA(insert ( 3580 uuid_bloom_ops PGNSP PGUID 5046 2950 f 2950 ));
DATA(insert ( 3580 range_inclusion_ops PGNSP PGUID 4103 3831 t 3831 ));
DATA(insert ( 3580 pg_lsn_minmax_ops PGNSP PGUID 4082 3220 t 3220 ));
+DATA(insert ( 3580 pg_lsn_bloom_ops PGNSP PGUID 5047 3220 f 3220 ));
/* no brin opclass for enum, tsvector, tsquery, jsonb */
DATA(insert ( 3580 box_inclusion_ops PGNSP PGUID 4104 603 t 603 ));
/* no brin opclass for the geometric types except box */
diff --git a/src/include/catalog/pg_opfamily.h b/src/include/catalog/pg_opfamily.h
index b544474..bc22ce3 100644
--- a/src/include/catalog/pg_opfamily.h
+++ b/src/include/catalog/pg_opfamily.h
@@ -160,30 +160,50 @@ DATA(insert OID = 4036 ( 2742 jsonb_ops PGNSP PGUID ));
DATA(insert OID = 4037 ( 2742 jsonb_path_ops PGNSP PGUID ));
DATA(insert OID = 4054 ( 3580 integer_minmax_ops PGNSP PGUID ));
+DATA(insert OID = 5024 ( 3580 integer_bloom_ops PGNSP PGUID ));
DATA(insert OID = 4055 ( 3580 numeric_minmax_ops PGNSP PGUID ));
+DATA(insert OID = 5045 ( 3580 numeric_bloom_ops PGNSP PGUID ));
DATA(insert OID = 4056 ( 3580 text_minmax_ops PGNSP PGUID ));
+DATA(insert OID = 5027 ( 3580 text_bloom_ops PGNSP PGUID ));
DATA(insert OID = 4058 ( 3580 timetz_minmax_ops PGNSP PGUID ));
+DATA(insert OID = 5042 ( 3580 timetz_bloom_ops PGNSP PGUID ));
DATA(insert OID = 4059 ( 3580 datetime_minmax_ops PGNSP PGUID ));
+DATA(insert OID = 5038 ( 3580 datetime_bloom_ops PGNSP PGUID ));
DATA(insert OID = 4062 ( 3580 char_minmax_ops PGNSP PGUID ));
+DATA(insert OID = 5022 ( 3580 char_bloom_ops PGNSP PGUID ));
DATA(insert OID = 4064 ( 3580 bytea_minmax_ops PGNSP PGUID ));
+DATA(insert OID = 5021 ( 3580 bytea_bloom_ops PGNSP PGUID ));
DATA(insert OID = 4065 ( 3580 name_minmax_ops PGNSP PGUID ));
+DATA(insert OID = 5023 ( 3580 name_bloom_ops PGNSP PGUID ));
DATA(insert OID = 4068 ( 3580 oid_minmax_ops PGNSP PGUID ));
+DATA(insert OID = 5029 ( 3580 oid_bloom_ops PGNSP PGUID ));
DATA(insert OID = 4069 ( 3580 tid_minmax_ops PGNSP PGUID ));
DATA(insert OID = 4070 ( 3580 float_minmax_ops PGNSP PGUID ));
+DATA(insert OID = 5030 ( 3580 float_bloom_ops PGNSP PGUID ));
DATA(insert OID = 4072 ( 3580 abstime_minmax_ops PGNSP PGUID ));
+DATA(insert OID = 5031 ( 3580 abstime_bloom_ops PGNSP PGUID ));
DATA(insert OID = 4073 ( 3580 reltime_minmax_ops PGNSP PGUID ));
+DATA(insert OID = 5032 ( 3580 reltime_bloom_ops PGNSP PGUID ));
DATA(insert OID = 4074 ( 3580 macaddr_minmax_ops PGNSP PGUID ));
+DATA(insert OID = 5033 ( 3580 macaddr_bloom_ops PGNSP PGUID ));
DATA(insert OID = 4109 ( 3580 macaddr8_minmax_ops PGNSP PGUID ));
+DATA(insert OID = 5034 ( 3580 macaddr8_bloom_ops PGNSP PGUID ));
DATA(insert OID = 4075 ( 3580 network_minmax_ops PGNSP PGUID ));
DATA(insert OID = 4102 ( 3580 network_inclusion_ops PGNSP PGUID ));
+DATA(insert OID = 5035 ( 3580 network_bloom_ops PGNSP PGUID ));
DATA(insert OID = 4076 ( 3580 bpchar_minmax_ops PGNSP PGUID ));
+DATA(insert OID = 5036 ( 3580 bpchar_bloom_ops PGNSP PGUID ));
DATA(insert OID = 4077 ( 3580 time_minmax_ops PGNSP PGUID ));
+DATA(insert OID = 5037 ( 3580 time_bloom_ops PGNSP PGUID ));
DATA(insert OID = 4078 ( 3580 interval_minmax_ops PGNSP PGUID ));
+DATA(insert OID = 5041 ( 3580 interval_bloom_ops PGNSP PGUID ));
DATA(insert OID = 4079 ( 3580 bit_minmax_ops PGNSP PGUID ));
DATA(insert OID = 4080 ( 3580 varbit_minmax_ops PGNSP PGUID ));
DATA(insert OID = 4081 ( 3580 uuid_minmax_ops PGNSP PGUID ));
+DATA(insert OID = 5046 ( 3580 uuid_bloom_ops PGNSP PGUID ));
DATA(insert OID = 4103 ( 3580 range_inclusion_ops PGNSP PGUID ));
DATA(insert OID = 4082 ( 3580 pg_lsn_minmax_ops PGNSP PGUID ));
+DATA(insert OID = 5047 ( 3580 pg_lsn_bloom_ops PGNSP PGUID ));
DATA(insert OID = 4104 ( 3580 box_inclusion_ops PGNSP PGUID ));
DATA(insert OID = 5000 ( 4000 box_ops PGNSP PGUID ));
DATA(insert OID = 5008 ( 4000 poly_ops PGNSP PGUID ));
diff --git a/src/include/catalog/pg_proc.h b/src/include/catalog/pg_proc.h
index f01648c..7154e5e 100644
--- a/src/include/catalog/pg_proc.h
+++ b/src/include/catalog/pg_proc.h
@@ -4374,6 +4374,16 @@ DESCR("BRIN inclusion support");
DATA(insert OID = 4108 ( brin_inclusion_union PGNSP PGUID 12 1 0 0 0 f f f f t f i s 3 0 16 "2281 2281 2281" _null_ _null_ _null_ _null_ _null_ brin_inclusion_union _null_ _null_ _null_ ));
DESCR("BRIN inclusion support");
+/* BRIN bloom */
+DATA(insert OID = 5017 ( brin_bloom_opcinfo PGNSP PGUID 12 1 0 0 0 f f f f t f i s 1 0 2281 "2281" _null_ _null_ _null_ _null_ _null_ brin_bloom_opcinfo _null_ _null_ _null_ ));
+DESCR("BRIN bloom support");
+DATA(insert OID = 5018 ( brin_bloom_add_value PGNSP PGUID 12 1 0 0 0 f f f f t f i s 4 0 16 "2281 2281 2281 2281" _null_ _null_ _null_ _null_ _null_ brin_bloom_add_value _null_ _null_ _null_ ));
+DESCR("BRIN bloom support");
+DATA(insert OID = 5019 ( brin_bloom_consistent PGNSP PGUID 12 1 0 0 0 f f f f t f i s 3 0 16 "2281 2281 2281" _null_ _null_ _null_ _null_ _null_ brin_bloom_consistent _null_ _null_ _null_ ));
+DESCR("BRIN bloom support");
+DATA(insert OID = 5020 ( brin_bloom_union PGNSP PGUID 12 1 0 0 0 f f f f t f i s 3 0 16 "2281 2281 2281" _null_ _null_ _null_ _null_ _null_ brin_bloom_union _null_ _null_ _null_ ));
+DESCR("BRIN bloom support");
+
/* userlock replacements */
DATA(insert OID = 2880 ( pg_advisory_lock PGNSP PGUID 12 1 0 0 0 f f f f t f v u 1 0 2278 "20" _null_ _null_ _null_ _null_ _null_ pg_advisory_lock_int8 _null_ _null_ _null_ ));
DESCR("obtain exclusive advisory lock");
diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out
new file mode 100644
index 0000000..ec6e27a
--- /dev/null
+++ b/src/test/regress/expected/brin_bloom.out
@@ -0,0 +1,438 @@
+CREATE TABLE brintest_bloom (byteacol bytea,
+ charcol "char",
+ namecol name,
+ int8col bigint,
+ int2col smallint,
+ int4col integer,
+ textcol text,
+ oidcol oid,
+ float4col real,
+ float8col double precision,
+ macaddrcol macaddr,
+ inetcol inet,
+ cidrcol cidr,
+ bpcharcol character,
+ datecol date,
+ timecol time without time zone,
+ timestampcol timestamp without time zone,
+ timestamptzcol timestamp with time zone,
+ intervalcol interval,
+ timetzcol time with time zone,
+ numericcol numeric,
+ uuidcol uuid,
+ lsncol pg_lsn
+) WITH (fillfactor=10);
+INSERT INTO brintest_bloom SELECT
+ repeat(stringu1, 8)::bytea,
+ substr(stringu1, 1, 1)::"char",
+ stringu1::name, 142857 * tenthous,
+ thousand,
+ twothousand,
+ repeat(stringu1, 8),
+ unique1::oid,
+ (four + 1.0)/(hundred+1),
+ odd::float8 / (tenthous + 1),
+ format('%s:00:%s:00:%s:00', to_hex(odd), to_hex(even), to_hex(hundred))::macaddr,
+ inet '10.2.3.4/24' + tenthous,
+ cidr '10.2.3/24' + tenthous,
+ substr(stringu1, 1, 1)::bpchar,
+ date '1995-08-15' + tenthous,
+ time '01:20:30' + thousand * interval '18.5 second',
+ timestamp '1942-07-23 03:05:09' + tenthous * interval '36.38 hours',
+ timestamptz '1972-10-10 03:00' + thousand * interval '1 hour',
+ justify_days(justify_hours(tenthous * interval '12 minutes')),
+ timetz '01:30:20+02' + hundred * interval '15 seconds',
+ tenthous::numeric(36,30) * fivethous * even / (hundred + 1),
+ format('%s%s-%s-%s-%s-%s%s%s', to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'))::uuid,
+ format('%s/%s%s', odd, even, tenthous)::pg_lsn
+FROM tenk1 ORDER BY unique2 LIMIT 100;
+-- throw in some NULL's and different values
+INSERT INTO brintest_bloom (inetcol, cidrcol) SELECT
+ inet 'fe80::6e40:8ff:fea9:8c46' + tenthous,
+ cidr 'fe80::6e40:8ff:fea9:8c46' + tenthous
+FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
+CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
+ byteacol bytea_bloom_ops,
+ charcol char_bloom_ops,
+ namecol name_bloom_ops,
+ int8col int8_bloom_ops,
+ int2col int2_bloom_ops,
+ int4col int4_bloom_ops,
+ textcol text_bloom_ops,
+ oidcol oid_bloom_ops,
+ float4col float4_bloom_ops,
+ float8col float8_bloom_ops,
+ macaddrcol macaddr_bloom_ops,
+ inetcol inet_bloom_ops,
+ cidrcol inet_bloom_ops,
+ bpcharcol bpchar_bloom_ops,
+ datecol date_bloom_ops,
+ timecol time_bloom_ops,
+ timestampcol timestamp_bloom_ops,
+ timestamptzcol timestamptz_bloom_ops,
+ intervalcol interval_bloom_ops,
+ timetzcol timetz_bloom_ops,
+ numericcol numeric_bloom_ops,
+ uuidcol uuid_bloom_ops,
+ lsncol pg_lsn_bloom_ops
+) with (pages_per_range = 1);
+CREATE TABLE brinopers_bloom (colname name, typ text,
+ op text[], value text[], matches int[],
+ check (cardinality(op) = cardinality(value)),
+ check (cardinality(op) = cardinality(matches)));
+INSERT INTO brinopers_bloom VALUES
+ ('byteacol', 'bytea',
+ '{=}',
+ '{BNAAAABNAAAABNAAAABNAAAABNAAAABNAAAABNAAAABNAAAA}',
+ '{1}'),
+ ('charcol', '"char"',
+ '{=}',
+ '{M}',
+ '{6}'),
+ ('namecol', 'name',
+ '{=}',
+ '{MAAAAA}',
+ '{2}'),
+ ('int2col', 'int2',
+ '{=}',
+ '{800}',
+ '{1}'),
+ ('int2col', 'int4',
+ '{=}',
+ '{800}',
+ '{1}'),
+ ('int2col', 'int8',
+ '{=}',
+ '{800}',
+ '{1}'),
+ ('int4col', 'int2',
+ '{=}',
+ '{800}',
+ '{1}'),
+ ('int4col', 'int4',
+ '{=}',
+ '{800}',
+ '{1}'),
+ ('int4col', 'int8',
+ '{=}',
+ '{800}',
+ '{1}'),
+ ('int8col', 'int8',
+ '{=}',
+ '{1257141600}',
+ '{1}'),
+ ('textcol', 'text',
+ '{=}',
+ '{BNAAAABNAAAABNAAAABNAAAABNAAAABNAAAABNAAAABNAAAA}',
+ '{1}'),
+ ('oidcol', 'oid',
+ '{=}',
+ '{8800}',
+ '{1}'),
+ ('float4col', 'float4',
+ '{=}',
+ '{1}',
+ '{4}'),
+ ('float4col', 'float8',
+ '{=}',
+ '{1}',
+ '{4}'),
+ ('float8col', 'float4',
+ '{=}',
+ '{0}',
+ '{1}'),
+ ('float8col', 'float8',
+ '{=}',
+ '{0}',
+ '{1}'),
+ ('macaddrcol', 'macaddr',
+ '{=}',
+ '{2c:00:2d:00:16:00}',
+ '{2}'),
+ ('inetcol', 'inet',
+ '{=}',
+ '{10.2.14.231/24}',
+ '{1}'),
+ ('inetcol', 'cidr',
+ '{=}',
+ '{fe80::6e40:8ff:fea9:8c46}',
+ '{1}'),
+ ('cidrcol', 'inet',
+ '{=}',
+ '{10.2.14/24}',
+ '{2}'),
+ ('cidrcol', 'inet',
+ '{=}',
+ '{fe80::6e40:8ff:fea9:8c46}',
+ '{1}'),
+ ('cidrcol', 'cidr',
+ '{=}',
+ '{10.2.14/24}',
+ '{2}'),
+ ('cidrcol', 'cidr',
+ '{=}',
+ '{fe80::6e40:8ff:fea9:8c46}',
+ '{1}'),
+ ('bpcharcol', 'bpchar',
+ '{=}',
+ '{W}',
+ '{6}'),
+ ('datecol', 'date',
+ '{=}',
+ '{2009-12-01}',
+ '{1}'),
+ ('timecol', 'time',
+ '{=}',
+ '{02:28:57}',
+ '{1}'),
+ ('timestampcol', 'timestamp',
+ '{=}',
+ '{1964-03-24 19:26:45}',
+ '{1}'),
+ ('timestampcol', 'timestamptz',
+ '{=}',
+ '{1964-03-24 19:26:45}',
+ '{1}'),
+ ('timestamptzcol', 'timestamptz',
+ '{=}',
+ '{1972-10-19 09:00:00-07}',
+ '{1}'),
+ ('intervalcol', 'interval',
+ '{=}',
+ '{1 mons 13 days 12:24}',
+ '{1}'),
+ ('timetzcol', 'timetz',
+ '{=}',
+ '{01:35:50+02}',
+ '{2}'),
+ ('numericcol', 'numeric',
+ '{=}',
+ '{2268164.347826086956521739130434782609}',
+ '{1}'),
+ ('uuidcol', 'uuid',
+ '{=}',
+ '{52225222-5222-5222-5222-522252225222}',
+ '{1}'),
+ ('lsncol', 'pg_lsn',
+ '{=, IS, IS NOT}',
+ '{44/455222, NULL, NULL}',
+ '{1, 25, 100}');
+DO $x$
+DECLARE
+ r record;
+ r2 record;
+ cond text;
+ idx_ctids tid[];
+ ss_ctids tid[];
+ count int;
+ plan_ok bool;
+ plan_line text;
+BEGIN
+ FOR r IN SELECT colname, oper, typ, value[ordinality], matches[ordinality] FROM brinopers_bloom, unnest(op) WITH ORDINALITY AS oper LOOP
+
+ -- prepare the condition
+ IF r.value IS NULL THEN
+ cond := format('%I %s %L', r.colname, r.oper, r.value);
+ ELSE
+ cond := format('%I %s %L::%s', r.colname, r.oper, r.value, r.typ);
+ END IF;
+
+ -- run the query using the brin index
+ SET enable_seqscan = 0;
+ SET enable_bitmapscan = 1;
+
+ plan_ok := false;
+ FOR plan_line IN EXECUTE format($y$EXPLAIN SELECT array_agg(ctid) FROM brintest_bloom WHERE %s $y$, cond) LOOP
+ IF plan_line LIKE '%Bitmap Heap Scan on brintest_bloom%' THEN
+ plan_ok := true;
+ END IF;
+ END LOOP;
+ IF NOT plan_ok THEN
+ RAISE WARNING 'did not get bitmap indexscan plan for %', r;
+ END IF;
+
+ EXECUTE format($y$SELECT array_agg(ctid) FROM brintest_bloom WHERE %s $y$, cond)
+ INTO idx_ctids;
+
+ -- run the query using a seqscan
+ SET enable_seqscan = 1;
+ SET enable_bitmapscan = 0;
+
+ plan_ok := false;
+ FOR plan_line IN EXECUTE format($y$EXPLAIN SELECT array_agg(ctid) FROM brintest_bloom WHERE %s $y$, cond) LOOP
+ IF plan_line LIKE '%Seq Scan on brintest_bloom%' THEN
+ plan_ok := true;
+ END IF;
+ END LOOP;
+ IF NOT plan_ok THEN
+ RAISE WARNING 'did not get seqscan plan for %', r;
+ END IF;
+
+ EXECUTE format($y$SELECT array_agg(ctid) FROM brintest_bloom WHERE %s $y$, cond)
+ INTO ss_ctids;
+
+ -- make sure both return the same results
+ count := array_length(idx_ctids, 1);
+
+ IF NOT (count = array_length(ss_ctids, 1) AND
+ idx_ctids @> ss_ctids AND
+ idx_ctids <@ ss_ctids) THEN
+ -- report the results of each scan to make the differences obvious
+ RAISE WARNING 'something not right in %: count %', r, count;
+ SET enable_seqscan = 1;
+ SET enable_bitmapscan = 0;
+ FOR r2 IN EXECUTE 'SELECT ' || r.colname || ' FROM brintest_bloom WHERE ' || cond LOOP
+ RAISE NOTICE 'seqscan: %', r2;
+ END LOOP;
+
+ SET enable_seqscan = 0;
+ SET enable_bitmapscan = 1;
+ FOR r2 IN EXECUTE 'SELECT ' || r.colname || ' FROM brintest_bloom WHERE ' || cond LOOP
+ RAISE NOTICE 'bitmapscan: %', r2;
+ END LOOP;
+ END IF;
+
+ -- make sure we found expected number of matches
+ IF count != r.matches THEN RAISE WARNING 'unexpected number of results % for %', count, r; END IF;
+ END LOOP;
+END;
+$x$;
+RESET enable_seqscan;
+RESET enable_bitmapscan;
+INSERT INTO brintest_bloom SELECT
+ repeat(stringu1, 42)::bytea,
+ substr(stringu1, 1, 1)::"char",
+ stringu1::name, 142857 * tenthous,
+ thousand,
+ twothousand,
+ repeat(stringu1, 42),
+ unique1::oid,
+ (four + 1.0)/(hundred+1),
+ odd::float8 / (tenthous + 1),
+ format('%s:00:%s:00:%s:00', to_hex(odd), to_hex(even), to_hex(hundred))::macaddr,
+ inet '10.2.3.4' + tenthous,
+ cidr '10.2.3/24' + tenthous,
+ substr(stringu1, 1, 1)::bpchar,
+ date '1995-08-15' + tenthous,
+ time '01:20:30' + thousand * interval '18.5 second',
+ timestamp '1942-07-23 03:05:09' + tenthous * interval '36.38 hours',
+ timestamptz '1972-10-10 03:00' + thousand * interval '1 hour',
+ justify_days(justify_hours(tenthous * interval '12 minutes')),
+ timetz '01:30:20' + hundred * interval '15 seconds',
+ tenthous::numeric(36,30) * fivethous * even / (hundred + 1),
+ format('%s%s-%s-%s-%s-%s%s%s', to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'))::uuid,
+ format('%s/%s%s', odd, even, tenthous)::pg_lsn
+FROM tenk1 ORDER BY unique2 LIMIT 5 OFFSET 5;
+SELECT brin_desummarize_range('brinidx_bloom', 0);
+ brin_desummarize_range
+------------------------
+
+(1 row)
+
+VACUUM brintest_bloom; -- force a summarization cycle in brinidx
+UPDATE brintest_bloom SET int8col = int8col * int4col;
+UPDATE brintest_bloom SET textcol = '' WHERE textcol IS NOT NULL;
+-- Tests for brin_summarize_new_values
+SELECT brin_summarize_new_values('brintest_bloom'); -- error, not an index
+ERROR: "brintest_bloom" is not an index
+SELECT brin_summarize_new_values('tenk1_unique1'); -- error, not a BRIN index
+ERROR: "tenk1_unique1" is not a BRIN index
+SELECT brin_summarize_new_values('brinidx_bloom'); -- ok, no change expected
+ brin_summarize_new_values
+---------------------------
+ 0
+(1 row)
+
+-- Tests for brin_desummarize_range
+SELECT brin_desummarize_range('brinidx_bloom', -1); -- error, invalid range
+ERROR: block number out of range: -1
+SELECT brin_desummarize_range('brinidx_bloom', 0);
+ brin_desummarize_range
+------------------------
+
+(1 row)
+
+SELECT brin_desummarize_range('brinidx_bloom', 0);
+ brin_desummarize_range
+------------------------
+
+(1 row)
+
+SELECT brin_desummarize_range('brinidx_bloom', 100000000);
+ brin_desummarize_range
+------------------------
+
+(1 row)
+
+-- Test brin_summarize_range
+CREATE TABLE brin_summarize_bloom (
+ value int
+) WITH (fillfactor=10, autovacuum_enabled=false);
+CREATE INDEX brin_summarize_bloom_idx ON brin_summarize_bloom USING brin (value) WITH (pages_per_range=2);
+-- Fill a few pages
+DO $$
+DECLARE curtid tid;
+BEGIN
+ LOOP
+ INSERT INTO brin_summarize_bloom VALUES (1) RETURNING ctid INTO curtid;
+ EXIT WHEN curtid > tid '(2, 0)';
+ END LOOP;
+END;
+$$;
+-- summarize one range
+SELECT brin_summarize_range('brin_summarize_bloom_idx', 0);
+ brin_summarize_range
+----------------------
+ 0
+(1 row)
+
+-- nothing: already summarized
+SELECT brin_summarize_range('brin_summarize_bloom_idx', 1);
+ brin_summarize_range
+----------------------
+ 0
+(1 row)
+
+-- summarize one range
+SELECT brin_summarize_range('brin_summarize_bloom_idx', 2);
+ brin_summarize_range
+----------------------
+ 1
+(1 row)
+
+-- nothing: page doesn't exist in table
+SELECT brin_summarize_range('brin_summarize_bloom_idx', 4294967295);
+ brin_summarize_range
+----------------------
+ 0
+(1 row)
+
+-- invalid block number values
+SELECT brin_summarize_range('brin_summarize_bloom_idx', -1);
+ERROR: block number out of range: -1
+SELECT brin_summarize_range('brin_summarize_bloom_idx', 4294967296);
+ERROR: block number out of range: 4294967296
+-- test brin cost estimates behave sanely based on correlation of values
+CREATE TABLE brin_test_bloom (a INT, b INT);
+INSERT INTO brin_test_bloom SELECT x/100,x%100 FROM generate_series(1,10000) x(x);
+CREATE INDEX brin_test_bloom_a_idx ON brin_test_bloom USING brin (a) WITH (pages_per_range = 2);
+CREATE INDEX brin_test_bloom_b_idx ON brin_test_bloom USING brin (b) WITH (pages_per_range = 2);
+VACUUM ANALYZE brin_test_bloom;
+-- Ensure brin index is used when columns are perfectly correlated
+EXPLAIN (COSTS OFF) SELECT * FROM brin_test_bloom WHERE a = 1;
+ QUERY PLAN
+--------------------------------------------------
+ Bitmap Heap Scan on brin_test_bloom
+ Recheck Cond: (a = 1)
+ -> Bitmap Index Scan on brin_test_bloom_a_idx
+ Index Cond: (a = 1)
+(4 rows)
+
+-- Ensure brin index is not used when values are not correlated
+EXPLAIN (COSTS OFF) SELECT * FROM brin_test_bloom WHERE b = 1;
+ QUERY PLAN
+-----------------------------
+ Seq Scan on brin_test_bloom
+ Filter: (b = 1)
+(2 rows)
+
diff --git a/src/test/regress/expected/opr_sanity.out b/src/test/regress/expected/opr_sanity.out
index 684f7f2..91b2ecc 100644
--- a/src/test/regress/expected/opr_sanity.out
+++ b/src/test/regress/expected/opr_sanity.out
@@ -1819,6 +1819,7 @@ ORDER BY 1, 2, 3;
2742 | 11 | ?&
3580 | 1 | <
3580 | 1 | <<
+ 3580 | 1 | =
3580 | 2 | &<
3580 | 2 | <=
3580 | 3 | &&
@@ -1880,7 +1881,7 @@ ORDER BY 1, 2, 3;
4000 | 25 | <<=
4000 | 26 | >>
4000 | 27 | >>=
-(121 rows)
+(122 rows)
-- Check that all opclass search operators have selectivity estimators.
-- This is not absolutely required, but it seems a reasonable thing
diff --git a/src/test/regress/parallel_schedule b/src/test/regress/parallel_schedule
index ad9434f..149999d 100644
--- a/src/test/regress/parallel_schedule
+++ b/src/test/regress/parallel_schedule
@@ -84,7 +84,7 @@ test: select_into select_distinct select_distinct_on select_implicit select_havi
# ----------
# Another group of parallel tests
# ----------
-test: brin gin gist spgist privileges init_privs security_label collate matview lock replica_identity rowsecurity object_address tablesample groupingsets drop_operator password
+test: brin brin_bloom gin gist spgist privileges init_privs security_label collate matview lock replica_identity rowsecurity object_address tablesample groupingsets drop_operator password
# ----------
# Another group of parallel tests
diff --git a/src/test/regress/serial_schedule b/src/test/regress/serial_schedule
index 27cd498..06c3488 100644
--- a/src/test/regress/serial_schedule
+++ b/src/test/regress/serial_schedule
@@ -106,6 +106,7 @@ test: delete
test: namespace
test: prepared_xacts
test: brin
+test: brin_bloom
test: gin
test: gist
test: spgist
diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql
new file mode 100644
index 0000000..8b2c005
--- /dev/null
+++ b/src/test/regress/sql/brin_bloom.sql
@@ -0,0 +1,391 @@
+CREATE TABLE brintest_bloom (byteacol bytea,
+ charcol "char",
+ namecol name,
+ int8col bigint,
+ int2col smallint,
+ int4col integer,
+ textcol text,
+ oidcol oid,
+ float4col real,
+ float8col double precision,
+ macaddrcol macaddr,
+ inetcol inet,
+ cidrcol cidr,
+ bpcharcol character,
+ datecol date,
+ timecol time without time zone,
+ timestampcol timestamp without time zone,
+ timestamptzcol timestamp with time zone,
+ intervalcol interval,
+ timetzcol time with time zone,
+ numericcol numeric,
+ uuidcol uuid,
+ lsncol pg_lsn
+) WITH (fillfactor=10);
+
+INSERT INTO brintest_bloom SELECT
+ repeat(stringu1, 8)::bytea,
+ substr(stringu1, 1, 1)::"char",
+ stringu1::name, 142857 * tenthous,
+ thousand,
+ twothousand,
+ repeat(stringu1, 8),
+ unique1::oid,
+ (four + 1.0)/(hundred+1),
+ odd::float8 / (tenthous + 1),
+ format('%s:00:%s:00:%s:00', to_hex(odd), to_hex(even), to_hex(hundred))::macaddr,
+ inet '10.2.3.4/24' + tenthous,
+ cidr '10.2.3/24' + tenthous,
+ substr(stringu1, 1, 1)::bpchar,
+ date '1995-08-15' + tenthous,
+ time '01:20:30' + thousand * interval '18.5 second',
+ timestamp '1942-07-23 03:05:09' + tenthous * interval '36.38 hours',
+ timestamptz '1972-10-10 03:00' + thousand * interval '1 hour',
+ justify_days(justify_hours(tenthous * interval '12 minutes')),
+ timetz '01:30:20+02' + hundred * interval '15 seconds',
+ tenthous::numeric(36,30) * fivethous * even / (hundred + 1),
+ format('%s%s-%s-%s-%s-%s%s%s', to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'))::uuid,
+ format('%s/%s%s', odd, even, tenthous)::pg_lsn
+FROM tenk1 ORDER BY unique2 LIMIT 100;
+
+-- throw in some NULL's and different values
+INSERT INTO brintest_bloom (inetcol, cidrcol) SELECT
+ inet 'fe80::6e40:8ff:fea9:8c46' + tenthous,
+ cidr 'fe80::6e40:8ff:fea9:8c46' + tenthous
+FROM tenk1 ORDER BY thousand, tenthous LIMIT 25;
+
+CREATE INDEX brinidx_bloom ON brintest_bloom USING brin (
+ byteacol bytea_bloom_ops,
+ charcol char_bloom_ops,
+ namecol name_bloom_ops,
+ int8col int8_bloom_ops,
+ int2col int2_bloom_ops,
+ int4col int4_bloom_ops,
+ textcol text_bloom_ops,
+ oidcol oid_bloom_ops,
+ float4col float4_bloom_ops,
+ float8col float8_bloom_ops,
+ macaddrcol macaddr_bloom_ops,
+ inetcol inet_bloom_ops,
+ cidrcol inet_bloom_ops,
+ bpcharcol bpchar_bloom_ops,
+ datecol date_bloom_ops,
+ timecol time_bloom_ops,
+ timestampcol timestamp_bloom_ops,
+ timestamptzcol timestamptz_bloom_ops,
+ intervalcol interval_bloom_ops,
+ timetzcol timetz_bloom_ops,
+ numericcol numeric_bloom_ops,
+ uuidcol uuid_bloom_ops,
+ lsncol pg_lsn_bloom_ops
+) with (pages_per_range = 1);
+
+CREATE TABLE brinopers_bloom (colname name, typ text,
+ op text[], value text[], matches int[],
+ check (cardinality(op) = cardinality(value)),
+ check (cardinality(op) = cardinality(matches)));
+
+INSERT INTO brinopers_bloom VALUES
+ ('byteacol', 'bytea',
+ '{=}',
+ '{BNAAAABNAAAABNAAAABNAAAABNAAAABNAAAABNAAAABNAAAA}',
+ '{1}'),
+ ('charcol', '"char"',
+ '{=}',
+ '{M}',
+ '{6}'),
+ ('namecol', 'name',
+ '{=}',
+ '{MAAAAA}',
+ '{2}'),
+ ('int2col', 'int2',
+ '{=}',
+ '{800}',
+ '{1}'),
+ ('int2col', 'int4',
+ '{=}',
+ '{800}',
+ '{1}'),
+ ('int2col', 'int8',
+ '{=}',
+ '{800}',
+ '{1}'),
+ ('int4col', 'int2',
+ '{=}',
+ '{800}',
+ '{1}'),
+ ('int4col', 'int4',
+ '{=}',
+ '{800}',
+ '{1}'),
+ ('int4col', 'int8',
+ '{=}',
+ '{800}',
+ '{1}'),
+ ('int8col', 'int8',
+ '{=}',
+ '{1257141600}',
+ '{1}'),
+ ('textcol', 'text',
+ '{=}',
+ '{BNAAAABNAAAABNAAAABNAAAABNAAAABNAAAABNAAAABNAAAA}',
+ '{1}'),
+ ('oidcol', 'oid',
+ '{=}',
+ '{8800}',
+ '{1}'),
+ ('float4col', 'float4',
+ '{=}',
+ '{1}',
+ '{4}'),
+ ('float4col', 'float8',
+ '{=}',
+ '{1}',
+ '{4}'),
+ ('float8col', 'float4',
+ '{=}',
+ '{0}',
+ '{1}'),
+ ('float8col', 'float8',
+ '{=}',
+ '{0}',
+ '{1}'),
+ ('macaddrcol', 'macaddr',
+ '{=}',
+ '{2c:00:2d:00:16:00}',
+ '{2}'),
+ ('inetcol', 'inet',
+ '{=}',
+ '{10.2.14.231/24}',
+ '{1}'),
+ ('inetcol', 'cidr',
+ '{=}',
+ '{fe80::6e40:8ff:fea9:8c46}',
+ '{1}'),
+ ('cidrcol', 'inet',
+ '{=}',
+ '{10.2.14/24}',
+ '{2}'),
+ ('cidrcol', 'inet',
+ '{=}',
+ '{fe80::6e40:8ff:fea9:8c46}',
+ '{1}'),
+ ('cidrcol', 'cidr',
+ '{=}',
+ '{10.2.14/24}',
+ '{2}'),
+ ('cidrcol', 'cidr',
+ '{=}',
+ '{fe80::6e40:8ff:fea9:8c46}',
+ '{1}'),
+ ('bpcharcol', 'bpchar',
+ '{=}',
+ '{W}',
+ '{6}'),
+ ('datecol', 'date',
+ '{=}',
+ '{2009-12-01}',
+ '{1}'),
+ ('timecol', 'time',
+ '{=}',
+ '{02:28:57}',
+ '{1}'),
+ ('timestampcol', 'timestamp',
+ '{=}',
+ '{1964-03-24 19:26:45}',
+ '{1}'),
+ ('timestampcol', 'timestamptz',
+ '{=}',
+ '{1964-03-24 19:26:45}',
+ '{1}'),
+ ('timestamptzcol', 'timestamptz',
+ '{=}',
+ '{1972-10-19 09:00:00-07}',
+ '{1}'),
+ ('intervalcol', 'interval',
+ '{=}',
+ '{1 mons 13 days 12:24}',
+ '{1}'),
+ ('timetzcol', 'timetz',
+ '{=}',
+ '{01:35:50+02}',
+ '{2}'),
+ ('numericcol', 'numeric',
+ '{=}',
+ '{2268164.347826086956521739130434782609}',
+ '{1}'),
+ ('uuidcol', 'uuid',
+ '{=}',
+ '{52225222-5222-5222-5222-522252225222}',
+ '{1}'),
+ ('lsncol', 'pg_lsn',
+ '{=, IS, IS NOT}',
+ '{44/455222, NULL, NULL}',
+ '{1, 25, 100}');
+
+DO $x$
+DECLARE
+ r record;
+ r2 record;
+ cond text;
+ idx_ctids tid[];
+ ss_ctids tid[];
+ count int;
+ plan_ok bool;
+ plan_line text;
+BEGIN
+ FOR r IN SELECT colname, oper, typ, value[ordinality], matches[ordinality] FROM brinopers_bloom, unnest(op) WITH ORDINALITY AS oper LOOP
+
+ -- prepare the condition
+ IF r.value IS NULL THEN
+ cond := format('%I %s %L', r.colname, r.oper, r.value);
+ ELSE
+ cond := format('%I %s %L::%s', r.colname, r.oper, r.value, r.typ);
+ END IF;
+
+ -- run the query using the brin index
+ SET enable_seqscan = 0;
+ SET enable_bitmapscan = 1;
+
+ plan_ok := false;
+ FOR plan_line IN EXECUTE format($y$EXPLAIN SELECT array_agg(ctid) FROM brintest_bloom WHERE %s $y$, cond) LOOP
+ IF plan_line LIKE '%Bitmap Heap Scan on brintest_bloom%' THEN
+ plan_ok := true;
+ END IF;
+ END LOOP;
+ IF NOT plan_ok THEN
+ RAISE WARNING 'did not get bitmap indexscan plan for %', r;
+ END IF;
+
+ EXECUTE format($y$SELECT array_agg(ctid) FROM brintest_bloom WHERE %s $y$, cond)
+ INTO idx_ctids;
+
+ -- run the query using a seqscan
+ SET enable_seqscan = 1;
+ SET enable_bitmapscan = 0;
+
+ plan_ok := false;
+ FOR plan_line IN EXECUTE format($y$EXPLAIN SELECT array_agg(ctid) FROM brintest_bloom WHERE %s $y$, cond) LOOP
+ IF plan_line LIKE '%Seq Scan on brintest_bloom%' THEN
+ plan_ok := true;
+ END IF;
+ END LOOP;
+ IF NOT plan_ok THEN
+ RAISE WARNING 'did not get seqscan plan for %', r;
+ END IF;
+
+ EXECUTE format($y$SELECT array_agg(ctid) FROM brintest_bloom WHERE %s $y$, cond)
+ INTO ss_ctids;
+
+ -- make sure both return the same results
+ count := array_length(idx_ctids, 1);
+
+ IF NOT (count = array_length(ss_ctids, 1) AND
+ idx_ctids @> ss_ctids AND
+ idx_ctids <@ ss_ctids) THEN
+ -- report the results of each scan to make the differences obvious
+ RAISE WARNING 'something not right in %: count %', r, count;
+ SET enable_seqscan = 1;
+ SET enable_bitmapscan = 0;
+ FOR r2 IN EXECUTE 'SELECT ' || r.colname || ' FROM brintest_bloom WHERE ' || cond LOOP
+ RAISE NOTICE 'seqscan: %', r2;
+ END LOOP;
+
+ SET enable_seqscan = 0;
+ SET enable_bitmapscan = 1;
+ FOR r2 IN EXECUTE 'SELECT ' || r.colname || ' FROM brintest_bloom WHERE ' || cond LOOP
+ RAISE NOTICE 'bitmapscan: %', r2;
+ END LOOP;
+ END IF;
+
+ -- make sure we found expected number of matches
+ IF count != r.matches THEN RAISE WARNING 'unexpected number of results % for %', count, r; END IF;
+ END LOOP;
+END;
+$x$;
+
+RESET enable_seqscan;
+RESET enable_bitmapscan;
+
+INSERT INTO brintest_bloom SELECT
+ repeat(stringu1, 42)::bytea,
+ substr(stringu1, 1, 1)::"char",
+ stringu1::name, 142857 * tenthous,
+ thousand,
+ twothousand,
+ repeat(stringu1, 42),
+ unique1::oid,
+ (four + 1.0)/(hundred+1),
+ odd::float8 / (tenthous + 1),
+ format('%s:00:%s:00:%s:00', to_hex(odd), to_hex(even), to_hex(hundred))::macaddr,
+ inet '10.2.3.4' + tenthous,
+ cidr '10.2.3/24' + tenthous,
+ substr(stringu1, 1, 1)::bpchar,
+ date '1995-08-15' + tenthous,
+ time '01:20:30' + thousand * interval '18.5 second',
+ timestamp '1942-07-23 03:05:09' + tenthous * interval '36.38 hours',
+ timestamptz '1972-10-10 03:00' + thousand * interval '1 hour',
+ justify_days(justify_hours(tenthous * interval '12 minutes')),
+ timetz '01:30:20' + hundred * interval '15 seconds',
+ tenthous::numeric(36,30) * fivethous * even / (hundred + 1),
+ format('%s%s-%s-%s-%s-%s%s%s', to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'), to_char(tenthous, 'FM0000'))::uuid,
+ format('%s/%s%s', odd, even, tenthous)::pg_lsn
+FROM tenk1 ORDER BY unique2 LIMIT 5 OFFSET 5;
+
+SELECT brin_desummarize_range('brinidx_bloom', 0);
+VACUUM brintest_bloom; -- force a summarization cycle in brinidx
+
+UPDATE brintest_bloom SET int8col = int8col * int4col;
+UPDATE brintest_bloom SET textcol = '' WHERE textcol IS NOT NULL;
+
+-- Tests for brin_summarize_new_values
+SELECT brin_summarize_new_values('brintest_bloom'); -- error, not an index
+SELECT brin_summarize_new_values('tenk1_unique1'); -- error, not a BRIN index
+SELECT brin_summarize_new_values('brinidx_bloom'); -- ok, no change expected
+
+-- Tests for brin_desummarize_range
+SELECT brin_desummarize_range('brinidx_bloom', -1); -- error, invalid range
+SELECT brin_desummarize_range('brinidx_bloom', 0);
+SELECT brin_desummarize_range('brinidx_bloom', 0);
+SELECT brin_desummarize_range('brinidx_bloom', 100000000);
+
+-- Test brin_summarize_range
+CREATE TABLE brin_summarize_bloom (
+ value int
+) WITH (fillfactor=10, autovacuum_enabled=false);
+CREATE INDEX brin_summarize_bloom_idx ON brin_summarize_bloom USING brin (value) WITH (pages_per_range=2);
+-- Fill a few pages
+DO $$
+DECLARE curtid tid;
+BEGIN
+ LOOP
+ INSERT INTO brin_summarize_bloom VALUES (1) RETURNING ctid INTO curtid;
+ EXIT WHEN curtid > tid '(2, 0)';
+ END LOOP;
+END;
+$$;
+
+-- summarize one range
+SELECT brin_summarize_range('brin_summarize_bloom_idx', 0);
+-- nothing: already summarized
+SELECT brin_summarize_range('brin_summarize_bloom_idx', 1);
+-- summarize one range
+SELECT brin_summarize_range('brin_summarize_bloom_idx', 2);
+-- nothing: page doesn't exist in table
+SELECT brin_summarize_range('brin_summarize_bloom_idx', 4294967295);
+-- invalid block number values
+SELECT brin_summarize_range('brin_summarize_bloom_idx', -1);
+SELECT brin_summarize_range('brin_summarize_bloom_idx', 4294967296);
+
+
+-- test brin cost estimates behave sanely based on correlation of values
+CREATE TABLE brin_test_bloom (a INT, b INT);
+INSERT INTO brin_test_bloom SELECT x/100,x%100 FROM generate_series(1,10000) x(x);
+CREATE INDEX brin_test_bloom_a_idx ON brin_test_bloom USING brin (a) WITH (pages_per_range = 2);
+CREATE INDEX brin_test_bloom_b_idx ON brin_test_bloom USING brin (b) WITH (pages_per_range = 2);
+VACUUM ANALYZE brin_test_bloom;
+
+-- Ensure brin index is used when columns are perfectly correlated
+EXPLAIN (COSTS OFF) SELECT * FROM brin_test_bloom WHERE a = 1;
+-- Ensure brin index is not used when values are not correlated
+EXPLAIN (COSTS OFF) SELECT * FROM brin_test_bloom WHERE b = 1;
--
2.9.5
--------------53C4B41F409B92A47ECAD3E5
Content-Type: text/x-patch;
name="0004-BRIN-multi-range-minmax-indexes.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename="0004-BRIN-multi-range-minmax-indexes.patch"
view thread (32+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected]
Subject: Re: [PATCH 3/4] BRIN bloom indexes
In-Reply-To: <no-message-id-242161@localhost>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox