6 ms·

MongoDB, count() and the big O

32 points by dpeck 15y ago

benologist 15y ago
MongoDB really sucks at count. It's a problem I've run into repeatedly with games that automatically submit highscores (ie without a name field/submit button) using an API call of ours that saves then returns the rank by checking how many scores are higher or lower than X.... on games that get millions of plays. My solution ultimately ended up being to put the leaderboards that are doing that particular thing into a special "truncate" list that periodically deletes everything after their 50,000th score.
- latch 15y ago
  I run/built mogade.com, which does the same thing. I blogged about how I switched to Redis for this specific feature (it made it top of HN, weren't you paying attention that day!?). Maybe you'll find it useful, simple test went from over 5minutes to 147ms: http://openmymind.net/2011/5/8/Practical-NoSQL-Solving-a-Real-Problem-w-Mongo-Red/ http://openmymind.net/2011/5/8/Practical-NoSQL-Solving-a-Rea...
  - benologist 15y ago
    I distinctly remember The Little MongoDb Book, I must have missed (or not had the problem at that time) the leaderboard one heh.
- cheald 15y ago
  For things like leaderboards, I'd recommend looking at Redis over Mongo. ZRANK is perfect for this sort of thing. http://redis.io/commands/zrank http://redis.io/commands/zrank
- dgottlieb 15y ago
  For what it's worth, I had used MySQL on a table with ~20 million rows and doing a count on an index would also be extremely slow. I put in triggers to do counts which worked perfectly for 99% of the sites, but there was some issue (either a bug or programmer error, never figured out which), but a handful of rows on this count table would claim there were a negative number of rows for a given query. (Any row with a negative number was typically zero a count of zero in the real table. In the cases where it was not zero, it was very close to it).
artsrc 15y ago
I think that SQL databases are bad at count too. I think the right map reduce view in Couch is good for count.
- LeafStorm 15y ago
  One of the things that I think puts people off from CouchDB is the comparative complicatedness of the query system, what with having to map/reduce and all. SQL queries are incredibly flexible by comparison, not to mention that SQL queries are how many developers think. But after studying data structures, I realized that most other databases have a lot of time complexity involved that they are basically sweeping under the rug, whereas Couch's relatively simple query model can guarantee that it's roughly O(log(M) + N).
- cheald 15y ago
  Postgres is notoriously bad at count. MySQL seems to handle it quite well, though, for some reason.
  - saurik 15y ago
    This is only true of the MyISAM backend (which has poor concurrency and has more complex table repair). If you use InnoDB, count(*) will be a full table scan, just as in PostgreSQL (as this is a direct tradeoff on those other properties).
    - onethumb 15y ago
      That's only true if you don't have any WHERE conditions. If you do, and they're indexed (as described by this author), it'll return the count fast.
      - saurik 15y ago
        Right... but PostgreSQL does that as well, so it really isn't relevant to a PostgreSQL vs. MySQL comment, which is what I was responding to. ;P PostgreSQL and InnoDB have the exact same constraints and tradeoffs with respect to count() performance, AFAIK. (That said, an index doesn't make this magically faster... the fast performance that people credit MyISAM with is that asking for the total number of rows in a table was O(1), as its lack of intricate transaction concurrency allowed it to just keep a global counter; one which of course was difficult and costly to repair after an unclean outage. In comparison, that indexes can optimize a count() over a where is obvious and true of any sane database engine, whether it be PostgreSQL or any of the common MySQL backends.)
dpeck 15y ago
Currently painted myself into a corner with this and trying to find a workaround that I'm happy with. Using mongoid as my ORM and subclassing models seemed like a great idea, that is until I've got 20M instances of these models. Its currently making my dashboard functionality both useless for the user and slowing the system down considerable when its requested. Understandably this is the cost of using things like mongodb. Until now I've been very happy with the benefits and tradeoffs but the problems with count() for reasonably sized collections was a particularly nasty surprise.
- cheald 15y ago
  Author of the article here. The count caching solved the problem for most practical production purposes (CRITICAL ALLITERATION), but it's still uglier than I'd like. However, if the use case is pagination, then "faking it" once you reach a certain size works well, and is unlikely to be noticed by the user. If your counts are on relatively static pieces of your dataset, then keeping counts manually somewhere (via $inc) will get you that performance back, but obviously at the cost of having to maintain it all manually. Incremental map/reduce isn't a bad idea, but again, depends on the complexity of what's being counted. All in all, it's something of a sore spot in an otherwise very enjoyable development experience.
wisty 15y ago
Count can be done with an incremental map-reduced. CouchDB does this automatically, but you could easily (read - with some difficulty) replicate this with any stack. This would be much easier to do if Mongo had triggers.
kevin1024 15y ago
You can combine limit() with count by passing true to the count function. So if you only care about counts greater than, say, 10000, you can do db.collection.find({criteria:'123}).limit(10000).count(true) and you will only get back a max of 10000. This puts an upper bound on waiting for some large counts to come back.
- cheald 15y ago
  That's awfully handy. It unfortunately doesn't solve the pagination problem, though. :/
  - taf2 15y ago
    it does, if you change your pagination interface to only care if there are more results after this page...
    - cheald 15y ago
      If your pagination interface is simply "Next", then why not skip the count all together, limit(N+1) documents, and offer the "Next" button if the result set is N+1 large?
  - kevin1024 15y ago
    By the way, if you do .limit() / .offset() pagination, by the time you get into really high offsets, queries will start going slow again. Mongo has to do a scan up to the document at offset that you are asking for.
  - josh_cutler 15y ago
    I forked a version of Kaminari a few months ago to solve this problem for me that I just updated with the latest upstream: https://github.com/joshcutler/kaminari https://github.com/joshcutler/kaminari I added a class method for Mongoid::Documents called limit_max_count_results_to that limits the size of Kaminari's total_count
siculars 15y ago
/rant/ You know what I think is "a big fat pile of suck"? This guy and his hack blog post. Congrats, you figured out what O(n) means. You know, this stuff is not magic. You can't magically say, hey database, give me everything I want and do it for me immediately. Oh, and make it open source, aka free. Oh, and on and on and on. This stuff is hard. Nothing comes for free. I don't even use mongodb in any production project and am really feeling for them. All these pseudo functional developers think they know how things should work and then get all indignant when stuff doesn't work the way they want it to or think it should. In this season of Thanks, let us give thanks to the real engineers who make these databases (and other software) and then give them out to everyone for free. Go send a polite email to their mailing lists and say "Dear OpenSource Developer, Thank you for all your hard work." Re. this specific problem - cache your data and stop crying about it or simply don't present counts to users.
- cheald 15y ago
  Hi, big fat pile of hack-posting author here. I know it's not magic. I'm a huge fan of Mongo. I blog about the issues I have with it, because the issues I don't have with it are far less interesting. The solution wasn't "AMG, MONGO SUX", it was "here's how I band-aided the problem". The impetus for this particular post was that it was somewhat surprising that counts were still doing full scans, even if the query conditions were on an indexed field. My expectation was that the index might have some information on how big a particular part of the index tree is (given two bounds), but it turns out that it doesn't, so you end up looking at each document and doing inspection per row. This isn't normally a problem, but the comparison is relatively slow, so the whole thing starts to drag down faster than you'd normally expect. When the problem is hidden below several levels of library/ORM candy coating, it's not going to be immediately obvious that this is a problem, especially if the queries against that field are otherwise performant thanks to proper use of indexes. It's non-obvious, and given that someone else found it interesting enough to post here, I'm apparently not the only person in the world to ever have this problem. There are multiple open tickets in the Mongo JIRA system, as well as multiple discussions on this topic on the mailing list. This isn't me whining that 10gen won't fix my software, it's an acknowledgment of the problem and steps towards fixing it. 10gen themselves have acknowledged via the mailing lists that counts are slower than they should be, and it's on the list of things to improve. Until then, we have to make do with workarounds.
scg 15y ago
On a related note, skip(n) is also O(n) so the farther you paginate the slower it gets.
- cheald 15y ago
  Yup, but the slow part of count() is the value comparison over n documents, moreso than the actual iteration. So while the point holds true, it's less of a practical concern.
sideshownz 15y ago
I had the same problem with a dataset of 1m+ records in mongo and really slow pagination with will_paginate. I have since swapped it out with the 'kaminari' gem (https://github.com/amatsuda/kaminari https://github.com/amatsuda/kaminari). This should solve your problem and is almost as simple as will_paginate to drop in. FYI im using mongoid and not mongo mapper
- cheald 15y ago
  Kaminari should suffer from the same issues; it's still invoking count() on the scope (at least, it appears to, from the source), which is going to trigger the problem. If you're counting the whole collection, it's going to be very fast, since mongo will just return the number of records in the collection, but if you're viewing a subset of the collection, it's still going to iterate over each record and do a value comparison.

32 points by dpeck 15y ago

MongoDB really sucks at count. It's a problem I've run into repeatedly with games that automatically submit highscores (ie without a name field/submit button) using an API call of ours that saves then returns the rank by checking how many scores are higher or lower than X.... on games that get millions of plays. My solution ultimately ended up being to put the leaderboards that are doing that particular thing into a special "truncate" list that periodically deletes everything after their 50,000th score.

latch 15y ago
I run/built mogade.com, which does the same thing. I blogged about how I switched to Redis for this specific feature (it made it top of HN, weren't you paying attention that day!?). Maybe you'll find it useful, simple test went from over 5minutes to 147ms: http://openmymind.net/2011/5/8/Practical-NoSQL-Solving-a-Real-Problem-w-Mongo-Red/ http://openmymind.net/2011/5/8/Practical-NoSQL-Solving-a-Rea...
- benologist 15y ago
  I distinctly remember The Little MongoDb Book, I must have missed (or not had the problem at that time) the leaderboard one heh.
cheald 15y ago
For things like leaderboards, I'd recommend looking at Redis over Mongo. ZRANK is perfect for this sort of thing. http://redis.io/commands/zrank http://redis.io/commands/zrank
dgottlieb 15y ago
For what it's worth, I had used MySQL on a table with ~20 million rows and doing a count on an index would also be extremely slow. I put in triggers to do counts which worked perfectly for 99% of the sites, but there was some issue (either a bug or programmer error, never figured out which), but a handful of rows on this count table would claim there were a negative number of rows for a given query. (Any row with a negative number was typically zero a count of zero in the real table. In the cases where it was not zero, it was very close to it).

artsrc 15y ago

I think that SQL databases are bad at count too. I think the right map reduce view in Couch is good for count.

LeafStorm 15y ago
One of the things that I think puts people off from CouchDB is the comparative complicatedness of the query system, what with having to map/reduce and all. SQL queries are incredibly flexible by comparison, not to mention that SQL queries are how many developers think. But after studying data structures, I realized that most other databases have a lot of time complexity involved that they are basically sweeping under the rug, whereas Couch's relatively simple query model can guarantee that it's roughly O(log(M) + N).
cheald 15y ago
Postgres is notoriously bad at count. MySQL seems to handle it quite well, though, for some reason.
- saurik 15y ago
  This is only true of the MyISAM backend (which has poor concurrency and has more complex table repair). If you use InnoDB, count(*) will be a full table scan, just as in PostgreSQL (as this is a direct tradeoff on those other properties).
  - onethumb 15y ago
    That's only true if you don't have any WHERE conditions. If you do, and they're indexed (as described by this author), it'll return the count fast.
    - saurik 15y ago
      Right... but PostgreSQL does that as well, so it really isn't relevant to a PostgreSQL vs. MySQL comment, which is what I was responding to. ;P PostgreSQL and InnoDB have the exact same constraints and tradeoffs with respect to count() performance, AFAIK. (That said, an index doesn't make this magically faster... the fast performance that people credit MyISAM with is that asking for the total number of rows in a table was O(1), as its lack of intricate transaction concurrency allowed it to just keep a global counter; one which of course was difficult and costly to repair after an unclean outage. In comparison, that indexes can optimize a count() over a where is obvious and true of any sane database engine, whether it be PostgreSQL or any of the common MySQL backends.)

dpeck 15y ago

Currently painted myself into a corner with this and trying to find a workaround that I'm happy with. Using mongoid as my ORM and subclassing models seemed like a great idea, that is until I've got 20M instances of these models. Its currently making my dashboard functionality both useless for the user and slowing the system down considerable when its requested. Understandably this is the cost of using things like mongodb. Until now I've been very happy with the benefits and tradeoffs but the problems with count() for reasonably sized collections was a particularly nasty surprise.

cheald 15y ago
Author of the article here. The count caching solved the problem for most practical production purposes (CRITICAL ALLITERATION), but it's still uglier than I'd like. However, if the use case is pagination, then "faking it" once you reach a certain size works well, and is unlikely to be noticed by the user. If your counts are on relatively static pieces of your dataset, then keeping counts manually somewhere (via $inc) will get you that performance back, but obviously at the cost of having to maintain it all manually. Incremental map/reduce isn't a bad idea, but again, depends on the complexity of what's being counted. All in all, it's something of a sore spot in an otherwise very enjoyable development experience.

wisty 15y ago

Count can be done with an incremental map-reduced. CouchDB does this automatically, but you could easily (read - with some difficulty) replicate this with any stack. This would be much easier to do if Mongo had triggers.

kevin1024 15y ago

You can combine limit() with count by passing true to the count function. So if you only care about counts greater than, say, 10000, you can do db.collection.find({criteria:'123}).limit(10000).count(true) and you will only get back a max of 10000. This puts an upper bound on waiting for some large counts to come back.

cheald 15y ago
That's awfully handy. It unfortunately doesn't solve the pagination problem, though. :/
- taf2 15y ago
  it does, if you change your pagination interface to only care if there are more results after this page...
  - cheald 15y ago
    If your pagination interface is simply "Next", then why not skip the count all together, limit(N+1) documents, and offer the "Next" button if the result set is N+1 large?
- kevin1024 15y ago
  By the way, if you do .limit() / .offset() pagination, by the time you get into really high offsets, queries will start going slow again. Mongo has to do a scan up to the document at offset that you are asking for.
- josh_cutler 15y ago
  I forked a version of Kaminari a few months ago to solve this problem for me that I just updated with the latest upstream: https://github.com/joshcutler/kaminari https://github.com/joshcutler/kaminari I added a class method for Mongoid::Documents called limit_max_count_results_to that limits the size of Kaminari's total_count

siculars 15y ago

/rant/ You know what I think is "a big fat pile of suck"? This guy and his hack blog post. Congrats, you figured out what O(n) means. You know, this stuff is not magic. You can't magically say, hey database, give me everything I want and do it for me immediately. Oh, and make it open source, aka free. Oh, and on and on and on. This stuff is hard. Nothing comes for free. I don't even use mongodb in any production project and am really feeling for them. All these pseudo functional developers think they know how things should work and then get all indignant when stuff doesn't work the way they want it to or think it should. In this season of Thanks, let us give thanks to the real engineers who make these databases (and other software) and then give them out to everyone for free. Go send a polite email to their mailing lists and say "Dear OpenSource Developer, Thank you for all your hard work." Re. this specific problem - cache your data and stop crying about it or simply don't present counts to users.

cheald 15y ago
Hi, big fat pile of hack-posting author here. I know it's not magic. I'm a huge fan of Mongo. I blog about the issues I have with it, because the issues I don't have with it are far less interesting. The solution wasn't "AMG, MONGO SUX", it was "here's how I band-aided the problem". The impetus for this particular post was that it was somewhat surprising that counts were still doing full scans, even if the query conditions were on an indexed field. My expectation was that the index might have some information on how big a particular part of the index tree is (given two bounds), but it turns out that it doesn't, so you end up looking at each document and doing inspection per row. This isn't normally a problem, but the comparison is relatively slow, so the whole thing starts to drag down faster than you'd normally expect. When the problem is hidden below several levels of library/ORM candy coating, it's not going to be immediately obvious that this is a problem, especially if the queries against that field are otherwise performant thanks to proper use of indexes. It's non-obvious, and given that someone else found it interesting enough to post here, I'm apparently not the only person in the world to ever have this problem. There are multiple open tickets in the Mongo JIRA system, as well as multiple discussions on this topic on the mailing list. This isn't me whining that 10gen won't fix my software, it's an acknowledgment of the problem and steps towards fixing it. 10gen themselves have acknowledged via the mailing lists that counts are slower than they should be, and it's on the list of things to improve. Until then, we have to make do with workarounds.

scg 15y ago

On a related note, skip(n) is also O(n) so the farther you paginate the slower it gets.

cheald 15y ago
Yup, but the slow part of count() is the value comparison over n documents, moreso than the actual iteration. So while the point holds true, it's less of a practical concern.

sideshownz 15y ago

I had the same problem with a dataset of 1m+ records in mongo and really slow pagination with will_paginate. I have since swapped it out with the 'kaminari' gem (https://github.com/amatsuda/kaminari https://github.com/amatsuda/kaminari). This should solve your problem and is almost as simple as will_paginate to drop in. FYI im using mongoid and not mongo mapper

cheald 15y ago
Kaminari should suffer from the same issues; it's still invoking count() on the scope (at least, it appears to, from the source), which is going to trigger the problem. If you're counting the whole collection, it's going to be very fast, since mongo will just return the number of records in the collection, but if you're viewing a subset of the collection, it's still going to iterate over each record and do a value comparison.