Hello, I am interested in the theoretical time / space complexity of SQL queries on indexed / non-indexed data.
I think I read somewhere that a JOIN on an indexed column is something like O[mn*log(mn)] (m rows joined to n). I assume without an index it is just O[m*n] Specifically I want to know the complexity of a query that does a 'cross tabulation' SELECT X, SUM(if(Y=1,Z,0)) AS s1, SUM(if(Y=2,Z,0)) AS s2, SUM(if(Y=3,Z,0)) AS s3, ... FROM T1 GROUP BY X; Assuming both X and Y are indexed, how does the complexity grow with increasing 's' (more if clauses). More basic, what is the complexity of the group by statement? Can anyone point me to a good online guide to complexity of SQL? Thanks very much for any suggestions :) Dan. -- MySQL General Mailing List For list archives: http://lists.mysql.com/mysql To unsubscribe: http://lists.mysql.com/[EMAIL PROTECTED]