public inbox for [email protected]help / color / mirror / Atom feed
Re: Optimizing nbtree ScalarArrayOp execution, allowing multi-column ordered scans, skip scan 4+ messages / 2 participants [nested] [flat]
* Re: Optimizing nbtree ScalarArrayOp execution, allowing multi-column ordered scans, skip scan @ 2023-11-28 17:19 Peter Geoghegan <[email protected]> 0 siblings, 1 reply; 4+ messages in thread From: Peter Geoghegan @ 2023-11-28 17:19 UTC (permalink / raw) To: Tomas Vondra <[email protected]>; +Cc: Matthias van de Meent <[email protected]>; PostgreSQL Hackers <[email protected]>; Tom Lane <[email protected]>; Jeff Davis <[email protected]>; benoit <[email protected]>; Alexander Korotkov <[email protected]> On Tue, Nov 28, 2023 at 4:29 AM Tomas Vondra <[email protected]> wrote: > I haven't looked at the code, but I decided to do a bit of blackbox perf > and stress testing, to get some feeling of what to expect in terms of > performance improvements, and see if there happen to be some unexpected > regressions. Attached is a couple simple bash scripts doing a > brute-force test with tables of different size / data distribution, > number of values in the SAOP expression, etc. My own stress-testing has focussed on the two obvious extremes for this patch, using variants of pgbench with SAOP SELECTs on pgbench_accounts: 1. The case where there is almost no chance of finding any two index tuples together on the same page, because the constants are completely random. This workload makes the patch's attempts at "coalescing together" index page reads pure overhead, with no possible benefit. Obviously that's a cost that needs to be kept under control. 2. The case where there are 255 of tuples with distinct values that are clustered together (both in the key space and in physical index pages). Usually they'll span two index pages, but they might all fit together on one index page, allowing us to descend to it directly and read it only once. With 32 clients, I typically see a regression of about 1.5% for the first case relative to master, measured in throughput/TPS. The second case typically sees throughput that's ~4.8x master (i.e. a ~380% increase). I consider both of these extremes to be fairly unrealistic. With fewer array constants, the speed-ups you'll see in sympathetic cases are still very significant, but nothing like 4.8x. They're more like the 30% numbers that you saw. As you know, I'm not actually all that excited about cases like 2 -- it's not where users are likely to benefit from the patch. The truly interesting cases are those cases where we can completely avoid heap accesses in the first place (not just *repeat* accesses to the same index pages), due to the patch's ability to consistently use index quals rather than filter quals. It's not that hard to show cases where there are 100x+ fewer pages accessed -- often with cases have very few array constants. It's just that these cases aren't that interesting from a performance validation point of view -- it's obvious that filter quals are terrible. Another thing that the patch does particularly well on is cases where the array keys don't have any matches at all, but there is significant clustering (relatively common when multiple SAOPs are used as index quals, which becomes far more likely due to the planner changes). We don't just skip over parts of the index that aren't relevant -- we also skip over parts of the arrays that aren't relevant. Some of my adversarial test cases that take ~1 millisecond for the patch to execute will practically take forever on master (I had to have my test suite not run those tests against master). You just need lots of array keys. What master does on those adversarial cases with billions of distinct combinations of array keys (not that unlikely if there are 4 or 5 SAOPs with mere hundreds or thousands of array keys each) is so inefficient that we might as well call it infinitely slower than the patch. This is interesting to me from a performance robustness/stability point of view. The slowest kind of SAOP index scan with the patch becomes a full index scan -- just as it would be if we were using any type of non-SOAP qual before now. The worst case is a lot easier to reason about. > I'm not convinced this is a problem we have to solve. It's possible it > only affects cases that are implausible in practice (the script forces a > particular scan type, and maybe it would not be picked in practice). But > maybe it's fixable ... I would expect the patch to do quite well (relative to what is actually possible) on cases like the two extremes that I've focussed on so far. It seems possible that it will do less well on cases that are somewhere in the middle (that also have lots of distinct values on each page). We effectively do a linear search on a page that we know has at least one more match (following a precheck that uses the high key). We hope that the next match (for the next array value) closely follows an initial match. But what if there are only 2 or 3 matches on each leaf page, that are spaced relatively far apart? You're going to have to grovel through the whole page. It's not obvious that that's a problem to be fixed -- we're still only descending the index once and still only locking the leaf page once, so we'll probably still win relative to master. And it's not that easy to imagine beating a linear search -- it's not like there is just one "next value" to search for in these cases. But it's something that deserves further consideration. -- Peter Geoghegan ^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: Optimizing nbtree ScalarArrayOp execution, allowing multi-column ordered scans, skip scan @ 2023-11-28 23:52 Peter Geoghegan <[email protected]> parent: Peter Geoghegan <[email protected]> 0 siblings, 1 reply; 4+ messages in thread From: Peter Geoghegan @ 2023-11-28 23:52 UTC (permalink / raw) To: Tomas Vondra <[email protected]>; +Cc: Matthias van de Meent <[email protected]>; PostgreSQL Hackers <[email protected]>; Tom Lane <[email protected]>; Jeff Davis <[email protected]>; benoit <[email protected]>; Alexander Korotkov <[email protected]> On Tue, Nov 28, 2023 at 9:19 AM Peter Geoghegan <[email protected]> wrote: > > I'm not convinced this is a problem we have to solve. It's possible it > > only affects cases that are implausible in practice (the script forces a > > particular scan type, and maybe it would not be picked in practice). But > > maybe it's fixable ... > > I would expect the patch to do quite well (relative to what is > actually possible) on cases like the two extremes that I've focussed > on so far. It seems possible that it will do less well on cases that > are somewhere in the middle (that also have lots of distinct values on > each page). Actually, I think that it's more likely that the problems that you saw are related to low cardinality data, which seems like it might not be a great fit for the heuristics that the patch uses to decide whether to continue the ongoing primitive index scan, or start a new one instead. I'm referring to the heuristics I describe here: https://postgr.es/m/CAH2-WzmTHoCsOmSgLg=yyft9LoERtuCKXyG2GZn+28PzonFA_g@mail.gmail.com The patch itself discusses these heuristics in a large comment block after the point that _bt_checkkeys() calls _bt_advance_array_keys(). I hardly paid any attention to low cardinality data in my performance validation work -- it was almost always indexes that had few or no indexes (just pgbench_accounts if we're talking pure stress-tests), just because those are more complicated, and so seemed more important. I'm not quite prepared to say that there is definitely a problem here, right this minute, but if there was then it wouldn't be terribly surprising (the problems are usually wherever it is that I didn't look for them). Attached is a sample of my debug instrumentation for one such query, based on running the test script that Tomas posted -- thanks for writing this script, Tomas (I'll use it as the basis for some of my own performance validation work going forward). I don't mind sharing the patch that outputs this stuff if anybody is interested (it's kind of a monstrosity, so I'm disinclined to post it with the patch until I have a reason). Even without this instrumentation, you can get some idea of the kinds of issues I'm talking about just by viewing EXPLAIN ANALYZE output for a bitmap index scan -- that breaks out the index page accesses separately, which is a number that we should expect to remain lower than what the master branch shows in approximately all cases. While I still think that we need heuristics that apply speculative criteria to decide whether or not going to the next page directly (when we have a choice at all), that doesn't mean that the v7 heuristics can't be improved on, with a little more thought. It's a bit tricky, since we're probably also benefiting from the same heuristics all the time -- probably even for this same test case. We do lose against the master branch, on balance, and by enough to concern me, though. (I don't want to promise that it'll never happen at all, but it should be very limited, which this wasn't.) I didn't bother to ascertain how much longer it takes to execute the query, since that question seems rather beside the point. The important thing to me is whether or not this behavior actually makes sense, all things considered, and what exactly can be done about it if it doesn't make sense. I will need to think about this some more. This is just a status update. Thanks -- Peter Geoghegan Attachments: [application/x-bzip2] index_walk_dump.txt.bz2 (86.5K, ../../CAH2-Wz=paSJk31VtMjYhHLAChCuD-Q=Qds-fTRjpC_L0dzOiXw@mail.gmail.com/2-index_walk_dump.txt.bz2) download ^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: Optimizing nbtree ScalarArrayOp execution, allowing multi-column ordered scans, skip scan @ 2023-11-29 00:57 Peter Geoghegan <[email protected]> parent: Peter Geoghegan <[email protected]> 0 siblings, 0 replies; 4+ messages in thread From: Peter Geoghegan @ 2023-11-29 00:57 UTC (permalink / raw) To: Tomas Vondra <[email protected]>; +Cc: Matthias van de Meent <[email protected]>; PostgreSQL Hackers <[email protected]>; Tom Lane <[email protected]>; Jeff Davis <[email protected]>; benoit <[email protected]>; Alexander Korotkov <[email protected]> On Tue, Nov 28, 2023 at 3:52 PM Peter Geoghegan <[email protected]> wrote: > While I still think that we need heuristics that apply speculative > criteria to decide whether or not going to the next page directly > (when we have a choice at all), that doesn't mean that the v7 > heuristics can't be improved on, with a little more thought. It's a > bit tricky, since we're probably also benefiting from the same > heuristics all the time -- probably even for this same test case. Correction: this particular test case happens to be one where the optimal strategy is to do *exactly* what the master branch does currently. The master branch is unbeatable, so the only reasonable goal for the patch is to not lose (or to lose by no more than a completely negligible amount). I'm now prepared to say that this behavior is not okay -- I definitely need to fix this. It's a bug. Because each distinct value never fits on one leaf page (it's more like 1.5 - 2 pages, even though we're deduplicating heavily), and because Postgres 12 optimizations are so effective with low cardinality/posting-list-heavy indexes such as this, we're bound to lose quite often. The only reason it doesn't happen _every single time_ we descend the index is because the test script uses CREATE INDEX, rather than using retail inserts (I tend to prefer the latter for this sort of analysis). Since nbtsort.c isn't as clever/aggressive about suffix truncation as the nbtsplitloc.c split strategies would have been, had we used them (had there been retail inserts), many individual leaf pages are left with high keys that aren't particularly good targets for the high key precheck optimization (see Postgres 12 commit 29b64d1d). If I wanted to produce a truly adversarial case for this issue (which this is already close to), I'd go with the following: 1. Retail inserts that leave each leaf page full of one single value, which will allow each high key to still make a "clean break" from the right sibling page -- it'll have the right sibling's value. Maybe insert 1200 - 1300 tuples per distinct index value for this. In other words, bulk loading that results in an index that never has to append a heap TID tiebreaker during suffix truncation, but comes very close to needing to. Bulk loading where nbtsplitloc.c needs to use SPLIT_MANY_DUPLICATES all the time, but never quite gets to the point of needing a SPLIT_SINGLE_VALUE split. 2. A SAOP query with an array with every second value in the index as an element. Something like "WHERE arr in (2, 4, 6, 8, ...)". The patch will read every single leaf page, whereas master will *reliably* only read every second leaf page. I didn't need to "trick" the patch in a contrived sort of way to get this bad outcome -- this scenario is fairly realistic. So this behavior is definitely not something that I'm prepared to defend. As I said, it's a bug. It'll be fixed in the next revision. -- Peter Geoghegan ^ permalink raw reply [nested|flat] 4+ messages in thread
* [PATCH v1 2/8] convert ParallelBitmapHeapState->state to an atomic @ 2026-07-09 18:38 Nathan Bossart <[email protected]> 0 siblings, 0 replies; 4+ messages in thread From: Nathan Bossart @ 2026-07-09 18:38 UTC (permalink / raw) --- src/backend/executor/nodeBitmapHeapscan.c | 21 ++++++--------------- 1 file changed, 6 insertions(+), 15 deletions(-) diff --git a/src/backend/executor/nodeBitmapHeapscan.c b/src/backend/executor/nodeBitmapHeapscan.c index 83d6478bc2b..f2bb487bf10 100644 --- a/src/backend/executor/nodeBitmapHeapscan.c +++ b/src/backend/executor/nodeBitmapHeapscan.c @@ -79,7 +79,6 @@ typedef enum /* ---------------- * ParallelBitmapHeapState information * tbmiterator iterator for scanning current pages - * mutex mutual exclusion for state * state current state of the TIDBitmap * cv conditional wait variable * ---------------- @@ -87,8 +86,7 @@ typedef enum typedef struct ParallelBitmapHeapState { dsa_pointer tbmiterator; - slock_t mutex; - SharedBitmapState state; + pg_atomic_uint32 state; ConditionVariable cv; } ParallelBitmapHeapState; @@ -228,9 +226,7 @@ BitmapHeapNext(BitmapHeapScanState *node) static inline void BitmapDoneInitializingSharedState(ParallelBitmapHeapState *pstate) { - SpinLockAcquire(&pstate->mutex); - pstate->state = BM_FINISHED; - SpinLockRelease(&pstate->mutex); + pg_atomic_write_membarrier_u32(&pstate->state, BM_FINISHED); ConditionVariableBroadcast(&pstate->cv); } @@ -480,11 +476,8 @@ BitmapShouldInitializeSharedState(ParallelBitmapHeapState *pstate) while (1) { - SpinLockAcquire(&pstate->mutex); - state = pstate->state; - if (pstate->state == BM_INITIAL) - pstate->state = BM_INPROGRESS; - SpinLockRelease(&pstate->mutex); + state = BM_INITIAL; + pg_atomic_compare_exchange_u32(&pstate->state, &state, BM_INPROGRESS); /* Exit if bitmap is done, or if we're the leader. */ if (state != BM_INPROGRESS) @@ -538,9 +531,7 @@ ExecBitmapHeapInitializeDSM(BitmapHeapScanState *node, pstate->tbmiterator = 0; - /* Initialize the mutex */ - SpinLockInit(&pstate->mutex); - pstate->state = BM_INITIAL; + pg_atomic_init_u32(&pstate->state, BM_INITIAL); ConditionVariableInit(&pstate->cv); @@ -565,7 +556,7 @@ ExecBitmapHeapReInitializeDSM(BitmapHeapScanState *node, if (dsa == NULL) return; - pstate->state = BM_INITIAL; + pg_atomic_write_u32(&pstate->state, BM_INITIAL); if (DsaPointerIsValid(pstate->tbmiterator)) tbm_free_shared_area(dsa, pstate->tbmiterator); -- 2.50.1 (Apple Git-155) --Ot5x3ffkWEuxilWO Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename=v1-0003-convert-FixedParallelState-last_xlog_end-to-an-at.patch ^ permalink raw reply [nested|flat] 4+ messages in thread
end of thread, other threads:[~2026-07-09 18:38 UTC | newest] Thread overview: 4+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2023-11-28 17:19 Re: Optimizing nbtree ScalarArrayOp execution, allowing multi-column ordered scans, skip scan Peter Geoghegan <[email protected]> 2023-11-28 23:52 ` Peter Geoghegan <[email protected]> 2023-11-29 00:57 ` Peter Geoghegan <[email protected]> 2026-07-09 18:38 [PATCH v1 2/8] convert ParallelBitmapHeapState->state to an atomic Nathan Bossart <[email protected]>
This inbox is served by agora; see mirroring instructions for how to clone and mirror all data and code used for this inbox