[SERVER-10426] Do not return 'true' from comparator for equal items in merge sort Created: 03/Aug/13  Updated: 11/Jul/16  Resolved: 03/Aug/13

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

Type: Bug Priority: Major - P3
Reporter: Tad Marshall Assignee: Tad Marshall
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Backwards Compatibility: Fully Compatible
Operating System: ALL
Participants:

 Description   

The Windows debug build has some runtime tests (in the debug version of the MSVC "C" runtime library) that other builds don't have. test.exe prints some errors in its debug build that indicate code problems.

http://buildbot.mongodb.org/builders/Windows%2064-bit%20DEBUG/builds/928/steps/test_1/logs/stdio
http://buildlogs.mongodb.org/Windows%2064-bit%20DEBUG/builds/928/test/core/test.exe

Sat Aug 03 11:20:17.980 [testsuite] going to run suite: query_stage_merge_sort_test
Sat Aug 03 11:20:17.980 [testsuite] 	 going to run test: class QueryStageMergeSortTests::QueryStageMergeSortPrefixIndex
Sat Aug 03 11:20:17.996 [testsuite] build index unittests.QueryStageMergeSort { _id: 1 }
Sat Aug 03 11:20:17.996 [testsuite] build index done.  scanned 0 total records. 0.001 secs
Sat Aug 03 11:20:18.058 [testsuite] build index unittests.QueryStageMergeSort { a: 1, c: 1 }
Sat Aug 03 11:20:18.074 [testsuite] build index done.  scanned 100 total records. 0.014 secs
Sat Aug 03 11:20:18.074 [testsuite] build index unittests.QueryStageMergeSort { b: 1, c: 1 }
Sat Aug 03 11:20:18.089 [testsuite] build index done.  scanned 100 total records. 0.014 secs
Sat Aug 03 11:20:18.089 [testsuite] *** C runtime error: C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\INCLUDE\algorithm(2457) : Assertion failed: invalid operator<
Sat Aug 03 11:20:18.978 [testsuite] test.exe  ...\src\mongo\util\stacktrace.cpp(169)                                          mongo::printStackTrace+0x5b
Sat Aug 03 11:20:18.978 [testsuite] test.exe  ...\src\mongo\util\stacktrace.cpp(284)                                          mongo::crtDebugCallback+0x137
Sat Aug 03 11:20:18.978 [testsuite] test.exe  f:\dd\vctools\crt_bld\self_64_amd64\crt\src\dbgrptt.c(605)                      _VCrtDbgReportW+0x812
Sat Aug 03 11:20:18.978 [testsuite] test.exe  f:\dd\vctools\crt_bld\self_64_amd64\crt\src\dbgrpt.c(242)                       _CrtDbgReportWV+0x43
Sat Aug 03 11:20:18.978 [testsuite] test.exe  f:\dd\vctools\crt_bld\self_64_amd64\crt\src\dbgrpt.c(258)                       _CrtDbgReportW+0x4d
Sat Aug 03 11:20:18.978 [testsuite] test.exe  f:\dd\vctools\crt_bld\self_64_amd64\crt\src\stdthrow.cpp(13)                    std::_Debug_message+0x34
Sat Aug 03 11:20:18.978 [testsuite] test.exe  c:\program files (x86)\microsoft visual studio 10.0\vc\include\xutility(690)    std::_Debug_lt_pred<mongo::MergeSortStage::StageWithValueComparison,std::_List_iterator<std::_List_val<mongo::MergeSortStage::StageWithValue,std::allocator<mongo::MergeSortStage::StageWithValue> > >,std::_List_iterator<std::_List_val<mongo::MergeSortStage::StageWithValue,std::allocator<mongo::MergeSortStage::StageWithValue> > > >+0x9a
Sat Aug 03 11:20:18.978 [testsuite] test.exe  c:\program files (x86)\microsoft visual studio 10.0\vc\include\algorithm(2458)  std::_Push_heap<std::_List_iterator<std::_List_val<mongo::MergeSortStage::StageWithValue,std::allocator<mongo::MergeSortStage::StageWithValue> > > * __ptr64,__int64,std::_List_iterator<std::_List_val<mongo::MergeSortStage::StageWithValue,std::allocator<mongo::MergeSortStage::StageWithValue> > >,mongo::MergeSortStage::StageWithValueComparison>+0xe7
Sat Aug 03 11:20:18.978 [testsuite] test.exe  c:\program files (x86)\microsoft visual studio 10.0\vc\include\algorithm(2477)  std::_Push_heap_0<std::_List_iterator<std::_List_val<mongo::MergeSortStage::StageWithValue,std::allocator<mongo::MergeSortStage::StageWithValue> > > * __ptr64,__int64,std::_List_iterator<std::_List_val<mongo::MergeSortStage::StageWithValue,std::allocator<mongo::MergeSortStage::StageWithValue> > >,mongo::MergeSortStage::StageWithValueComparison>+0xf5
Sat Aug 03 11:20:18.978 [testsuite] test.exe  c:\program files (x86)\microsoft visual studio 10.0\vc\include\algorithm(2492)  std::push_heap<std::_Vector_iterator<std::_Vector_val<std::_List_iterator<std::_List_val<mongo::MergeSortStage::StageWithValue,std::allocator<mongo::MergeSortStage::StageWithValue> > >,std::allocator<std::_List_iterator<std::_List_val<mongo::MergeSortStage::StageWithValue,std::allocator<mongo::MergeSortStage::StageWithValue> > > > > >,mongo::MergeSortStage::StageWithValueComparison>+0x34d
Sat Aug 03 11:20:18.978 [testsuite] test.exe  c:\program files (x86)\microsoft visual studio 10.0\vc\include\queue(305)       std::priority_queue<std::_List_iterator<std::_List_val<mongo::MergeSortStage::StageWithValue,std::allocator<mongo::MergeSortStage::StageWithValue> > >,std::vector<std::_List_iterator<std::_List_val<mongo::MergeSortStage::StageWithValue,std::allocator<mongo::MergeSortStage::StageWithValue> > >,std::allocator<std::_List_iterator<std::_List_val<mongo::MergeSortStage::StageWithValue,std::allocator<mongo::MergeSortStage::StageWithValue> > > > >,mongo::MergeSortStage::StageWithValueComparison>::push+0x102
Sat Aug 03 11:20:18.978 [testsuite] test.exe  ...\src\mongo\db\exec\merge_sort.cpp(99)                                        mongo::MergeSortStage::work+0x34d
Sat Aug 03 11:20:18.978 [testsuite] test.exe  ...\src\mongo\db\query\simple_plan_runner.h(57)                                 mongo::SimplePlanRunner::getNext+0x7e
Sat Aug 03 11:20:18.978 [testsuite] test.exe  ...\src\mongo\dbtests\query_stage_merge_sort.cpp(132)                           QueryStageMergeSortTests::QueryStageMergeSortPrefixIndex::run+0x880
Sat Aug 03 11:20:18.978 [testsuite] test.exe  ...\src\mongo\unittest\unittest.h(296)                                          mongo::unittest::Suite::runTestObject<QueryStageMergeSortTests::QueryStageMergeSortPrefixIndex>+0x33
Sat Aug 03 11:20:18.978 [testsuite] test.exe  ...\src\third_party\boost\boost\function\function_template.hpp(113)             boost::detail::function::void_function_invoker0<void (__cdecl*)(void),void>::invoke+0x2f
Sat Aug 03 11:20:18.978 [testsuite] test.exe  ...\src\third_party\boost\boost\function\function_template.hpp(761)             boost::function0<void>::operator()+0x87
Sat Aug 03 11:20:18.978 [testsuite] test.exe  ...\src\mongo\unittest\unittest.h(194)                                          mongo::unittest::TestHolder::run+0x2f
Sat Aug 03 11:20:18.978 [testsuite] test.exe  ...\src\mongo\unittest\unittest.cpp(164)                                        mongo::unittest::Suite::run+0x74b
Sat Aug 03 11:20:18.978 [testsuite] test.exe  ...\src\mongo\unittest\unittest.cpp(228)                                        mongo::unittest::Suite::run+0x498

