From c27f02d2839e08ebcee852448ed3838c8932d2ea Mon Sep 17 00:00:00 2001 From: Tomas Vondra Date: Mon, 23 Oct 2017 22:48:58 +0200 Subject: [PATCH 1/2] brin bloom v1 --- doc/src/sgml/brin.sgml | 236 ++++++++++ src/backend/access/brin/Makefile | 2 +- src/backend/access/brin/brin_bloom.c | 727 +++++++++++++++++++++++++++++++ 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/opr_sanity.out | 3 +- 9 files changed, 1233 insertions(+), 2 deletions(-) create mode 100644 src/backend/access/brin/brin_bloom.c diff --git a/doc/src/sgml/brin.sgml b/doc/src/sgml/brin.sgml index b7483df..49d53e1 100644 --- a/doc/src/sgml/brin.sgml +++ b/doc/src/sgml/brin.sgml @@ -118,6 +118,13 @@ + abstime_bloom_ops + abstime + + = + + + abstime_minmax_ops abstime @@ -129,6 +136,13 @@ + int8_bloom_ops + bigint + + = + + + int8_minmax_ops bigint @@ -180,6 +194,13 @@ + bytea_bloom_ops + bytea + + = + + + bytea_minmax_ops bytea @@ -191,6 +212,13 @@ + bpchar_bloom_ops + character + + = + + + bpchar_minmax_ops character @@ -202,6 +230,13 @@ + char_bloom_ops + "char" + + = + + + char_minmax_ops "char" @@ -213,6 +248,13 @@ + date_bloom_ops + date + + = + + + date_minmax_ops date @@ -224,6 +266,13 @@ + float8_bloom_ops + double precision + + = + + + float8_minmax_ops double precision @@ -235,6 +284,13 @@ + inet_bloom_ops + inet + + = + + + inet_minmax_ops inet @@ -258,6 +314,13 @@ + int4_bloom_ops + integer + + = + + + int4_minmax_ops integer @@ -269,6 +332,13 @@ + interval_bloom_ops + interval + + = + + + interval_minmax_ops interval @@ -280,6 +350,13 @@ + macaddr_bloom_ops + macaddr + + = + + + macaddr_minmax_ops macaddr @@ -291,6 +368,13 @@ + macaddr8_bloom_ops + macaddr8 + + = + + + macaddr8_minmax_ops macaddr8 @@ -302,6 +386,13 @@ + name_bloom_ops + name + + = + + + name_minmax_ops name @@ -313,6 +404,13 @@ + numeric_bloom_ops + numeric + + = + + + numeric_minmax_ops numeric @@ -324,6 +422,13 @@ + pg_lsn_bloom_ops + pg_lsn + + = + + + pg_lsn_minmax_ops pg_lsn @@ -335,6 +440,13 @@ + oid_bloom_ops + oid + + = + + + oid_minmax_ops oid @@ -366,6 +478,13 @@ + float4_bloom_ops + real + + = + + + float4_minmax_ops real @@ -377,6 +496,13 @@ + reltime_bloom_ops + reltime + + = + + + reltime_minmax_ops reltime @@ -388,6 +514,13 @@ + int2_bloom_ops + smallint + + = + + + int2_minmax_ops smallint @@ -399,6 +532,13 @@ + text_bloom_ops + text + + = + + + text_minmax_ops text @@ -410,6 +550,13 @@ + tid_bloom_ops + tid + + = + + + tid_minmax_ops tid @@ -421,6 +568,13 @@ + timestamp_bloom_ops + timestamp without time zone + + = + + + timestamp_minmax_ops timestamp without time zone @@ -432,6 +586,13 @@ + timestamptz_bloom_ops + timestamp with time zone + + = + + + timestamptz_minmax_ops timestamp with time zone @@ -443,6 +604,13 @@ + time_bloom_ops + time without time zone + + = + + + time_minmax_ops time without time zone @@ -454,6 +622,13 @@ + timetz_bloom_ops + time with time zone + + = + + + timetz_minmax_ops time with time zone @@ -465,6 +640,13 @@ + uuid_bloom_ops + uuid + + = + + + uuid_minmax_ops uuid @@ -814,6 +996,60 @@ typedef struct BrinOpcInfo + 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 + . + All operator class members (procedures and operators) are mandatory. + + + + Procedure and Support Numbers for Bloom Operator Classes + + + + Operator class member + Object + + + + + Support Procedure 1 + internal function brin_bloom_opcinfo() + + + Support Procedure 2 + internal function brin_bloom_add_value() + + + Support Procedure 3 + internal function brin_bloom_consistent() + + + Support Procedure 4 + internal function brin_bloom_union() + + + Support Procedure 11 + function to compute hash of an element + + + Operator Strategy 1 + operator equal-to + + + +
+ + + 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. + + + 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..c08f686 --- /dev/null +++ b/src/backend/access/brin/brin_bloom.c @@ -0,0 +1,727 @@ +/* + * 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 + +#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 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); + + elog(DEBUG1, "create bloom filter m=%d k=%d", m, k); + + /* + * 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; + + /* assume 'not updated' by default */ + if (updated) + *updated = false; + + 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 regular hashing phase */ + Assert(filter->phase == BLOOM_PHASE_HASH); + + /* we're in the ah */ + for (i = 0; i < filter->nhashes; i++) + { + /* + * Our "hash functions" are effectively hashes of the original + * hash, with different seeds. + */ + uint32 h = ((uint32)DatumGetInt64(hash_uint32_extended(value, i))) % filter->nbits; + + 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; + } + } + + 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; + + elog(WARNING, "switching %p to hashing (sorted %d, total %d)", filter, filter->nsorted, filter->nvalues); + + /* + * 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; + + 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); + + for (i = 0; i < filter->nhashes; i++) + { + /* compute the hashes with a seed, used for the bloom filter */ + uint32 h = ((uint32)DatumGetInt64(hash_uint32_extended(value, i))) % filter->nbits; + + 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; + } + + /* all hashes found in bloom filter */ + return true; +} + +/* + * bloom_filter_count + * Estimate the number of distinct values stored in the bloom filter. + */ +static int +bloom_filter_count(BloomFilter *filter) +{ + if (filter->phase == BLOOM_PHASE_SORTED) + return (filter->nvalues + filter->nsorted); + else + return ceil(- (filter->nbits * 1.0 / filter->nhashes * log(1 - filter->nbits_set * 1.0 / filter->nbits))); +} + +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 *) DatumGetPointer(column->bv_values[0]); + + elog(DEBUG1, "brin_bloom_add_value: filter=%p bits=%d hashes=%d values=%d set=%d estimate=%d", + filter, filter->nbits, filter->nhashes, filter->nvalues, filter->nbits_set, + bloom_filter_count(filter)); + + /* + * 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)); + + column->bv_values[0] = PointerGetDatum(bloom_add_value(filter, hashValue, &updated)); + + 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 key = (ScanKey) PG_GETARG_POINTER(2); + Oid colloid = PG_GET_COLLATION(); + AttrNumber attno; + Datum value; + Datum matches; + FmgrInfo *finfo; + uint32 hashValue; + BloomFilter *filter; + + Assert(key->sk_attno == column->bv_attno); + + /* handle IS NULL/IS NOT NULL tests */ + if (key->sk_flags & SK_ISNULL) + { + if (key->sk_flags & SK_SEARCHNULL) + { + if (column->bv_allnulls || column->bv_hasnulls) + PG_RETURN_BOOL(true); + PG_RETURN_BOOL(false); + } + + /* + * For IS NOT NULL, we can only skip ranges that are known to have + * only nulls. + */ + if (key->sk_flags & SK_SEARCHNOTNULL) + PG_RETURN_BOOL(!column->bv_allnulls); + + /* + * Neither IS NULL nor IS NOT NULL was used; assume all indexable + * operators are strict and return false. + */ + PG_RETURN_BOOL(false); + } + + /* if the range is all empty, it cannot possibly be consistent */ + if (column->bv_allnulls) + PG_RETURN_BOOL(false); + + filter = (BloomFilter *) DatumGetPointer(column->bv_values[0]); + + Assert(filter); + + 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; + } + + 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) +{ + BrinDesc *bdesc = (BrinDesc *) PG_GETARG_POINTER(0); + BrinValues *col_a = (BrinValues *) PG_GETARG_POINTER(1); + BrinValues *col_b = (BrinValues *) PG_GETARG_POINTER(2); + AttrNumber attno; + Form_pg_attribute attr; + + 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(); + + attno = col_a->bv_attno; + attr = TupleDescAttr(bdesc->bd_tupdesc, attno - 1); + + /* + * 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], + attr->attbyval, attr->attlen); + PG_RETURN_VOID(); + } + + /* FIXME merge the two bloom filters */ + elog(WARNING, "FIXME: merge bloom filters"); + + 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 f850be4..ef5b692 100644 --- a/src/include/catalog/pg_amop.h +++ b/src/include/catalog/pg_amop.h @@ -894,18 +894,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 )); @@ -952,6 +958,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 )); @@ -959,12 +975,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 ( 5028 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 )); @@ -992,6 +1012,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 )); @@ -999,24 +1024,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 )); @@ -1030,18 +1063,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 )); @@ -1088,6 +1127,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 )); @@ -1095,12 +1144,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 )); @@ -1119,12 +1172,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 )); @@ -1146,6 +1203,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 1c95846..cef4a7c 100644 --- a/src/include/catalog/pg_amproc.h +++ b/src/include/catalog/pg_amproc.h @@ -341,16 +341,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 )); @@ -391,16 +409,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 ( 5028 26 26 1 5017 )); +DATA(insert ( 5028 26 26 2 5018 )); +DATA(insert ( 5028 26 26 3 5019 )); +DATA(insert ( 5028 26 26 4 5020 )); +DATA(insert ( 5028 26 26 11 453 )); /* minmax tid */ DATA(insert ( 4069 27 27 1 3383 )); DATA(insert ( 4069 27 27 2 3384 )); @@ -427,26 +476,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 )); @@ -460,16 +546,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 )); @@ -510,16 +614,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 )); @@ -535,11 +670,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 )); @@ -553,6 +700,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 28dbc74..ce28469 100644 --- a/src/include/catalog/pg_opclass.h +++ b/src/include/catalog/pg_opclass.h @@ -213,36 +213,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 5028 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 0d0ba7c..bf9c578 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 = 5028 ( 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 )); diff --git a/src/include/catalog/pg_proc.h b/src/include/catalog/pg_proc.h index 93c031a..5852496 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/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 -- 2.9.5