[SERVER-67416] Always sort fieldpath string sets using custom comparator Created: 21/Jun/22  Updated: 29/Oct/23  Resolved: 06/Jul/22

Status: Closed
Project: Core Server
Component/s: None
Affects Version/s: None
Fix Version/s: 6.1.0-rc0, 6.0.5

Type: Improvement Priority: Major - P3
Reporter: Steve Tarzia Assignee: Steve Tarzia
Resolution: Fixed Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Backports
Depends
is depended on by SERVER-72651 $match filter is erroneously pushed p... Closed
Related
is related to SERVER-66418 Bad projection created during depende... Closed
Backwards Compatibility: Fully Compatible
Backport Requested:
v6.0
Sprint: QO 2022-06-27, QO 2022-07-11
Participants:

 Description   

Whenever we store sets of field paths strings (eg., ["a.b", "a", "c.d"]) use a custom string comparator that treats "." as the first character.

This is to protect us against future bugs like SERVER-66418.  It also makes the solution to that issue more efficient (because it avoids a set copy) and would allow O(n log n) solutions to many field path comparison functions that currently are O(n^2).  For example `isIndependentOf` and `isOnlyDependentOn` in https://github.com/mongodb/mongo/blob/master/src/mongo/db/matcher/expression_algo.cpp#L802



 Comments   
Comment by Githook User [ 19/Jan/23 ]

Author:

{'name': 'Steve Tarzia', 'email': 'steve.tarzia@mongodb.com', 'username': 'starzia'}

Message: SERVER-67416 Always sort fieldpath string sets using custom comparator
Branch: v6.0
https://github.com/mongodb/mongo/commit/e69b196acf52afe38a15fc55b4626ac8bfddc5c7

Comment by Githook User [ 19/Jan/23 ]

Author:

{'name': 'Steve Tarzia', 'email': 'steve.tarzia@mongodb.com', 'username': 'starzia'}

Message: SERVER-67416 Always sort fieldpath string sets using custom comparator
Branch: v6.0
https://github.com/10gen/mongo-enterprise-modules/commit/ca6b6383477a01f7291c46519159bc62c70ee0dc

Comment by Steve Tarzia [ 09/Jan/23 ]

Will backport to v6.0 to fix a plan generation bug explained in this comment in BF-27387

Comment by Steve Tarzia [ 06/Jul/22 ]

The patch for this seems to fix some instances of a long-standing query correctness bug (SERVER-23229), but we should do more investigation to find and add the test cases that still fail.  It's doubtful that that bug was really fixed by this.

Edit: My mistake – I confirmed that SERVER-23229 is not at all related to the work on this ticket.

Comment by Githook User [ 06/Jul/22 ]

Author:

{'name': 'Steve Tarzia', 'email': 'steve.tarzia@mongodb.com', 'username': 'starzia'}

Message: SERVER-67416 SERVER-23229 Always sort fieldpath string sets using custom comparator
Branch: master
https://github.com/mongodb/mongo/commit/19bd7993d149b68918f0d589551c1bf6781c5b63

Comment by Githook User [ 06/Jul/22 ]

Author:

{'name': 'Steve Tarzia', 'email': 'steve.tarzia@mongodb.com', 'username': 'starzia'}

Message: SERVER-67416 SERVER-23229 Always sort fieldpath string sets using custom comparator
Branch: master
https://github.com/10gen/mongo-enterprise-modules/commit/2b29a176797d02ce13be38fa8ad097dba7ec1286

Comment by Steve Tarzia [ 05/Jul/22 ]

Passed all tests here: https://spruce.mongodb.com/version/62bf72ef57e85a3859f459d8/tasks

Resolved merge conflicts and created mergeQueue patch here:
https://spruce.mongodb.com/version/62c455ff3e8e86453ecb041d/tasks?sorts=STATUS%3AASC%3BBASE_STATUS%3ADESC 

 

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