[SERVER-36791] $addToSet with $each takes quadratic time while holding locks Created: 21/Aug/18  Updated: 06/Dec/22

Status: Backlog
Project: Core Server
Component/s: Querying
Affects Version/s: 3.2.20, 3.6.6, 4.0.1
Fix Version/s: None

Type: Bug Priority: Major - P3
Reporter: Bruce Lucas (Inactive) Assignee: Backlog - Query Execution
Resolution: Unresolved Votes: 1
Labels: query-44-grooming
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Depends
Related
related to SERVER-32156 Linear field lookup in update subsyst... Backlog
is related to SERVER-40043 $set takes quadratic time while holdi... Closed
Assigned Teams:
Query Execution
Participants:
Case:

 Description   

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<mongo::FieldRef>) 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<mongo::BSONObj> 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::BSONObj>*, 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 ()



 Comments   
Comment by Asya Kamsky [ 28/Aug/18 ]

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.

 

Comment by Justin Seyster [ 21/Aug/18 ]

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.

Comment by David Storch [ 21/Aug/18 ]

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?

Generated at Thu Feb 08 04:44:05 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.