Info

Following takes quadratic time (I suspect product of number of existing elements and number being added) function repro() { n = 10000 // 3.6 s n = 20000 // 7.4 s n = 40000 // 22 s n = 80000 // 83 s e = [] for (var i = 0; i < n; i++) e.push(i) db.c.drop() db.c.insert({_id: 0}, {x: []}) db.c.update({_id: 0}, {$addToSet: {x: {$each: e}}}) db.c.update({_id: 0}, {$addToSet: {x: {$each: e}}}) } It does not yield during this which can block operations requiring strong locks which can stall all operations. Typical stack (4.01): Thread 3 (Thread 0x7f892131b700 (LWP 20933)): #0 0x0000556fb9ac19c2 in mongo::mutablebson::Element::compareWithBSONElement(mongo::BSONElement const&, mongo::StringData::ComparatorInterface const*, bool) const () #1 0x0000556fb9789fc9 in mongo::AddToSetNode::updateExistingElement(mongo::mutablebson::Element*, std::shared_ptr) const () #2 0x0000556fb978d696 in mongo::ModifierNode::applyToExistingElement(mongo::UpdateNode::ApplyParams) const () #3 0x0000556fb978f85f in mongo::ModifierNode::apply(mongo::UpdateNode::ApplyParams) const () #4 0x0000556fb97a39b6 in mongo::(anonymous namespace)::applyChild(mongo::UpdateNode const&, mongo::StringData, mongo::UpdateNode::ApplyParams*, mongo::UpdateNode::ApplyResult*) [clone .constprop.219] () #5 0x0000556fb97a5f5a in mongo::UpdateObjectNode::apply(mongo::UpdateNode::ApplyParams) const () #6 0x0000556fb97882e5 in mongo::UpdateDriver::update(mongo::StringData, mongo::mutablebson::Document*, bool, mongo::FieldRefSet const&, mongo::BSONObj*, bool*) () #7 0x0000556fb8999b6f in mongo::UpdateStage::transformAndUpdate(mongo::Snapshotted const&, mongo::RecordId&) () #8 0x0000556fb899b79d in mongo::UpdateStage::doWork(unsigned long*) () #9 0x0000556fb8975ffb in mongo::PlanStage::work(unsigned long*) () #10 0x0000556fb89c6c05 in mongo::PlanExecutor::getNextImpl(mongo::Snapshotted*, mongo::RecordId*) () #11 0x0000556fb89c73db in mongo::PlanExecutor::getNext(mongo::BSONObj*, mongo::RecordId*) () #12 0x0000556fb89c750d in mongo::PlanExecutor::executePlan() () #13 0x0000556fb8716b69 in mongo::performUpdates(mongo::OperationContext*, mongo::write_ops::Update const&) () #14 0x0000556fb870ed1d in mongo::(anonymous namespace)::CmdUpdate::Invocation::runImpl(mongo::OperationContext*, mongo::BSONObjBuilder&) const ()

Top User Comments

asya commented on Tue, 28 Aug 2018 18:32:51 +0000: Note that adding thousands of elements to an array containing thousands of elements is not considered a good practice, likely the schema design is not correct given the workload. justin.seyster commented on Tue, 21 Aug 2018 19:25:47 +0000: david.storch Yes, both version of the $addToSet code (before and after the UpdateNode implementation in 3.6) use a quadratic-time loop to insert elements from $each without duplicating existing elements in the array. david.storch commented on Tue, 21 Aug 2018 18:31:32 +0000: justin.seyster, at a glance, it appears that this quadratic behavior was inherited from the old ModifierAddToSet implementation, and therefore affects all supported versions. Can you confirm?

Steps to Reproduce