dolthub / dolthub/dolt

Detect and deduplicate self-joins on unique keys

Open
#7,709 1 comment 0 reactions 0 assignees View on GitHub
analyzer sql
Dominant language
Go
Stars
24.4k
Forks
873
Avg merge
1d 8h
Merged PRs (30d)
120

Description

A table that joins itself on a unique key can be deduplicated:

```sql
select * from mytable a join mytable b on a.i = b.i;
=>
select i, s, i, s from mytable;
```

In the above query, `(i)` is a unique key, and the output of the join will simply be the output of a single table.

This came up recently in a context where there was a self join on a non-unique key, but with a DISTINCT field that in practice collapses any join cardinality amplification:
```sql
select count(*) from (select distinct a.i from mytable a join mytable b on a.s = b.s);
=>
select count(*) from mytable;
```

In the above query, we join two tables on a non-unique key, `(s)`. Because `(s)` is non-unique, the output of a self-join on `s` might be greater than the table on its own. The DISTINCT operator removes any of this duplication, letting us remove the self-join.

In the general case, DISTINCT only nullifies some varieties of join duplication:

```sql
select * from (select distinct a,i, count(*) as cnt from mytable a join mytable b on a.s = b.s where cnt > 3)
```

In the query above, we added a filter between the self-join and DISTINCT that depends on the self-join cardinality. Aggregations, windows, or scalar subqueries whose logic depends on self-join cardinality all have this issue (and potentially other operators).

I think it might be safe to apply this optimization:
- same table joined on a unique key
- same table joined on a non-unique key and a DISTINCT operator and no aggregation/window/scalar subquery expression between the join and DISTINCT

Contributor guide

No contributing guide indexed for this repository

Research direction

The issue names no implementation files or tests. Start by locating the SQL optimizer entry points for self-joins, unique-key reasoning, DISTINCT, and cardinality-sensitive operators, then test the supplied queries and their edge cases. Done means the optimization is applied only under the stated safety conditions and existing query results remain unchanged.

Written by the indexing model from the issue text.

Assessment

Tech stack
go, sql
Domain
databases, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
32/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.