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
