public inbox for [email protected]
help / color / mirror / Atom feedFrom: Peter Geoghegan <[email protected]>
To: PostgreSQL Hackers <[email protected]>
Cc: Tom Lane <[email protected]>
Cc: Tomas Vondra <[email protected]>
Cc: Jeff Davis <[email protected]>
Cc: benoit <[email protected]>
Subject: Optimizing nbtree ScalarArrayOp execution, allowing multi-column ordered scans, skip scan
Date: Mon, 24 Jul 2023 18:33:52 -0700
Message-ID: <CAH2-Wz=ksvN_sjcnD1+Bt-WtifRA5ok48aDYnq3pkKhxgMQpcw@mail.gmail.com> (raw)
I've been working on a variety of improvements to nbtree's native
ScalarArrayOpExpr execution. This builds on Tom's work in commit
9e8da0f7.
Attached patch is still at the prototype stage. I'm posting it as v1 a
little earlier than I usually would because there has been much back
and forth about it on a couple of other threads involving Tomas Vondra
and Jeff Davis -- seems like it would be easier to discuss with
working code available.
The patch adds two closely related enhancements to ScalarArrayOp
execution by nbtree:
1. Execution of quals with ScalarArrayOpExpr clauses during nbtree
index scans (for equality-strategy SK_SEARCHARRAY scan keys) can now
"advance the scan's array keys locally", which sometimes avoids
significant amounts of unneeded pinning/locking of the same set of
index pages.
SAOP index scans become capable of eliding primitive index scans for
the next set of array keys in line in cases where it isn't truly
necessary to descend the B-Tree again. Index scans are now capable of
"sticking with the existing leaf page for now" when it is determined
that the end of the current set of array keys is physically close to
the start of the next set of array keys (the next set in line to be
materialized by the _bt_advance_array_keys state machine). This is
often possible.
Naturally, we still prefer to advance the array keys in the
traditional way ("globally") much of the time. That means we'll
perform another _bt_first/_bt_search descent of the index, starting a
new primitive index scan. Whether we try to skip pages on the leaf
level or stick with the current primitive index scan (by advancing
array keys locally) is likely to vary a great deal. Even during the
same index scan. Everything is decided dynamically, which is the only
approach that really makes sense.
This optimization can significantly lower the number of buffers pinned
and locked in cases with significant locality, and/or with many array
keys with no matches. The savings (when measured in buffers
pined/locked) can be as high as 10x, 100x, or even more. Benchmarking
has shown that transaction throughput for variants of "pgbench -S"
designed to stress the implementation (hundreds of array constants)
under concurrent load can have up to 5.5x higher transaction
throughput with the patch. Less extreme cases (10 array constants,
spaced apart) see about a 20% improvement in throughput. There are
similar improvements to latency for the patch, in each case.
2. The optimizer now produces index paths with multiple SAOP clauses
(or other clauses we can safely treat as "equality constraints'') on
each of the leading columns from a composite index -- all while
preserving index ordering/useful pathkeys in most cases.
The nbtree work from item 1 is useful even with the simplest IN() list
query involving a scan of a single column index. Obviously, it's very
inefficient for the nbtree code to use 100 primitive index scans when
1 is sufficient. But that's not really why I'm pursuing this project.
My real goal is to implement (or to enable the implementation of) a
whole family of useful techniques for multi-column indexes. I call
these "MDAM techniques", after the 1995 paper "Efficient Search of
Multidimensional B-Trees" [1][2]-- MDAM is short for "multidimensional
access method". In the context of the paper, "dimension" refers to
dimensions in a decision support system.
The most compelling cases for the patch all involve multiple index
columns with multiple SAOP clauses (especially where each column
represents a separate "dimension", in the DSS sense). It's important
that index sort be preserved whenever possible, too. Sometimes this is
directly useful (e.g., because the query has an ORDER BY), but it's
always indirectly needed, on the nbtree side (when the optimizations
are applicable at all). The new nbtree code now has special
requirements surrounding SAOP search type scan keys with composite
indexes. These requirements make changes in the optimizer all but
essential.
Index order
===========
As I said, there are cases where preserving index order is immediately
and obviously useful, in and of itself. Let's start there.
Here's a test case that you can run against the regression test database:
pg@regression:5432 =# create index order_by_saop on tenk1(two,four,twenty);
CREATE INDEX
pg@regression:5432 =# EXPLAIN (ANALYZE, BUFFERS)
select ctid, thousand from tenk1
where two in (0,1) and four in (1,2) and twenty in (1,2)
order by two, four, twenty limit 20;
With the patch, this query gets 13 buffer hits. On the master branch,
it gets 1377 buffer hits -- which exceeds the number you'll get from a
sequential scan by about 4x. No coaxing was required to get the
planner to produce this plan on the master branch. Almost all of the
savings shown here are related to heap page buffer hits -- the nbtree
changes don't directly help in this particular example (strictly
speaking, you only need the optimizer changes to get this result).
Obviously, the immediate reason why the patch wins by so much is
because it produces a plan that allows the LIMIT to terminate the scan
far sooner. Benoit Tigeot (CC'd) happened to run into this issue
organically -- that was also due to heap hits, a LIMIT, and so on. As
luck would have it, I stumbled upon his problem report (in the
Postgres slack channel) while I was working on this patch. He produced
a fairly complete test case, which was helpful [3]. This example is
more or less just a distillation of his test case, designed to be easy
for a Postgres hacker to try out for themselves.
There are also variants of this query where a LIMIT isn't the crucial
factor, and where index page hits are the problem. This query uses an
index-only scan, both on master and with the patch (same index as
before):
select count(*), two, four, twenty
from tenk1
where two in (0, 1) and four in (1, 2, 3, 4) and
twenty in (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,14,15)
group by two, four, twenty
order by two, four, twenty;
The patch gets 18 buffer hits for this query. That outcome makes
intuitive sense, since this query is highly unselective -- it's
approaching the selectivity of the query "select count(*) from tenk1".
The simple count(*) query gets 19 buffer hits for its own index-only
scan, confirming that the patch managed to skip only one or two leaf
pages in the complicated "group by" variant of the count(*) query.
Overall, the GroupAggregate plan used by the patch is slower than the
simple count(*) case (despite touching fewer pages). But both plans
have *approximately* the same execution cost, which makes sense, since
they both have very similar selectivities.
The master branch gets 245 buffer hits for the same group by query.
This is almost as many hits as a sequential scan would require -- even
though there are precisely zero heap accesses needed by the underlying
index-only scan. As with the first example, no planner coaxing was
required to get this outcome on master. It is inherently very
difficult to predict how selective a query like this will be using
conventional statistics. But that's not actually the problem in this
example -- the planner gets that part right, on this occasion. The
real problem is that there is a multiplicative factor to worry about
on master, when executing multiple SAOPs. That makes it almost
impossible to predict the number of pages we'll pin. While with the
patch, scans with multiple SAOPs are often fairly similar to scans
that happen to just have one on the leading column.
With the patch, it is simply impossible for an SAOP index scan to
visit any single leaf page more than once. Just like a conventional
index scan. Whereas right now, on master, using more than one SAOP
clause for a multi column index seems to me to be a wildly risky
proposition. You can easily have cases that work just fine on master,
while only slight variations of the same query see costs explode
(especially likely with a LIMIT). ISTM that there is significant value
in knowing for sure in having a pretty accurate idea of the worst case
in the planner.
Giving nbtree the ability to skip or not skip dynamically, based on
actual conditions in the index (not on statistics), seems like it has
a lot of potential as a way of improving performance *stability*.
Personally I'm most interested in this aspect of the project.
Note: we can visit internal pages more than once, but that seems to
make a negligible difference to the overall cost profile of scans. Our
policy is to not charge an I/O cost for those pages. Plus, the number
of internal page access is dramatically reduced (it's just not
guaranteed that there won't be any repeat accesses for internal pages,
is all).
Note also: there are hard-to-pin-down interactions between the
immediate problem on the nbtree side, and the use of filter quals
rather than true index quals, where the use of index quals is possible
in principle. Some problematic cases see excessive amounts of heap
page hits only (as with my first example query). Other problematic
cases see excessive amounts of index page hits, with little to no
impact on heap page hits at all (as with my second example query).
Some combination of the two is also possible.
Safety
======
As mentioned already, the ability to "advance the current set of array
keys locally" during a scan (the nbtree work in item 1) actually
relies the optimizer work in item 2 -- it's not just a question of
unlocking the potential of the nbtree work. Now I'll discuss those
aspects in a bit more detail.
Without the optimizer work, nbtree will produce wrong answers to
queries, in a way that resembles the complaint addressed by historical
bugfix commit 807a40c5. This incorrect behavior (if the optimizer were
to permit it) would only be seen when there are multiple
arrays/columns, and an inequality on a leading column -- just like
with that historical bug. (It works both ways, though -- the nbtree
changes also make the optimizer changes safe by limiting the worst
case, which would otherwise be too much of a risk to countenance. You
can't separate one from the other.)
The primary change on the optimizer side is the addition of logic to
differentiate between the following two cases when building an index
path in indxpath.c:
* Unsafe: Cases where it's fundamentally unsafe to treat
multi-column-with-SAOP-clause index paths as returning tuples in a
useful sort order.
For example, the test case committed as part of that bugfix involves
an inequality, so it continues to be treated as unsafe.
* Safe: Cases where (at least in theory) bugfix commit 807a40c5 went
further than it really had to.
Those cases get to use the optimization, and usually get to have
useful path keys.
My optimizer changes are very kludgey. I came up with various ad-hoc
rules to distinguish between the safe and unsafe cases, without ever
really placing those changes into some kind of larger framework. That
was enough to validate the general approach in nbtree, but it
certainly has problems -- glaring problems. The biggest problem of all
may be my whole "safe vs unsafe" framing itself. I know that many of
the ostensibly unsafe cases are in fact safe (with the right
infrastructure in place), because the MDAM paper says just that. The
optimizer can't support inequalities right now, but the paper
describes how to support "NOT IN( )" lists -- clearly an inequality!
The current ad-hoc rules are at best incomplete, and at worst are
addressing the problem in fundamentally the wrong way.
CNF -> DNF conversion
=====================
Like many great papers, the MDAM paper takes one core idea, and finds
ways to leverage it to the hilt. Here the core idea is to take
predicates in conjunctive normal form (an "AND of ORs"), and convert
them into disjunctive normal form (an "OR of ANDs"). DNF quals are
logically equivalent to CNF quals, but ideally suited to SAOP-array
style processing by an ordered B-Tree index scan -- they reduce
everything to a series of non-overlapping primitive index scans, that
can be processed in keyspace order. We already do this today in the
case of SAOPs, in effect. The nbtree "next array keys" state machine
already materializes values that can be seen as MDAM style DNF single
value predicates. The state machine works by outputting the cartesian
product of each array as a multi-column index is scanned, but that
could be taken a lot further in the future. We can use essentially the
same kind of state machine to do everything described in the paper --
ultimately, it just needs to output a list of disjuncts, like the DNF
clauses that the paper shows in "Table 3".
In theory, anything can be supported via a sufficiently complete CNF
-> DNF conversion framework. There will likely always be the potential
for unsafe/unsupported clauses and/or types in an extensible system
like Postgres, though. So we will probably need to retain some notion
of safety. It seems like more of a job for nbtree preprocessing (or
some suitably index-AM-agnostic version of the same idea) than the
optimizer, in any case. But that's not entirely true, either (that
would be far too easy).
The optimizer still needs to optimize. It can't very well do that
without having some kind of advanced notice of what is and is not
supported by the index AM. And, the index AM cannot just unilaterally
decide that index quals actually should be treated as filter/qpquals,
after all -- it doesn't get a veto. So there is a mutual dependency
that needs to be resolved. I suspect that there needs to be a two way
conversation between the optimizer and nbtree code to break the
dependency -- a callback that does some of the preprocessing work
during planning. Tom said something along the same lines in passing,
when discussing the MDAM paper last year [2]. Much work remains here.
Skip Scan
=========
MDAM encompasses something that people tend to call "skip scan" --
terminology with a great deal of baggage. These days I prefer to call
it "filling in missing key predicates", per the paper. That's much
more descriptive, and makes it less likely that people will conflate
the techniques with InnoDB style "loose Index scans" -- the latter is
a much more specialized/targeted optimization. (I now believe that
these are very different things, though I was thrown off by the
superficial similarities for a long time. It's pretty confusing.)
I see this work as a key enabler of "filling in missing key
predicates". MDAM describes how to implement this technique by
applying the same principles that it applies everywhere else: it
proposes a scheme that converts predicates from CNF to DNF. With just
a little extra logic required to do index probes to feed the
DNF-generating state machine, on demand.
More concretely, in Postgres terms: skip scan can be implemented by
inventing a new placeholder clause that can be composed alongside
ScalarArrayOpExprs, in the same way that multiple ScalarArrayOpExprs
can be composed together in the patch already. I'm thinking of a type
of clause that makes the nbtree code materialize a set of "array keys"
for a SK_SEARCHARRAY scan key dynamically, via ad-hoc index probes
(perhaps static approaches would be better for types like boolean,
which the paper contemplates). It should be possible to teach the
_bt_advance_array_keys state machine to generate those values in
approximately the same fashion as it already does for
ScalarArrayOpExprs -- and, it shouldn't be too hard to do it in a
localized fashion, allowing everything else to continue to work in the
same way without any special concern. This separation of concerns is a
nice consequence of the way that the MDAM design really leverages
preprocessing/DNF for everything.
Both types of clauses can be treated as part of a general class of
ScalarArrayOpExpr-like clauses. Making the rules around
"composability" simple will be important.
Although skip scan gets a lot of attention, it's not necessarily the
most compelling MDAM technique. It's also not especially challenging
to implement on top of everything else. It really isn't that special.
Right now I'm focussed on the big picture, in any case. I want to
emphasize the very general nature of these techniques. Although I'm
focussed on SOAPs in the short term, many queries that don't make use
of SAOPs should ultimately see similar benefits. For example, the
paper also describes transformations that apply to BETWEEN/range
predicates. We might end up needing a third type of expression for
those. They're all just DNF single value predicates, under the hood.
Thoughts?
[1] http://vldb.org/conf/1995/P710.PDF
[2] https://www.postgresql.org/message-id/[email protected]
[3] https://gist.github.com/benoittgt/ab72dc4cfedea2a0c6a5ee809d16e04d
--
Peter Geoghegan
Attachments:
[application/octet-stream] v1-0001-Enhance-nbtree-ScalarArrayOp-execution.patch (56.2K, ../CAH2-Wz=ksvN_sjcnD1+Bt-WtifRA5ok48aDYnq3pkKhxgMQpcw@mail.gmail.com/2-v1-0001-Enhance-nbtree-ScalarArrayOp-execution.patch)
download | inline diff:
From d4459fe464d41bdd3fa5e81b310b095560f4f5b0 Mon Sep 17 00:00:00 2001
From: Peter Geoghegan <[email protected]>
Date: Sat, 17 Jun 2023 17:03:36 -0700
Subject: [PATCH v1] Enhance nbtree ScalarArrayOp execution.
Teach nbtree to avoid primitive index when executing a scan with
ScalarArrayOp keys.
---
src/include/access/nbtree.h | 46 +-
src/backend/access/nbtree/nbtree.c | 21 +-
src/backend/access/nbtree/nbtsearch.c | 85 +++-
src/backend/access/nbtree/nbtutils.c | 589 +++++++++++++++++++++++++-
src/backend/optimizer/path/indxpath.c | 206 +++++++--
src/backend/utils/adt/selfuncs.c | 56 ++-
6 files changed, 919 insertions(+), 84 deletions(-)
diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h
index 8891fa797..5935dbc86 100644
--- a/src/include/access/nbtree.h
+++ b/src/include/access/nbtree.h
@@ -1034,6 +1034,42 @@ typedef struct BTArrayKeyInfo
Datum *elem_values; /* array of num_elems Datums */
} BTArrayKeyInfo;
+/*
+ * _bt_readpage state used across _bt_checkkeys calls for a page
+ */
+typedef struct BTReadPageState
+{
+ /*
+ * Input parameters set by _bt_readpage, for _bt_checkkeys.
+ *
+ * dir: scan direction
+ *
+ * highkey: page high key
+ *
+ * SK_SEARCHARRAY forward scans are required to set the page high key up
+ * front.
+ */
+ ScanDirection dir;
+ IndexTuple highkey;
+
+ /*
+ * Output parameters set by _bt_checkkeys, for _bt_readpage.
+ *
+ * continuescan: Is there a need to continue the scan beyond this tuple?
+ */
+ bool continuescan;
+
+ /*
+ * Private _bt_checkkeys state, describes caller's page.
+ *
+ * match_for_cur_array_keys: _bt_checkkeys returned true once or more?
+ *
+ * highkeychecked: Current set of array keys checked against high key?
+ */
+ bool match_for_cur_array_keys;
+ bool highkeychecked;
+} BTReadPageState;
+
typedef struct BTScanOpaqueData
{
/* these fields are set by _bt_preprocess_keys(): */
@@ -1047,7 +1083,9 @@ typedef struct BTScanOpaqueData
* there are any unsatisfiable array keys) */
int arrayKeyCount; /* count indicating number of array scan keys
* processed */
+ bool arrayKeysStarted; /* Scan still processing array keys? */
BTArrayKeyInfo *arrayKeys; /* info about each equality-type array key */
+ BTScanInsert arrayPoskey; /* initial positioning insertion scan key */
MemoryContext arrayContext; /* scan-lifespan context for array data */
/* info about killed items if any (killedItems is NULL if never used) */
@@ -1253,8 +1291,12 @@ extern bool _bt_advance_array_keys(IndexScanDesc scan, ScanDirection dir);
extern void _bt_mark_array_keys(IndexScanDesc scan);
extern void _bt_restore_array_keys(IndexScanDesc scan);
extern void _bt_preprocess_keys(IndexScanDesc scan);
-extern bool _bt_checkkeys(IndexScanDesc scan, IndexTuple tuple,
- int tupnatts, ScanDirection dir, bool *continuescan);
+extern void _bt_array_keys_save_scankeys(IndexScanDesc scan,
+ BTScanInsert inskey);
+extern bool _bt_checkkeys(IndexScanDesc scan, IndexTuple tuple, bool final,
+ BTReadPageState *pstate);
+extern void _bt_checkfinalkeys(IndexScanDesc scan, BTReadPageState *pstate);
+extern bool _bt_nocheckkeys(IndexScanDesc scan, ScanDirection dir);
extern void _bt_killitems(IndexScanDesc scan);
extern BTCycleId _bt_vacuum_cycleid(Relation rel);
extern BTCycleId _bt_start_vacuum(Relation rel);
diff --git a/src/backend/access/nbtree/nbtree.c b/src/backend/access/nbtree/nbtree.c
index 4553aaee5..7ccd5f3f3 100644
--- a/src/backend/access/nbtree/nbtree.c
+++ b/src/backend/access/nbtree/nbtree.c
@@ -363,7 +363,9 @@ btbeginscan(Relation rel, int nkeys, int norderbys)
so->arrayKeyData = NULL; /* assume no array keys for now */
so->numArrayKeys = 0;
+ so->arrayKeysStarted = false;
so->arrayKeys = NULL;
+ so->arrayPoskey = NULL;
so->arrayContext = NULL;
so->killedItems = NULL; /* until needed */
@@ -404,6 +406,7 @@ btrescan(IndexScanDesc scan, ScanKey scankey, int nscankeys,
so->markItemIndex = -1;
so->arrayKeyCount = 0;
+ so->arrayKeysStarted = false;
BTScanPosUnpinIfPinned(so->markPos);
BTScanPosInvalidate(so->markPos);
@@ -752,7 +755,23 @@ _bt_parallel_done(IndexScanDesc scan)
* keys.
*
* Updates the count of array keys processed for both local and parallel
- * scans.
+ * scans. (XXX Really? Then why is "scan->parallel_scan != NULL" used as a
+ * gating condition by our caller?)
+ *
+ * XXX Local advancement of array keys occurs dynamically, and affects the
+ * top-level scan state. This is at odds with how parallel scans deal with
+ * array key advancement here, so for now we just don't support them at all.
+ *
+ * The issue here is that the leader instructs workers to process array keys
+ * in whatever order is convenient, without concern for repeat or concurrent
+ * accesses to the same physical leaf pages by workers. This can be addressed
+ * by assigning batches of array keys to workers. Each individual batch would
+ * match a range from the key space covered by some specific leaf page. That
+ * whole approach requires dynamic back-and-forth key space partitioning.
+ *
+ * It seems important that parallel index scans match serial index scans in
+ * promising that no single leaf page will be accessed more than once. That
+ * makes reasoning about the worst case much easier when costing scans.
*/
void
_bt_parallel_advance_array_keys(IndexScanDesc scan)
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index 3230b3b89..dcf399acd 100644
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -890,6 +890,18 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
Assert(!BTScanPosIsValid(so->currPos));
+ /*
+ * XXX Queries with SAOPs have always accounted for each call here as one
+ * "index scan". This meant that the accounting showed one index scan per
+ * distinct SAOP constant. This approach is consistent with how it was
+ * done before nbtree was taught to handle ScalarArrayOpExpr quals itself
+ * (it's also how non-amsearcharray index AMs still do it).
+ *
+ * Right now, eliding a primitive index scan elides a call here, resulting
+ * in one less "index scan" recorded by pgstat. This seems defensible,
+ * though not necessarily desirable. Now implementation details can have
+ * a significant impact on user-visible index scan counts.
+ */
pgstat_count_index_scan(rel);
/*
@@ -1370,6 +1382,13 @@ _bt_first(IndexScanDesc scan, ScanDirection dir)
inskey.scantid = NULL;
inskey.keysz = keysCount;
+ /*
+ * Save insertion scan key for SK_SEARCHARRAY scans, which need it to
+ * advance the scan's array keys locally
+ */
+ if (so->numArrayKeys > 0)
+ _bt_array_keys_save_scankeys(scan, &inskey);
+
/*
* Use the manufactured insertion scan key to descend the tree and
* position ourselves on the target leaf page.
@@ -1548,9 +1567,8 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum)
BTPageOpaque opaque;
OffsetNumber minoff;
OffsetNumber maxoff;
+ BTReadPageState pstate;
int itemIndex;
- bool continuescan;
- int indnatts;
/*
* We must have the buffer pinned and locked, but the usual macro can't be
@@ -1570,8 +1588,12 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum)
_bt_parallel_release(scan, BufferGetBlockNumber(so->currPos.buf));
}
- continuescan = true; /* default assumption */
- indnatts = IndexRelationGetNumberOfAttributes(scan->indexRelation);
+ pstate.dir = dir;
+ pstate.highkey = NULL;
+ pstate.continuescan = true; /* default assumption */
+ pstate.match_for_cur_array_keys = false;
+ pstate.highkeychecked = false;
+
minoff = P_FIRSTDATAKEY(opaque);
maxoff = PageGetMaxOffsetNumber(page);
@@ -1606,6 +1628,14 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum)
if (ScanDirectionIsForward(dir))
{
+ /* SK_SEARCHARRAY scans must provide high key up front */
+ if (so->numArrayKeys && !P_RIGHTMOST(opaque))
+ {
+ ItemId iid = PageGetItemId(page, P_HIKEY);
+
+ pstate.highkey = (IndexTuple) PageGetItem(page, iid);
+ }
+
/* load items[] in ascending order */
itemIndex = 0;
@@ -1628,7 +1658,7 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum)
itup = (IndexTuple) PageGetItem(page, iid);
- if (_bt_checkkeys(scan, itup, indnatts, dir, &continuescan))
+ if (_bt_checkkeys(scan, itup, false, &pstate))
{
/* tuple passes all scan key conditions */
if (!BTreeTupleIsPosting(itup))
@@ -1661,7 +1691,7 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum)
}
}
/* When !continuescan, there can't be any more matches, so stop */
- if (!continuescan)
+ if (!pstate.continuescan)
break;
offnum = OffsetNumberNext(offnum);
@@ -1678,17 +1708,19 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum)
* only appear on non-pivot tuples on the right sibling page are
* common.
*/
- if (continuescan && !P_RIGHTMOST(opaque))
+ if (pstate.continuescan)
{
- ItemId iid = PageGetItemId(page, P_HIKEY);
- IndexTuple itup = (IndexTuple) PageGetItem(page, iid);
- int truncatt;
+ if (!P_RIGHTMOST(opaque) && !pstate.highkey)
+ {
+ ItemId iid = PageGetItemId(page, P_HIKEY);
- truncatt = BTreeTupleGetNAtts(itup, scan->indexRelation);
- _bt_checkkeys(scan, itup, truncatt, dir, &continuescan);
+ pstate.highkey = (IndexTuple) PageGetItem(page, iid);
+ }
+
+ _bt_checkfinalkeys(scan, &pstate);
}
- if (!continuescan)
+ if (!pstate.continuescan)
so->currPos.moreRight = false;
Assert(itemIndex <= MaxTIDsPerBTreePage);
@@ -1722,8 +1754,8 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum)
*/
if (scan->ignore_killed_tuples && ItemIdIsDead(iid))
{
- Assert(offnum >= P_FIRSTDATAKEY(opaque));
- if (offnum > P_FIRSTDATAKEY(opaque))
+ Assert(offnum >= minoff);
+ if (offnum > minoff)
{
offnum = OffsetNumberPrev(offnum);
continue;
@@ -1736,8 +1768,8 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum)
itup = (IndexTuple) PageGetItem(page, iid);
- passes_quals = _bt_checkkeys(scan, itup, indnatts, dir,
- &continuescan);
+ passes_quals = _bt_checkkeys(scan, itup, offnum == minoff,
+ &pstate);
if (passes_quals && tuple_alive)
{
/* tuple passes all scan key conditions */
@@ -1776,16 +1808,25 @@ _bt_readpage(IndexScanDesc scan, ScanDirection dir, OffsetNumber offnum)
}
}
}
- if (!continuescan)
- {
- /* there can't be any more matches, so stop */
- so->currPos.moreLeft = false;
+ /* When !continuescan, there can't be any more matches, so stop */
+ if (!pstate.continuescan)
break;
- }
offnum = OffsetNumberPrev(offnum);
}
+ /*
+ * Backward scans never check the high key, but must still call
+ * _bt_nocheckkeys when they reach the last page (the leftmost page)
+ * without any tuple ever setting continuescan to false.
+ */
+ if (pstate.continuescan && P_LEFTMOST(opaque) &&
+ _bt_nocheckkeys(scan, dir))
+ pstate.continuescan = false;
+
+ if (!pstate.continuescan)
+ so->currPos.moreLeft = false;
+
Assert(itemIndex >= 0);
so->currPos.firstItem = itemIndex;
so->currPos.lastItem = MaxTIDsPerBTreePage - 1;
diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c
index 7da499c4d..af8accbd3 100644
--- a/src/backend/access/nbtree/nbtutils.c
+++ b/src/backend/access/nbtree/nbtutils.c
@@ -45,11 +45,19 @@ static int _bt_sort_array_elements(IndexScanDesc scan, ScanKey skey,
bool reverse,
Datum *elems, int nelems);
static int _bt_compare_array_elements(const void *a, const void *b, void *arg);
+static bool _bt_advance_array_keys_locally(IndexScanDesc scan,
+ IndexTuple tuple, bool final,
+ BTReadPageState *pstate);
+static bool _bt_tuple_advances_keys(IndexScanDesc scan, IndexTuple tuple,
+ ScanDirection dir);
static bool _bt_compare_scankey_args(IndexScanDesc scan, ScanKey op,
ScanKey leftarg, ScanKey rightarg,
bool *result);
static bool _bt_fix_scankey_strategy(ScanKey skey, int16 *indoption);
static void _bt_mark_scankey_required(ScanKey skey);
+static bool _bt_check_compare(ScanKey keyData, int keysz,
+ IndexTuple tuple, int tupnatts, TupleDesc tupdesc,
+ ScanDirection dir, bool *continuescan);
static bool _bt_check_rowcompare(ScanKey skey,
IndexTuple tuple, int tupnatts, TupleDesc tupdesc,
ScanDirection dir, bool *continuescan);
@@ -202,6 +210,29 @@ _bt_freestack(BTStack stack)
* array keys, it's sufficient to find the extreme element value and replace
* the whole array with that scalar value.
*
+ * It's important that we consistently avoid leaving behind SK_SEARCHARRAY
+ * inequalities after preprocessing, since _bt_advance_array_keys_locally
+ * expects to be able to treat SK_SEARCHARRAY keys as equality constraints.
+ * This makes it possible for the scan to take advantage of naturally occuring
+ * locality to avoid continually redescending the index in _bt_first. We can
+ * advance the array keys opportunistically inside _bt_check_array_keys. This
+ * won't affect the externally visible behavior of the scan.
+ *
+ * In the worst case, the number of primitive index scans will equal the
+ * number of array elements (or the product of the number of array keys when
+ * there are multiple arrays/columns involved). It's also possible that the
+ * total number of primitive index scans will be far less than that.
+ *
+ * We always sort and deduplicate arrays up-front for equality array keys.
+ * ScalarArrayOpExpr execution need only visit leaf pages that might contain
+ * matches exactly once, while preserving the sort order of the index. This
+ * isn't just about performance; it also avoids needing duplicate elimination
+ * of matching TIDs (we prefer deduplicating search keys once, up-front).
+ * Equality SK_SEARCHARRAY keys are disjuncts that we always process in
+ * index/key space order, which makes this general approach feasible. Every
+ * index tuple will match no more than one single distinct combination of
+ * equality-constrained keys (array keys and other equality keys).
+ *
* Note: the reason we need so->arrayKeyData, rather than just scribbling
* on scan->keyData, is that callers are permitted to call btrescan without
* supplying a new set of scankey data.
@@ -539,6 +570,9 @@ _bt_start_array_keys(IndexScanDesc scan, ScanDirection dir)
curArrayKey->cur_elem = 0;
skey->sk_argument = curArrayKey->elem_values[curArrayKey->cur_elem];
}
+
+ /* Tell _bt_advance_array_keys to advance array keys when called */
+ so->arrayKeysStarted = true;
}
/*
@@ -546,6 +580,10 @@ _bt_start_array_keys(IndexScanDesc scan, ScanDirection dir)
*
* Returns true if there is another set of values to consider, false if not.
* On true result, the scankeys are initialized with the next set of values.
+ *
+ * On false result, local advancement of the array keys has reached the end of
+ * each of the arrays for the current scan direction. Only our btgettuple and
+ * btgetbitmap callers should rely on this.
*/
bool
_bt_advance_array_keys(IndexScanDesc scan, ScanDirection dir)
@@ -554,6 +592,9 @@ _bt_advance_array_keys(IndexScanDesc scan, ScanDirection dir)
bool found = false;
int i;
+ if (!so->arrayKeysStarted)
+ return false;
+
/*
* We must advance the last array key most quickly, since it will
* correspond to the lowest-order index column among the available
@@ -594,6 +635,10 @@ _bt_advance_array_keys(IndexScanDesc scan, ScanDirection dir)
break;
}
+ /* Scan reached the end of its array keys in the current scan direction */
+ if (!found)
+ so->arrayKeysStarted = false;
+
/* advance parallel scan */
if (scan->parallel_scan != NULL)
_bt_parallel_advance_array_keys(scan);
@@ -601,6 +646,391 @@ _bt_advance_array_keys(IndexScanDesc scan, ScanDirection dir)
return found;
}
+/*
+ * Check if we need to advance SK_SEARCHARRAY array keys when _bt_checkkeys
+ * returns false and sets continuescan=false. It's possible that the tuple
+ * will be a match after we advance the array keys.
+ *
+ * It is often possible for SK_SEARCHARRAY scans to skip one or more primitive
+ * index scans. Starting a new primitive scan is only required when it is
+ * truly necessary to reposition the top-level scan to some distant leaf page
+ * (where the start of the key space for the next set of search keys begins).
+ * This process (redescending the index) is implemented by calling _bt_first
+ * after the array keys are "globally advanced" by the top-level index scan.
+ *
+ * Starting a new primitive index scan is avoided whenever the end of matches
+ * for the current set of array keys happens to be physically close to the
+ * start of matches for the next set of array keys. The technique isn't used
+ * when matches for the next set of array keys aren't found on the same leaf
+ * page (unless there is good reason to believe that a visit to the next leaf
+ * page needs to take place).
+ *
+ * In the worst case the top-level index scan performs one primitive index
+ * scan per distinct set of array/search keys. In the best case we require
+ * only a single primitive index scan for the entire top-level index scan
+ * (this is even possible with arbitrarily-many distinct sets of array keys).
+ * The optimization is particularly effective with queries that have several
+ * SK_SEARCHARRAY keys (one per index column) when scanning a composite index.
+ * Most individual search key combinations (which are simple conjunctions) may
+ * well turn out to have no matching index tuples.
+ *
+ * Returns false when array keys have not or cannot advance. A new primitive
+ * index scan will be required -- except when the top-level, btrescan-wise
+ * index scan has processed all array keys in the current scan direction.
+ *
+ * Returns true when array keys were advanced "locally". Caller must recheck
+ * the tuple that initially set continuescan=false against the new array keys.
+ * At this point the newly advanced array keys are provisional. The "current"
+ * keys only get "locked in" to the ongoing primitive scan when _bt_checkkeys
+ * returns its first match for the keys. This must happen almost immediately;
+ * we should only invest in eliding primitive index scans when we're almost
+ * certain that it'll work out.
+ *
+ * Note: The fact that we only advance array keys "provisionally" imposes a
+ * requirement on _bt_readpage: it must call _bt_checkfinalkeys whenever its
+ * scan of a leaf page wasn't terminated when it called _bt_checkkeys against
+ * non-pivot tuples. This scheme ensures that we'll always have at least one
+ * opportunity to change our minds per leaf page scanned (even, say, on a page
+ * that only contains non-pivot tuples whose LP_DEAD bits are set).
+ *
+ * Note: We can determine that the next leaf page ought to be handled by the
+ * ongoing primitive index scan without being fully sure that it'll work out.
+ * This occasionally results in primitive index scans that waste cycles on a
+ * useless visit to an extra page, which then terminates the primitive scan.
+ * Such wasted accesses are only possible when the high key (or the final key
+ * in the case of backwards scans) is within the bounds of the latest set of
+ * array keys that the primitive scan can advance to.
+ *
+ * Note: There are cases where we visit the next leaf page during a primitive
+ * index scan without being completely certain about whether or not we really
+ * need to visit that page at all. In other words, sometimes we speculatively
+ * visit the next leaf page, which risks wasting a leaf page access.
+ */
+static bool
+_bt_advance_array_keys_locally(IndexScanDesc scan, IndexTuple tuple,
+ bool final, BTReadPageState *pstate)
+{
+ BTScanOpaque so = (BTScanOpaque) scan->opaque;
+
+ Assert(!pstate->continuescan);
+ Assert(so->arrayKeysStarted);
+
+ if (!so->arrayPoskey)
+ {
+ /*
+ * Scans that lack an initial positioning key (and so must go through
+ * _bt_endpoint rather than calling _bt_search from _bt_first) are not
+ * capable of locally advancing array keys
+ */
+ return false;
+ }
+
+ /*
+ * Current search type scan keys (including current array keys) indicated
+ * that this tuple terminates the scan in _bt_checkkeys caller. Can this
+ * tuple be a match for later sets of array keys, once advanced?
+ */
+ if (!_bt_tuple_advances_keys(scan, tuple, pstate->dir))
+ {
+ /*
+ * Tuple definitely isn't a match for any set of search keys. Tuple
+ * definitely won't be returned by _bt_checkkeys. Now we need to
+ * determine if the scan will continue to the next tuple/page.
+ *
+ * If this is a forwards scan, check the high key -- page state
+ * stashes it in order to allow us to terminate processing of a page
+ * (and the primitive index scan as a whole) early.
+ *
+ * If this is a backwards scan, treat the first non-pivot tuple as a
+ * stand-in for the page high key. Unlike the forward scan case, this
+ * is only possible when _bt_checkkeys reaches the final tuple on the
+ * page. (Only the more common forward scan case has the ability to
+ * end the scan of an individual page early using the high key because
+ * we always have the high key stashed.)
+ *
+ * This always needs to happen before we leave each leaf page, for all
+ * sets of array keys up to and including the last set we advance to.
+ * We must avoid becoming confused about which primitive index scan
+ * (the current or the next) returns matches for any set of array
+ * keys.
+ */
+ if (!pstate->match_for_cur_array_keys &&
+ (final || (!pstate->highkeychecked && pstate->highkey)))
+ {
+ Assert(ScanDirectionIsForward(pstate->dir) || !pstate->highkey);
+ Assert(ScanDirectionIsBackward(pstate->dir) || !final);
+
+ pstate->highkeychecked = true; /* iff this is a forward scan */
+
+ if (final || !_bt_tuple_advances_keys(scan, pstate->highkey,
+ pstate->dir))
+ {
+ /*
+ * We're unlikely to find any further matches for the current
+ * set of array keys on the next sibling leaf page.
+ *
+ * Back up the array keys so that btgettuple or btgetbitmap
+ * won't advance the keys past the now-current set. This is
+ * safe because we haven't returned any tuples matching this
+ * set of keys.
+ */
+ ScanDirection flipdir = -pstate->dir;
+
+ if (!_bt_advance_array_keys(scan, flipdir))
+ Assert(false);
+
+ _bt_preprocess_keys(scan);
+
+ /* End the current primitive index scan */
+ pstate->continuescan = false; /* redundant */
+ return false;
+ }
+ }
+
+ /*
+ * Continue the current primitive index scan. Returning false
+ * indicates that we're done with this tuple. The ongoing primitive
+ * index scan will proceed to the next non-pivot tuple on this page
+ * (or to the first non-pivot tuple on the next page).
+ */
+ pstate->continuescan = true;
+ return false;
+ }
+
+ if (!_bt_advance_array_keys(scan, pstate->dir))
+ {
+ Assert(!so->arrayKeysStarted);
+
+ /*
+ * Ran out of array keys to advance the scan to. The top-level,
+ * btrescan-wise scan has been terminated by this tuple.
+ */
+ pstate->continuescan = false; /* redundant */
+ return false;
+ }
+
+ /*
+ * Successfully advanced the array keys. We'll now need to see what
+ * _bt_checkkeys loop says about the same tuple with this new set of keys.
+ *
+ * Advancing the arrays keys is only provisional at this point. If there
+ * are no matches for the new array keys before we leave the page, and
+ * high key check indicates that there is little chance of finding any
+ * matches for the new keys on the next page, we will change our mind.
+ * This is handled by "backing up" the array keys, and then starting a new
+ * primitive index scan for the same set of array keys.
+ *
+ * XXX Clearly it would be a lot more efficient if we were to implement
+ * all this by searching for the next set of array keys using this tuple's
+ * key values, directly. Right now we effectively use a linear search
+ * (though one that can terminate upon finding the first match). We must
+ * make it into a binary search to get acceptable performance.
+ *
+ * Our current naive approach works well enough for prototyping purposes,
+ * but chokes in extreme cases where the Cartesian product of all SAOP
+ * arrays (i.e. the total number of DNF single value predicates generated
+ * by the _bt_advance_array_keys state machine) starts to get unwieldy.
+ * We're holding a buffer lock here, so this isn't really negotiable.
+ *
+ * It's not particular unlikely that the total number of DNF predicates
+ * exceeds the number of tuples that'll be returned by the ongoing scan.
+ * Efficiently advancing the array keys might turn out to matter almost as
+ * much as efficiently searching for the next matching index tuple.
+ */
+ _bt_preprocess_keys(scan);
+
+ if (pstate->highkey)
+ {
+ /* High key precheck might need to be repeated for new array keys */
+ pstate->match_for_cur_array_keys = false;
+ pstate->highkeychecked = false;
+ }
+
+ /*
+ * Note: It doesn't matter how continuescan is set by us at this point.
+ * The next iteration of caller's loop will overwrite continuescan.
+ */
+ return true;
+}
+
+/*
+ * Helper routine used by _bt_advance_array_keys_locally.
+ *
+ * We're called with tuples that _bt_checkkeys set continuescan to false for.
+ * We distinguish between search-type scan keys that have equality constraints
+ * on an index column (which are always marked as required in both directions)
+ * and other search-type scan keys that are required in one direction only.
+ * The distinction is important independent of the current scan direction,
+ * since caller should only advance array keys when an equality constraint
+ * indicated the end of the current set of array keys. (Note also that
+ * non-equality "required in one direction only" scan keys can only end the
+ * entire btrescan-wise scan when we run out of array keys to process for the
+ * current scan direction).
+ *
+ * We help our caller identify where matches for the next set of array keys
+ * _might_ begin when it turns out that we can elide another descent of the
+ * index for the next set of array keys. There will be a gap of 0 or more
+ * non-matching index tuples between the last tuple that satisfies the current
+ * set of scan keys (including its array keys), and the first tuple that might
+ * satisfy the next set (caller won't know for sure until after it advances
+ * the current set of array keys). This gap might be negligible, or it might
+ * be a significant fraction of all non-pivot tuples on the leaf level.
+ *
+ * The qual "WHERE x IN (3,4,5) AND y < 42" will have its 'y' scan key marked
+ * SK_BT_REQFWD (not SK_BT_REQBKWD) -- 'y' isn't an equality constraint.
+ * _bt_checkkeys will set continuescan=false as soon as the scan reaches a
+ * tuple matching (3, 42) or a tuple matching (4, 1). Eliding the next
+ * primitive index scan (by advancing the array keys locally) happens when the
+ * gap is confined to a single leaf page. Caller continues its scan through
+ * these gap tuples, and calls back here to check if it has found the point
+ * that it might be necessary to advance its array keys.
+ *
+ * Returns false when caller's tuple definitely isn't where the next group of
+ * matching tuples begins. Caller can either continue the process with the
+ * very next tuple from its leaf page, or give up completely. Giving up means
+ * that caller accepts that there must be another _bt_first descent (in the
+ * likely event of another call to btgettuple/btgetbitmap from the executor).
+ *
+ * Returns true when caller passed a tuple that might be a match for the next
+ * set of array keys. That is, when tuple is > the current set of array keys
+ * and other equality constraints for a forward scan (or < for a backwards
+ * scans). Caller must attempt to advance the array keys when this happens.
+ *
+ * Note: Our test is based on the current equality constraint scan keys rather
+ * than the next set in line because it's not yet clear if the next set in
+ * line will find any matches whatsoever. Once caller is positioned at the
+ * first tuple that might satisfy the next set of array keys, it could be
+ * necessary for it to advance its array keys more than once.
+ */
+static bool
+_bt_tuple_advances_keys(IndexScanDesc scan, IndexTuple tuple, ScanDirection dir)
+{
+ BTScanOpaque so = (BTScanOpaque) scan->opaque;
+ Relation rel = scan->indexRelation;
+ TupleDesc itupdesc = RelationGetDescr(rel);
+ bool tuple_ahead = true;
+ int ncmpkey;
+
+ Assert(so->qual_ok);
+ Assert(so->numArrayKeys > 0);
+ Assert(so->numberOfKeys > 0);
+ Assert(so->arrayPoskey->keysz > 0);
+
+ ncmpkey = Min(BTreeTupleGetNAtts(tuple, rel), so->numberOfKeys);
+ for (int attnum = 1; attnum <= ncmpkey; attnum++)
+ {
+ ScanKey cur = &so->keyData[attnum - 1];
+ ScanKey iscankey;
+ Datum datum;
+ bool isNull;
+ int32 result;
+
+ if ((ScanDirectionIsForward(dir) &&
+ (cur->sk_flags & SK_BT_REQFWD) == 0) ||
+ (ScanDirectionIsBackward(dir) &&
+ (cur->sk_flags & SK_BT_REQBKWD) == 0))
+ {
+ /*
+ * This scan key is not marked as required for the current
+ * direction, so there are no further attributes to consider. This
+ * tuple definitely isn't at the start of the next group of
+ * matching tuples.
+ */
+ break;
+ }
+
+ Assert(cur->sk_attno == attnum);
+ if (cur->sk_attno > so->arrayPoskey->keysz)
+ {
+ /*
+ * There is no equality constraint on this column/scan key to
+ * break the tie. This tuple definitely isn't at the start of the
+ * next group of matching tuples.
+ */
+ Assert(cur->sk_strategy != BTEqualStrategyNumber);
+ Assert((cur->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) !=
+ (SK_BT_REQFWD | SK_BT_REQBKWD));
+ break;
+ }
+
+ /*
+ * This column has an equality constraint/insertion scan key entry
+ */
+ Assert((cur->sk_flags & (SK_BT_REQFWD | SK_BT_REQBKWD)) ==
+ (SK_BT_REQFWD | SK_BT_REQBKWD));
+ Assert(cur->sk_strategy == BTEqualStrategyNumber);
+
+ /*
+ * Row comparison scan keys may be present after (though never before)
+ * columns that we recognized as having equality constraints.
+ *
+ * A qual like "WHERE a in (1, 2, 3) AND (b, c) >= (500, 7)" is safe,
+ * whereas "WHERE (a, b) >= (1, 500) AND c in (7, 8, 9)" is unsafe.
+ * Assert that this isn't one of the unsafe cases in passing.
+ */
+ Assert((cur->sk_flags & SK_ROW_HEADER) == 0);
+
+ /*
+ * We'll need to use this attribute's 3-way comparison order proc
+ * (btree opclass support function 1) from its insertion-type scan key
+ */
+ iscankey = &so->arrayPoskey->scankeys[attnum - 1];
+ Assert(iscankey->sk_flags == cur->sk_flags);
+ Assert(iscankey->sk_attno == cur->sk_attno);
+ Assert(iscankey->sk_subtype == cur->sk_subtype);
+ Assert(iscankey->sk_collation == cur->sk_collation);
+
+ /*
+ * The 3-way comparison order proc will be called using the
+ * search-type scan key's current sk_argument
+ */
+ datum = index_getattr(tuple, attnum, itupdesc, &isNull);
+ if (iscankey->sk_flags & SK_ISNULL) /* key is NULL */
+ {
+ if (isNull)
+ result = 0; /* NULL "=" NULL */
+ else if (iscankey->sk_flags & SK_BT_NULLS_FIRST)
+ result = -1; /* NULL "<" NOT_NULL */
+ else
+ result = 1; /* NULL ">" NOT_NULL */
+ }
+ else if (isNull) /* key is NOT_NULL and item is NULL */
+ {
+ if (iscankey->sk_flags & SK_BT_NULLS_FIRST)
+ result = 1; /* NOT_NULL ">" NULL */
+ else
+ result = -1; /* NOT_NULL "<" NULL */
+ }
+ else
+ {
+ /*
+ * The sk_func needs to be passed the index value as left arg and
+ * the sk_argument as right arg (they might be of different
+ * types). We want to keep this consistent with what _bt_compare
+ * does, so we flip the sign of the comparison result. (Unless
+ * it's a DESC column, in which case we *don't* flip the sign.)
+ */
+ result = DatumGetInt32(FunctionCall2Coll(&iscankey->sk_func,
+ cur->sk_collation, datum,
+ cur->sk_argument));
+ if (!(iscankey->sk_flags & SK_BT_DESC))
+ INVERT_COMPARE_RESULT(result);
+ }
+
+ if (result != 0)
+ {
+ if (ScanDirectionIsForward(dir))
+ tuple_ahead = result < 0;
+ else
+ tuple_ahead = result > 0;
+
+ break;
+ }
+ }
+
+ return tuple_ahead;
+}
+
/*
* _bt_mark_array_keys() -- Handle array keys during btmarkpos
*
@@ -744,6 +1174,12 @@ _bt_restore_array_keys(IndexScanDesc scan)
* storage is that we are modifying the array based on comparisons of the
* key argument values, which could change on a rescan or after moving to
* new elements of array keys. Therefore we can't overwrite the source data.
+ *
+ * TODO Replace all calls to this function added by the patch with calls to
+ * some other more specialized function with reduced surface area -- something
+ * that is explicitly safe to call while holding a buffer lock. That's been
+ * put off for now because the code in this function is likely to need to be
+ * better integrated with the planner before long anyway.
*/
void
_bt_preprocess_keys(IndexScanDesc scan)
@@ -1012,6 +1448,45 @@ _bt_preprocess_keys(IndexScanDesc scan)
so->numberOfKeys = new_numberOfKeys;
}
+/*
+ * Save insertion scankey for searches with a SK_SEARCHARRAY scan key.
+ *
+ * We must save the initial positioning insertion scan key for SK_SEARCHARRAY
+ * scans (barring those that only have SK_SEARCHARRAY inequalities). Each
+ * insertion scan key entry/column will have a corresponding "=" operator in
+ * caller's search-type scan key, but that's no substitute for the 3-way
+ * comparison function.
+ *
+ * _bt_tuple_advances_keys needs to perform 3-way comparisons to figure out if
+ * an ongoing scan can elide another descent of the index in _bt_first. It
+ * works by locating the end of the _current_ set of equality constraint type
+ * scan keys -- not by locating the start of the next set. This is not unlike
+ * the approach taken by _bt_search with a nextkey=true search.
+ */
+void
+_bt_array_keys_save_scankeys(IndexScanDesc scan, BTScanInsert inskey)
+{
+ BTScanOpaque so = (BTScanOpaque) scan->opaque;
+ Size sksize;
+
+ Assert(inskey->keysz > 0);
+ Assert(so->numArrayKeys > 0);
+ Assert(so->qual_ok);
+ Assert(!BTScanPosIsValid(so->currPos));
+
+ if (so->arrayPoskey)
+ {
+ /* Reuse the insertion scan key from the last primitive index scan */
+ Assert(so->arrayPoskey->keysz == inskey->keysz);
+ return;
+ }
+
+ sksize = offsetof(BTScanInsertData, scankeys) +
+ sizeof(ScanKeyData) * inskey->keysz;
+ so->arrayPoskey = palloc(sksize);
+ memcpy(so->arrayPoskey, inskey, sksize);
+}
+
/*
* Compare two scankey values using a specified operator.
*
@@ -1348,35 +1823,68 @@ _bt_mark_scankey_required(ScanKey skey)
* this tuple, and set *continuescan accordingly. See comments for
* _bt_preprocess_keys(), above, about how this is done.
*
- * Forward scan callers can pass a high key tuple in the hopes of having
- * us set *continuescan to false, and avoiding an unnecessary visit to
- * the page to the right.
+ * Advances the current set of array keys locally for SK_SEARCHARRAY scans
+ * where appropriate. These callers are required to initialize the page level
+ * high key in pstate.
*
* scan: index scan descriptor (containing a search-type scankey)
* tuple: index tuple to test
- * tupnatts: number of attributes in tupnatts (high key may be truncated)
- * dir: direction we are scanning in
- * continuescan: output parameter (will be set correctly in all cases)
+ * final: final tuple/call for this page, from a backwards scan?
+ * pstate: Page level input and output parameters
*/
bool
-_bt_checkkeys(IndexScanDesc scan, IndexTuple tuple, int tupnatts,
- ScanDirection dir, bool *continuescan)
+_bt_checkkeys(IndexScanDesc scan, IndexTuple tuple, bool final,
+ BTReadPageState *pstate)
+{
+ TupleDesc tupdesc = RelationGetDescr(scan->indexRelation);
+ int natts = BTreeTupleGetNAtts(tuple, scan->indexRelation);
+ BTScanOpaque so = (BTScanOpaque) scan->opaque;
+ bool res;
+
+ /* This loop handles advancing to the next array elements, if any */
+ do
+ {
+ res = _bt_check_compare(so->keyData, so->numberOfKeys,
+ tuple, natts, tupdesc,
+ pstate->dir, &pstate->continuescan);
+
+ /* If we have a tuple, return it ... */
+ if (res)
+ {
+ pstate->match_for_cur_array_keys = true;
+
+ Assert(!so->numArrayKeys || !so->arrayPoskey ||
+ _bt_tuple_advances_keys(scan, tuple, pstate->dir));
+ break;
+ }
+
+ /* ... otherwise see if we have more array keys to deal with */
+ } while (so->numArrayKeys && !pstate->continuescan &&
+ _bt_advance_array_keys_locally(scan, tuple, final, pstate));
+
+ return res;
+}
+
+/*
+ * Test whether an indextuple satisfies current scan condition.
+ *
+ * Return true if so, false if not. If not, also clear *continuescan if
+ * it's not possible for any future tuples in the current scan direction to
+ * pass the qual with the current set of array keys.
+ *
+ * This is a subroutine for _bt_checkkeys.
+ */
+static bool
+_bt_check_compare(ScanKey keyData, int keysz,
+ IndexTuple tuple, int tupnatts, TupleDesc tupdesc,
+ ScanDirection dir, bool *continuescan)
{
- TupleDesc tupdesc;
- BTScanOpaque so;
- int keysz;
int ikey;
ScanKey key;
- Assert(BTreeTupleGetNAtts(tuple, scan->indexRelation) == tupnatts);
-
*continuescan = true; /* default assumption */
- tupdesc = RelationGetDescr(scan->indexRelation);
- so = (BTScanOpaque) scan->opaque;
- keysz = so->numberOfKeys;
-
- for (key = so->keyData, ikey = 0; ikey < keysz; key++, ikey++)
+ for (key = keyData, ikey = 0; ikey < keysz; key++, ikey++)
{
Datum datum;
bool isNull;
@@ -1523,7 +2031,7 @@ _bt_checkkeys(IndexScanDesc scan, IndexTuple tuple, int tupnatts,
* it's not possible for any future tuples in the current scan direction
* to pass the qual.
*
- * This is a subroutine for _bt_checkkeys, which see for more info.
+ * This is a subroutine for _bt_check_compare/_bt_checkkeys_compare.
*/
static bool
_bt_check_rowcompare(ScanKey skey, IndexTuple tuple, int tupnatts,
@@ -1690,6 +2198,49 @@ _bt_check_rowcompare(ScanKey skey, IndexTuple tuple, int tupnatts,
return result;
}
+void
+_bt_checkfinalkeys(IndexScanDesc scan, BTReadPageState *pstate)
+{
+ IndexTuple highkey = pstate->highkey;
+
+ Assert(pstate->continuescan);
+
+ if (!pstate->highkey)
+ {
+ _bt_nocheckkeys(scan, pstate->dir);
+ pstate->continuescan = false;
+ return;
+ }
+
+ pstate->highkey = NULL;
+ _bt_checkkeys(scan, highkey, false, pstate);
+}
+
+/*
+ * Perform final steps when the "end point" is reached on the leaf level
+ * without any call to _bt_checkkeys setting *continuescan to false.
+ *
+ * Called on the rightmost page in the forward scan case, and the leftmost
+ * page in the backwards scan case. Only call here when _bt_checkkeys hasn't
+ * already set continuescan to false.
+ */
+bool
+_bt_nocheckkeys(IndexScanDesc scan, ScanDirection dir)
+{
+ BTScanOpaque so = (BTScanOpaque) scan->opaque;
+
+ /* Only need to do real work in SK_SEARCHARRAY case, for now */
+ if (!so->numArrayKeys)
+ return false;
+
+ Assert(so->arrayKeysStarted);
+
+ while (_bt_advance_array_keys(scan, dir))
+ _bt_preprocess_keys(scan);
+
+ return true;
+}
+
/*
* _bt_killitems - set LP_DEAD state for items an indexscan caller has
* told us were killed
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 6a93d767a..73064758d 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -32,6 +32,7 @@
#include "optimizer/paths.h"
#include "optimizer/prep.h"
#include "optimizer/restrictinfo.h"
+#include "utils/fmgroids.h"
#include "utils/lsyscache.h"
#include "utils/selfuncs.h"
@@ -107,7 +108,7 @@ static List *build_index_paths(PlannerInfo *root, RelOptInfo *rel,
bool useful_predicate,
ScanTypeControl scantype,
bool *skip_nonnative_saop,
- bool *skip_lower_saop);
+ bool *skip_unordered_saop);
static List *build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel,
List *clauses, List *other_clauses);
static List *generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
@@ -706,8 +707,8 @@ eclass_already_used(EquivalenceClass *parent_ec, Relids oldrelids,
* index AM supports them natively, we should just include them in simple
* index paths. If not, we should exclude them while building simple index
* paths, and then make a separate attempt to include them in bitmap paths.
- * Furthermore, we should consider excluding lower-order ScalarArrayOpExpr
- * quals so as to create ordered paths.
+ * Furthermore, we should consider excluding ScalarArrayOpExpr quals whose
+ * inclusion would force the path as a whole to be unordered.
*/
static void
get_index_paths(PlannerInfo *root, RelOptInfo *rel,
@@ -716,28 +717,28 @@ get_index_paths(PlannerInfo *root, RelOptInfo *rel,
{
List *indexpaths;
bool skip_nonnative_saop = false;
- bool skip_lower_saop = false;
+ bool skip_unordered_saop = false;
ListCell *lc;
/*
* Build simple index paths using the clauses. Allow ScalarArrayOpExpr
* clauses only if the index AM supports them natively, and skip any such
- * clauses for index columns after the first (so that we produce ordered
- * paths if possible).
+ * clauses for index columns whose inclusion would make it impossible to
+ * produce ordered paths.
*/
indexpaths = build_index_paths(root, rel,
index, clauses,
index->predOK,
ST_ANYSCAN,
&skip_nonnative_saop,
- &skip_lower_saop);
+ &skip_unordered_saop);
/*
- * If we skipped any lower-order ScalarArrayOpExprs on an index with an AM
- * that supports them, then try again including those clauses. This will
- * produce paths with more selectivity but no ordering.
+ * If we skipped any ScalarArrayOpExprs without ordered paths on an index
+ * with an AM that supports them, then try again including those clauses.
+ * This will produce paths with more selectivity.
*/
- if (skip_lower_saop)
+ if (skip_unordered_saop)
{
indexpaths = list_concat(indexpaths,
build_index_paths(root, rel,
@@ -817,11 +818,9 @@ get_index_paths(PlannerInfo *root, RelOptInfo *rel,
* to true if we found any such clauses (caller must initialize the variable
* to false). If it's NULL, we do not ignore ScalarArrayOpExpr clauses.
*
- * If skip_lower_saop is non-NULL, we ignore ScalarArrayOpExpr clauses for
- * non-first index columns, and we set *skip_lower_saop to true if we found
- * any such clauses (caller must initialize the variable to false). If it's
- * NULL, we do not ignore non-first ScalarArrayOpExpr clauses, but they will
- * result in considering the scan's output to be unordered.
+ * If skip_unordered_saop is non-NULL, we ignore ScalarArrayOpExpr clauses
+ * whose inclusion forces us to treat the scan's output as unordered. If it's
+ * NULL then we allow it, in order to produce paths with greater selectivity.
*
* 'rel' is the index's heap relation
* 'index' is the index for which we want to generate paths
@@ -829,7 +828,7 @@ get_index_paths(PlannerInfo *root, RelOptInfo *rel,
* 'useful_predicate' indicates whether the index has a useful predicate
* 'scantype' indicates whether we need plain or bitmap scan support
* 'skip_nonnative_saop' indicates whether to accept SAOP if index AM doesn't
- * 'skip_lower_saop' indicates whether to accept non-first-column SAOP
+ * 'skip_unordered_saop' indicates whether to accept unordered SOAPs
*/
static List *
build_index_paths(PlannerInfo *root, RelOptInfo *rel,
@@ -837,7 +836,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
bool useful_predicate,
ScanTypeControl scantype,
bool *skip_nonnative_saop,
- bool *skip_lower_saop)
+ bool *skip_unordered_saop)
{
List *result = NIL;
IndexPath *ipath;
@@ -848,10 +847,13 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
List *orderbyclausecols;
List *index_pathkeys;
List *useful_pathkeys;
- bool found_lower_saop_clause;
+ bool row_compare_seen_already;
+ bool saop_included_already;
+ bool saop_invalidates_ordering;
bool pathkeys_possibly_useful;
bool index_is_ordered;
bool index_only_scan;
+ int prev_equality_indexcol;
int indexcol;
/*
@@ -880,25 +882,27 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
* on by btree and possibly other places.) The list can be empty, if the
* index AM allows that.
*
- * found_lower_saop_clause is set true if we accept a ScalarArrayOpExpr
- * index clause for a non-first index column. This prevents us from
- * assuming that the scan result is ordered. (Actually, the result is
- * still ordered if there are equality constraints for all earlier
- * columns, but it seems too expensive and non-modular for this code to be
- * aware of that refinement.)
+ * saop_invalidates_ordering is set true if we accept a ScalarArrayOpExpr
+ * index clause that invalidates the sort order. In practice this is
+ * always due to the presence of a non-first index column. This prevents
+ * us from assuming that the scan result is ordered.
*
* We also build a Relids set showing which outer rels are required by the
* selected clauses. Any lateral_relids are included in that, but not
* otherwise accounted for.
*/
index_clauses = NIL;
- found_lower_saop_clause = false;
+ prev_equality_indexcol = -1;
+ row_compare_seen_already = false;
+ saop_included_already = false;
+ saop_invalidates_ordering = false;
outer_relids = bms_copy(rel->lateral_relids);
for (indexcol = 0; indexcol < index->nkeycolumns; indexcol++)
{
+ List *colclauses = clauses->indexclauses[indexcol];
ListCell *lc;
- foreach(lc, clauses->indexclauses[indexcol])
+ foreach(lc, colclauses)
{
IndexClause *iclause = (IndexClause *) lfirst(lc);
RestrictInfo *rinfo = iclause->rinfo;
@@ -906,6 +910,8 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
/* We might need to omit ScalarArrayOpExpr clauses */
if (IsA(rinfo->clause, ScalarArrayOpExpr))
{
+ ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) rinfo->clause;
+
if (!index->amsearcharray)
{
if (skip_nonnative_saop)
@@ -916,18 +922,152 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
}
/* Caller had better intend this only for bitmap scan */
Assert(scantype == ST_BITMAPSCAN);
+ saop_invalidates_ordering = true; /* defensive */
+ goto include_clause;
}
- if (indexcol > 0)
+
+ /*
+ * Index AM that handles ScalarArrayOpExpr quals natively.
+ *
+ * We assume that it's always better to apply a clause as an
+ * indexqual than as a filter (qpqual); which is where an
+ * available clause would end up being applied if we omit it
+ * from the indexquals.
+ *
+ * XXX Currently, nbtree just assumes that all SK_SEARCHARRAY
+ * search-type scankeys will be marked as required, with the
+ * exception of the first attribute without an "=" key (any
+ * such attribute is marked SK_BT_REQFWD or SK_BT_REQBKWD, but
+ * it won't be in the initial positioning insertion scan key,
+ * so _bt_array_continuescan() won't consider it).
+ */
+ if (row_compare_seen_already)
{
- if (skip_lower_saop)
+ /*
+ * Cannot safely include a ScalarArrayOpExpr after a
+ * higher-order RowCompareExpr (barring the "=" case).
+ */
+ Assert(indexcol > 0);
+ continue;
+ }
+
+ /*
+ * Make a blanket assumption that any index column with more
+ * than a single clause cannot include ScalarArrayOpExpr
+ * clauses >= that column. Quals like "WHERE my_col in (1,2)
+ * AND my_col < 1" are unsafe without this.
+ *
+ * XXX This is overkill.
+ */
+ if (list_length(colclauses) > 1)
+ continue;
+
+ if (indexcol != prev_equality_indexcol + 1)
+ {
+ /*
+ * An index attribute that lacks an equality constraint
+ * was included as a clause already. This may make it
+ * unsafe to include this ScalarArrayOpExpr clause now.
+ */
+ if (saop_included_already)
{
- /* Caller doesn't want to lose index ordering */
- *skip_lower_saop = true;
+ /*
+ * We included at least one ScalarArrayOpExpr clause
+ * earlier, too. (This must have been included before
+ * the inequality, since we treat ScalarArrayOpExpr
+ * clauses as equality constraints by default.)
+ *
+ * We cannot safely include this ScalarArrayOpExpr as
+ * a clause for the current index path. It'll become
+ * qpqual conditions instead.
+ */
continue;
}
- found_lower_saop_clause = true;
+
+ /*
+ * This particular ScalarArrayOpExpr happens to be the
+ * most significant one encountered so far. That makes it
+ * safe to include, despite gaps in constraints on prior
+ * index columns -- provided we invalidate ordering for
+ * the index path as a whole.
+ */
+ if (skip_unordered_saop)
+ {
+ /* Caller doesn't want to lose index ordering */
+ *skip_unordered_saop = true;
+ continue;
+ }
+
+ /* Caller prioritizes selectivity over ordering */
+ saop_invalidates_ordering = true;
}
+
+ /*
+ * Includable ScalarArrayOpExpr clauses are themselves
+ * equality constraints (they don't make the inclusion of
+ * further ScalarArrayOpExpr clauses invalidate ordering).
+ *
+ * XXX excludes inequality-type SAOPs using get_oprrest, which
+ * seems particularly kludgey.
+ */
+ saop_included_already = true;
+ if (saop->useOr && get_oprrest(saop->opno) == F_EQSEL)
+ prev_equality_indexcol = indexcol;
}
+ else if (IsA(rinfo->clause, NullTest))
+ {
+ NullTest *nulltest = (NullTest *) rinfo->clause;
+
+ /*
+ * Like ScalarArrayOpExpr clauses, IS NULL NullTest clauses
+ * are treated as equality conditions, despite not being
+ * recognized as such by the equivalence class machinery.
+ *
+ * This relies on the assumption that amsearcharray index AMs
+ * will treat NULL as just another value from the domain of
+ * indexed values for initial search purposes.
+ */
+ if (!nulltest->argisrow && nulltest->nulltesttype == IS_NULL)
+ prev_equality_indexcol = indexcol;
+ }
+ else if (IsA(rinfo->clause, RowCompareExpr))
+ {
+ /*
+ * RowCompareExpr clause will make it unsafe to include any
+ * ScalarArrayOpExpr encountered in lower-order clauses.
+ * (Already-included ScalarArrayOpExpr clauses can stay.)
+ */
+ row_compare_seen_already = true;
+ }
+ else if (rinfo->mergeopfamilies)
+ {
+ /*
+ * Equality constraint clause -- won't make it unsafe to
+ * include later ScalarArrayOpExpr clauses
+ */
+ prev_equality_indexcol = indexcol;
+ }
+ else
+ {
+ /*
+ * Clause isn't an equality condition according to the EQ
+ * machinery (not a NullTest or ScalarArrayOpExpr, either).
+ *
+ * If there are any later ScalarArrayOpExpr clauses, they must
+ * not be used as index quals. We'll either make it safe by
+ * setting saop_invalidates_ordering to true, or by just not
+ * including them (they can still be qpqual conditions).
+ *
+ * Note: there are several interesting types of expressions
+ * that we deem incompatible with ScalarArrayOpExpr clauses
+ * due to a lack of infrastructure to perform transformations
+ * of predicates from CNF (conjunctive normal form) to DNF
+ * (disjunctive normal form). The MDAM paper describes many
+ * examples of these transformations.
+ */
+ }
+
+ include_clause:
/* OK to include this clause */
index_clauses = lappend(index_clauses, iclause);
@@ -960,7 +1100,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
* assume the scan is unordered.
*/
pathkeys_possibly_useful = (scantype != ST_BITMAPSCAN &&
- !found_lower_saop_clause &&
+ !saop_invalidates_ordering &&
has_useful_pathkeys(root, rel));
index_is_ordered = (index->sortopfamily != NULL);
if (index_is_ordered && pathkeys_possibly_useful)
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index c4fcd0076..51de102b0 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -6700,9 +6700,9 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
* For a RowCompareExpr, we consider only the first column, just as
* rowcomparesel() does.
*
- * If there's a ScalarArrayOpExpr in the quals, we'll actually perform N
- * index scans not one, but the ScalarArrayOpExpr's operator can be
- * considered to act the same as it normally does.
+ * If there's a ScalarArrayOpExpr in the quals, we'll perform N primitive
+ * index scans in the worst case. Assume that worst case, for now. We'll
+ * clamp later on if the tally approaches the total number of index pages.
*/
indexBoundQuals = NIL;
indexcol = 0;
@@ -6754,7 +6754,15 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
clause_op = saop->opno;
found_saop = true;
- /* count number of SA scans induced by indexBoundQuals only */
+
+ /*
+ * Count number of SA scans induced by indexBoundQuals only.
+ *
+ * Since this is multiplicative, it can wildly inflate the
+ * assumed number of descents (number of primitive index
+ * scans) for scans with several SAOP clauses. We might clamp
+ * num_sa_scans later on to deal with this.
+ */
if (alength > 1)
num_sa_scans *= alength;
}
@@ -6832,6 +6840,39 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
genericcostestimate(root, path, loop_count, &costs);
+ /*
+ * The btree index AM will automatically combine individual primitive
+ * index scans whenever the tuples covered by the next set of array keys
+ * are close to tuples covered by the current set. This optimization
+ * makes the final number of descents particularly difficult to estimate.
+ * However, btree scans never visit any single leaf page more than once.
+ * That puts a natural floor under the worst case number of descents.
+ *
+ * Clamp the number of descents to the estimated number of leaf page
+ * visits. This is still fairly pessimistic, but tends to result in more
+ * accurate costing of scans with several SAOP clauses -- especially when
+ * each array has more than a few elements.
+ *
+ * Also clamp the number of descents to 1/3 the number of index pages.
+ * This avoids implausibly high estimates with low selectivity paths,
+ * where scans frequently require no more than one or two descents.
+ *
+ * XXX genericcostestimate is still the dominant influence on the total
+ * cost of SAOP-heavy index paths -- indexTotalCost is still calculated in
+ * a way that assumes significant repeat access to leaf pages for a path
+ * with SAOP clauses. This just isn't sensible anymore. Note that nbtree
+ * scans promise to avoid accessing any leaf page more than once. The
+ * worst case I/O cost of an SAOP-heavy path is therefore guaranteed to
+ * never exceed the I/O cost of a conventional full index scan (though
+ * this relies on standard assumptions about internal page access costs).
+ */
+ if (num_sa_scans > 1)
+ {
+ num_sa_scans = Min(num_sa_scans, costs.numIndexPages);
+ num_sa_scans = Min(num_sa_scans, index->pages / 3);
+ num_sa_scans = Max(num_sa_scans, 1);
+ }
+
/*
* Add a CPU-cost component to represent the costs of initial btree
* descent. We don't charge any I/O cost for touching upper btree levels,
@@ -6847,7 +6888,7 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
{
descentCost = ceil(log(index->tuples) / log(2.0)) * cpu_operator_cost;
costs.indexStartupCost += descentCost;
- costs.indexTotalCost += costs.num_sa_scans * descentCost;
+ costs.indexTotalCost += num_sa_scans * descentCost;
}
/*
@@ -6858,11 +6899,12 @@ btcostestimate(PlannerInfo *root, IndexPath *path, double loop_count,
* in cases where only a single leaf page is expected to be visited. This
* cost is somewhat arbitrarily set at 50x cpu_operator_cost per page
* touched. The number of such pages is btree tree height plus one (ie,
- * we charge for the leaf page too). As above, charge once per SA scan.
+ * we charge for the leaf page too). As above, charge once per estimated
+ * primitive SA scan.
*/
descentCost = (index->tree_height + 1) * DEFAULT_PAGE_CPU_MULTIPLIER * cpu_operator_cost;
costs.indexStartupCost += descentCost;
- costs.indexTotalCost += costs.num_sa_scans * descentCost;
+ costs.indexTotalCost += num_sa_scans * descentCost;
/*
* If we can get an estimate of the first column's ordering correlation C
--
2.40.1
view thread (3+ 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], [email protected], [email protected]
Subject: Re: Optimizing nbtree ScalarArrayOp execution, allowing multi-column ordered scans, skip scan
In-Reply-To: <CAH2-Wz=ksvN_sjcnD1+Bt-WtifRA5ok48aDYnq3pkKhxgMQpcw@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