Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-10426

Do not return 'true' from comparator for equal items in merge sort

    XMLWordPrintable

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major - P3
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 2.5.2
    • Component/s: Querying
    • Labels:
      None
    • Backwards Compatibility:
      Fully Compatible
    • Operating System:
      ALL

      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'.

        Attachments

          Activity

            People

            Assignee:
            tad Tad Marshall
            Reporter:
            tad Tad Marshall
            Participants:
            Votes:
            0 Vote for this issue
            Watchers:
            2 Start watching this issue

              Dates

              Created:
              Updated:
              Resolved: