SELECT DISTINCT inner join is not optimized as semijoin, causing duplicate-insensitive fanout expansion

Summary

In MariaDB 12.3.2, a SELECT DISTINCT query is planned with a join order that expands the fanout of an inner-joined table even though that table contributes no projected columns and only provides existence semantics.

The default plan runs about 13.5 ms. A JOIN_ORDER hint that places the duplicate-insensitive table last runs about 2.0 ms because the last table uses "distinct": true. A result-equivalent EXISTS rewrite in this testcase runs about 0.9-1.0 ms using a materialized subquery with distinct_key.

This looks like a missed semijoin / duplicate-insensitive join optimization under SELECT DISTINCT.

Version

12.3.2-MariaDB

Session settings:

optimizer_prune_level = 0

optimizer_join_limit_pref_ratio = 0

The attached testcase runs ANALYZE TABLE and ANALYZE TABLE ... PERSISTENT FOR ALL before collecting plans.

How to reproduce

Run the attached testcase:

mariadb --comments --table < mariadb_distinct_semijoin_missed_repro_plus_controls.sql > result.txt 2>&1

The --comments option is important because the testcase uses an optimizer hint.

Query

Default query:

SELECT DISTINCT t0.c1 AS ref0, t3.c1, t0.c0

FROM t3

JOIN t0 ON t3.c0 = t0.c0

JOIN t1 ON t0.c0 = t1.c0

ORDER BY t0.c7 ASC

LIMIT 8;

Hinted query:

SELECT /*+ JOIN_ORDER(t3, t0, t1) */ DISTINCT t0.c1 AS ref0, t3.c1, t0.c0

FROM t3

JOIN t0 ON t3.c0 = t0.c0

JOIN t1 ON t0.c0 = t1.c0

ORDER BY t0.c7 ASC

LIMIT 8;

Result-equivalent EXISTS rewrite in this testcase:

SELECT DISTINCT t0.c1 AS ref0, t3.c1, t0.c0

FROM t3

JOIN t0 ON t3.c0 = t0.c0

WHERE EXISTS (

  SELECT 1

  FROM t1

  WHERE t1.c0 = t0.c0

)

ORDER BY t0.c7 ASC

LIMIT 8;

Observed behavior

All three queries return the same result set.

ANALYZE FORMAT=JSON shows:

default SELECT DISTINCT inner join:

  cost ~= 1.84

  runtime ~= 13.5 ms

JOIN_ORDER(t3,t0,t1):

  cost ~= 8.83

  runtime ~= 2.0 ms

EXISTS rewrite:

  cost ~= 0.40

  runtime ~= 0.9-1.0 ms

In my run, the hinted plan is estimated as more expensive, but runs about 6-7x faster. The EXISTS rewrite runs about 14-15x faster than the default plan.

Plan evidence

The default plan is:

t0 -> t1 -> t3

The default plan expands t1 fanout before probing t3:

t1:

  r_loops = 90

  r_rows  = 15.2

t3:

  r_loops = 1368

  r_rows  = 14.78

The hinted plan is:

t3 -> t0 -> t1

The last table t1 has:

"distinct": true

and ANALYZE shows:

t1:

  r_loops = 1317

  r_rows  = 0.863

This suggests that when t1 is joined last, MariaDB can stop after the first matching t1 row because t1 does not contribute columns to the SELECT DISTINCT output.

The EXISTS rewrite uses a materialized semijoin-like plan:

<table_name>: <subquery2>

access_type: eq_ref

key: distinct_key

materialized: unique = 1

Auxiliary scale-up testcase

I also attached a scale-up testcase that keeps the DISTINCT result cardinality at 7 rows but increases the duplicate-insensitive t1 fanout.

In this testcase:

t0 rows = 320

t1 rows = 7000

t3 rows = 320

full DISTINCT result cardinality = 7

raw inner join rows for hot keys ~= 5,600,000

The unhinted SELECT DISTINCT inner join still chooses a fanout-expanding join order:

t0 -> t1 -> t3

ANALYZE FORMAT=JSON shows:

default:

  cost ~= 4.66

  runtime ~= 3450 ms

  t1 r_rows ~= 437.5

  t3 r_loops = 140000

JOIN_ORDER(t3,t0,t1):

  cost ~= 32.11

  runtime ~= 18 ms

  t1 has "distinct": true

  t1 r_rows ~= 0.875

EXISTS rewrite:

  cost ~= 2.53

  runtime ~= 7 ms

  t1 has "first_match": "t0"

  t1 r_rows ~= 0.875

In my run, the hinted plan is estimated as more expensive but runs about 188x faster. The EXISTS rewrite runs about 476x faster.

The same issue also appears in the no ORDER/LIMIT control. Therefore this does not appear to be only an ORDER BY/LIMIT costing problem; it is mainly duplicate-insensitive fanout expansion under SELECT DISTINCT.

The scale-up testcase is intended as an impact amplifier. The smaller testcase above is the primary reproducer because it is simpler and also includes additional controls.

Why this looks like an optimizer issue

The table t1 does not contribute any projected columns:

SELECT DISTINCT t0.c1, t3.c1, t0.c0

Under DISTINCT semantics, t1 multiplicity is duplicate-insensitive. t1 is only needed to test whether a matching row exists.

MariaDB already handles the explicit EXISTS version efficiently using semijoin strategies: materialized subquery / distinct_key lookup in the main testcase, and first_match in the scale-up testcase. However, it does not infer the same existence semantics from the SELECT DISTINCT inner join form.

Additional controls

The attached testcase includes two additional controls.

1. Removing ORDER BY/LIMIT does not remove the issue. The default DISTINCT inner join still runs about 13.2 ms, while the EXISTS rewrite runs about 0.88 ms.

2. Replacing ORDER BY with a projected column also does not remove the issue. The default plan still runs about 13.3 ms, while the EXISTS rewrite runs about 0.90 ms.

So the issue does not appear to be only an ORDER BY/LIMIT costing issue. The main issue is missed semijoin / duplicate-insensitive fanout handling under SELECT DISTINCT.

Expected behavior

The optimizer should avoid expanding duplicate-insensitive fanout under SELECT DISTINCT when a joined table contributes no projected columns and only provides existence semantics.

Possible approaches might include:

• choosing a join order where the duplicate-insensitive table is joined last and can use DISTINCT early-stop;
• transforming/costing the join similarly to an EXISTS / semijoin;
• accounting for the fact that this table's multiplicity will be removed by DISTINCT and should not be expanded before probing later tables.