[SERVER-6126] Value::compare is not a transitive comparison for certain numeric values Created: 19/Jun/12  Updated: 11/Jul/16  Resolved: 11/Dec/12

Status: Closed
Project: Core Server
Component/s: Aggregation Framework
Affects Version/s: None
Fix Version/s: 2.3.2

Type: Improvement Priority: Major - P3
Reporter: Aaron Staple Assignee: Mathias Stearn
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
is related to SERVER-3719 woCompare does not provide a total or... Closed
Participants:

 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.



 Comments   
Comment by Mathias Stearn [ 11/Dec/12 ]

Resolving now that behavior is the same as BSON. A more complete change will be needed after SERVER-3719 is resolved.

Comment by auto [ 11/Dec/12 ]

Author:

{u'date': u'2012-11-28T00:34:39Z', u'email': u'mathias@10gen.com', u'name': u'Mathias Stearn'}

Message: Make Value::compare behave the same as BSONElement::woCompare

Related cases:
SERVER-6125 $sort on heterogeneous types
SERVER-6126 Value::compare transitivity (now exactly as broken as BSONObj)
Branch: master
https://github.com/mongodb/mongo/commit/323f3924fbb835c8180d95153fb976c4a224157b

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