Refine Index Join

[zz-jason]

Feature Request

At present, the Index Join implementation is not efficient at some scenarios:

1. It may cause TiDB OOM because it uses the inner table to construct the hash table
2. It can not response to the parent in a short period, because it has to wait to all the inner rows matched the outer join key to be fetched out from TiKV and have build hash table on it, and do the join operation on the main thread.
3. The execution is not efficient, because all the join work are performed in the main thread, the outer and inner workers are only responsible for fetching data from TiKV

Describe the feature you'd like:

Split Index Join into two operators:

1. One for keep order. In this operator, the output of the Index Join should be ordered by the outer join key. We can do a Merge Join on a task
2. One for no need to keep order. In this operator, the output of the Index Join can have arbitrary order. In order to limit the memory consumption, we can use the outer rows inside a task to build the hash table and do hash join on the fetched inner rows, return a Chunk as soon as possible.

Describe alternatives you've considered:

No

Teachability, Documentation, Adoption, Migration Strategy:

After discussing offline, @yu34po will work on this issue.

[yu34po]

will fix the index join featuer in 3 PRs 1.add indexhashjoin for non order by query, Reserved old inderlookupjoin for order by query https://github.com/pingcap/tidb/pull/8661 2.add new joiner to fix column order with trytomatch/onmissmatch problems of indexhashjoin 3.add indexmergejoin to slove order by situation

[XuHuaiyu]

index hash join:

• [x] support index hash join in the execution engine basically https://github.com/pingcap/tidb/pull/8661
• [x] add interface tryToMatchOuters in joiner.go https://github.com/pingcap/tidb/pull/11922
• [x] support individual physical plan for index hash join
• [x] support new cost model for index hash join

index merge join:

• [x] support new cost model and individual physical plan for index merge join https://github.com/pingcap/tidb/pull/11338
• [x] support index merge join in the execution engine #12024