On 2/20/07, Gregory Maxwell gmaxwell@gmail.com wrote:
On 2/20/07, Simetrical Simetrical+wikilist@gmail.com wrote:
Are you using COUNT(*)? That's O(N) on InnoDB, which is why we don't use it: too slow for large categories. If you have an extra field in the database somewhere rather than COUNT(*), maybe it would be good for trunk (although that's for Tim, Domas, etc. to decide).
O(N).. er. Ah, you mean O(N) on results...
I believe it's O(N) on number of rows in the table, actually, not just on number of results (which any query is going to be, I guess, although I don't know much of anything about computational complexity). I was really just repeating what Tim said:
It's a common pitfall for new developers to submit code containing SQL queries which examine huge numbers of rows. Remember that COUNT(*) is O(N), counting rows in a table is like counting beans in a bucket.
http://svn.wikimedia.org/viewvc/mediawiki/trunk/phase3/docs/database.txt?vie...
Apparently this is because of the transactional nature of the tables http://dev.mysql.com/doc/refman/5.1/en/group-by-functions.html. I'm not sure why it couldn't maintain a slightly-inaccurate count (so that behavior doesn't differ between storage engines, I guess), but it doesn't, apparently, so it has to recount them every time.
Then again, probably I misunderstood you and am not telling you anything you didn't already know.