sql: propagate equalities to optimize JOIN filters further

[knz]

Pursuant to #12617, suggested by @RaduBerinde, relative to predicates over JOINs

it wouldn't be too hard to also duplicate any vars that refer to right columns which are constrained to be equal to a left column (and vice-versa). This can happen regardless if merged columns exist.

For example SELECT * FROM a JOIN b where a.x = b.y AND b.y > 5 AND b.y < 10. It would be nice for the 5-10 range to make it to the a source.

This entails propagating the equalities to the inequalities, perform range analysis, and propagate the resulting ranges towards the JOIN operands.

[RaduBerinde]

This entails propagating the equalities to the inequalities, perform range analysis, and propagate the resulting ranges towards the JOIN operands.

My suggestion was not around range analysis and such, but simply to allow splitFilter to convert between left and right IndexVars that we know are equal. If the splitFilter callback knows that b.y is the same as a.x, it can go from
a.x = b.y AND b.y > 5 AND b.y < 10 to a leftExpr of a.x > 5 AND a.x < 10.

It's not clear how to calculate the remaining filter (the part that can't be pushed down) with this method, but we can be less functional on that part (it's not a big deal if it's not as small as possible, as long as it disappears in common cases where it needs to disappear).

[knz]

Even equalities should be propagated.

@bdarnell reports:

root@:26257/test> explain select * from customer join orders on (customer.id=orders.customer_id) where customer.id='x';
+-------+------+----------+----------------------+
| Level | Type |  Field   |     Description      |
+-------+------+----------+----------------------+
|     0 | join |          |                      |
|     0 |      | type     | inner                |
|     0 |      | equality | (id) = (customer_id) |
|     1 | scan |          |                      |
|     1 |      | table    | customer@primary     |
|     1 |      | spans    | /"x"-/"x\x00"        |
|     1 | scan |          |                      |
|     1 |      | table    | orders@primary       |
|     1 |      | spans    | ALL                  |
+-------+------+----------+----------------------+
(9 rows)
root@:26257/test> explain select * from customer join orders on (customer.id=orders.customer_id) where customer.id='x' and orders.customer_id='x';
+-------+------+----------+----------------------+
| Level | Type |  Field   |     Description      |
+-------+------+----------+----------------------+
|     0 | join |          |                      |
|     0 |      | type     | inner                |
|     0 |      | equality | (id) = (customer_id) |
|     1 | scan |          |                      |
|     1 |      | table    | customer@primary     |
|     1 |      | spans    | /"x"-/"x\x00"        |
|     1 | scan |          |                      |
|     1 |      | table    | orders@primary       |
|     1 |      | spans    | /"x"-/"x\x00"        |
+-------+------+----------+----------------------+
(9 rows)

Also my manual optimizations on https://forum.cockroachlabs.com/t/select-query-not-responding/672/32

[petermattis]

Is there a complexity here that I'm not seeing? Seems like there is a pretty big win on many queries from implementing this.

[knz]

Yes the complexity is that I still do not understand splitFilter() well enough that I would know where to implement this effectively.

[RaduBerinde]

The logic would be in the varConvertFunc callback that is passed to splitFilter - if we're trying to get a filter for a and the function knows that a.x = b.y and sees b.y it can convert it to a.x rather than returning !ok.

[petermattis]

The action is all in planner.addJoinFilter, right? Conceptually straightforward, but after looking at that code I now understand @knz's statement.

[knz]

Yet I think I understand what Radu is saying :)
I'll have a look next week.

[andy-kimball]

Propagation for this case appears supported by both the heuristic optimizer and the cost-based optimizer. Closing as "Fixed".