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

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

    XMLWordPrintableJSON

Details

    • Icon: Improvement Improvement
    • Resolution: Done
    • Icon: Major - P3 Major - P3
    • 2.3.2
    • None
    • Aggregation Framework
    • None

    Description

      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.

      Attachments

        Activity

          People

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

            Dates

              Created:
              Updated:
              Resolved: