reported by FourQuare

---------- Forwarded message ----------
From: Jon Hoffman <jon@foursquare.com>
Date: Sat, Dec 4, 2010 at 12:33 PM
Subject: Re: slow query construction (java driver issue)
To: harryh <harryh@foursquare.com>
Cc: Eliot Horowitz <eliot@10gen.com>, "Brendan W. McAdams" <brendan@10gen.com>

should be O(1)

On Dec 4, 2010, at 1:18 PM, harryh wrote:

> Ya, I just found that as well. It should be O.
>
> On Sat, Dec 4, 2010 at 1:17 PM, Jon Hoffman <jon@foursquare.com> wrote:
>> BasicBSONList.keySet is O(n^2)
>>
>>
>> On Dec 4, 2010, at 1:04 PM, harryh wrote:
>>
>>> What's Brendan's @10gen e-mail? This is totally his territory.
>>>
>>> We found a bug in foursquare last night where under certain rare
>>> circumstances we were constructing a mongo query with a 50 thousand
>>> item $in clause. This is obviously bad on our part and we fixed it,
>>> but I'm also pretty sure it uncovered an efficiency problem in the
>>> mongo java driver. It was taking on the order of 10 seconds to
>>> construct the query to send to the database. Relavent stack trace
>>> is below. I've only just begun looking through the code, but I'm
>>> already struck by the N^2 code that executes as the
>>> c.m.util.OrderedSet is filled up with the 50k ids in question. That
>>> might be worth changing?
>>>
>>> -harryh
>>>
>>> "710173487@qtp-768288241-81" prio=10 tid=0x00007fb2c002c000 nid=0x778e
>>> runnable [0x00007fb2ae0e2000]
>>> java.lang.Thread.State: RUNNABLE
>>> at java.util.ArrayList.indexOf(ArrayList.java:216)
>>> at java.util.ArrayList.contains(ArrayList.java:199)
>>> at com.mongodb.util.OrderedSet.add(OrderedSet.java:35)
>>> at org.bson.types.BasicBSONList.keySet(BasicBSONList.java:137)
>>> at org.bson.BSONEncoder.putObject(BSONEncoder.java:109)
>>> at org.bson.BSONEncoder._putObjectField(BSONEncoder.java:154)
>>> at org.bson.BSONEncoder.putObject(BSONEncoder.java:119)
>>> at org.bson.BSONEncoder._putObjectField(BSONEncoder.java:154)
>>> at org.bson.BSONEncoder.putObject(BSONEncoder.java:119)
>>> at org.bson.BSONEncoder.putObject(BSONEncoder.java:65)
>>> at com.mongodb.OutMessage._appendQuery(OutMessage.java:70)
>>> at com.mongodb.OutMessage.query(OutMessage.java:55)
>>> at com.mongodb.DBApiLayer$MyCollection.__find(DBApiLayer.java:221)
>>> at com.mongodb.DBCursor._check(DBCursor.java:252)
>>> at com.mongodb.DBCursor._hasNext(DBCursor.java:372)
>>> at com.mongodb.DBCursor._fill(DBCursor.java:440)
>>> at com.mongodb.DBCursor.toArray(DBCursor.java:470)
>>> at com.mongodb.DBCursor.toArray(DBCursor.java:459)
>>> at net.liftweb.mongodb.record.MongoMetaRecord$$anonfun$findAll$4.apply(MongoMetaRecord.scala:154)
>>> at net.liftweb.mongodb.record.MongoMetaRecord$$anonfun$findAll$4.apply(MongoMetaRecord.scala:146)
>>> at net.liftweb.mongodb.MongoDB$.useCollection(Mongo.scala:155)
>>> at net.liftweb.mongodb.record.MongoMetaRecord$class.useColl(MongoMetaRecord.scala:54)
>>> at com.foursquare.model.Badge$.useColl(Badge.scala:69)
>>> at net.liftweb.mongodb.record.MongoMetaRecord$class.findAll(MongoMetaRecord.scala:146)
>>> at com.foursquare.model.Badge$.findAll(Badge.scala:69)
>>> at net.liftweb.mongodb.record.MongoMetaRecord$class.findAll(MongoMetaRecord.scala:133)
>>> at com.foursquare.model.Badge$.com$foursquare$record$FSMongoMetaRecord$$super$findAll(Badge.scala:69)
>>> at com.foursquare.record.FSMongoMetaRecord$$anonfun$findAll$4.apply(FSMongoRecord.scala:167)
>>> at com.foursquare.record.FSMongoMetaRecord$$anonfun$findAll$4.apply(FSMongoRecord.scala:167)
>>> at com.foursquare.record.FSMongoMetaRecord$class.logTime(FSMongoRecord.scala:198)
>>> at com.foursquare.model.Badge$.logTime(Badge.scala:69)
>>> at com.foursquare.record.FSMongoMetaRecord$class.findAll(FSMongoRecord.scala:167)
>>> at com.foursquare.model.Badge$.findAll(Badge.scala:69)
>>> at net.liftweb.mongodb.record.MongoMetaRecord$class.findAll(MongoMetaRecord.scala:182)
>>> at com.foursquare.model.Badge$.findAll(Badge.scala:69)
>>> at com.foursquare.model.User$$anonfun$13.apply(User.scala:665)
>>
>>