On Sun, Aug 13, 2023 at 5:50 PM Peter Geoghegan <p...@bowt.ie> wrote: > All that it would take to fix the problem is per-attribute > BTScanInsertData.nextkey values. There is no reason why "nextkey" > semantics should only work for the last attribute in the insertion > scan key. Under this scheme, _bt_first() would be taught to set up the > insertion scan key with (say) nextkey=true for the "four > 2" > attribute, and nextkey=false for the other 3 attributes (since we do > that whenever >= or = are used). It would probably also make sense to > generalize this approach to handle (say) a third query that had a > "four < 2" inequality, but otherwise matched the first two queries. So > we wouldn't literally use multiple "nextkey" fields to do this.
Actually, that can't work when there are a huge number of index tuples with the same values for "four" (enough to span many internal pages). So we'd need specialized knowledge of the data type (probably from an opclass support function) to transform "four > 2" into "four >= 3" up front. Alternatively, we could do roughly the same thing via an initial index probe to do the same thing. The latter approach would be needed for continuous data types, where the transformation isn't possible at all. The probing approach could work by finding an initial position in the same way as we currently locate an initial leaf page -- the way that I complained about earlier on, but with an important twist. Once we'd established that the first "four" value in the index > 2 really was 3 (or whatever it turned out to be), we could fill that value into a new insertion scan key. It would then be possible to do another descent of the index, skipping over most of the leaf pages that we'll access needlessly right now. (Actually, we'd only do all that when it seemed likely to allow us to skip a significant number of intermediate leaf pages -- which is what we saw in my test case.) This is directly related to skip scan. The former approach is more or less what the MDAM paper calls "dense" access (which is naturally limited to discrete data types like integer), while the latter probing approach is what it calls "sparse" access. Skip scan performs this process repeatedly, most of the time, but we'd only skip once here. In fact, if my example had used (say) "four > 1" instead, then it would have made sense to skip multiple times -- not just once, after an initial descent. Because then we'd have had to consider matches for both "two=1 and four=2" and "two=1 and four=3" (there aren't any "two=1 and four=4" matches so we'd then be done). In fact, had there been no mention of the "four" column in the query whatsoever (which is how we tend to think of skip scan), then a decent implementation of skip scan would effectively behave as if the query had been written "two=1 and four > -inf and ...", while following the same general approach. (Or "two=1 and four < +inf and ...", if this was a similar looking backwards scan.) -- Peter Geoghegan
