Loose index scan can be used to speed up DISTINCT upon JOIN

[winoros]

Description

In issue https://github.com/pingcap/tidb/issues/14460. It proposed a scan method called loose index scan. This method is to scan the index and skip the same value.

In this issue, we describe a scene that is not mentioned in that issue.

Consider query select distinct t2.a from t1, t2 where t1.a=t2.a.

Since we need unique t2.a. So we also don't need t1.a return the same value twice, which means that we can apply a loose index scan on the t1 side.

Score

6600

Mentor

@winoros (Slack ID: Cui Yiding)

#sig-planner

Recommend Skills

• Golang and Rust

[winoros]

This cannot be easily done by pushing the aggregation down to the join. In this case, the t2 side may be very small. So we need also apply an index join on the t1. But index join will be abandoned if its child is aggregation.

And if the index used in the example is (a, col). Then the same value of the column a may not be in one region. So here we still need aggregation to duplicate the input of the t1.

But this will make the index join's construct logic strange. One solution is that we do the deduplication inside the index scan executor. Then we don't need to modify the index join's logic. Just support loose index scan for index reader executor.

[winoros]

Meanwhile, we can convert the inner join of this case to a semi join. Since it does behave like a semi join in this case.

[williamxiongwei]

/pick-up

[ti-challenge-bot[bot]]

It is not a pickable issue!

[watchpoints]

I want to do it, I am reading , the run explain and https://docs.qq.com/pdf/DSkNaZW9hTXNqWXVH

but I not how to start from code?

 explain select distinct t2.a from t1, t2 where t1.a=t2.a;
+-------------------------------+---------+-----------+----------------------+----------------------------------------------------------------------------+
| id                            | estRows | task      | access object        | operator info                                                              |
+-------------------------------+---------+-----------+----------------------+----------------------------------------------------------------------------+
| HashAgg_10                    | 99.90   | root      |                      | group by:test.t2.a, funcs:firstrow(test.t2.a)->test.t2.a                   |
| └─IndexMergeJoin_24           | 99.90   | root      |                      | inner join, inner:IndexReader_22, outer key:test.t1.a, inner key:test.t2.a |
|   ├─IndexReader_43(Build)     | 99.90   | root      |                      | index:IndexFullScan_42                                                     |
|   │ └─IndexFullScan_42        | 99.90   | cop[tikv] | table:t1, index:a(a) | keep order:false, stats:pseudo                                             |
|   └─IndexReader_22(Probe)     | 1.00    | root      |                      | index:Selection_21                                                         |
|     └─Selection_21            | 1.00    | cop[tikv] |                      | not(isnull(test.t2.a))                                                     |
|       └─IndexRangeScan_20     | 1.00    | cop[tikv] | table:t2, index:a(a) | range: decided by [eq(test.t2.a, test.t1.a)], keep order:true              |
+-------------------------------+---------+-----------+----------------------+----------------------------------------------------------------------------+

[winoros]

@watchpoints Do you have account in our community slack workspace? (you can find it in https://github.com/pingcap/community/#communication)

You can ask help in channel #sig-planner

[qxhy123]

/pick-up

[ti-challenge-bot[bot]]

Pick up success.

[qxhy123]

/give-up

[ti-challenge-bot[bot]]

Give up success.

[Reminiscent]

/pick-up

[ti-challenge-bot[bot]]

Pick up success.