On Thu, Apr 25, 2013 at 05:08:04PM +0200, Daniel Winter scratched on the wall: > 2013/4/25 James K. Lowden <jklow...@schemamania.org> > > > > > Nonsense. The query parser sees GROUP BY A,B. The optimizer sees an > > index ordered B,A. By permuting the order of the columns in the GROUP > > BY clause, it finds a match for the index and uses it. > > > > Yes, the problem is O(n^2), where n is the number of columns in the > > GROUP BY, but n is always small; even 7 columns could be checked in > > less than 50 iterations. > > > > I believe its O(n!), but still doable for small n. I don't know the inner > workings of the query optimizer but mabye instead of asking/check for a > index of every permutation of the columns in the group by, it could just > check if an index exists which covers all columns (even the sorting order > doesn't matter). (the virtual table api needs an addition for that to work)
Permutations are O(N!), but that's not really what you want. Given a set of GROUP BY terms you want, generally, the index with the most terms in any initial order. You don't need a full match for the index to be a win. For example, GROUP BY A,B,C,D,E is likely to get a performance boost from an index on (A,D,B) and, *in general*, that should be a bigger win than an index on (B,C). Of course, since this is a query optimizer, there are always edge cases... For example, if there is an index over (E) that has 99% unique values, it is likely a better choice than (A,D,B)... it depends on the distribution of the index. Similarly, if any GROUP BY term maps to a unique index... boom, you're done. As with most things having to do with query optimization, the problem quickly explodes. On the other hand, SQLite must already have assumptions about index costs (with or without ANALYZE), so at least there's an existing set of weights and assumptions to work from. -j -- Jay A. Kreibich < J A Y @ K R E I B I.C H > "Intelligence is like underwear: it is important that you have it, but showing it to the wrong people has the tendency to make them feel uncomfortable." -- Angela Johnson _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
