Support left outer (anti) right semi join
Open
Nobody has claimed this yet.
type/enhancement
- Dominant language
- C++
- Stars
- 1k
- Forks
- 423
- Avg merge
- 1d 15h
- Merged PRs (30d)
- 24
Description
Enhancement
This pr https://github.com/pingcap/tiflash/pull/7267 has implemented right semi and right anti join, which uses the left table to build hash table. But we still missing the left outer version of right semi and right anti join.
For example:
mysql> explain select * from nation where N_REGIONKEY not in (select L_SUPPKEY from lineitem);
+--------------------------------------+-------------+--------------+----------------+---------------------------------------------------------------------------------------------------------------------------------+
| id | estRows | task | access object | operator info |
+--------------------------------------+-------------+--------------+----------------+---------------------------------------------------------------------------------------------------------------------------------+
| TableReader_31 | 20.00 | root | | MppVersion: 2, data:ExchangeSender_30 |
| └─ExchangeSender_30 | 20.00 | mpp[tiflash] | | ExchangeType: PassThrough |
| └─HashJoin_29 | 20.00 | mpp[tiflash] | | anti semi join, equal:[eq(tpch10.nation.n_regionkey, tpch10.lineitem.l_suppkey)], stream_count: 10 |
| ├─ExchangeReceiver_13(Build) | 25.00 | mpp[tiflash] | | stream_count: 10 |
| │ └─ExchangeSender_12 | 25.00 | mpp[tiflash] | | ExchangeType: HashPartition, Compression: FAST, Hash Cols: [name: tpch10.nation.n_regionkey, collate: binary], stream_count: 10 |
| │ └─TableFullScan_11 | 25.00 | mpp[tiflash] | table:nation | keep order:false |
| └─ExchangeReceiver_16(Probe) | 59986052.00 | mpp[tiflash] | | |
| └─ExchangeSender_15 | 59986052.00 | mpp[tiflash] | | ExchangeType: HashPartition, Compression: FAST, Hash Cols: [name: tpch10.lineitem.l_suppkey, collate: binary] |
| └─TableFullScan_14 | 59986052.00 | mpp[tiflash] | table:lineitem | keep order:false |
+--------------------------------------+-------------+--------------+----------------+---------------------------------------------------------------------------------------------------------------------------------+
9 rows in set (0.03 sec)
mysql> explain select * from nation where N_REGIONKEY not in (select L_SUPPKEY from lineitem) or N_REGIONKEY > 100;
+------------------------------------------+-------------+--------------+----------------+-----------------------------------------------------------------------------------------------------+
| id | estRows | task | access object | operator info |
+------------------------------------------+-------------+--------------+----------------+-----------------------------------------------------------------------------------------------------+
| TableReader_34 | 20.00 | root | | MppVersion: 2, data:ExchangeSender_33 |
| └─ExchangeSender_33 | 20.00 | mpp[tiflash] | | ExchangeType: PassThrough |
| └─Projection_8 | 20.00 | mpp[tiflash] | | tpch10.nation.n_nationkey, tpch10.nation.n_name, tpch10.nation.n_regionkey, tpch10.nation.n_comment |
| └─Selection_32 | 20.00 | mpp[tiflash] | | or(Column#21, gt(tpch10.nation.n_regionkey, 100)) |
| └─HashJoin_29 | 25.00 | mpp[tiflash] | | anti left outer semi join, equal:[eq(tpch10.nation.n_regionkey, tpch10.lineitem.l_suppkey)] |
| ├─ExchangeReceiver_16(Build) | 59986052.00 | mpp[tiflash] | | |
| │ └─ExchangeSender_15 | 59986052.00 | mpp[tiflash] | | ExchangeType: Broadcast, Compression: FAST |
| │ └─TableFullScan_14 | 59986052.00 | mpp[tiflash] | table:lineitem | keep order:false |
| └─TableFullScan_13(Probe) | 25.00 | mpp[tiflash] | table:nation | keep order:false |
+------------------------------------------+-------------+--------------+----------------+-----------------------------------------------------------------------------------------------------+
9 rows in set (0.00 sec)
In the first anti semi join, the nation that is the smaller table can be used to build hash table, while in the second anti left outer semi join, the lineitem is used to build hash table.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by reviewing PR 7267 and tracing the existing right semi and right anti join implementation in the join planning and execution paths. The issue names no files or tests; completion should support the left outer variants and produce the anti left outer semi join plans shown in the SQL examples.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- databases
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 30/100