[SERVER-40043] $set takes quadratic time while holding locks Created: 08/Mar/19  Updated: 06/Dec/22  Resolved: 28/Mar/19

Status: Closed
Project: Core Server
Component/s: Querying
Affects Version/s: None
Fix Version/s: None

Type: Bug Priority: Major - P3
Reporter: Kelsey Schubert Assignee: Backlog - Query Team (Inactive)
Resolution: Duplicate Votes: 1
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Duplicate
duplicates SERVER-32156 Linear field lookup in update subsyst... Backlog
Related
related to SERVER-32156 Linear field lookup in update subsyst... Backlog
related to SERVER-36791 $addToSet with $each takes quadratic ... Backlog
Assigned Teams:
Query
Operating System: ALL
Participants:
Case:

 Description   

Confirmed in 3.6.8 and 4.0.6:

from collections import OrderedDict
from pymongo import MongoClient
 
client = MongoClient()
d = client['test']
c = d['foo']
 
setDict = {}
numElements = 50000
for x in range(numElements):
    setDict['a'+str(x)] = 1
 
c.update_one({'_id':1},{'$set': setDict})

Num Elements Duration
50000 16s
100000 70s
150000 143s
200000 257s

Since this operation does not yield, it can block operations that require stronger locks stalling all operations.

Typical stack in 4.0.6

Thread 2 (Thread 0x7fda2f02f700 (LWP 1481)):
#0  0x00007fda3deb726b in mongo::mutablebson::Element::findFirstChildNamed(mongo::StringData) const ()
#1  0x00007fda3db9178e in mongo::(anonymous namespace)::getChild(mongo::mutablebson::Element, mongo::StringData) ()
#2  0x00007fda3db91ea0 in mongo::(anonymous namespace)::applyChild(mongo::UpdateNode const&, mongo::StringData, mongo::UpdateNode::ApplyParams*, mon
#3  0x00007fda3db941fa in mongo::UpdateObjectNode::apply(mongo::UpdateNode::ApplyParams) const ()
#4  0x00007fda3db76525 in mongo::UpdateDriver::update(mongo::StringData, mongo::mutablebson::Document*, bool, mongo::FieldRefSet const&, mongo::BSON
#5  0x00007fda3ce723cf in mongo::UpdateStage::transformAndUpdate(mongo::Snapshotted<mongo::BSONObj> const&, mongo::RecordId&) ()
#6  0x00007fda3ce73f6d in mongo::UpdateStage::doWork(unsigned long*) ()
#7  0x00007fda3ce4e96b in mongo::PlanStage::work(unsigned long*) ()
#8  0x00007fda3ce9f42d in mongo::PlanExecutor::getNextImpl(mongo::Snapshotted<mongo::BSONObj>*, mongo::RecordId*) ()
#9  0x00007fda3ce9fdbb in mongo::PlanExecutor::getNext(mongo::BSONObj*, mongo::RecordId*) ()
#10 0x00007fda3ce9feed in mongo::PlanExecutor::executePlan() ()
#11 0x00007fda3cc586c5 in mongo::performUpdates(mongo::OperationContext*, mongo::write_ops::Update const&) ()
#12 0x00007fda3cc5075d in mongo::(anonymous namespace)::CmdUpdate::Invocation::runImpl(mongo::OperationContext*, mongo::BSONObjBuilder&) const ()
#13 0x00007fda3cc4e8b2 in mongo::(anonymous namespace)::WriteCommand::InvocationBase::run(mongo::OperationContext*, mongo::CommandReplyBuilder*) ()
#14 0x00007fda3c63a6bc in mongo::(anonymous namespace)::execCommandDatabase(mongo::OperationContext*, mongo::Command*, mongo::OpMsgRequest const&, m
#15 0x00007fda3c63bda9 in mongo::(anonymous namespace)::receivedCommands(mongo::OperationContext*, mongo::Message const&, mongo::ServiceEntryPointCo
#16 0x00007fda3c63ccf1 in mongo::ServiceEntryPointCommon::handleRequest(mongo::OperationContext*, mongo::Message const&, mongo::ServiceEntryPointCom
#17 0x00007fda3c6284ba in mongo::ServiceEntryPointMongod::handleRequest(mongo::OperationContext*, mongo::Message const&) ()
#18 0x00007fda3c634fea in mongo::ServiceStateMachine::_processMessage(mongo::ServiceStateMachine::ThreadGuard) ()
#19 0x00007fda3c62fc67 in mongo::ServiceStateMachine::_runNextInGuard(mongo::ServiceStateMachine::ThreadGuard) ()
#20 0x00007fda3c6334b1 in std::_Function_handler<void (), mongo::ServiceStateMachine::_scheduleNextWithGuard(mongo::ServiceStateMachine::ThreadGuard
#21 0x00007fda3d7c0d72 in mongo::transport::ServiceExecutorSynchronous::schedule(std::function<void ()>, mongo::transport::ServiceExecutor::Schedule
#22 0x00007fda3c62de50 in mongo::ServiceStateMachine::_scheduleNextWithGuard(mongo::ServiceStateMachine::ThreadGuard, mongo::transport::ServiceExecu
#23 0x00007fda3c631035 in mongo::ServiceStateMachine::_sourceCallback(mongo::Status) ()
#24 0x00007fda3c62f3a7 in mongo::ServiceStateMachine::_sourceMessage(mongo::ServiceStateMachine::ThreadGuard) ()
#25 0x00007fda3c62fced in mongo::ServiceStateMachine::_runNextInGuard(mongo::ServiceStateMachine::ThreadGuard) ()
#26 0x00007fda3c6334b1 in std::_Function_handler<void (), mongo::ServiceStateMachine::_scheduleNextWithGuard(mongo::ServiceStateMachine::ThreadGuard
#27 0x00007fda3d7c12d5 in std::_Function_handler<void (), mongo::transport::ServiceExecutorSynchronous::schedule(std::function<void ()>, mongo::tran
#28 0x00007fda3de885f4 in mongo::(anonymous namespace)::runFunc(void*) ()
#29 0x00007fda3ac18184 in start_thread () from /lib/x86_64-linux-gnu/libpthread.so.0
#30 0x00007fda3a94503d in clone () from /lib/x86_64-linux-gnu/libc.so.6



 Comments   
Comment by Asya Kamsky [ 22/Mar/19 ]

I believe this is a duplicate of SERVER-32156 and in particular related to this comment

If that's the case this ticket should be closed as duplicate and we can re-triage SERVER-32156 for prioritization.

Comment by Craig Homa [ 18/Mar/19 ]

asya to investigate priority.

Comment by Tess Avitabile (Inactive) [ 12/Mar/19 ]

acm, correct, this would not have changed with the 3.6 update refactor. I like your idea for a solution. Another idea is to stop searching for the child once we reached the first newly added child, since all newly added children go at the end. This might be simpler, but it doesn't have the advantage of avoiding multiple scans of existing children.

justin.seyster

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