Обсуждение: MDAM techniques and Index Skip Scan patch
I returned to the 1995 paper "Efficient Search of Multidimensional B-Trees" [1] as part of the process of reviewing v39 of the skip scan patch, which was posted back in May. It's a great paper, and anybody involved in the skip scan effort should read it thoroughly (if they haven't already). It's easy to see why people get excited about skip scan [2]. But there is a bigger picture here. I don't necessarily expect to come away from this discussion with a much better high level architecture for the patch, or any kind of deeper insight, or even a frame of reference for further discussion. I just think that we ought to *try* to impose some order on this stuff. Like many difficult patches, the skip scan patch is not so much troubled by problems with the implementation as it is troubled by *ambiguity* about the design. Particularly concerning how skip scan meshes with existing designs, as well as future designs -- particularly designs for other MDAM techniques. I've started this thread to have a big picture conversation about how to think about these things. Many other MDAM techniques also seem highly appealing. Much of the MDAM stuff is for data warehousing use-cases, while skip scan/loose index scan is seen as more of an OLTP thing. But they are still related, clearly. I'd like to also talk about another patch, that ISTM had that same quality -- it was also held back by high level design uncertainty. Back in 2018, Tom abandoned a patch that transformed a star-schema style query with left outer joins on dimension tables with OR conditions, into an equivalent query that UNIONs together 2 distinct queries [3][4]. Believe it or not, I am now reminded of that patch by the example of "IN() Lists", from page 5 of the paper. We see this example SQL query: SELECT date, item_class, store, sum(total_sales) FROM sales WHERE date between '06/01/95' and '06/30/95' and item_class IN (20,35,50) and store IN (200,250) GROUP BY dept, date, item_class, store; Granted, this SQL might not seem directly relevant to Tom's patch at first -- there is no join for the optimizer to even try to eliminate, which was the whole basis of Jim Nasby's original complaint, which is what spurred Tom to write the patch in the first place. But hear me out: there is still a fact table (the sales table) with some dimensions (the 'D' from 'MDAM') shown in the predicate. Moreover, the table (and this SQL query) drives discussion of an optimization involving transforming a predicate with many ORs (which is explicitly said to be logically/semantically equivalent to the IN() lists from the query). They transform the query into a bunch of disjunct clauses that can easily be independently executed, and combined at the end (see also "General OR Optimization" on page 6 of the paper). Also...I'm not entirely sure that the intended underlying "physical plan" is truly free of join-like scans. If you squint just right, you might see something that you could think of as a "physical join" (at least very informally). The whole point of this particular "IN() Lists" example is that we get to the following, for each distinct "dept" and "date" in the table: dept=1, date='06/04/95', item_class=20, store=200 dept=1, date='06/04/95', item_class=20, store=250 dept=1, date='06/04/95', item_class=35, store=200 dept=1, date='06/04/95', item_class=35, store=250 dept=1, date='06/04/95', item_class=50, store=200 dept=1, date='06/04/95', item_class=50, store=250 There are 2400 such accesses in total after transformation -- imagine additional lines like these, for every distinct combination of dept and date (only for those dates that actually had sales, which they enumerate up-front), for store 200 and 250, and item_class 20, 35, and 50. This adds up to 2400 lines in total. Even 2400 index probes will be much faster than a full table scan, given that this is a large fact table. The "sales" table is a clustered index whose keys are on the columns "(dept, date, item_class, store)", per note at the top of page 4. The whole point is to avoid having any secondary indexes on this fact table, without getting a full scan. We can just probe the primary key 2400 times instead, following this transformation. No need for secondary indexes. The plan can be thought of as a DAG, at least informally. This is also somewhat similar to what Tom was thinking about back in 2018. Tom had to deduplicate rows during execution (IIRC using a UNION style ad-hoc approach that sorted on TIDs), whereas I think that they can get away with skipping that extra step. Page 7 says "MDAM removes duplicates before reading the data, so it does not have to do any post read operations to accomplish duplicate elimination (a common problem with OR optimization)". My general concern is that the skip scan patch may currently be structured in a way that paints us into a corner, MDAM-wise. Note that the MDAM paper treats skipping a prefix of columns as a case where the prefix is handled by pretending that there is a clause that looks like this: "WHERE date between -inf AND +inf" -- which is not so different from the original sales SQL query example that I have highlighted. We don't tend to think of queries like this (like my sales query) as in any way related to skip-scan, because we don't imagine that there is any skipping going on. But maybe we should recognize the similarities. BTW, these imaginary -inf/+inf values seem to me to be just like the sentinel values already used inside nbtree, for pivot tuples -- they have explicit -inf values for truncated suffix key columns, and you can think of a rightmost page as having a +inf high key, per the L&Y paper. Wearing my B-Tree hat, I don't see much difference between imaginary -inf/+inf values, and values from the BETWEEN "date" range from the example SQL query. I have in the past wondered if _bt_get_endpoint() should have been implemented that way -- we could go through _bt_search() instead, and get rid of that code. All we need is insertion scan keys that can explicitly contain the same -inf/+inf sentinel values. Maybe this also allows us to get rid of BTScanInsertData.nextkey semantics (not sure offhand). Another more concrete concern about the patch series comes from the backwards scan stuff. This is added by a later patch in the patch series, "v39-0004-Extend-amskip-implementation-for-Btree.patch". It strikes me as a bad thing that we cannot just do leaf-page-at-a-time processing, without usually needing to hold a pin on the leaf page. After all, ordinary backwards scans manage to avoid that today, albeit by using trickery inside _bt_walk_left(). MDAM-style "Maintenance of Index Order" (as described on page 8) seems like a good goal for us here. I don't like the idea of doing ad-hoc duplicate TID elimination inside nbtree, across calls made from the executor (whether it's during backwards skip scans, or at any other time). Not because it seems to go against the approach taken by the MDAM paper (though it does); just because it seems kludgy. (I think that Tom felt the same way about the TID deduplication stuff in his own patch back in 2018, too.) Open question: What does all of this MDAM business mean for ScalarArrayOpExpr, if anything? I freely admit that I could easily be worrying over nothing here. But if I am, I'd really like to know *why* that's the case. [1] http://vldb.org/conf/1995/P710.PDF [2] https://blog.timescale.com/blog/how-we-made-distinct-queries-up-to-8000x-faster-on-postgresql/ [3] https://www.postgresql.org/message-id/flat/7f70bd5a-5d16-e05c-f0b4-2fdfc8873489%40BlueTreble.com [4] https://www.postgresql.org/message-id/flat/14593.1517581614%40sss.pgh.pa.us#caf373b36332f25acb7673bff331c95e -- Peter Geoghegan
Great to see some interest in the skip scan patch series again! > Like many difficult patches, the skip scan patch is not so much troubled by > problems with the implementation as it is troubled by > *ambiguity* about the design. Particularly concerning how skip scan meshes > with existing designs, as well as future designs -- particularly designs for > other MDAM techniques. I've started this thread to have a big picture > conversation about how to think about these things. Many other MDAM > techniques also seem highly appealing. I think it is good to have this discussion. In my opinion, Postgres could make really good use of some of the described MDAMtechniques. > Much of the MDAM stuff is for data warehousing use-cases, while skip > scan/loose index scan is seen as more of an OLTP thing. But they are still > related, clearly. FWIW I think skip scan is very much data warehousing use-case related - hence why the TimescaleDb people in your [2] referenceimplemented a simple form of it already for their extension. Skip scan is a really useful feature for large datasets. However, I agree it is only one part of the bigger MDAM picture. > > My general concern is that the skip scan patch may currently be structured in > a way that paints us into a corner, MDAM-wise. > One of the concerns I raised before was that the patch may be thinking too simplistically on some things, that would makeit difficult to adopt more complex optimizations in the future. One concrete example can be illustrated by a differentquery on the sales table of the paper's example: SELECT DISTINCT dept, date WHERE item_class = 100 This should skip with prefix of (dept, date). Suppose we're at (dept, date) = (1, 2021-01-01) and it's skipping to the nextprefix, the patch just implements what the MDAM paper describes as the 'probing' step. It finds the beginning of thenext prefix. This could be for example (dept, date, item_class) = (1, 2021-01-02, 1). From there onwards, it would justscan the index until it finds item_class=100. What it should do however, is to first 'probe' for the next prefix valueand then skip directly to (1, 2021-01-02, 100) (skipping item_class 1-99 altogether). The problem if it doesn't supportthis is that skip scan could have a quite unpredictable performance, because sometimes it'll end up going throughmost of the index where it should be skipping. A while ago, I spent quite some time trying to come up with an implementation that would work in this more general case.The nice thing is that with such a more generic implementation, you get almost all the features from the MDAM paperalmost for free. I focused on the executor code, not on the planner code - the planner code is for the DISTINCT skippart very similar to the original patch and I hacked in a way to make it choose a 'skip scan' also for non-DISTINCT queriesfor testing purposes. For this discussion about MDAM, the planner part is less relevant though. There's still a lotof discussion and work on the planner-side too, but I think that is completely independent from each other. The more generic patch I originally posted in [1], together with some technical considerations. That was quite a while agoso it obviously doesn't apply anymore on master. Therefore, I've attached a rebased version. Unfortunately, it's stillbased on an older version of the UniqueKeys patch - but since that patch is all planner machinery as well, it doesn'tmatter so much for the discussion about the executor code either. I believe if we want something that fits better with future MDAM use cases, we should take a closer look at the executorcode of this patch to drive this discussion. The logic is definitely more complex than the original patch, howeverI believe it is also more flexible and future-proof. > > Another more concrete concern about the patch series comes from the > backwards scan stuff. This is added by a later patch in the patch series, "v39- > 0004-Extend-amskip-implementation-for-Btree.patch". It strikes me as a bad > thing that we cannot just do leaf-page-at-a-time processing, without usually > needing to hold a pin on the leaf page. > After all, ordinary backwards scans manage to avoid that today, albeit by > using trickery inside _bt_walk_left(). MDAM-style "Maintenance of Index > Order" (as described on page 8) seems like a good goal for us here. I don't > like the idea of doing ad-hoc duplicate TID elimination inside nbtree, across > calls made from the executor (whether it's during backwards skip scans, or at > any other time). Not because it seems to go against the approach taken by > the MDAM paper (though it does); just because it seems kludgy. (I think that > Tom felt the same way about the TID deduplication stuff in his own patch > back in 2018, > too.) It's good to mention that the patch I attached does proper 'leaf-page-at-a-time' processing, so it avoids the problem youdescribe with v39. It is implemented instead in the same way as a "regular" index scan - we process the full leaf pageand store the matched tuples in the local state. If a DISTINCT scan wants to do a skip, we check our local state firstif that skipping would be possible with the matched tuples from the current page. Then we avoid double work and alsothe need to look at the same page again. > Open question: What does all of this MDAM business mean for > ScalarArrayOpExpr, if anything? > This is a really interesting combination actually. I think, ideally, you'd probably get rid of it and provide full supportfor that with the 'skip' based approach (essentially the ScalarArrayOpExpr seems to do some form of skipping already- it transforms x IN (1,2,3) into 3 separate index scans for x). However, even without doing any work on it, it actually interacts nicely with the skip based approach. As an example, here's some queries based on the 'sales' table of the paper with some data in it (18M rows total, see sales_query.sqlattachment for the full example): -- terminology from paper: "intervening range predicate" select date, sum(total_sales) from sales where dept between 2 and 3 and date between '2021-01-05' and '2021-01-10' and item_class=20 and store=250 group by dept, date ; Patch: Execution Time: 0.368 ms Master: Execution Time: 416.792 ms -- terminology from paper: "missing key predicate" select date, sum(total_sales) from sales where date between '2021-01-05' and '2021-01-10' and item_class=20 and store=250 group by dept, date ; Patch: Execution Time: 0.667 ms Master: Execution Time: 654.684 ms -- terminology from paper: "IN lists" -- this is similar to the query from your example with an IN list -- in the current patch, this query is done with a skip scan with skip prefix (dept, date) and then the ScalarOpArray foritem_class=(20,30,50) select date, sum(total_sales) from sales where date between '2021-01-05' and '2021-01-10' and item_class in (20, 30, 50) and store=250 group by dept, date ; Patch: Execution Time: 1.767 ms Master: Execution Time: 629.792 ms The other mentioned MDAM optimizations in the paper (NOT =, general OR) are not implemented but don't seem to be conflictingat all with the current implementation - they seem to be just a matter of transforming the expressions into theright form. From the patch series above, v9-0001/v9-0002 is the UniqueKeys patch series, which focuses on the planner. v2-0001 is Dmitry'spatch that extends it to make it possible to use UniqueKeys for the skip scan. Both of these are unfortunately stillolder patches, but because they are planner machinery they are less relevant to the discussion about the executor here. Patch v2-0002 contains most of my work and introduces all the executor logic for the skip scan and hooks up the planner forDISTINCT queries to use the skip scan. Patch v2-0003 is a planner hack that makes the planner pick a skip scan on virtually every possibility. This also enablesthe skip scan on the queries above that don't have a DISTINCT but where it could be useful. -Floris [1] https://www.postgresql.org/message-id/c5c5c974714a47f1b226c857699e8680@opammb0561.comp.optiver.com
Вложения
> On Thu, Oct 21, 2021 at 07:16:00PM -0700, Peter Geoghegan wrote: > > My general concern is that the skip scan patch may currently be > structured in a way that paints us into a corner, MDAM-wise. > > Note that the MDAM paper treats skipping a prefix of columns as a case > where the prefix is handled by pretending that there is a clause that > looks like this: "WHERE date between -inf AND +inf" -- which is not so > different from the original sales SQL query example that I have > highlighted. We don't tend to think of queries like this (like my > sales query) as in any way related to skip-scan, because we don't > imagine that there is any skipping going on. But maybe we should > recognize the similarities. To avoid potential problems with extensibility in this sense, the implementation needs to explicitly work with sets of disjoint intervals of values instead of simple prefix size, one set of intervals per scan key. An interesting idea, doesn't seem to be a big change in terms of the patch itself.
Hi Peter, On 10/21/21 22:16, Peter Geoghegan wrote: > I returned to the 1995 paper "Efficient Search of Multidimensional > B-Trees" [1] as part of the process of reviewing v39 of the skip scan > patch, which was posted back in May. It's a great paper, and anybody > involved in the skip scan effort should read it thoroughly (if they > haven't already). It's easy to see why people get excited about skip > scan [2]. But there is a bigger picture here. > Thanks for starting this thread ! The Index Skip Scan patch could affect a lot of areas, so keeping MDAM in mind is definitely important. However, I think the key part to progress on the "core" functionality (B-tree related changes) is to get the planner functionality in place first. Hopefully we can make progress on that during the November CommitFest based on Andy's patch. Best regards, Jesper
Hi, On Sat, Oct 23, 2021 at 07:30:47PM +0000, Floris Van Nee wrote: > > From the patch series above, v9-0001/v9-0002 is the UniqueKeys patch series, > which focuses on the planner. v2-0001 is Dmitry's patch that extends it to > make it possible to use UniqueKeys for the skip scan. Both of these are > unfortunately still older patches, but because they are planner machinery > they are less relevant to the discussion about the executor here. Patch > v2-0002 contains most of my work and introduces all the executor logic for > the skip scan and hooks up the planner for DISTINCT queries to use the skip > scan. Patch v2-0003 is a planner hack that makes the planner pick a skip > scan on virtually every possibility. This also enables the skip scan on the > queries above that don't have a DISTINCT but where it could be useful. The patchset doesn't apply anymore: http://cfbot.cputube.org/patch_36_1741.log === Applying patches on top of PostgreSQL commit ID a18b6d2dc288dfa6e7905ede1d4462edd6a8af47 === === applying patch ./v2-0001-Extend-UniqueKeys.patch [...] patching file src/include/optimizer/paths.h Hunk #2 FAILED at 299. 1 out of 2 hunks FAILED -- saving rejects to file src/include/optimizer/paths.h.rej Could you send a rebased version? In the meantime I will change the status on the cf app to Waiting on Author.
> > Could you send a rebased version? In the meantime I will change the status > on the cf app to Waiting on Author. Attached a rebased version.
Вложения
> On Thu, Jan 13, 2022 at 03:27:08PM +0000, Floris Van Nee wrote: > > > > Could you send a rebased version? In the meantime I will change the status > > on the cf app to Waiting on Author. > > Attached a rebased version. FYI, I've attached this thread to the CF item as an informational one, but as there are some patches posted here, folks may get confused. For those who have landed here with no context, I feel obliged to mention that now there are two alternative patch series posted under the same CF item: * the original one lives in [1], waiting for reviews since the last May * an alternative one posted here from Floris [1]: https://www.postgresql.org/message-id/flat/20200609102247.jdlatmfyeecg52fi@localhost
Hi, On Fri, Jan 14, 2022 at 08:55:26AM +0100, Dmitry Dolgov wrote: > > FYI, I've attached this thread to the CF item as an informational one, > but as there are some patches posted here, folks may get confused. For > those who have landed here with no context, I feel obliged to mention > that now there are two alternative patch series posted under the same > CF item: > > * the original one lives in [1], waiting for reviews since the last May > * an alternative one posted here from Floris Ah, I indeed wasn't sure of which patchset(s) should actually be reviewed. It's nice to have the alternative approach threads linkied in the commit fest, but it seems that the cfbot will use the most recent attachments as the only patchset, thus leaving the "original" one untested. I'm not sure of what's the best approach in such situation. Maybe creating a different CF entry for each alternative, and link the other cf entry on the cf app using the "Add annotations" or "Links" feature rather than attaching threads?
> On Fri, Jan 14, 2022 at 04:03:41PM +0800, Julien Rouhaud wrote: > Hi, > > On Fri, Jan 14, 2022 at 08:55:26AM +0100, Dmitry Dolgov wrote: > > > > FYI, I've attached this thread to the CF item as an informational one, > > but as there are some patches posted here, folks may get confused. For > > those who have landed here with no context, I feel obliged to mention > > that now there are two alternative patch series posted under the same > > CF item: > > > > * the original one lives in [1], waiting for reviews since the last May > > * an alternative one posted here from Floris > > Ah, I indeed wasn't sure of which patchset(s) should actually be reviewed. > It's nice to have the alternative approach threads linkied in the commit fest, > but it seems that the cfbot will use the most recent attachments as the only > patchset, thus leaving the "original" one untested. > > I'm not sure of what's the best approach in such situation. Maybe creating a > different CF entry for each alternative, and link the other cf entry on the cf > app using the "Add annotations" or "Links" feature rather than attaching > threads? I don't mind having all of the alternatives under the same CF item, only one being tested seems to be only a small limitation of cfbot.
Hi, On 2022-01-22 22:37:19 +0100, Dmitry Dolgov wrote: > > On Fri, Jan 14, 2022 at 04:03:41PM +0800, Julien Rouhaud wrote: > > Hi, > > > > On Fri, Jan 14, 2022 at 08:55:26AM +0100, Dmitry Dolgov wrote: > > > > > > FYI, I've attached this thread to the CF item as an informational one, > > > but as there are some patches posted here, folks may get confused. For > > > those who have landed here with no context, I feel obliged to mention > > > that now there are two alternative patch series posted under the same > > > CF item: > > > > > > * the original one lives in [1], waiting for reviews since the last May > > > * an alternative one posted here from Floris > > > > Ah, I indeed wasn't sure of which patchset(s) should actually be reviewed. > > It's nice to have the alternative approach threads linkied in the commit fest, > > but it seems that the cfbot will use the most recent attachments as the only > > patchset, thus leaving the "original" one untested. > > > > I'm not sure of what's the best approach in such situation. Maybe creating a > > different CF entry for each alternative, and link the other cf entry on the cf > > app using the "Add annotations" or "Links" feature rather than attaching > > threads? > > I don't mind having all of the alternatives under the same CF item, only > one being tested seems to be only a small limitation of cfbot. IMO it's pretty clear that having "duelling" patches below one CF entry is a bad idea. I think they should be split, with inactive approaches marked as returned with feeback or whatnot. Either way, currently this patch fails on cfbot due to a new GUC: https://api.cirrus-ci.com/v1/artifact/task/5134905372835840/log/src/test/recovery/tmp_check/regression.diffs https://cirrus-ci.com/task/5134905372835840 Greetings, Andres Freund
> On Mon, Mar 21, 2022 at 06:34:09PM -0700, Andres Freund wrote: > > > I don't mind having all of the alternatives under the same CF item, only > > one being tested seems to be only a small limitation of cfbot. > > IMO it's pretty clear that having "duelling" patches below one CF entry is a > bad idea. I think they should be split, with inactive approaches marked as > returned with feeback or whatnot. On the other hand even for patches with dependencies (i.e. the patch A depends on the patch B) different CF items cause a lot of confusion for reviewers. I guess for various flavours of the same patch it would be even worse. But I don't have a strong opinion here. > Either way, currently this patch fails on cfbot due to a new GUC: > https://api.cirrus-ci.com/v1/artifact/task/5134905372835840/log/src/test/recovery/tmp_check/regression.diffs > https://cirrus-ci.com/task/5134905372835840 This seems to be easy to solve.
Вложения
On Tue, Mar 22, 2022 at 2:34 PM Andres Freund <andres@anarazel.de> wrote: > IMO it's pretty clear that having "duelling" patches below one CF entry is a > bad idea. I think they should be split, with inactive approaches marked as > returned with feeback or whatnot. I have the impression that this thread is getting some value from having a CF entry, as a multi-person collaboration where people are trading ideas and also making progress that no one wants to mark as returned, but it's vexing for people managing the CF because it's not really proposed for 15. Perhaps what we lack is a new status, "Work In Progress" or something?
Peter Geoghegan <pg@bowt.ie> writes: > Like many difficult patches, the skip scan patch is not so much > troubled by problems with the implementation as it is troubled by > *ambiguity* about the design. Particularly concerning how skip scan > meshes with existing designs, as well as future designs -- > particularly designs for other MDAM techniques. I've started this > thread to have a big picture conversation about how to think about > these things. Peter asked me off-list to spend some time thinking about the overall direction we ought to be pursuing here. I have done that, and here are a few modest suggestions. 1. Usually I'm in favor of doing this sort of thing in an index AM agnostic way, but here I don't see much point. All of the ideas at stake rely fundamentally on having a lexicographically-ordered multi column index; but we don't have any of those except btree, nor do I think we're likely to get any soon. This motivates the general tenor of my remarks below, which is "do it in access/nbtree/ not in the planner". 2. The MDAM paper Peter cited is really interesting. You can see fragments of those ideas in our existing btree code, particularly in the scan setup stuff that detects redundant or contradictory keys and determines a scan start strategy. The special handling we implemented awhile ago for ScalarArrayOp index quals is also a subset of what they were talking about. It seems to me that if we wanted to implement more of those ideas, the relevant work should almost all be done in nbtree proper. The planner would need only minor adjustments: btcostestimate would have to be fixed to understand the improvements, and there are some rules in indxpath.c that prevent us from passing "too complicated" sets of indexquals to the AM, which would need to be relaxed or removed altogether. 3. "Loose" indexscan (i.e., sometimes re-descend from the tree root to find the next index entry) is again something that seems like it's mainly nbtree's internal problem. Loose scan is interesting if we have index quals for columns that are after the first column that lacks an equality qual, otherwise not. I've worried in the past that we'd need planner/statistical support to figure out whether a loose scan is likely to be useful compared to just plowing ahead in the index. However, that seems to be rendered moot by the idea used in the current patchsets, ie scan till we find that we'll have to step off the current page, and re-descend at that point. (When and if we find that that heuristic is inadequate, we could work on passing some statistical data forward. But we don't need any in the v1 patch.) Again, we need some work in btcostestimate to understand how the index scan cost will be affected, but I still don't see any pressing need for major planner changes or plan tree contents changes. 4. I find each of the above ideas to be far more attractive than optimizing SELECT-DISTINCT-that-matches-an-index, so I don't really understand why the current patchsets seem to be driven largely by that single use-case. I wouldn't even bother with that for the initial patch. When we do get around to it, it still doesn't need major planner support, I think --- again fixing the cost estimation is the bulk of the work. Munro's original 2014 patch showed that we don't really need all that much to get the planner to build such a plan; the problem is to convince it that that plan will be cheap. In short: I would throw out just about all the planner infrastructure that's been proposed so far. It looks bulky, expensive, and drastically undercommented, and I don't think it's buying us anything of commensurate value. The part of the planner that actually needs serious thought is btcostestimate, which has been woefully neglected in both of the current patchsets. BTW, I've had a bee in my bonnet for a long time about whether some of nbtree's scan setup work could be done once during planning, rather than over again during each indexscan start. This issue might become more pressing if the work becomes significantly more complicated/expensive, which these ideas might cause. But it's a refinement that could be left for later --- and in any case, the responsibility would still fundamentally be nbtree's. I don't think the planner would do more than call some AM routine that could add decoration to an IndexScan plan node. Now ... where did I put my flameproof vest? regards, tom lane
Hi, On 2022-03-22 16:55:49 -0400, Tom Lane wrote: > 4. I find each of the above ideas to be far more attractive than > optimizing SELECT-DISTINCT-that-matches-an-index, so I don't really > understand why the current patchsets seem to be driven largely > by that single use-case. It's something causing plenty pain in production environments... Obviously it'd be even better if the optimization also triggered in cases like SELECT some_indexed_col FROM blarg GROUP BY some_indexed_col which seems to be what ORMs like to generate. > BTW, I've had a bee in my bonnet for a long time about whether some of > nbtree's scan setup work could be done once during planning, rather than > over again during each indexscan start. It does show up in simple-index-lookup heavy workloads. Not as a major thing, but it's there. And it's just architecturally displeasing :) Are you thinking of just moving the setup stuff in nbtree (presumably parts of _bt_first() / _bt_preprocess_keys()) or also stuff in ExecIndexBuildScanKeys()? The latter does show up a bit more heavily in profiles than nbtree specific setup, and given that it's generic executor type stuff, seems even more amenable to being moved to plan time. Greetings, Andres Freund
Andres Freund <andres@anarazel.de> writes: > On 2022-03-22 16:55:49 -0400, Tom Lane wrote: >> BTW, I've had a bee in my bonnet for a long time about whether some of >> nbtree's scan setup work could be done once during planning, rather than >> over again during each indexscan start. > It does show up in simple-index-lookup heavy workloads. Not as a major thing, > but it's there. And it's just architecturally displeasing :) > Are you thinking of just moving the setup stuff in nbtree (presumably parts of > _bt_first() / _bt_preprocess_keys()) or also stuff in > ExecIndexBuildScanKeys()? Didn't really have specifics in mind. The key stumbling block is that some (not all) of the work depends on knowing the specific values of the indexqual comparison keys, so while you could do that work in advance for constant keys, you'd still have to be prepared to do work at scan start for non-constant keys. I don't have a clear idea about how to factorize that effectively. A couple of other random ideas in this space: * I suspect that a lot of this work overlaps with the efforts that btcostestimate makes along the way to getting a cost estimate. So it's interesting to wonder whether we could refactor so that btcostestimate is integrated with this hypothetical plan-time key preprocessing and doesn't duplicate work. * I think that we run through most or all of that preprocessing logic even for internal catalog accesses, where we know darn well how the keys are set up. We ought to think harder about how we could short-circuit pointless work in those code paths. I don't think any of this is an essential prerequisite to getting something done for loose index scans, which ISTM ought to be the first point of attack for v16. Loose index scans per se shouldn't add much to the key preprocessing costs. But these ideas likely would be useful to look into before anyone starts on the more complicated preprocessing that would be needed for the ideas in the MDAM paper. regards, tom lane
> On Tue, Mar 22, 2022 at 04:55:49PM -0400, Tom Lane wrote: > Peter Geoghegan <pg@bowt.ie> writes: > > Like many difficult patches, the skip scan patch is not so much > > troubled by problems with the implementation as it is troubled by > > *ambiguity* about the design. Particularly concerning how skip scan > > meshes with existing designs, as well as future designs -- > > particularly designs for other MDAM techniques. I've started this > > thread to have a big picture conversation about how to think about > > these things. > > Peter asked me off-list to spend some time thinking about the overall > direction we ought to be pursuing here. I have done that, and here > are a few modest suggestions. Thanks. To make sure I understand your proposal better, I have a couple of questions: > In short: I would throw out just about all the planner infrastructure > that's been proposed so far. It looks bulky, expensive, and > drastically undercommented, and I don't think it's buying us anything > of commensurate value. Broadly speaking planner related changes proposed in the patch so far are: UniqueKey, taken from the neighbour thread about select distinct; list of uniquekeys to actually pass information about the specified loose scan prefix into nbtree; some verification logic to prevent applying skipping when it's not supported. I can imagine taking out UniqueKeys and passing loose scan prefix in some other form (the other parts seems to be essential) -- is that what you mean?
Dmitry Dolgov <9erthalion6@gmail.com> writes: > On Tue, Mar 22, 2022 at 04:55:49PM -0400, Tom Lane wrote: >> In short: I would throw out just about all the planner infrastructure >> that's been proposed so far. It looks bulky, expensive, and >> drastically undercommented, and I don't think it's buying us anything >> of commensurate value. > Broadly speaking planner related changes proposed in the patch so far > are: UniqueKey, taken from the neighbour thread about select distinct; > list of uniquekeys to actually pass information about the specified > loose scan prefix into nbtree; some verification logic to prevent > applying skipping when it's not supported. I can imagine taking out > UniqueKeys and passing loose scan prefix in some other form (the other > parts seems to be essential) -- is that what you mean? My point is that for pure loose scans --- that is, just optimizing a scan, not doing AM-based duplicate-row-elimination --- you do not need to pass any new data to btree at all. It can infer what to do on the basis of the set of index quals it's handed. The bigger picture here is that I think the reason this patch series has failed to progress is that it's too scattershot. You need to pick a minimum committable feature and get that done, and then you can move on to the next part. I think the minimum committable feature is loose scans, which will require a fair amount of work in access/nbtree/ but very little new planner code, and will be highly useful in their own right even if we never do anything more. In general I feel that the UniqueKey code is a solution looking for a problem, and that treating it as the core of the patchset is a mistake. We should be driving this work off of what nbtree needs to make progress, and not building more infrastructure elsewhere than we have to. Maybe we'll end up with something that looks like UniqueKeys, but I'm far from convinced of that. regards, tom lane
> On Wed, Mar 23, 2022 at 05:32:46PM -0400, Tom Lane wrote: > Dmitry Dolgov <9erthalion6@gmail.com> writes: > > On Tue, Mar 22, 2022 at 04:55:49PM -0400, Tom Lane wrote: > >> In short: I would throw out just about all the planner infrastructure > >> that's been proposed so far. It looks bulky, expensive, and > >> drastically undercommented, and I don't think it's buying us anything > >> of commensurate value. > > > Broadly speaking planner related changes proposed in the patch so far > > are: UniqueKey, taken from the neighbour thread about select distinct; > > list of uniquekeys to actually pass information about the specified > > loose scan prefix into nbtree; some verification logic to prevent > > applying skipping when it's not supported. I can imagine taking out > > UniqueKeys and passing loose scan prefix in some other form (the other > > parts seems to be essential) -- is that what you mean? > > My point is that for pure loose scans --- that is, just optimizing a scan, > not doing AM-based duplicate-row-elimination --- you do not need to pass > any new data to btree at all. It can infer what to do on the basis of the > set of index quals it's handed. > > The bigger picture here is that I think the reason this patch series has > failed to progress is that it's too scattershot. You need to pick a > minimum committable feature and get that done, and then you can move on > to the next part. I think the minimum committable feature is loose scans, > which will require a fair amount of work in access/nbtree/ but very little > new planner code, and will be highly useful in their own right even if we > never do anything more. > > In general I feel that the UniqueKey code is a solution looking for a > problem, and that treating it as the core of the patchset is a mistake. > We should be driving this work off of what nbtree needs to make progress, > and not building more infrastructure elsewhere than we have to. Maybe > we'll end up with something that looks like UniqueKeys, but I'm far from > convinced of that. I see. I'll need some thinking time about how it may look like (will probably return with more questions). The CF item could be set to RwF, what would you say, Jesper?
On 3/23/22 18:22, Dmitry Dolgov wrote: > > The CF item could be set to RwF, what would you say, Jesper? > We want to thank the community for the feedback that we have received over the years for this feature. Hopefully a future implementation can use Tom's suggestions to get closer to a committable solution. Here is the last CommitFest entry [1] for the archives. RwF [1] https://commitfest.postgresql.org/37/1741/ Best regards, Dmitry & Jesper
On Tue, Mar 22, 2022 at 4:06 PM Andres Freund <andres@anarazel.de> wrote: > Are you thinking of just moving the setup stuff in nbtree (presumably parts of > _bt_first() / _bt_preprocess_keys()) or also stuff in > ExecIndexBuildScanKeys()? > > The latter does show up a bit more heavily in profiles than nbtree specific > setup, and given that it's generic executor type stuff, seems even more > amenable to being moved to plan time. When I was working on the patch series that became the nbtree Postgres 12 work, this came up. At one point I discovered that using palloc0() for the insertion scankey in _bt_first() was a big problem with nested loop joins -- it became a really noticeable bottleneck with one of my test cases. I independently discovered what Tom must have figured out back in 2005, when he committed d961a56899. This led to my making the new insertion scan key structure (BTScanInsertData) not use dynamic allocation. So _bt_first() is definitely performance critical for certain types of queries. We could get rid of dynamic allocations for BTStackData in _bt_first(), perhaps. The problem is that there is no simple, reasonable proof of the maximum height on a B-tree, even though a B-Tree with more than 7 or 8 levels seems extraordinarily unlikely. You could also invent a slow path (maybe do what we do in _bt_insert_parent() in the event of a concurrent root page split/NULL stack), but that runs into the problem of being awkward to test, and pretty ugly. It's doable, but I wouldn't do it unless there was a pretty noticeable payoff. -- Peter Geoghegan
Peter Geoghegan <pg@bowt.ie> writes: > We could get rid of dynamic allocations for BTStackData in > _bt_first(), perhaps. The problem is that there is no simple, > reasonable proof of the maximum height on a B-tree, even though a > B-Tree with more than 7 or 8 levels seems extraordinarily unlikely. Start with a few entries preallocated, and switch to dynamically allocated space if there turn out to be more levels than that, perhaps? Not sure if it's worth the trouble. In any case, what I was on about is _bt_preprocess_keys() and adjacent code. I'm surprised that those aren't more expensive than one palloc in _bt_first. Maybe that logic falls through very quickly in simple cases, though. regards, tom lane
On Tue, Mar 22, 2022 at 1:55 PM Tom Lane <tgl@sss.pgh.pa.us> wrote: > Peter asked me off-list to spend some time thinking about the overall > direction we ought to be pursuing here. Thanks for taking a look! "5.5 Exploiting Key Prefixes" and "5.6 Ordered Retrieval" from "Modern B-Tree Techniques" are also good, BTW. The terminology in this area is a mess. MySQL calls SELECT-DISTINCT-that-matches-an-index "loose index scans". I think that you're talking about skip scan when you say "loose index scan". Skip scan is where there is an omitted prefix of columns in the SQL query -- omitted columns after the first column that lack an equality qual. Pretty sure that MySQL/InnoDB can't do that -- it can only "skip" to the extent required to make SELECT-DISTINCT-that-matches-an-index perform well, but that's about it. It might be useful for somebody to go write a "taxonomy of MDAM techniques", or a glossary. The existing "Loose indexscan" Postgres wiki page doesn't seem like enough. Something very high level and explicit, with examples, just so we don't end up talking at cross purposes too much. > 1. Usually I'm in favor of doing this sort of thing in an index AM > agnostic way, but here I don't see much point. All of the ideas at > stake rely fundamentally on having a lexicographically-ordered multi > column index; but we don't have any of those except btree, nor do > I think we're likely to get any soon. This motivates the general > tenor of my remarks below, which is "do it in access/nbtree/ not in > the planner". That was my intuition all along, but I didn't quite have the courage to say so -- sounds too much like something that an optimizer dilettante like me would be expected to say. :-) Seems like one of those things where lots of high level details intrinsically need to be figured out on-the-fly, at execution time, rather than during planning. Perhaps it'll be easier to correctly determine that a skip scan plan is the cheapest in practice than to accurately cost skip scan plans. If the only alternative is a sequential scan, then perhaps a very approximate cost model will work well enough. It's probably way too early to tell right now, though. > I've worried in the past that we'd > need planner/statistical support to figure out whether a loose scan > is likely to be useful compared to just plowing ahead in the index. I don't expect to be able to come up with a structure that leaves no unanswered questions about future MDAM work -- it's not realistic to expect everything to just fall into place. But that's okay. Just having everybody agree on roughly the right conceptual model is the really important thing. That now seems quite close, which I count as real progress. > 4. I find each of the above ideas to be far more attractive than > optimizing SELECT-DISTINCT-that-matches-an-index, so I don't really > understand why the current patchsets seem to be driven largely > by that single use-case. I wouldn't even bother with that for the > initial patch. I absolutely agree. I wondered about that myself in the past. My best guess is that a certain segment of users are familiar with SELECT-DISTINCT-that-matches-an-index from MySQL. And so to some extent application frameworks evolved in a world where that capability existed. IIRC Jesper once said that Hibernate relied on this capability. It's probably a lot easier to implement SELECT-DISTINCT-that-matches-an-index if you have the MySQL storage engine model, with concurrency control that's typically based on two-phase locking. I think that MySQL does some amount of deduplication in its executor here -- and *not* in what they call the storage engine. This is exactly what I'd like to avoid in Postgres; as I said "Maintenance of Index Order" (as the paper calls it) seems important, and not something to be added later on. Optimizer and executor layers that each barely know the difference between a skip scan and a full index scan seems like something we might actually want to aim for, rather than avoid. Teaching nbtree to transform quals into ranges sounds odd at first, but it seems like the right approach now, on balance -- that's the only *good* way to maintain index order. (Maintaining index order is needed to avoid needing or relying on deduplication in the executor proper, which is even inappropriate in an implementation of SELECT-DISTINCT-that-matches-an-index IMO.) -- Peter Geoghegan
On Mon, Mar 28, 2022 at 5:21 PM Tom Lane <tgl@sss.pgh.pa.us> wrote: > In any case, what I was on about is _bt_preprocess_keys() and > adjacent code. I'm surprised that those aren't more expensive > than one palloc in _bt_first. Maybe that logic falls through very > quickly in simple cases, though. I assume that it doesn't really appear in very simple cases (also common cases). But delaying the scan setup work until execution time does seem ugly. That's probably a good enough reason to refactor. -- Peter Geoghegan
Peter Geoghegan <pg@bowt.ie> writes: > The terminology in this area is a mess. MySQL calls > SELECT-DISTINCT-that-matches-an-index "loose index scans". I think > that you're talking about skip scan when you say "loose index scan". > Skip scan is where there is an omitted prefix of columns in the SQL > query -- omitted columns after the first column that lack an equality > qual. Right, that's the case I had in mind --- apologies if my terminology was faulty. btree can actually handle such a case now, but what it fails to do is re-descend from the tree root instead of plowing forward in the index to find the next matching entry. > It might be useful for somebody to go write a "taxonomy of MDAM > techniques", or a glossary. +1. We at least need to be sure we all are using these terms the same way. regards, tom lane
On Mon, Mar 28, 2022 at 7:07 PM Tom Lane <tgl@sss.pgh.pa.us> wrote: > Right, that's the case I had in mind --- apologies if my terminology > was faulty. btree can actually handle such a case now, but what it > fails to do is re-descend from the tree root instead of plowing > forward in the index to find the next matching entry. KNNGIST seems vaguely related to what we'd build for nbtree skip scan, though. GiST index scans are "inherently loose", though. KNNGIST uses a pairing heap/priority queue, which seems like the kind of thing nbtree skip scan can avoid. > +1. We at least need to be sure we all are using these terms > the same way. Yeah, there are *endless* opportunities for confusion here. -- Peter Geoghegan