matrixorigin / matrixorigin/matrixone

[Performance]: Avoid full probe-table scans for right SINGLE joins without breaking multi-CN execution

Open
#25,862 2 comments 0 reactions 1 assignee Assigned to @XuPeng-SH View on GitHub
kind/performance severity/s0
Dominant language
Go
Stars
1.9k
Forks
311
Avg merge
1d 3h
Merged PRs (30d)
768

Description

### Is there an existing issue for performance?

- [x] I have checked the existing issues.

### Environment

- Version or commit-id: `main` at `946427b877c1b12c497743eff264047e60a00be2`
- Deployment: two-CN `make dev-up` cluster
- Hardware parameters: 24 CPU cores; 6 GiB file-service memory cache per CN
- OS type: Linux

### Details of Performance

A correlated scalar subquery can be flattened into a right `SINGLE` hash join when the preserved outer relation is much smaller than the inner table:

```sql
CREATE DATABASE rsingle_perf;
USE rsingle_perf;

CREATE TABLE big(id BIGINT PRIMARY KEY, v BIGINT);
INSERT INTO big
SELECT result, result * 10
FROM generate_series(1, 1000000, 1);

CREATE TABLE small(id BIGINT PRIMARY KEY);
INSERT INTO small VALUES (1), (5000000), (10000000);

ANALYZE TABLE big;
ANALYZE TABLE small;

SELECT s.id,
(SELECT b.v FROM big b WHERE b.id = s.id) AS v
FROM small s
ORDER BY s.id;
```

The optimizer physically swaps the scalar `SINGLE` join so that the small preserved relation is the hash-build side and `big` is the probe table:

```text
Join Type: RIGHT SINGLE
Join Cond: (b.id = s.id)
├── Table Scan: big -- probe; unmatched rows are discarded
└── Table Scan: small -- build and preserved side
```

On `main`, `generateRuntimeFilters` rejects every `Node_SINGLE` join. As a result, the query scans and probes all rows from `big`, even though the build side contains only three keys.

A one-CN prototype that generates a runtime filter only for right `SINGLE` reduced the work as follows:

| Metric from `EXPLAIN ANALYZE` | Main-equivalent path (RF disabled) | Right-SINGLE RF prototype |
| --- | ---: | ---: |
| `big` input blocks | 123 | 1 |
| `big` input rows | 1,000,000 | 1 |
| Join input rows | 1,000,003 | 4 |
| Scan read size | 7.68 MiB | 96.33 KiB |
| Warm-cache client latency | 0.21 s | 0.21 s |

The warm-cache latency at this scale is dominated by fixed/client overhead, but the avoided scan, I/O, and hash-probe work is substantial and should matter for larger/wider tables, cold cache, and concurrent workloads.

#### Important multi-CN constraint

Simply allowing `Node_SINGLE && IsRightJoin` through the existing runtime-filter gate is not safe.

With the same one-million-row data set forced onto the multi-CN execution path:

| Optimizer settings | Result |
| --- | --- |
| `runtimeFilter=1,execType=3` (RF disabled) | Completed correctly in 0.23 s |
| `execType=3` (naive right-SINGLE RF enabled) | Did not finish after 37.10 s; canceled manually with `context canceled` |

A natural ten-million-row AP multi-CN plan with the naive RF also failed to finish after more than 80 seconds. Therefore, this issue must not be fixed by only relaxing the join-type check. The right-SINGLE runtime-filter message/scheduling lifecycle must work across CNs, or the eligible plan must be safely constrained to one CN.

### Expected behavior / acceptance criteria

1. Eligible right `SINGLE` joins can filter a discardable table-scan probe using keys from the preserved build side.
2. Left `SINGLE` joins remain excluded because unmatched probe rows must be preserved.
3. Existing runtime-filter eligibility guards remain effective, including non-leading composite-primary-key checks and cardinality/selectivity limits.
4. Scalar-subquery semantics remain correct for matching keys, missing keys (`NULL`), and duplicate inner matches (cardinality violation).
5. Both one-CN and multi-CN executions finish without hangs and return identical results with the optimization enabled or disabled.
6. A multi-CN BVT/regression test covers the runtime-filter message lifecycle, not only the presence of Build/Probe specs in the logical plan.
7. `EXPLAIN ANALYZE` demonstrates reduced probe blocks/rows on a large-table/small-build case.

### Additional information

The right-SINGLE output-cardinality calculation has a separate optimizer-phase concern: `IsRightJoin` is set before `swapJoinChildren`, while the physical child order changes later. A generic cardinality change based only on `IsRightJoin` can be correct after the swap but wrong during earlier join-ordering passes. That change should not be bundled into this performance fix without a phase-safe preserved-side model and a downstream-join plan regression test.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.