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

Value::compare is not a transitive comparison for certain numeric values

    • Type: Icon: Improvement Improvement
    • Resolution: Done
    • Priority: Icon: Major - P3 Major - P3
    • 2.3.2
    • Affects Version/s: None
    • Component/s: Aggregation Framework
    • None

      In particular, certain high precision long longs can compare equal to their shared double approximations but not equal to each other. This can cause out of order sorting and potentially undefined behavior when the Value::compare is used by a library.

      As a slightly separate issue, I think the comparison is also problematic for NaN double values.

      Test:

      c = db.c;
      c.drop();
      
      Random.setRandomSeed();
      
      // Insert some long longs requiring high precision, that may or may not round trip as doubles.    
      s = "11235399833116571";
      for( i = 0; i < 1000; ++i ) {
          n = NumberLong( s + Random.randInt( 10 ) );
          // Randomly pick either the long long or its float approximation to insert.                   
          c.insert( { x: ( Random.randInt( 2 ) ? n : n.floatApprox ) } );
      }
      
      // If both a and b cannot be represented as doubles, assert that a <= b.                          
      function assertLteIfHighPrecisionLongs( a, b ) {
          if ( !a.bottom || !b.bottom ) {
      	return;
          }
          assert.lte( a.top, b.top );
          if ( a.top == b.top ) {
      	assert.lte( a.bottom, b.bottom );
          }
      }
      
      // Verify sorted aggregation results are in a consistent order.                                   
      result = c.aggregate( { $sort:{ x:1 } } ).result;
      assert.eq( 1000, result.length );
      for( right = 1; right < 1000; ++right ) {
          for( left = 0; left < right; ++left ) {
      	assertLteIfHighPrecisionLongs( result[ left ].x, result[ right ].x );
          }
      }
      

      Observed behavior: Certain numeric comparisons do not satisfy the transitive property.
      Expected behavior: All comparisons satisfy the transitive property.

            Assignee:
            mathias@mongodb.com Mathias Stearn
            Reporter:
            aaron Aaron Staple
            Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

              Created:
              Updated:
              Resolved: