On 2/20/07, Gregory Maxwell <gmaxwell(a)gmail.com> wrote:
On 2/20/07, Simetrical
<Simetrical+wikilist(a)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?vi…
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.