optimization: self-join no longer results in delta query plan after relation CSE transform

[asenac]

materialize=> explain SELECT * FROM t1, t1 t3 WHERE t3.f1 = t1.f1;                                                            
                Optimized Plan                
----------------------------------------------
 %0 = Let l0 =                               +
 | Get materialize.public.t1 (u31)           +
 | Filter !(isnull(#0))                      +
                                             +
 %1 =                                        +
 | Get %0 (l0)                               +
 | ArrangeBy (#0)                            +
                                             +
 %2 =                                        +
 | Join %1 %0 (= #0 #2)                      +
 | | implementation = Differential %0 %1.(#0)+
 | | demand = (#0, #1, #3)                   +
 | Project (#0, #1, #0, #3)                  +

(1 row)

materialize=>

The query above used to result in a DeltaQuery before #7715

[frankmcsherry]

What was the delta query it used to be? Was the filter hoisted and we used an existing arrangement, or was %0 arranged once, and then shared by both inputs? ~It seems that the weirdness here is that we have pushed down a null filter into one branch but not the other, even though we would be happy with either arranged filtered data, or arranged non-filtered data with a post-processing filter.~

Does the same thing happen with a AND f1 = 7 sort of constraint, that would be another filter predicate that could be pushed down one side and not the other, or is it specific to null tests? (nvm: I will test this part out!)

[asenac]

The scenario is:

create table t1(f1 int, f2 int);
create index i1 on t1(f1);

so the arrangement used was an existing one.

[frankmcsherry]

Hrm. Looking at it, it seems like it could be fixed by something simple, which is "ArrangeBy pushdown", where if we arrange a local Get we might as well push down the arrangement instructions. I don't know if that is over fixated on this one problem, but it seems potentially legit. We didn't have this problem pre-LIR because arranging a Get would "share" the arrangement, but I bet join planning wouldn't have been bright enough to use that.

~This seems also bad / much worse, in that the above is 2x the memory we need, but this below is unboundedly more than we need:~ I got confused about whether the filter was shared (~%0 is not l0~ the actual problem was thinking that l0 is the top of the first stack, not the end). Nvm the "even worse" vibe.

materialize=> explain SELECT * FROM t1, t1 t3 WHERE t3.f1 = t1.f1 and t1.f1 = 7;
               Optimized Plan               
--------------------------------------------
 %0 = Let l0 =                             +
 | Get materialize.public.t1 (u1)          +
 | Filter (#0 = 7)                         +
                                           +
 %1 =                                      +
 | Get %0 (l0)                             +
 | ArrangeBy ()                            +
                                           +
 %2 =                                      +
 | Join %1 %0                              +
 | | implementation = Differential %0 %1.()+
 | | demand = (#0..#3)                     +

[frankmcsherry]

It kind of makes me think we should reconsider ArrangeBy at some point, now knowing more about the logical/physical split (where it probably ends up in the physical side of things).

In other words: it seems like both of the above should have relation CSE trigger, but somehow it didn't find the re-use until after we introduced the ArrangeBy. Or it found the re-use, but perhaps join planning then broke it by putting an arrange in front of only one of them?

[asenac]

Or it found the re-use, but perhaps join planning then broke it by putting an arrange in front of only one of them?

That is exactly what happened. RelationCSE happens before JoinImplementation so we through the following steps:

 %0 =                             +
 | Get materialize.public.t1 (u1)          +
 | Filter (#0 = 7)                         +
                                           +
 %1 =                                      +
 | Get materialize.public.t1 (u1)          +
 | Filter (#0 = 7)                         +
                                           +
 %2 =                                      +
 | Join %1 %0                              +
 | | implementation = ... +

--------------------------------------------
 %0 = Let l0 =                             +
 | Get materialize.public.t1 (u1)          +
 | Filter (#0 = 7)                         +
                                           +                                          +
 %1 =                                      +
 | Join %0 %0                              +
 | | implementation = Differential ...+
--------------------------------------------
 %0 = Let l0 =                             +
 | Get materialize.public.t1 (u1)          +
 | Filter (#0 = 7)                         +
                                           +
 %1 =                                      +
 | Get %0 (l0)                             +
 | ArrangeBy ()                            +
                                           +
 %2 =                                      +
 | Join %1 %0                              +
 | | implementation = Differential %0 %1.()+
 | | demand = (#0..#3)       

[wangandi]

This is fixed by #7864, but we should not close this ticket until we more thoroughly evaluate whether or not we want to keep the solution in its current form.

---

Explanation of current fix:

Turning

 %0 =                             +
 | Get materialize.public.t1 (u1)          +
 | Filter (#0 = 7)                         +
                                           +
 %1 =                                      +
 | Get materialize.public.t1 (u1)          +
 | Filter (#0 = 7)                         +

into ​

%0 = Let l0 =                             +
​| Get materialize.public.t1 (u1)          +
​| Filter (#0 = 7)                         +

is beneficial for eliminating redundant joins but is bad when deciding the join implementation because JoinImplementation cannot peer through a Get(<local id>).

My fix is to add a step right before JoinImplementation to inline Lets whose value is an MFP around a Get so that JoinImplementation can lift MFPs around the Get to use an arrangement. https://github.com/MaterializeInc/materialize/blob/c3d1c74c001ef7065aa03c55ec9e481e60dcfaad/src/transform/src/lib.rs#L304

[uce]

We probably look at this in a more holistic manner when revisiting join planning.