[SERVER-63099] Constant folding should not assume arithmetic is associative or commutative in the general case Created: 28/Jan/22  Updated: 29/Oct/23  Resolved: 11/Jul/22

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

Type: Bug Priority: Major - P3
Reporter: Davis Haupt (Inactive) Assignee: Davis Haupt (Inactive)
Resolution: Fixed Votes: 0
Labels: query-director-triage
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Backports
Depends
depends on SERVER-65735 $add operator should not use DoubleDo... Closed
Documented
is documented by DOCS-15241 [SERVER] Constant folding not commuta... Closed
Duplicate
is duplicated by SERVER-66969 The $add aggregation expression is no... Closed
Problem/Incident
causes SERVER-67011 $const folding in $add expression in ... Closed
Related
related to SERVER-63018 Have ExpressionAdd::evaluate() return... Closed
is related to SERVER-65735 $add operator should not use DoubleDo... Closed
Backwards Compatibility: Fully Compatible
Operating System: ALL
Backport Requested:
v6.0
Steps To Reproduce:

db.coll.drop()
db.coll.insert({_id: 0, v: NumberDecimal("917.6875119062092")})
db.coll.insert({_id: 1, v: NumberDecimal("927.3345924210555")})
const pipeline = [
{$project: {product: {$multiply: [
	-3.14159265859,
	"$v",
	-314159255
]}}}
]
db.coll.aggregate(pipeline)
db.adminCommand({
	configureFailPoint: 'disablePipelineOptimization',
	mode: 'alwaysOn',
})
db.coll.aggregate(pipeline)
db.adminCommand({
	configureFailPoint: 'disablePipelineOptimization',
	mode: 'off',
})

Sprint: QO 2022-02-07, QO 2022-02-21
Participants:
Linked BF Score: 149

 Description   

Currently, arithmetic aggregation expressions like $multiply are marked as associative and commutative which allows the constant folding optimization to rearrange constants to combine as many of them as possible during optimization.

There are three reasons this is not a valid optimization in general:

1. For integers, this is not a safe optimization due to overflow. For example, 1073741824*-1*2 == -2147483648, but 1073741824*2*-1 overflows.

2. Floating point arithmetic is not generally associative. See this paper, specifically:

Due to roundoff errors, the associative laws of algebra do not necessarily hold for floating-point numbers. For example, the expression (x+y)z has a totally different answer than x(y+z) when x = 1030, y = -1030 and z = 1 (it is 1 in the former case, 0 in the latter). The importance of preserving parentheses cannot be overemphasized.

3. Type coercions occur when performing an operation on multiple types. For example, 1 + 0.5 + 2 will convert 1 from an integer to a float before adding it to 0.5. These type coercions are dependent on the order of operations and could change the result. See the "steps to reproduce" section for an example with `NumberDecimal`.

Because we can't know if a fieldpath will resolve to a specific number type or a value within a specific range, we cannot rule out any kind of overflow or type coercion.

After investigation, this only applies to ExpressionAdd and ExpressionMultiply.

As part of the fix for this ticket, we'll implement a left-to-right constant folding optimization that respects the order of operations during query execution while folding as many constants as is safe. For example, [c1, c2, c3, "$v", c5, c6] will be folded to [c', "$v", c5, c6].



 Comments   
Comment by Liubov Molchanova [ 26/Jul/22 ]

Requesting Backport as the issue reproduced in BFG-1274926 on v6.0.

Comment by Githook User [ 11/Jul/22 ]

Author:

{'name': 'Davis Haupt', 'email': 'davis.haupt@mongodb.com', 'username': 'davish'}

Message: SERVER-63099 Add left-associative constant folding optimization for $add and $multiply
Branch: master
https://github.com/mongodb/mongo/commit/b06f115c9575f51013c77c76b12d986c3373cd1f

Comment by Githook User [ 23/Jun/22 ]

Author:

{'name': 'Davis Haupt', 'email': 'davis.haupt@mongodb.com', 'username': 'davish'}

