Monday, December 09, 2019, 1:32:40 PM, Digital Dog <digitald...@gmail.com> wrote:
> On Sat, Dec 7, 2019 at 3:50 AM Simon Slavin <slav...@bigfraud.org> wrote: >> On 7 Dec 2019, at 2:26am, Shawn Wagner <shawnw.mob...@gmail.com> wrote: >> >> > The first one uses the index for all sorting, but the second one only >> uses it for sorting a, not b. I feel like the descending sort could make >> use of the index too, just reading the b sections backwards to get the >> right order. Is there something I'm overlooking that would make this sort >> of optimization impractical or otherwise a bad idea? >> >> Hmm. Try running ANALYZE and then doing the EXPLAIN QUERY PLAN lines >> again. >> >> But I think that without 'chunkiness' information (how many values columns >> a and b have) it would not be worth doing the complicated programming >> required for reverse-mini-scanning of that index. The programming is quite >> complicated and unless your index "b" is chunky it won't save you much time >> over the plan shown. >> > So it's better to allocate memory, block the execution until all rows are > read and use cpu time to do unnecessary sorting that could easily be > avoided by just reading index backwards? It should only need to collect-and-sort groups of rows with equal "a" values, rather than ALL rows (and the EXPLAIN QUERY PLAN seems to support this). In theory, it should be possible to emit rows in these groups, but I don't know enough about reading VDBE (output of EXPLAIN SELECT...) to know if it does this or accumulates ALL rows before emitting the first. > Is it really so hard to program > it? I do not think so. I've no idea. If reverse-mini-scanning an index ISN'T "so hard", then from past experience there's a moderate chance one of the devs is looking to see if it CAN be done. However, the fact that it HASN'T been done, when reverse-mini-scanning seems an "obvious" optimisation, suggests to me it is not as easy as one might think, and that the potential saving isn't that great. Especially when you could always create a second index on "a, b DESC". > However the heuristic to decide when to do backward index scan needs to be > smart enough to select this only as last resort optimization, just before > falling back to explicit sort. This "decision problem" is -- I believe -- a key factor in deciding whether to add any specific optimisation. For every (potential) optimisation that could be added, you need to add code that decides whether it's worth using that optimisation. The savings from USING the optimisation only benefit SOME queries, but the code that decides whether or not to USE the optimisation has to be executed for many, many more queries. The risk is that you slow lots and lots of queries down a little bit, for only an occasional gain for the few queries where the optimisation does make sense. I don't know the actual code, but I'm guessing the optimiser never really "knows" there is an index where doing a "reverse-mini-scan" could help. I suspect it (a) realises there isn't a "prefect" index; (b) finds an index that sorts as much as possible (in this case, the only index), and (c) fulfils the rest of the ORDER BY requirements using a temp b-tree. (With, probably, some exceptions for optimisations that HAVE been implemented). To implement a reverse-mini-scan, not only would you have to add the code to do the reverse scan itself, but the code that does (b) above (find AN index that sorts as much as possible) would need to be much more complex and consider ALL indices that start by ordering "a ASC" to see if any of THOSE would allow a reverse-scan. It might even need to see if a "seemingly worse" index (+reverse-scan) might be better than an "obviously better" index. For instance, with more fields, an "ORDER BY a, b DESC, c" might be better served by an index on "( a, b, c )" with reverse-scan than a seemingly better index on "( a, b DESC, d ). Graham _______________________________________________ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