This problem produces a scarier-looking "Assertion failed: invalid heap" as well:

Sat Aug 03 11:20:19.930 [testsuite] *** C runtime error: C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\INCLUDE\algorithm(2387) : Assertion failed: invalid heap
Sat Aug 03 11:20:20.804 [testsuite] test.exe  ...\src\mongo\util\stacktrace.cpp(169)                                          mongo::printStackTrace+0x5b
Sat Aug 03 11:20:20.804 [testsuite] test.exe  ...\src\mongo\util\stacktrace.cpp(284)                                          mongo::crtDebugCallback+0x137
Sat Aug 03 11:20:20.804 [testsuite] test.exe  f:\dd\vctools\crt_bld\self_64_amd64\crt\src\dbgrptt.c(605)                      _VCrtDbgReportW+0x812
Sat Aug 03 11:20:20.804 [testsuite] test.exe  f:\dd\vctools\crt_bld\self_64_amd64\crt\src\dbgrpt.c(242)                       _CrtDbgReportWV+0x43
Sat Aug 03 11:20:20.804 [testsuite] test.exe  f:\dd\vctools\crt_bld\self_64_amd64\crt\src\dbgrpt.c(258)                       _CrtDbgReportW+0x4d
Sat Aug 03 11:20:20.804 [testsuite] test.exe  f:\dd\vctools\crt_bld\self_64_amd64\crt\src\stdthrow.cpp(13)                    std::_Debug_message+0x34
Sat Aug 03 11:20:20.804 [testsuite] test.exe  c:\program files (x86)\microsoft visual studio 10.0\vc\include\algorithm(2387)  std::_Debug_heap<std::_List_iterator<std::_List_val<mongo::MergeSortStage::StageWithValue,std::allocator<mongo::MergeSortStage::StageWithValue> > > * __ptr64,mongo::MergeSortStage::StageWithValueComparison>+0x101
Sat Aug 03 11:20:20.804 [testsuite] test.exe  c:\program files (x86)\microsoft visual studio 10.0\vc\include\algorithm(2622)  std::pop_heap<std::_Vector_iterator<std::_Vector_val<std::_List_iterator<std::_List_val<mongo::MergeSortStage::StageWithValue,std::allocator<mongo::MergeSortStage::StageWithValue> > >,std::allocator<std::_List_iterator<std::_List_val<mongo::MergeSortStage::StageWithValue,std::allocator<mongo::MergeSortStage::StageWithValue> > > > > >,mongo::MergeSortStage::StageWithValueComparison>+0x1a3
Sat Aug 03 11:20:20.804 [testsuite] test.exe  c:\program files (x86)\microsoft visual studio 10.0\vc\include\queue(349)       std::priority_queue<std::_List_iterator<std::_List_val<mongo::MergeSortStage::StageWithValue,std::allocator<mongo::MergeSortStage::StageWithValue> > >,std::vector<std::_List_iterator<std::_List_val<mongo::MergeSortStage::StageWithValue,std::allocator<mongo::MergeSortStage::StageWithValue> > >,std::allocator<std::_List_iterator<std::_List_val<mongo::MergeSortStage::StageWithValue,std::allocator<mongo::MergeSortStage::StageWithValue> > > > >,mongo::MergeSortStage::StageWithValueComparison>::pop+0xe0
Sat Aug 03 11:20:20.804 [testsuite] test.exe  ...\src\mongo\db\exec\merge_sort.cpp(131)                                       mongo::MergeSortStage::work+0x4c4
Sat Aug 03 11:20:20.804 [testsuite] test.exe  ...\src\mongo\db\query\simple_plan_runner.h(57)                                 mongo::SimplePlanRunner::getNext+0x7e
Sat Aug 03 11:20:20.804 [testsuite] test.exe  ...\src\mongo\dbtests\query_stage_merge_sort.cpp(132)                           QueryStageMergeSortTests::QueryStageMergeSortPrefixIndex::run+0x880
Sat Aug 03 11:20:20.804 [testsuite] test.exe  ...\src\mongo\unittest\unittest.h(296)                                          mongo::unittest::Suite::runTestObject<QueryStageMergeSortTests::QueryStageMergeSortPrefixIndex>+0x33
Sat Aug 03 11:20:20.804 [testsuite] test.exe  ...\src\third_party\boost\boost\function\function_template.hpp(113)             boost::detail::function::void_function_invoker0<void (__cdecl*)(void),void>::invoke+0x2f
Sat Aug 03 11:20:20.804 [testsuite] test.exe  ...\src\third_party\boost\boost\function\function_template.hpp(761)             boost::function0<void>::operator()+0x87
Sat Aug 03 11:20:20.804 [testsuite] test.exe  ...\src\mongo\unittest\unittest.h(194)                                          mongo::unittest::TestHolder::run+0x2f
Sat Aug 03 11:20:20.804 [testsuite] test.exe  ...\src\mongo\unittest\unittest.cpp(164)                                        mongo::unittest::Suite::run+0x74b
Sat Aug 03 11:20:20.804 [testsuite] test.exe  ...\src\mongo\unittest\unittest.cpp(228)                                        mongo::unittest::Suite::run+0x498
Sat Aug 03 11:20:20.804 [testsuite] test.exe  ...\src\mongo\dbtests\framework.cpp(270)                                        mongo::dbtests::runDbTests+0x1328
Sat Aug 03 11:20:20.804 [testsuite] test.exe  ...\src\mongo\dbtests\dbtests.cpp(41)                                           dbtestsMain+0x170

