On Fri, 18 Oct 2024 at 18:17, Peter Geoghegan <p...@bowt.ie> wrote:
>
> On Wed, Oct 16, 2024 at 1:14 PM Peter Geoghegan <p...@bowt.ie> wrote:
> > Attached is v10, which is another revision that's intended only to fix
> > bit rot against the master branch. There are no notable changes to
> > report.
>
> Attached is v11, which is yet another revision whose sole purpose is
> to fix bit rot/make the patch apply cleanly against the master
> branch's tip.
This is a review on v11, not the latest v13. I suspect most comments
still apply, but I haven't verified this.
Re: design
I'm a bit concerned about the additional operations that are being
added to the scan. Before this patch, the amount of work in the
"horizontal" portion of the scan was limited to user-supplied
scankeys, so O(1) even when the index condition is only (f < 7). But,
with this patch, we're adding work for (a=, b=, c=, etc.) for every
tuple in the scan.
As these new "skip array" keys are primarily useful for inter-page
coordination (by determining if we want to start a primitive scan to
skip to a different page and which value range that primitive scan
would search for, or continue on to the next sibling), can't we only
apply the "skip array" portion of the code at the final tuple we
access on this page?
> +++ b/doc/src/sgml/indices.sgml
[...]
> + leading prefix column, but this is usually much less efficient than a scan
> + of an index without the extra prefix column. See <xref
I think this last part is a bit more clear about what should go
without the prefix column when formulated as follows:
[...], but this is usually much less efficient than scanning an index
without the extra prefix column.
> - would be almost useless for queries involving only <literal>y</literal>,
> so it
> - should not be the only index. A combination of the multicolumn index
> - and a separate index on <literal>y</literal> would serve reasonably well.
> For
> + would be less useful for queries involving only <literal>y</literal>.
> Just
> + how useful might depend on how effective the B-Tree index skip scan
> + optimization is; if <literal>x</literal> has no more than several hundred
While this section already defines some things about index scans which
seem btree-specific, I don't think we should add more references to
btree scan internals in a section about bitmaps and bitmap index
scans. While presumably btree is the most commonly used index type,
I'm not sure if we should just assume that's the only one that does
efficient non-prefix searches. GIN, for example, is quite efficient
for searches on non-primary columns, and BRIN's performance also
generally doesn't care about which column of the index is searched.
> +++ b/src/backend/access/nbtree/nbtree.c
[...]
> - slock_t btps_mutex; /* protects above variables,
> btps_arrElems */
> + LWLock btps_lock; /* protects above variables,
> btps_arrElems */
Why is this changed to LWLock, when it's only ever acquired exclusively?
> +btestimateparallelscan(Relation rel, int nkeys, int norderbys)
I notice you're using DatumSerialize. Are there reasons why we
wouldn't want to use heap_fill_tuple, which generally produces much
more compact output?
Also, I think you can limit the space usage to BLCKSZ in total,
because a full index tuple can't be larger than 1/3rd of a block; and
for skip scans we'll only have known equality bounds for a prefix of
attributes available in the index tuples, and a single (?)
index-produced dynamic attribute we want to skip ahead of. So, IIUC,
at most we'll have 2 index tuples' worth of data, or 2/3 BLCKSZ.
Right?
> +++ b/src/backend/access/nbtree/nbtsearch.c
[...]
> + * Skip scan works by having _bt_preprocess_keys cons up = boundary keys
I needed to look up what this 'cons up' thing is, as it wasn't
something that I'd seen before. It also seems used exclusively in
btree code, and only after the array keys patch, so I think it'd be
better in general to use 'construct' here.
> +++ b/src/backend/access/nbtree/nbtcompare.c
The changes here are essentially 6x the same code, but for different
types. What do you think about the attached
0001-Deduplicate[...].patch.txt, which has the same effect but with
only 1 copy of the code checked in?
> +++b/src/backend/access/nbtree/nbtutils.c
[...]
> +_bt_decide_skipatts(IndexScanDesc scan, BTSkipPreproc *skipatts)
Why does this stop processing keys after hitting a row compare?
Doesn't skip scan still apply to any subsequent normal keys? E.g.
"c=1" creates a scan "a=skip, b=skip, c=1", so "(a, b)>(1, 2), c=1"
should IMO still allow a skip scan for a=skip, b=1 to be constructed -
it shouldn't be that we get a much less specific (and potentially,
performant) scan just by adding a rowcompare scankey on early
attributes.
> _bt_preprocess_array_keys
> - output_ikey = 0;
> + numArrayKeyData,
> + numSkipArrayKeys;
I don't think numArrayKeyData/arrayKeyData are good names here, as it
confused me many times reviewing this function's changes. On a scankey
of a=1,b=2 we won't have any array keys, yet this variable is set to
2. Something like numOutputKeys is probably more accurate.
> + /* Create a skip array and scan key where indicated by skipatts */
> + while (numSkipArrayKeys &&
> + attno_skip <= scan->keyData[input_ikey].sk_attno)
> + {
> + Oid opcintype = rel->rd_opcintype[attno_skip - 1];
> + Oid collation = rel->rd_indcollation[attno_skip - 1];
> + Oid eq_op = skipatts[attno_skip - 1].eq_op;
> + RegProcedure cmp_proc;
> +
> + if (!OidIsValid(eq_op))
> + {
> + /* won't skip using this attribute */
> + attno_skip++;
Isn't this branch impossible, given that numSkipArrayKeys is output
from _bt_decide_skipatts, whose output won't contain skipped
attributes which have eq_op=InvalidOid? I'd replace this with
Assert(OidIsValid(eq_op)).
> _bt_rewind_nonrequired_arrays
What types of scan keys can still generate non-required array keys? It
seems to me those are now mostly impossible, as this patch generates
required skip arrays for all attributes that don't yet have an
equality key and which are ahead of any (in)equality keys, except the
case with row compare keys which I already commented on above.
> utils/skipsupport.[ch]
I'm not sure why this is included in utils - isn't this exclusively
used in access/nbtree/*?
> +++ b/src/include/access/nbtree.h
BTArrayKeyInfo explodes in size, from 24B to 88B. I think some of that
is necessary, but should it really be that large?
Kind regards,
Matthias van de Meent
Neon (https://neon.tech)
From 37e59d701698e985007236a374448a6cfcb02f18 Mon Sep 17 00:00:00 2001
From: Matthias van de Meent <boekewurm+postg...@gmail.com>
Date: Sun, 20 Oct 2024 15:34:59 +0200
Subject: [PATCH] Deduplicate nbtcompare's scan key support functions
This saves some 150 lines of duplicated trivial functions.
---
src/backend/access/nbtree/nbtcompare.c | 357 ++++++-------------------
src/include/c.h | 1 +
2 files changed, 86 insertions(+), 272 deletions(-)
diff --git a/src/backend/access/nbtree/nbtcompare.c
b/src/backend/access/nbtree/nbtcompare.c
index 26ebbf776a..e6af77aae1 100644
--- a/src/backend/access/nbtree/nbtcompare.c
+++ b/src/backend/access/nbtree/nbtcompare.c
@@ -69,6 +69,91 @@
#define A_GREATER_THAN_B 1
#endif
+/*
+ * Macros to implement skip support generically across types
+ *
+ * This reduces code duplication for the 6 types we define compare operators
+ * for in this file: bool, int2, int4, int8, oid, and "char".
+ */
+
+#define decrement_fnname(typname) CppConcat(typname, _decrement)
+#define increment_fnname(typname) CppConcat(typname, _increment)
+#define sksup_fnname(typname) CppConcat3(bt, typname, skipsupport)
+
+#define discrete_type_decrement_impl(typ, typname, datname, minvalue) \
+static Datum \
+decrement_fnname(typname)(Relation rel, Datum existing, bool *underflow) \
+{ \
+ typ t_existing = CppConcat(DatumGet, datname)(existing); \
+\
+ if (t_existing == minvalue) \
+ { \
+ /* return value is undefined */ \
+ *underflow = true; \
+ return (Datum) 0; \
+ } \
+ \
+ *underflow = false; \
+ return CppConcat(datname, GetDatum)(t_existing - 1); \
+}
+
+#define discrete_type_increment_impl(typ, typname, datname, maxvalue) \
+static Datum \
+increment_fnname(typname)(Relation rel, Datum existing, bool *overflow) \
+{ \
+ typ t_existing = CppConcat(DatumGet, datname)(existing); \
+\
+ if (t_existing == maxvalue) \
+ { \
+ /* return value is undefined */ \
+ *overflow = true; \
+ return (Datum) 0; \
+ } \
+ \
+ *overflow = false; \
+ return CppConcat(datname, GetDatum)(t_existing + 1); \
+}
+
+#define discrete_type_skipsupport(typ, typname, datname, minvalue, maxvalue) \
+Datum \
+sksup_fnname(typname)(PG_FUNCTION_ARGS) \
+{ \
+ SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0); \
+\
+ sksup->decrement = decrement_fnname(typname); \
+ sksup->increment = increment_fnname(typname); \
+ sksup->low_elem = CppConcat(datname, GetDatum)(minvalue); \
+ sksup->high_elem = CppConcat(datname, GetDatum)(maxvalue); \
+\
+ PG_RETURN_VOID(); \
+}
+
+/* Actually generate the functions */
+#define impl_discrete_type_sksup(typ, typname, datumname, minvalue, maxvalue) \
+ discrete_type_decrement_impl(typ, typname, datumname, minvalue) \
+ discrete_type_increment_impl(typ, typname, datumname, minvalue) \
+ discrete_type_skipsupport(typ, typname, datumname, minvalue, maxvalue)
+
+/* Implement for various types */
+impl_discrete_type_sksup(int16, int2, Int16, PG_INT16_MIN, PG_INT16_MAX)
+impl_discrete_type_sksup(int32, int4, Int32, PG_INT32_MIN, PG_INT32_MAX)
+impl_discrete_type_sksup(int64, int8, Int64, PG_INT64_MIN, PG_INT64_MAX)
+impl_discrete_type_sksup(Oid, oid, ObjectId, InvalidOid, OID_MAX)
+impl_discrete_type_sksup(uint8, char, UInt8, 0, PG_UINT8_MAX)
+
+/*
+ * If bool is a #define (e.g. on _Bool), the macro substitution will fail,
+ * so we substitute the #define with a true typedef here, so that macro
+ * expansion will use bool instead of e.g. _Bool in the function names.
+ */
+#ifdef bool
+typedef bool substitute_bool;
+#undef bool
+typedef substitute_bool bool;
+#endif
+
+impl_discrete_type_sksup(bool, bool, Bool, false, true)
+
Datum
btboolcmp(PG_FUNCTION_ARGS)
@@ -79,51 +164,6 @@ btboolcmp(PG_FUNCTION_ARGS)
PG_RETURN_INT32((int32) a - (int32) b);
}
-static Datum
-bool_decrement(Relation rel, Datum existing, bool *underflow)
-{
- bool bexisting = DatumGetBool(existing);
-
- if (bexisting == false)
- {
- /* return value is undefined */
- *underflow = true;
- return (Datum) 0;
- }
-
- *underflow = false;
- return BoolGetDatum(bexisting - 1);
-}
-
-static Datum
-bool_increment(Relation rel, Datum existing, bool *overflow)
-{
- bool bexisting = DatumGetBool(existing);
-
- if (bexisting == true)
- {
- /* return value is undefined */
- *overflow = true;
- return (Datum) 0;
- }
-
- *overflow = false;
- return BoolGetDatum(bexisting + 1);
-}
-
-Datum
-btboolskipsupport(PG_FUNCTION_ARGS)
-{
- SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
-
- sksup->decrement = bool_decrement;
- sksup->increment = bool_increment;
- sksup->low_elem = BoolGetDatum(false);
- sksup->high_elem = BoolGetDatum(true);
-
- PG_RETURN_VOID();
-}
-
Datum
btint2cmp(PG_FUNCTION_ARGS)
{
@@ -151,51 +191,6 @@ btint2sortsupport(PG_FUNCTION_ARGS)
PG_RETURN_VOID();
}
-static Datum
-int2_decrement(Relation rel, Datum existing, bool *underflow)
-{
- int16 iexisting = DatumGetInt16(existing);
-
- if (iexisting == PG_INT16_MIN)
- {
- /* return value is undefined */
- *underflow = true;
- return (Datum) 0;
- }
-
- *underflow = false;
- return Int16GetDatum(iexisting - 1);
-}
-
-static Datum
-int2_increment(Relation rel, Datum existing, bool *overflow)
-{
- int16 iexisting = DatumGetInt16(existing);
-
- if (iexisting == PG_INT16_MAX)
- {
- /* return value is undefined */
- *overflow = true;
- return (Datum) 0;
- }
-
- *overflow = false;
- return Int16GetDatum(iexisting + 1);
-}
-
-Datum
-btint2skipsupport(PG_FUNCTION_ARGS)
-{
- SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
-
- sksup->decrement = int2_decrement;
- sksup->increment = int2_increment;
- sksup->low_elem = Int16GetDatum(PG_INT16_MIN);
- sksup->high_elem = Int16GetDatum(PG_INT16_MAX);
-
- PG_RETURN_VOID();
-}
-
Datum
btint4cmp(PG_FUNCTION_ARGS)
{
@@ -219,51 +214,6 @@ btint4sortsupport(PG_FUNCTION_ARGS)
PG_RETURN_VOID();
}
-static Datum
-int4_decrement(Relation rel, Datum existing, bool *underflow)
-{
- int32 iexisting = DatumGetInt32(existing);
-
- if (iexisting == PG_INT32_MIN)
- {
- /* return value is undefined */
- *underflow = true;
- return (Datum) 0;
- }
-
- *underflow = false;
- return Int32GetDatum(iexisting - 1);
-}
-
-static Datum
-int4_increment(Relation rel, Datum existing, bool *overflow)
-{
- int32 iexisting = DatumGetInt32(existing);
-
- if (iexisting == PG_INT32_MAX)
- {
- /* return value is undefined */
- *overflow = true;
- return (Datum) 0;
- }
-
- *overflow = false;
- return Int32GetDatum(iexisting + 1);
-}
-
-Datum
-btint4skipsupport(PG_FUNCTION_ARGS)
-{
- SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
-
- sksup->decrement = int4_decrement;
- sksup->increment = int4_increment;
- sksup->low_elem = Int32GetDatum(PG_INT32_MIN);
- sksup->high_elem = Int32GetDatum(PG_INT32_MAX);
-
- PG_RETURN_VOID();
-}
-
Datum
btint8cmp(PG_FUNCTION_ARGS)
{
@@ -307,51 +257,6 @@ btint8sortsupport(PG_FUNCTION_ARGS)
PG_RETURN_VOID();
}
-static Datum
-int8_decrement(Relation rel, Datum existing, bool *underflow)
-{
- int64 iexisting = DatumGetInt64(existing);
-
- if (iexisting == PG_INT64_MIN)
- {
- /* return value is undefined */
- *underflow = true;
- return (Datum) 0;
- }
-
- *underflow = false;
- return Int64GetDatum(iexisting - 1);
-}
-
-static Datum
-int8_increment(Relation rel, Datum existing, bool *overflow)
-{
- int64 iexisting = DatumGetInt64(existing);
-
- if (iexisting == PG_INT64_MAX)
- {
- /* return value is undefined */
- *overflow = true;
- return (Datum) 0;
- }
-
- *overflow = false;
- return Int64GetDatum(iexisting + 1);
-}
-
-Datum
-btint8skipsupport(PG_FUNCTION_ARGS)
-{
- SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
-
- sksup->decrement = int8_decrement;
- sksup->increment = int8_increment;
- sksup->low_elem = Int64GetDatum(PG_INT64_MIN);
- sksup->high_elem = Int64GetDatum(PG_INT64_MAX);
-
- PG_RETURN_VOID();
-}
-
Datum
btint48cmp(PG_FUNCTION_ARGS)
{
@@ -473,51 +378,6 @@ btoidsortsupport(PG_FUNCTION_ARGS)
PG_RETURN_VOID();
}
-static Datum
-oid_decrement(Relation rel, Datum existing, bool *underflow)
-{
- Oid oexisting = DatumGetObjectId(existing);
-
- if (oexisting == InvalidOid)
- {
- /* return value is undefined */
- *underflow = true;
- return (Datum) 0;
- }
-
- *underflow = false;
- return ObjectIdGetDatum(oexisting - 1);
-}
-
-static Datum
-oid_increment(Relation rel, Datum existing, bool *overflow)
-{
- Oid oexisting = DatumGetObjectId(existing);
-
- if (oexisting == OID_MAX)
- {
- /* return value is undefined */
- *overflow = true;
- return (Datum) 0;
- }
-
- *overflow = false;
- return ObjectIdGetDatum(oexisting + 1);
-}
-
-Datum
-btoidskipsupport(PG_FUNCTION_ARGS)
-{
- SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
-
- sksup->decrement = oid_decrement;
- sksup->increment = oid_increment;
- sksup->low_elem = ObjectIdGetDatum(InvalidOid);
- sksup->high_elem = ObjectIdGetDatum(OID_MAX);
-
- PG_RETURN_VOID();
-}
-
Datum
btoidvectorcmp(PG_FUNCTION_ARGS)
{
@@ -551,50 +411,3 @@ btcharcmp(PG_FUNCTION_ARGS)
/* Be careful to compare chars as unsigned */
PG_RETURN_INT32((int32) ((uint8) a) - (int32) ((uint8) b));
}
-
-static Datum
-char_decrement(Relation rel, Datum existing, bool *underflow)
-{
- uint8 cexisting = UInt8GetDatum(existing);
-
- if (cexisting == 0)
- {
- /* return value is undefined */
- *underflow = true;
- return (Datum) 0;
- }
-
- *underflow = false;
- return CharGetDatum((uint8) cexisting - 1);
-}
-
-static Datum
-char_increment(Relation rel, Datum existing, bool *overflow)
-{
- uint8 cexisting = UInt8GetDatum(existing);
-
- if (cexisting == UCHAR_MAX)
- {
- /* return value is undefined */
- *overflow = true;
- return (Datum) 0;
- }
-
- *overflow = false;
- return CharGetDatum((uint8) cexisting + 1);
-}
-
-Datum
-btcharskipsupport(PG_FUNCTION_ARGS)
-{
- SkipSupport sksup = (SkipSupport) PG_GETARG_POINTER(0);
-
- sksup->decrement = char_decrement;
- sksup->increment = char_increment;
-
- /* btcharcmp compares chars as unsigned */
- sksup->low_elem = UInt8GetDatum(0);
- sksup->high_elem = UInt8GetDatum(UCHAR_MAX);
-
- PG_RETURN_VOID();
-}
diff --git a/src/include/c.h b/src/include/c.h
index 55dec71a6d..cbf6499151 100644
--- a/src/include/c.h
+++ b/src/include/c.h
@@ -329,6 +329,7 @@
#define CppAsString(identifier) #identifier
#define CppAsString2(x) CppAsString(x)
#define CppConcat(x, y) x##y
+#define CppConcat3(x, y, z) x##y##z
/*
* VA_ARGS_NARGS
--
2.46.0