Message: Merge remote-tracking branch 'origin/master' into davish/SERVER-63099
Branch: davish/SERVER-63099
https://github.com/mongodb/mongo/commit/a119091c8ea63adc1126f92247457c02781e1797

Comment by Githook User [ 23/Jun/22 ]

Author:

{'name': 'Davis Haupt', 'email': 'davis.haupt@mongodb.com', 'username': 'davish'}

Message: Merge remote-tracking branch 'origin/master' into davish/SERVER-63099
Branch: davish/SERVER-63099
https://github.com/mongodb/mongo/commit/0d2029091f28a5e7e6c5fc225937dabf197cdd8b

Comment by Davis Haupt (Inactive) [ 10/May/22 ]

Satisfactory integration tests for this PR are blocked on SERVER-65735.

Comment by Davis Haupt (Inactive) [ 03/Mar/22 ]

david.percy I agree that that's a valid way to interpret it, but to give the other interpretation, the distinction that geert.bosch and anna.wawrzyniak made in the type promotion discussion last month was that users provide arguments to expressions like $add and $multiply in an explicit ordering. Accumulators like $sum, on the other hand, operate over a stream of documents that the user isn't explicitly providing in any order, and so it's much less unexpected that the optimizer could choose the ordering of the stream of documents based on an index, for example.

Comment by Timour Katchaounov [ 16/Feb/22 ]

The above benchmark clearly shows that in some cases (that can be quite common) there will be a ~20% performance regression. This is very substantial, and I believe we cannot push such a change.
There could be other solutions to this problem. For instance, if the arguments of all affected functions are normalized (ordered in some deterministic way) in advance, then both constant folding and direct execution should produce the same result. This normalization could be based on some heuristic that minimizes the possibility of overflow and other edge cases.

Comment by Davis Haupt (Inactive) [ 11/Feb/22 ]

The new Genny workload in PERF-2796 seems to 1) measure the impact of constant folding well and 2) show that adding a left-associative constant folding optimization can bring performance back up to the level seen on master currently if users manually re-arrange their operands to put all fieldpaths at the end of the operand list.

 
The new workload measures three optimization levels:

  • Full associativity and commutativity (master): All constants in an operand list are folded together into a single constant placed at the end of the operand list. [c1, c2, "$v", c3, c4] => ["$v", c'].
     
  • No associativity: If there is any fieldpath in the operand list, then no constants are folded together. [c1, c2, "$v", c3, c4] => [c1, c2, "$v", c3, c4], but [c1, c2, c3, c4] => c'.
  • Left associativity: All constants before the first fieldpath are folded together. [c1, c2, "$v", c3, c4] => [c'', "$v", c3, c4].

 

Note that the following results are from a single run of each configuration and so some variance is expected, but the orders of magnitude are what is significant. All numbers are in nanoseconds.

 

Test full associativity (master) no associativity left-associative folding
All Constants 7,644,713 8,708,571.2 (-14%) 8,606,583.6 (-13%)
Fieldpath at start 9,068,763.1 1,970,502,869.6 (-21,600%) 1,988,735,127.5 (-21,800%)
Fieldpath in middle 9,105,555.1 1,921,775,986.3 (-21,000%) 563,282,252.6 (-6,000%)
Fieldpath at end 9,032,214.8 1,958,538,232.6 (-21,500%) 8,572,041.8 (+5.09%)
Comment by Davis Haupt (Inactive) [ 10/Feb/22 ]

Opened PERF-2796 (with a PR here: https://github.com/mongodb/genny/pull/617) to create a new workload to measure constant folding speedups and get some baseline metrics on performance before fixing correctness. I'm also planning on adding a new DSI configuration variant with optimization disabled to compare metrics with the additional left-associative constant folding logic that's to be added.

Comment by Davis Haupt (Inactive) [ 28/Jan/22 ]

The simplest fix would be to change isAssociative() and isCommutative() for multiplication and addition. But there should be some discussion on whether there's a way to enable these optimizations in special cases where it's known to not cause overflow or trigger a type conversion.

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