[SERVER-33966] redundant $sort in aggregation prevents best $limit $sort consolidation Created: 19/Mar/18  Updated: 29/Oct/23  Resolved: 24/Jul/20

Status: Closed
Project: Core Server
Component/s: Aggregation Framework
Affects Version/s: None
Fix Version/s: 4.7.0, 4.4.3

Type: Improvement Priority: Major - P3
Reporter: Asya Kamsky Assignee: Ribhav Jain (Inactive)
Resolution: Fixed Votes: 0
Labels: QFB, neweng, optimization, performance, query-44-grooming
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Backports
Problem/Incident
causes SERVER-50897 Fix Sort/Limit/Sort Optimization Closed
Related
Backwards Compatibility: Minor Change
Backport Requested:
v4.7, v4.4
Sprint: Query 2020-06-29, Query 2020-07-13, Query 2020-07-27
Participants:
Case:
Linked BF Score: 16

 Description   

If there is an extra $sort that's identical to one before it, and there's a $limit after it, it causes an unfortunate full $sort of every document before the second sort which absorbed $limit is executed.

db.c.explain().aggregate([ {$sort: {a: 1}},{$sort:{a:1}},{$limit:5}]);
{
	"stages" : [
		{
			"$cursor" : {
				"query" : {
 
				},
				"sort" : {
					"a" : 1
				},
				"queryPlanner" : {
					"plannerVersion" : 1,
					"namespace" : "test.c",
					"indexFilterSet" : false,
					"parsedQuery" : {
 
					},
					"winningPlan" : {
						"stage" : "EOF"
					},
					"rejectedPlans" : [ ]
				}
			}
		},
		{
			"$sort" : {
				"sortKey" : {
					"a" : 1
				},
				"limit" : NumberLong(5)
			}
		}
	],
	"ok" : 1
}



 Comments   
Comment by Githook User [ 23/Oct/20 ]

Author:

{'name': 'Ribhav Jain', 'email': 'ribhav.jain@mongodb.com', 'username': 'ribhavjain'}

Message: SERVER-33966 Removed Redundant Sort

This reverts commit 861c7c059b48bfae315605a3f66fc3866b40dc7d.

(cherry picked from commit 052b000ab50bbf10f089f578ff6392c8d627dfc4)
Branch: v4.4
https://github.com/mongodb/mongo/commit/9b2ee74bf481010096207871e20e22e3f0584e0e

Comment by Githook User [ 21/Oct/20 ]

Author:

{'name': 'Nick Zolnierz', 'email': 'nicholas.zolnierz@mongodb.com', 'username': 'nzolnierzmdb'}

