sql: support lookup joins on secondary indexes

[petermattis]

Lookup joins are currently only supported when the right side of the join (the lookup side) is for the primary index. Supporting secondary index lookup joins requires an extra level of lookup (if the secondary index doesn't cover the columns in the query): first level lookup finds the primary key and the second level lookup reads the row. We have at least one user with a query which can benefit from this. The workaround is to perform the join "in the application", which is unsatisfactory.

If adding support for lookup joins on secondary indexes is not too intrusive, we should consider backporting this to 2.0.x.

[petermattis]

This looks relatively straightforward to do. Currently, joinReader only uses a single additional lookup for the right-hand side. Specifically, joinReader.mainLoop calls joinReader.indexLookup with a list of keys (spans) to read from the right-hand side. joinReader.indexLookup performs a scan (using a RowFetcher) for those keys and then outputs the resulting rows. Allowing lookup joins on secondary indexes would require another RowFetcher that takes the output of the first step and uses it to lookup rows in the primary index.

[jordanlewis]

There's also a small matter of allowing joinReader to construct secondary index keys in the first place. It's currently hardcoded to construct primary index keys.

Finally, joinReader should understand when the secondary index it's looking up into is covering, and not create a second index lookup step in that case.

[petermattis]

There's also a small matter of allowing joinReader to construct secondary index keys in the first place. It's currently hardcoded to construct primary index keys.

Where does that hardcoding occur? I see where the primaryKeyIndex variable is created, but besides the name I'm not seeing anything that is assuming that is the primary index.

[jordanlewis]

I think you're right, I was going on memory and the variable name confused me.

[knz]

I looked into this as well. Before going the route of the full indirect lookup, some mileage could be gained by extending verifyLookupJoin to accept secondary indexes that are covering of the requested columns. I think the entire execution logic would work in that case but there's a predicate against that in verifyLookupJoin for a reason that escapes me.

[petermattis]

@knz My understanding is that the full indirect lookup join is necessary for the customer query we were looking at last week. We could ask for the schema to be changed in order to be covering, though that might have negative effects (one of the fields was a string field of unknown size). My point in looking at this and filing this bug was to quantify the work involved in supporting indirect lookup joins. My conclusion is that it is straightforward work on deterministic code that we can knock out quickly.

[solongordon]

The approach @petermattis described makes sense to me, but it seems like we could also handle the second lookup via physical planning by adding an index join after the lookup join. I think that would keep the joinreader logic simpler since we wouldn't have to add the nested RowFetcher, but can anyone think of disadvantages?

[petermattis]

@solongordon That's a good idea. I can't think of any disadvantages, though you might run into practical problems as you explore this approach.

[petermattis]

Also, be aware that you'll have to adjust the distsql physical planning code (regardless of which approach to enhancing joinReader you take).

[solongordon]

The case where the secondary index doesn't cover all output columns may be trickier than we thought. Currently the logical planner plans an index join prior to the inner join, which seems problematic since we want it to come after.

root@:26257/> CREATE DATABASE d;
root@:26257/> CREATE TABLE d.t (x INT, y INT, z INT, PRIMARY KEY (x, y), INDEX y_idx (y));
root@:26257/> EXPLAIN SELECT t2.z FROM d.t t1 JOIN d.t@y_idx t2 ON t1.y = t2.y;
+----------------------+----------+-------------+
|         Tree         |  Field   | Description |
+----------------------+----------+-------------+
| render               |          |             |
|  └── join            |          |             |
|       │              | type     | inner       |
|       │              | equality | (y) = (y)   |
|       ├── scan       |          |             |
|       │              | table    | t@primary   |
|       │              | spans    | ALL         |
|       └── index-join |          |             |
|            ├── scan  |          |             |
|            │         | table    | t@y_idx     |
|            │         | spans    | ALL         |
|            └── scan  |          |             |
|                      | table    | t@primary   |
+----------------------+----------+-------------+

(I'm specifying d.t@y_idx for the right side since otherwise it just selects the primary index.)

I'm going to focus on the covering case for now but interested to hear thoughts on this.

[knz]

Solon perhaps we can make a heuristic that lifts the index join above the join in specific cases, in expandPlan(). Ping me or Radu if you want suggestions. -- Sent from my Android device with K-9 Mail. Please excuse my brevity.

[petermattis]

@solongordon I thought the point of your earlier suggestion was to change the planning so that the index-join is performed after the lookup-join. That is, the plan described in #25431 (comment) needs to be converted to one that looks like:

+------------------------+----------+-------------+
|         Tree           |  Field   | Description |
+------------------------+----------+-------------+
| render                 |          |             |
|  └── index-join        |          |             |
|        ├── lookup-join |          |             |
|        │     │         | type     | inner       |
|        │     │         | equality | (y) = (y)   |
|        │     ├── scan  |          |             |
|        │     │         | table    | t@primary   |
|        │     │         | spans    | ALL         |
|        │     └── scan  |          |             |
|        │               | table    | t@y_idx     |
|        │               | spans    | ALL         |
|        └── scan        |          |             |
|                        | table    | t@primary   |
+------------------------+----------+-------------+

I was imagining you would do this during distsql physical planning. @knz might have a better suggestion to do this during expandPlan. But mucking with the planning code might be more difficult than adding smarts to joinReader to be able to handle a lookup join on a secondary index during execution.

[solongordon]

Yes, that plan is what I had in mind though I hadn't realized that an index join would be logically planned below the inner join. It just makes things a bit more complicated since like @knz says we need to identify and "lift" the index join. I think this is the case even if we add more logic to joinReader since we still need to avoid performing the index join beforehand. I'll explore these options though.

[petermattis]

Yes, we need some tweak to planning even if we add more logic to joinReader. I was initially imagining this would happen in DistSQLPlanner.createPlanForJoin. If lookup-joins are enabled, then look for a structure where the right side of the join as an index-join and the left side of the join is a scan. If a lookup join is feasible, we convert this into either a lookup-join where the right side is a secondary index and joinReader is enhanced to support that, or we lift the index-join about the lookup-join. You should consult with @RaduBerinde and @knz about what is easier to do.