On Sat, Aug 3, 2024 at 3:34 PM Dmitry Dolgov <9erthali...@gmail.com> wrote: > I see that the patch is not supposed to deal with aggregates in any special > way.
Right. > But from what I understand after a quick review, skip scan is not getting > applied to them if there are no quals in the query (in that case > _bt_preprocess_keys returns before calling _bt_preprocess_array_keys). Right. > Yet such queries could benefit from skipping, I assume they still could be > handled by > the machinery introduced in this patch? I'm not sure. There are no real changes required inside _bt_advance_array_keys with this patch -- skip arrays are dealt with in essentially the same way as conventional arrays (as of Postgres 17). I suspect that loose index scan would be best implemented using _bt_advance_array_keys. It could also "plug in" to the existing _bt_advance_array_keys design, I suppose. As I touched on already, your loose index scan patch applies high-level semantic information in a way that is very different to my skip scan patch. This means that it makes revisions to the index AM API (if memory serves it adds a callback called amskip to that API). It also means that loose index scan can actually avoid heap accesses; loose scans wholly avoid accessing logical rows (in both the index and the heap) by reasoning that it just isn't necessary to do so at all. Skipping happens in both data structures. Right? Obviously, my new skip scan patch cannot possibly reduce the number of heap page accesses required by a given index scan. Precisely the same logical rows must be accessed as before. There is no two-way conversation between the index AM and the table AM about which rows/row groupings have at least one visible tuple. We're just navigating through the index more efficiently, without changing any contract outside of nbtree itself. The "skip scan" name collision is regrettable. But the fact is that Oracle, MySQL, and now SQLite all call this feature skip scan. That feels like the right precedent to follow. > Do I understand correctly, that the only way how multiplying ndistincts could > produce too pessimistic results is when there is a correlation between > distinct > values? Yes, that's one problem with the costing. Not the only one, though. The true number of primitive index scans depends on the cardinality of the data. For example, a skip scan might be the cheapest plan by far if (say) 90% of the index has the same leading column value and the remaining 10% has totally unique values. We'd still do a bad job of costing this query with an accurate ndistinct for the leading column. We really one need to do one or two primitive index scans for "the first 90% of the index", and one more primitive index scan for "the remaining 10% of the index". For a query such as this, we "require a full index scan for the remaining 10% of the index", which is suboptimal, but doesn't fundamentally change anything (I guess that a skip scan is always suboptimal, in the sense that you could always do better by having more indexes). > Can one benefit from the extended statistics here? I really don't know. Certainly seems possible in cases with more than one skipped leading column. The main problem with the costing right now is that it's just not very well thought through, in general. The performance at runtime depends on the layout of values in the index itself, so the underlying way that you'd model the costs doesn't have any great precedent in costsize.c. We do have some idea of the number of leaf pages we'll access in btcostestimate(), but that works in a way that isn't really fit for purpose. It kind of works with one primitive index scan, but works much less well with multiple primitive scans. > And while we're at it, I think it would be great if the implementation will > allow some level of visibility about the skip scan. From what I see, currently > it's by design impossible for users to tell whether something was skipped or > not. But when it comes to planning and estimates, maybe it's not a bad idea to > let explain analyze show something like "expected number of primitive scans / > actual number of primitive scans". I agree. I think that that's pretty much mandatory for this patch. At least the actual number of primitive scans should be exposed. Not quite as sure about showing the estimated number, since that might be embarrassingly wrong quite regularly, without it necessarily mattering that much (I'd worry that it'd be distracting). Displaying the number of primitive scans would already be useful for index scans with SAOPs, even without this patch. The same general concepts (estimated vs. actual primitive index scans) already exist, as of Postgres 17. That's really nothing new. -- Peter Geoghegan
