[SERVER-67776] Heuristic CE for FilterNode with a Boolean expression over comparison predicates Created: 05/Jul/22  Updated: 29/Oct/23  Resolved: 17/Aug/22

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

Type: Task Priority: Minor - P4
Reporter: Timour Katchaounov Assignee: Henri Nikku
Resolution: Fixed Votes: 0
Labels: M2
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Duplicate
is duplicated by SERVER-67774 Heuristic CE for FilterNode with a si... Closed
Backwards Compatibility: Fully Compatible
Sprint: QO 2022-08-08, QO 2022-08-22
Participants:

 Description   

Implement heuristic CE for FilterNode that contains a Boolean path expression of comparison operations. Boolean expressions inside a FilterNode are expressed via PathComposeM (AND), and PathComposeA (OR) nodes. This task should implement a transport that walks such path expression trees, and:

  • given an atomic comparison predicate uses Heuristic CE,
  • given a conjunction/disjunction applies exponential backoff estimation via bottom-up recursion.

This one example of a disjunction:

Query: {$or: [{a0: {$gt:44}}, {a0: {$lt: 9}}]}
 
Root []
|   |   projections: 
|   |       scan_0
|   RefBlock: 
|       Variable [scan_0]
Filter []
|   EvalFilter []
|   |   Variable [scan_0]
|   PathComposeA []
|   |   PathGet [a0]
|   |   PathTraverse []
|   |   PathComposeM []
|   |   |   PathCompare [Gte]
|   |   |   Const [nan]
|   |   PathCompare [Lt]
|   |   Const [9]
|   PathGet [a0]
|   PathTraverse []
|   PathComposeM []
|   |   PathCompare [Lt]
|   |   Const [""]
|   PathCompare [Gt]
|   Const [44]
Scan [test]
    BindBlock:
        [scan_0]
            Source []

This an example of more complex conjunction:

Query: {$and : [{$or : [ {a0 : {$gt : 11}}, {a0 : {$lt : 44}} ]},{$or : [ {a0 : {$gt : 77}}, {a0 : {$eq : 51}} ]}]}
Initial ABT:
Root []
|   |   projections: 
|   |       scan_0
|   RefBlock: 
|       Variable [scan_0]
Filter []
|   EvalFilter []
|   |   Variable [scan_0]
|   PathComposeA []
|   |   PathGet [a0]
|   |   PathTraverse []
|   |   PathCompare [Eq]
|   |   Const [51]
|   PathGet [a0]
|   PathTraverse []
|   PathComposeM []
|   |   PathCompare [Lt]
|   |   Const [""]
|   PathCompare [Gt]
|   Const [77]
Filter []
|   EvalFilter []
|   |   Variable [scan_0]
|   PathComposeA []
|   |   PathGet [a0]
|   |   PathTraverse []
|   |   PathComposeM []
|   |   |   PathCompare [Gte]
|   |   |   Const [nan]
|   |   PathCompare [Lt]
|   |   Const [44]
|   PathGet [a0]
|   PathTraverse []
|   PathComposeM []
|   |   PathCompare [Lt]
|   |   Const [""]
|   PathCompare [Gt]
|   Const [11]
Scan [test]
    BindBlock:
        [scan_0]
            Source []



 Comments   
Comment by Githook User [ 17/Aug/22 ]

Author:

{'name': 'Henri Nikku', 'email': 'henri.nikku@mongodb.com', 'username': 'henrinikku'}

Message: SERVER-67776 Heuristic CE for FilterNode with a Boolean expression over comparison predicates
Branch: master
https://github.com/mongodb/mongo/commit/08fff9d743eaa50932a42f43f8441b01fc36ebbd

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