[SERVER-57533] Avoid creating intermediate objects for covered projections with OR stage Created: 08/Jun/21  Updated: 12/Dec/22  Resolved: 10/Dec/22

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

Type: Improvement Priority: Major - P3
Reporter: Nikita Lapkov (Inactive) Assignee: Drew Paroski
Resolution: Duplicate Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Duplicate
duplicates SERVER-71820 [SBE] Optimize projections and sorts ... Closed
Related
related to SERVER-72027 Complete TODO listed in SERVER-57533 Closed
related to SERVER-72052 Complete TODO listed in SERVER-57533 Closed
is related to SERVER-54745 Avoid creating intermediate object in... Closed
Assigned Teams:
Query Execution
Participants:

 Description   

Consider an example:

> db.test.insert({})
> db.test.createIndex({a: 1, b: 1})
> db.test.createIndex({b: 1, a: 1})
> db.test.find({$or: [{a: 1}, {b: 1}]}, {a: 1, b: 1, _id: 0}).explain()

The following plan will be selected for this covered query:

PROJECT -> OR -> [IXSCAN a,b ;  IXSCAN b,a]

The following SBE tree will be generated:

[4] traverse s18 s17 s15 [s16] {} {}
from
    [3] unique [s16]
    [3] union [s15, s16] [
        [s8, s5] [1] project [s8 = newObj ("a", s3, "b", s4)]
        [1] nlj [] [s6, s7]
            left
                [1] project [s6 = KS(2B020A0104), s7 = KS(2B02F0FE04)]
                [1] limit 1
                [1] coscan
            right
                [1] ixseek s6 s7 none s5 none [s3 = 0, s4 = 1] @"..." @"a_1_b_1" true
 
        ,
        [s14, s11] [2] project [s14 = newObj ("b", s9, "a", s10)]
        [2] nlj [] [s12, s13]
            left
                [2] project [s12 = KS(2B020A0104), s13 = KS(2B02F0FE04)]
                [2] limit 1
                [2] coscan
            right
                [2] ixseek s12 s13 none s11 none [s9 = 0, s10 = 1] @"9aaa2d3b-aafe-4c1f-a845-e6d06f97b9b2" @"b_1_a_1" true
 
 
   ]
in
    [4] cfilter {isObject (s15)}
    [4] mkbson s17 s15 [a, b] keep [] true false
    [4] limit 1
    [4] coscan

Each of the index scans is represented by the branch in the union stage. Each branch rehydrates index keys and creates intermediate objects. These objects are then traversed and passed into mkbson stage.

Instead, we can directly use the slots provided by union branches to build the resulting object once, without traverse, in the same way as SERVER-54745. Currently, we cannot do this because SBE stage builder assumes that for covered plans only one index exists. We have a fixed-size bitset to request index keys from child stages and fixed-size vector to retrieve them.

We should reconsider how we handle index keys for covered plans to fix this.



 Comments   
Comment by Ethan Zhang (Inactive) [ 15/Jun/21 ]

ksuarz@gmail.com We assigned this to the feature gap project, feel free to reassign if that's not appropriate.

Comment by Nikita Lapkov (Inactive) [ 09/Jun/21 ]

Plans with sort merge have the same problem.

Query:

> db.test.insert({})
> db.test.createIndex({a: 1, b: 1})
> db.test.createIndex({b: 1, a: 1})
> db.test.find({$or: [{a: 1}, {b: 1}]}, {_id: 0, a: 1, b: 1}).sort({a: 1, b: 1}).explain()

Plan:

PROJECT -> SORT_MERGE -> [IXSCAN a,b ;  IXSCAN b,a]

SBE tree:

[4] traverse s18 s17 s16 [s15] {} {}
from
    [3] unique [s15]
    [3] smerge [s15, s16] [asc, asc] [
        [s3, s4] [s5, s8] [1] project [s8 = newObj ("a", s3, "b", s4)]
        [1] nlj [] [s6, s7]
            left
                [1] project [s6 = KS(2B020A0104), s7 = KS(2B02F0FE04)]
                [1] limit 1
                [1] coscan
            right
                [1] ixseek s6 s7 none s5 none [s3 = 0, s4 = 1] @"..." @"a_1_b_1" true
 
        ,
        [s10, s9] [s11, s14] [2] project [s14 = newObj ("b", s9, "a", s10)]
        [2] nlj [] [s12, s13]
            left
                [2] project [s12 = KS(2B020A0104), s13 = KS(2B02F0FE04)]
                [2] limit 1
                [2] coscan
            right
                [2] ixseek s12 s13 none s11 none [s9 = 0, s10 = 1] @"9aaa2d3b-aafe-4c1f-a845-e6d06f97b9b2" @"b_1_a_1" true
 
 
   ]
in
    [4] cfilter {isObject (s16)}
    [4] mkbson s17 s16 [a, b] keep [] true false
    [4] limit 1
    [4] coscan

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