Message: TIG-2569 Block listing redundant sort in v4.4 for SERVER-33966 (BACKP… (#377)
Branch: master
https://github.com/10gen/jstestfuzz/commit/bcdc1bfb7a725e693fa78d2e6e25433c70f0a4d6

Comment by Githook User [ 24/Jul/20 ]

Author:

{'name': 'Ribhav Jain', 'email': 'ribhavjain@gmail.com', 'username': 'ribhavjain'}

Message: Revert "TIG-2569 Black listing redundant sort in v4.4 for SERVER-33966 (BACKPORT-7521)" (#361)
Branch: master
https://github.com/10gen/jstestfuzz/commit/3744b6790738812980a1750c18947cb56bc6cf2b

Comment by Githook User [ 24/Jul/20 ]

Author:

{'name': 'Ribhav Jain', 'email': 'ribhav.jain@mongodb.com', 'username': 'ribhavjain'}

Message: Revert "SERVER-33966 Removed Redundant Sort"

This reverts commit ed966606c2e5eb82f447c81986c64f8cfa0c74d7.
Branch: v4.4
https://github.com/mongodb/mongo/commit/563487e100c4215e2dce98d0af2a6a5a2d67c5cf

Comment by Githook User [ 23/Jul/20 ]

Author:

{'name': 'Ribhav Jain', 'email': 'ribhav.jain@mongodb.com', 'username': 'ribhavjain'}

Message: SERVER-33966 Removed Redundant Sort

This reverts commit 861c7c059b48bfae315605a3f66fc3866b40dc7d.

(cherry picked from commit be2be96f88517f8911b75223b4965d143ec79ba4)
Branch: v4.4
https://github.com/mongodb/mongo/commit/ed966606c2e5eb82f447c81986c64f8cfa0c74d7

Comment by Githook User [ 23/Jul/20 ]

Author:

{'name': 'Ribhav Jain', 'email': 'ribhavjain@gmail.com', 'username': 'ribhavjain'}

Message: TIG-2569 Black listing redundant sort in v4.4 for SERVER-33966 (BACKPORT-7521) (#358)
Branch: master
https://github.com/10gen/jstestfuzz/commit/0989a4b357974d12d32c3aa44f5d0d75eab3cc43

Comment by Githook User [ 10/Jul/20 ]

Author:

{'name': 'Ribhav Jain', 'email': 'ribhav.jain@mongodb.com'}

Message: SERVER-33966 Removed Redundant Sort

This reverts commit 861c7c059b48bfae315605a3f66fc3866b40dc7d.
Branch: master
https://github.com/mongodb/mongo/commit/052b000ab50bbf10f089f578ff6392c8d627dfc4

Comment by Githook User [ 10/Jul/20 ]

Author:

{'name': 'Ribhav Jain', 'email': 'ribhav.jain@mongodb.com'}

Message: Revert "SERVER-33966 Removed Redundant Sort"

This reverts commit 96cb86d41e4800b0f359a4d25dad2a6a94501e32.
Branch: master
https://github.com/mongodb/mongo/commit/251e0da292c5ac2cd55f148a1cc6b32568087cce

Comment by Githook User [ 10/Jul/20 ]

Author:

{'name': 'Ben Caimano', 'email': 'ben.caimano@10gen.com'}

Message: SERVER-33966 Removed Redundant Sort
Branch: master
https://github.com/mongodb/mongo/commit/96cb86d41e4800b0f359a4d25dad2a6a94501e32

Comment by Githook User [ 09/Jul/20 ]

Author:

{'name': 'Ribhav Jain', 'email': 'ribhavjain@gmail.com', 'username': 'ribhavjain'}

Message: TIG-2569 Added black listing for SERVER-33966 (#354)
Branch: master
https://github.com/10gen/jstestfuzz/commit/d2f2b228421fbc710de19ae3986201d8073b91f0

Comment by Githook User [ 08/Jul/20 ]

Author:

{'name': 'Ribhav Jain', 'email': 'ribhavjain@gmail.com', 'username': 'ribhavjain'}

Message: TIG-2569 Blacklist redundant $sort stages for 4.5 (SERVER-33966) (#351)
Branch: master
https://github.com/10gen/jstestfuzz/commit/973facabede7e2e2bcc2e64ec7ac744dd5792b4b

Comment by Asya Kamsky [ 26/Jun/20 ]

Having thought about it for 2 minutes I believe $sort should be able to disregard incoming order (consider sharding).

Comment by Asya Kamsky [ 26/Jun/20 ]

This ticket is about identical redundant sorts. $sort on a followed by sort on a is ... 100% a no-op or should be.

Interesting question about whether sort on a followed by sort on be is equivalent to sort on b:1,a:1... naively I would not fault users for assuming that it is so. But I don’t believe we guarantee it anywhere.... if they want to sort by two things they should be combined in the same sort.

Comment by David Percy [ 23/Jun/20 ]

Is $sort stable? Or is it allowed to discard the order of its input? If $sort is not stable, then we could eliminate redundant sorts (regardless of whether there is a $limit involved). For example, [ {$sort:{a:1}}, {$sort{b:1}} ] could be optimized to [ {$sort:{b:1}} ]. Then the usual $sort+$limit optimization would apply.

Comment by Asya Kamsky [ 26/Apr/18 ]

This ticket tracks $sort stage consolidation. SERVER-27744 tracks the same for $project/$addFields.

Comment by Ian Whalen (Inactive) [ 13/Apr/18 ]

asya each optimization would have to be implemented differently, so it'd be appreciated if you could file a specific ticket for each which you identify we don't do right now.

Comment by Asya Kamsky [ 09/Apr/18 ]

Did a quick test and we combine two sequential $match stages, combine any adjacent $limit and $skips, but we don't do anything to adjacent identical $project stages. Not sure if that should be handled with this ticket or separately (we do have SERVER-27744 for combining $project and $addFields when possible).

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