The problem code is src/mongo/db/exec/merge_sort.cpp line 205 (line 26 below):

    // Is lhs less than rhs?  Note that priority_queue is a max heap by default so we invert
    // the return from the expected value.
    bool MergeSortStage::StageWithValueComparison::operator()(
        const MergingRef& lhs, const MergingRef& rhs) {
 
        WorkingSetMember* lhsMember = _ws->get(lhs->id);
        WorkingSetMember* rhsMember = _ws->get(rhs->id);
 
        BSONObjIterator it(_pattern);
        while (it.more()) {
            BSONElement patternElt = it.next();
            string fn = patternElt.fieldName();
 
            BSONElement lhsElt;
            verify(lhsMember->getFieldDotted(fn, &lhsElt));
 
            BSONElement rhsElt;
            verify(rhsMember->getFieldDotted(fn, &rhsElt));
 
            // false means don't compare field name.
            int x = lhsElt.woCompare(rhsElt, false);
            if (-1 == patternElt.number()) { x = -x; }
            if (x != 0) { return x > 0; }
        }
 
        return true;
    }

Since the comparison function is supposed to return true or false in answer to the question "Is lhs less than rhs?" (strict weak ordering), the correct return value for equal items is 'false'.



 Comments   
Comment by auto [ 03/Aug/13 ]

Author:

{u'username': u'tadmarshall', u'name': u'Tad Marshall', u'email': u'tad@10gen.com'}

Message: SERVER-10426 Do not return 'true' from comparator for equal items in merge sort
Branch: master
https://github.com/mongodb/mongo/commit/dfc343cdf11462e89201d833db515de85f97bb45

Generated at Thu Feb 08 03:23:08 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.