agora inbox for pgsql-hackers@postgresql.orghelp / color / mirror / Atom feed
[PATCH 5/8] bloom fixes and tweaks 3+ messages / 2 participants [nested] [flat]
* [PATCH 5/8] bloom fixes and tweaks @ 2021-01-12 23:59 Tomas Vondra <tomas.vondra@postgresql.org> 0 siblings, 0 replies; 3+ messages in thread From: Tomas Vondra @ 2021-01-12 23:59 UTC (permalink / raw) --- doc/src/sgml/ref/create_index.sgml | 2 +- src/backend/access/brin/brin_bloom.c | 84 ++++++++++++++---------- src/test/regress/expected/brin_bloom.out | 14 ++-- src/test/regress/sql/brin_bloom.sql | 6 +- 4 files changed, 60 insertions(+), 46 deletions(-) diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml index 8db10b7b1e..244e5834d8 100644 --- a/doc/src/sgml/ref/create_index.sgml +++ b/doc/src/sgml/ref/create_index.sgml @@ -573,7 +573,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ [ IF NOT EXISTS ] <replaceable class= equal to -1, the number of distinct non-null is assumed linear with the maximum possible number of tuples in the block range (about 290 rows per block). The default values is <literal>-0.1</literal>, and - the minimum number of distinct non-null values is <literal>128</literal>. + the minimum number of distinct non-null values is <literal>16</literal>. </para> </listitem> </varlistentry> diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c index b7aa6d9f11..ffeb459d3e 100644 --- a/src/backend/access/brin/brin_bloom.c +++ b/src/backend/access/brin/brin_bloom.c @@ -8,12 +8,12 @@ * * A BRIN opclass summarizing page range into a bloom filter. * - * Bloom filters allow efficient test whether a given page range contains + * Bloom filters allow efficient testing whether a given page range contains * a particular value. Therefore, if we summarize each page range into a - * bloom filter, we can easily and cheaply test wheter it containst values + * bloom filter, we can easily and cheaply test wheter it contains values * we get later. * - * The index only supports equality operator, similarly to hash indexes. + * The index only supports equality operators, similarly to hash indexes. * BRIN bloom indexes are however much smaller, and support only bitmap * scans. * @@ -51,9 +51,9 @@ * the bloom filter. On the other hand, we want to keep the index as small * as possible - that's one of the basic advantages of BRIN indexes. * - * The number of distinct elements (in a page range) depends on the data, - * we can consider it fixed. This simplifies the trade-off to just false - * positive rate vs. size. + * Although the number of distinct elements (in a page range) depends on + * the data, we can consider it fixed. This simplifies the trade-off to + * just false positive rate vs. size. * * At the page range level, false positive rate is a probability the bloom * filter matches a random value. For the whole index (with sufficiently @@ -65,7 +65,7 @@ * the bitmap is inherently random, compression can't reliably help here. * To reduce the size of a filter (to fit to a page), we have to either * accept higher false positive rate (undesirable), or reduce the number - * of distinct items to be stored in the filter. We can't quite the input + * of distinct items to be stored in the filter. We can't alter the input * data, of course, but we may make the BRIN page ranges smaller - instead * of the default 128 pages (1MB) we may build index with 16-page ranges, * or something like that. This does help even for random data sets, as @@ -87,7 +87,8 @@ * not entirely clear how to distrubute the space between those columns. * * The current logic, implemented in brin_bloom_get_ndistinct, attempts to - * make some basic sizing decisions, based on the table ndistinct estimate. + * make some basic sizing decisions, based on the size of BRIN ranges, and + * the maximum number of rows per range. * * * sort vs. hash @@ -200,10 +201,20 @@ typedef struct BloomOptions /* * Allowed range and default value for the false positive range. The exact - * values are somewhat arbitrary. + * values are somewhat arbitrary, but were chosen considering the various + * parameters (size of filter vs. page size, etc.). + * + * The lower the false-positive rate, the more accurate the filter is, but + * it also gets larger - at some point this eliminates the main advantage + * of BRIN indexes, which is the tiny size. At 0.01% the index is about + * 10% of the table (assuming 290 distinct values per 8kB page). + * + * On the other hand, as the false-positive rate increases, larger part of + * the table has to be scanned due to mismatches - at 25% we're probably + * close to sequential scan being cheaper. */ -#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.001 /* 0.1% fp rate */ -#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.1 /* 10% fp rate */ +#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */ +#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */ #define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */ #define BloomGetNDistinctPerRange(opts) \ @@ -302,11 +313,21 @@ bloom_init(int ndistinct, double false_positive_rate) Assert(ndistinct > 0); Assert((false_positive_rate > 0) && (false_positive_rate < 1.0)); - m = ceil((ndistinct * log(false_positive_rate)) / log(1.0 / (pow(2.0, log(2.0))))); + /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */ + m = ceil(- (ndistinct * log(false_positive_rate)) / pow(log(2.0), 2)); /* round m to whole bytes */ m = ((m + 7) / 8) * 8; + /* + * Reject filters that are obviously too large to store on a page. + * + * We do expect the bloom filter to eventually switch to hashing mode, + * and it's bound to be almost perfectly random, so not compressible. + */ + if ((m/8) > BLCKSZ) + elog(ERROR, "the bloom filter is too large (%d > %d)", (m/8), BLCKSZ); + /* * round(log(2.0) * m / ndistinct), but assume round() may not be * available on Windows @@ -315,16 +336,10 @@ bloom_init(int ndistinct, double false_positive_rate) k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k); /* - * Allocate the bloom filter with a minimum size 64B (about 40B in the - * bitmap part). We require space at least for the header. - * - * XXX Maybe the 64B min size is not really needed? + * Allocate the bloom filter (initially it's just a header, we'll make + * it larger as needed). */ - len = Max(offsetof(BloomFilter, data), 64); - - /* Reject filters that are obviously too large to store on a page. */ - if (len > BLCKSZ) - elog(ERROR, "the bloom filter is too large (%zu > %d)", len, BLCKSZ); + len = offsetof(BloomFilter, data); filter = (BloomFilter *) palloc0(len); @@ -686,7 +701,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS) * brin_bloom_get_ndistinct * Determine the ndistinct value used to size bloom filter. * - * Tweak the ndistinct value based on the pagesPerRange value. First, + * Adjust the ndistinct value based on the pagesPerRange value. First, * if it's negative, it's assumed to be relative to maximum number of * tuples in the range (assuming each page gets MaxHeapTuplesPerPage * tuples, which is likely a significant over-estimate). We also clamp @@ -701,6 +716,10 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS) * and compute the expected number of distinct values in a range. But * that may be tricky due to data being sorted in various ways, so it * seems better to rely on the upper estimate. + * + * XXX We might also calculate a better estimate of rows per BRIN range, + * instead of using MaxHeapTuplesPerPage (which probably produces values + * much higher than reality). */ static int brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts) @@ -738,11 +757,6 @@ brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts) return (int) ndistinct; } -static double -brin_bloom_get_fp_rate(BrinDesc *bdesc, BloomOptions *opts) -{ - return BloomGetFalsePositiveRate(opts); -} /* * Examine the given index tuple (which contains partial status of a certain @@ -777,7 +791,7 @@ brin_bloom_add_value(PG_FUNCTION_ARGS) if (column->bv_allnulls) { filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts), - brin_bloom_get_fp_rate(bdesc, opts)); + BloomGetFalsePositiveRate(opts)); column->bv_values[0] = PointerGetDatum(filter); column->bv_allnulls = false; updated = true; @@ -949,7 +963,7 @@ brin_bloom_union(PG_FUNCTION_ARGS) * Cache and return inclusion opclass support procedure * * Return the procedure corresponding to the given function support number - * or null if it is not exists. + * or null if it does not exists. */ static FmgrInfo * bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum) @@ -1050,11 +1064,8 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS) initStringInfo(&str); appendStringInfoChar(&str, '{'); - /* - * XXX not sure the detoasting is necessary (probably not, this - * can only be in an index). - */ - filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_BYTEA_PP(0)); + /* Detoasting not needed (this can only be in an index). */ + filter = (BloomFilter *) PG_GETARG_BYTEA_PP(0); if (BLOOM_IS_HASHED(filter)) { @@ -1063,9 +1074,12 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS) } else { + /* + * XXX Maybe include the sorted/unsorted values? Seems a bit too + * much useless detail (internal hash values). + */ appendStringInfo(&str, "mode: sorted nvalues: %u nsorted: %u", filter->nvalues, filter->nsorted); - /* TODO include the sorted/unsorted values */ } appendStringInfoChar(&str, '}'); diff --git a/src/test/regress/expected/brin_bloom.out b/src/test/regress/expected/brin_bloom.out index 19b866283a..24ea5f6e42 100644 --- a/src/test/regress/expected/brin_bloom.out +++ b/src/test/regress/expected/brin_bloom.out @@ -58,17 +58,17 @@ CREATE INDEX brinidx_bloom ON brintest_bloom USING brin ( ); ERROR: value -1.1 out of bounds for option "n_distinct_per_range" DETAIL: Valid values are between "-1.000000" and "2147483647.000000". --- false_positive_rate must be between 0.001 and 1.0 +-- false_positive_rate must be between 0.0001 and 0.25 CREATE INDEX brinidx_bloom ON brintest_bloom USING brin ( - byteacol bytea_bloom_ops(false_positive_rate = 0.0009) + byteacol bytea_bloom_ops(false_positive_rate = 0.00009) ); -ERROR: value 0.0009 out of bounds for option "false_positive_rate" -DETAIL: Valid values are between "0.001000" and "0.100000". +ERROR: value 0.00009 out of bounds for option "false_positive_rate" +DETAIL: Valid values are between "0.000100" and "0.250000". CREATE INDEX brinidx_bloom ON brintest_bloom USING brin ( - byteacol bytea_bloom_ops(false_positive_rate = 0.11) + byteacol bytea_bloom_ops(false_positive_rate = 0.26) ); -ERROR: value 0.11 out of bounds for option "false_positive_rate" -DETAIL: Valid values are between "0.001000" and "0.100000". +ERROR: value 0.26 out of bounds for option "false_positive_rate" +DETAIL: Valid values are between "0.000100" and "0.250000". CREATE INDEX brinidx_bloom ON brintest_bloom USING brin ( byteacol bytea_bloom_ops, charcol char_bloom_ops, diff --git a/src/test/regress/sql/brin_bloom.sql b/src/test/regress/sql/brin_bloom.sql index 3c2ef56316..d587f3962f 100644 --- a/src/test/regress/sql/brin_bloom.sql +++ b/src/test/regress/sql/brin_bloom.sql @@ -59,12 +59,12 @@ FROM tenk1 ORDER BY thousand, tenthous LIMIT 25; CREATE INDEX brinidx_bloom ON brintest_bloom USING brin ( byteacol bytea_bloom_ops(n_distinct_per_range = -1.1) ); --- false_positive_rate must be between 0.001 and 1.0 +-- false_positive_rate must be between 0.0001 and 0.25 CREATE INDEX brinidx_bloom ON brintest_bloom USING brin ( - byteacol bytea_bloom_ops(false_positive_rate = 0.0009) + byteacol bytea_bloom_ops(false_positive_rate = 0.00009) ); CREATE INDEX brinidx_bloom ON brintest_bloom USING brin ( - byteacol bytea_bloom_ops(false_positive_rate = 0.11) + byteacol bytea_bloom_ops(false_positive_rate = 0.26) ); CREATE INDEX brinidx_bloom ON brintest_bloom USING brin ( -- 2.26.2 --------------CF71AF65F7C337C37C24B045 Content-Type: text/x-patch; charset=UTF-8; name="0006-add-sort_mode-opclass-parameter-20210112.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0006-add-sort_mode-opclass-parameter-20210112.patch" ^ permalink raw reply [nested|flat] 3+ messages in thread
* [PATCH v3] Link to MVCC docs in MERGE docs @ 2022-05-18 16:41 Alvaro Herrera <alvherre@alvh.no-ip.org> 0 siblings, 0 replies; 3+ messages in thread From: Alvaro Herrera @ 2022-05-18 16:41 UTC (permalink / raw) --- doc/src/sgml/mvcc.sgml | 10 +++++----- doc/src/sgml/ref/merge.sgml | 2 ++ 2 files changed, 7 insertions(+), 5 deletions(-) diff --git a/doc/src/sgml/mvcc.sgml b/doc/src/sgml/mvcc.sgml index 341fea524a..1d4d5a62f9 100644 --- a/doc/src/sgml/mvcc.sgml +++ b/doc/src/sgml/mvcc.sgml @@ -425,13 +425,13 @@ COMMIT; <para> <command>MERGE</command> allows the user to specify various combinations of <command>INSERT</command>, <command>UPDATE</command> - or <command>DELETE</command> subcommands. A <command>MERGE</command> + and <command>DELETE</command> subcommands. A <command>MERGE</command> command with both <command>INSERT</command> and <command>UPDATE</command> subcommands looks similar to <command>INSERT</command> with an <literal>ON CONFLICT DO UPDATE</literal> clause but does not guarantee that either <command>INSERT</command> or <command>UPDATE</command> will occur. - If MERGE attempts an <command>UPDATE</command> or + If <command>MERGE</command> attempts an <command>UPDATE</command> or <command>DELETE</command> and the row is concurrently updated but the join condition still passes for the current target and the current source tuple, then <command>MERGE</command> will behave @@ -448,9 +448,9 @@ COMMIT; and execute the first one that succeeds. If <command>MERGE</command> attempts an <command>INSERT</command> and a unique index is present and a duplicate row is concurrently - inserted, then a uniqueness violation is raised. - <command>MERGE</command> does not attempt to avoid the - error by executing an <command>UPDATE</command>. + inserted, then a uniqueness violation error is raised; + <command>MERGE</command> does not attempt to avoid such + errors by evaluating <literal>MATCHED</literal> conditions. </para> <para> diff --git a/doc/src/sgml/ref/merge.sgml b/doc/src/sgml/ref/merge.sgml index f68aa09736..271076bfd5 100644 --- a/doc/src/sgml/ref/merge.sgml +++ b/doc/src/sgml/ref/merge.sgml @@ -539,6 +539,8 @@ MERGE <replaceable class="parameter">total_count</replaceable> </para> <para> + See <xref linkend="xact-read-committed"/> for a thorough explanation on the behavior of + <command>MERGE</command> under concurrency<!-- in READ COMMITTED isolation mode -->. You may also wish to consider using <command>INSERT ... ON CONFLICT</command> as an alternative statement which offers the ability to run an <command>UPDATE</command> if a concurrent <command>INSERT</command> -- 2.30.2 --bsuz7mbwvsdnim3l-- ^ permalink raw reply [nested|flat] 3+ messages in thread
* [PATCH v2] Link to MVCC docs in MERGE docs. @ 2022-05-18 16:41 Alvaro Herrera <alvherre@alvh.no-ip.org> 0 siblings, 0 replies; 3+ messages in thread From: Alvaro Herrera @ 2022-05-18 16:41 UTC (permalink / raw) --- doc/src/sgml/mvcc.sgml | 2 +- doc/src/sgml/ref/merge.sgml | 2 ++ 2 files changed, 3 insertions(+), 1 deletion(-) diff --git a/doc/src/sgml/mvcc.sgml b/doc/src/sgml/mvcc.sgml index 341fea524a..4446e1c484 100644 --- a/doc/src/sgml/mvcc.sgml +++ b/doc/src/sgml/mvcc.sgml @@ -425,7 +425,7 @@ COMMIT; <para> <command>MERGE</command> allows the user to specify various combinations of <command>INSERT</command>, <command>UPDATE</command> - or <command>DELETE</command> subcommands. A <command>MERGE</command> + and <command>DELETE</command> subcommands. A <command>MERGE</command> command with both <command>INSERT</command> and <command>UPDATE</command> subcommands looks similar to <command>INSERT</command> with an <literal>ON CONFLICT DO UPDATE</literal> clause but does not diff --git a/doc/src/sgml/ref/merge.sgml b/doc/src/sgml/ref/merge.sgml index f68aa09736..6b94c863b5 100644 --- a/doc/src/sgml/ref/merge.sgml +++ b/doc/src/sgml/ref/merge.sgml @@ -539,6 +539,8 @@ MERGE <replaceable class="parameter">total_count</replaceable> </para> <para> + See <xref linkend="mvcc"/> for more details on the behavior of + <command>MERGE</command> under concurrency. You may also wish to consider using <command>INSERT ... ON CONFLICT</command> as an alternative statement which offers the ability to run an <command>UPDATE</command> if a concurrent <command>INSERT</command> -- 2.30.2 --2wzyrvwjlnwluax2-- ^ permalink raw reply [nested|flat] 3+ messages in thread
end of thread, other threads:[~2022-05-18 16:41 UTC | newest] Thread overview: 3+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2021-01-12 23:59 [PATCH 5/8] bloom fixes and tweaks Tomas Vondra <tomas.vondra@postgresql.org> 2022-05-18 16:41 [PATCH v3] Link to MVCC docs in MERGE docs Alvaro Herrera <alvherre@alvh.no-ip.org> 2022-05-18 16:41 [PATCH v2] Link to MVCC docs in MERGE docs. Alvaro Herrera <alvherre@alvh.no-ip.org>
This inbox is served by agora; see mirroring instructions for how to clone and mirror all data and code used for this inbox