public inbox for [email protected]
help / color / mirror / Atom feedFrom: Ayush Tiwari <[email protected]>
To: Tom Lane <[email protected]>
Cc: 王跃林 <[email protected]>
Cc: pgsql-bugs <[email protected]>
Cc: 3764353996 <[email protected]>
Subject: Re: Fw:Re: Fw: gbt_var_consistent in contrib/btree_gist/btree_utils_var.c has internal-node type confusion on the <> strategy, bypassing exclusion constraints
Date: Thu, 2 Jul 2026 23:16:04 +0530
Message-ID: <CAJTYsWVus+7hn846A0gMJYk+9uUGZxizk5Herbxb4CmhF3vndQ@mail.gmail.com> (raw)
In-Reply-To: <[email protected]>
References: <AH*AvQCYKhQGVvPWi1GiU4oY.8.1781609375063.Hmail.3020001251@tju.edu.cn>
<CAJTYsWWSx+5-kVaivB_znaQCk3TmHrO4QNNM-CD3AN-oOSmG8w@mail.gmail.com>
<AGoA0AD5KvwQ8G7e6ofMyap6.3.1781760245047.Hmail.3020001251@tju.edu.cn>
<[email protected]>
<CAJTYsWX1C5JLj92QdqEcArWs4XtXPog+yvyb6=X=_cghjXnkYQ@mail.gmail.com>
<[email protected]>
Hi,
On Thu, 2 Jul 2026 at 22:24, Tom Lane <[email protected]> wrote:
> Ayush Tiwari <[email protected]> writes:
> > On Thu, 2 Jul 2026 at 20:08, Tom Lane <[email protected]> wrote:
> >> None of this passes the smell test for me. If it's unsafe to
> >> call the type's f_eq function on a truncated key, how is it
> >> any safer to call the f_cmp function?
>
> > I think the difference is that for bit/varbit f_eq and f_cmp aren't the
> > same kind of function. f_eq is biteq (reads bit_len, does VARSIZE-8),
> > while f_cmp is byteacmp (plain byte-wise, only needs the varlena
> > header).
>
> Oh! You are right, the internal keys are *not* valid bit/varbit
> values, just bytea. The level of non-documentation in this code
> is staggering.
>
> So the actual API contract here is that f_eq etc. are to be used only
> on leaf keys, while f_cmp is to be used only on internal keys. It's
> not too surprising that whoever added NotEqual support didn't know
> that, it being documented nowhere.
>
> It kind of looks actually like there's an expectation that all
> internal keys are effectively bytea's; note the naming of
> gbt_bytea_pf_match, despite the fact that it's applied to all
> types under the purview of btree_utils_var.c.
>
> Anyway, I think part of our work here has got to be to raise the
> level of documentation of this code. I've had it with having
> to reverse-engineer details as fundamental as these.
>
I've added some documentation in code, patch attached.
Please help reviewing if it looks good or should we be adding
something more.
Regards,
Ayush
Attachments:
[application/octet-stream] v2-0001-Fix-btree_gist-strategy-on-internal-index-pages.patch (5.7K, ../CAJTYsWVus+7hn846A0gMJYk+9uUGZxizk5Herbxb4CmhF3vndQ@mail.gmail.com/3-v2-0001-Fix-btree_gist-strategy-on-internal-index-pages.patch)
download | inline diff:
From 15d79c377f3b182a3fb12fab840cd37921163113 Mon Sep 17 00:00:00 2001
From: Ayush Tiwari <[email protected]>
Date: Thu, 2 Jul 2026 23:09:23 +0530
Subject: [PATCH v2] Fix btree_gist <> strategy on internal index pages
gbt_var_consistent() handled the <> (BtreeGistNotEqual) strategy without
distinguishing leaf from internal pages, unlike every other strategy.
Internal keys are lossy, truncated prefixes, and for bit/varbit the
leaf-to-node transform drops the VarBit length header, so such a key is
not a valid value of the indexed type -- it is effectively just a bytea.
Passing it to the type's equality function is a type confusion. For
bit/varbit it reaches bit_cmp(), where VARBITBYTES() computes VARSIZE - 8;
a key with VARSIZE < 8 yields a negative length that, passed to memcmp()
as size_t, becomes huge and reads out of bounds (eventually crashing the
backend).
Make the <> branch distinguish leaf and internal pages: on a leaf, negate
the equality test against the stored value; on an internal page, recurse
unconditionally (a non-equal value can always exist below). The fix is
in the shared gbt_var_consistent() and so covers every variable-length
type.
Also document the leaf-vs-internal key contract in gbt_var_consistent():
the type-specific callbacks (f_eq/f_lt/...) may be used only on leaf
keys, while internal keys are effectively bytea and must be compared
only with f_cmp. Add a regression test.
---
contrib/btree_gist/btree_utils_var.c | 30 ++++++++++++++++++++---
contrib/btree_gist/expected/not_equal.out | 24 ++++++++++++++++++
contrib/btree_gist/sql/not_equal.sql | 18 ++++++++++++++
3 files changed, 69 insertions(+), 3 deletions(-)
diff --git a/contrib/btree_gist/btree_utils_var.c b/contrib/btree_gist/btree_utils_var.c
index 25c3bbe8eac..8becf68f31c 100644
--- a/contrib/btree_gist/btree_utils_var.c
+++ b/contrib/btree_gist/btree_utils_var.c
@@ -558,7 +558,23 @@ gbt_var_picksplit(const GistEntryVector *entryvec, GIST_SPLITVEC *v,
/*
- * The GiST consistent method
+ * The GiST consistent method.
+ *
+ * The stored key has two forms, with different rules:
+ *
+ * - Leaf keys (key->lower == key->upper) are genuine values of the indexed
+ * type, so the type-specific callbacks (f_eq/f_lt/f_le/f_gt/f_ge) may be
+ * used on them.
+ *
+ * - Internal keys are a lossy [lower, upper] range whose bounds are truncated
+ * prefixes (see gbt_var_node_truncate). They are effectively just bytea,
+ * not necessarily valid values of the indexed type -- e.g. for bit/varbit
+ * the leaf-to-node transform drops the length header. So only f_cmp (a raw
+ * byte compare) and the prefix-match helpers may be applied to internal
+ * keys; the type-specific f_eq/f_lt/... callbacks must not be.
+ *
+ * The leaf-page tests use the mirror callback with swapped operands (e.g.
+ * f_gt(query, lower) means "lower < query"), which is why they look reversed.
*/
bool
gbt_var_consistent(GBT_VARKEY_R *key,
@@ -611,8 +627,16 @@ gbt_var_consistent(GBT_VARKEY_R *key,
|| gbt_var_node_pf_match(key, query, tinfo);
break;
case BtreeGistNotEqualStrategyNumber:
- retval = !(tinfo->f_eq(query, key->lower, collation, flinfo) &&
- tinfo->f_eq(query, key->upper, collation, flinfo));
+
+ /*
+ * On a leaf, "not equal" is the negation of equality. On an
+ * internal page we must not call f_eq (see above); a non-equal
+ * value can always exist below, so just recurse.
+ */
+ if (is_leaf)
+ retval = !tinfo->f_eq(query, key->lower, collation, flinfo);
+ else
+ retval = true;
break;
default:
retval = false;
diff --git a/contrib/btree_gist/expected/not_equal.out b/contrib/btree_gist/expected/not_equal.out
index 85b1e868a87..922950e0c2f 100644
--- a/contrib/btree_gist/expected/not_equal.out
+++ b/contrib/btree_gist/expected/not_equal.out
@@ -39,3 +39,27 @@ INSERT INTO zoo VALUES(123, 'lion');
ERROR: conflicting key value violates exclusion constraint "zoo_cage_animal_excl"
DETAIL: Key (cage, animal)=(123, lion) conflicts with existing key (cage, animal)=(123, zebra).
INSERT INTO zoo VALUES(124, 'lion');
+-- A <> search must descend internal pages instead of comparing the query to a
+-- truncated internal key. Use a multi-level index and check it agrees with seq scan.
+CREATE TABLE bitne (a bit(8));
+INSERT INTO bitne SELECT (g % 256)::bit(8) FROM generate_series(1, 20000) g;
+CREATE INDEX bitne_idx ON bitne USING gist (a);
+SET enable_seqscan to on;
+SET enable_indexscan to off;
+SET enable_bitmapscan to off;
+SELECT count(*) FROM bitne WHERE a <> B'00000000';
+ count
+-------
+ 19922
+(1 row)
+
+SET enable_seqscan to off;
+SET enable_indexscan to on;
+SET enable_bitmapscan to on;
+SELECT count(*) FROM bitne WHERE a <> B'00000000';
+ count
+-------
+ 19922
+(1 row)
+
+DROP TABLE bitne;
diff --git a/contrib/btree_gist/sql/not_equal.sql b/contrib/btree_gist/sql/not_equal.sql
index 6dfac5d0aae..ecb135f47d2 100644
--- a/contrib/btree_gist/sql/not_equal.sql
+++ b/contrib/btree_gist/sql/not_equal.sql
@@ -34,3 +34,21 @@ INSERT INTO zoo VALUES(123, 'zebra');
INSERT INTO zoo VALUES(123, 'zebra');
INSERT INTO zoo VALUES(123, 'lion');
INSERT INTO zoo VALUES(124, 'lion');
+
+-- A <> search must descend internal pages instead of comparing the query to a
+-- truncated internal key. Use a multi-level index and check it agrees with seq scan.
+CREATE TABLE bitne (a bit(8));
+INSERT INTO bitne SELECT (g % 256)::bit(8) FROM generate_series(1, 20000) g;
+CREATE INDEX bitne_idx ON bitne USING gist (a);
+
+SET enable_seqscan to on;
+SET enable_indexscan to off;
+SET enable_bitmapscan to off;
+SELECT count(*) FROM bitne WHERE a <> B'00000000';
+
+SET enable_seqscan to off;
+SET enable_indexscan to on;
+SET enable_bitmapscan to on;
+SELECT count(*) FROM bitne WHERE a <> B'00000000';
+
+DROP TABLE bitne;
--
2.34.1
view thread (13+ 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], [email protected], [email protected], [email protected]
Subject: Re: Fw:Re: Fw: gbt_var_consistent in contrib/btree_gist/btree_utils_var.c has internal-node type confusion on the <> strategy, bypassing exclusion constraints
In-Reply-To: <CAJTYsWVus+7hn846A0gMJYk+9uUGZxizk5Herbxb4CmhF3vndQ@mail.gmail.com>
* 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