DISTINCT

Parse SELECT DISTINCT and COUNT(DISTINCT e), remove repeated output rows with a set of the rows already seen, hand each new row up at once so a LIMIT can still stop early, and leave the Distinct out when the rows cannot repeat.

Not run yet · 11 tests

Why this stage exists

select dept from emp prints a department for every employee, so eng comes out three times. Most of the time the question was which departments are there?, and the answer is each one once. That is select distinct dept from emp.

You have already built it, almost. DISTINCT is GROUP BY over the whole select list with no aggregates: select distinct dept from emp gives the same rows as select dept from emp group by dept. Rows are compared item by item, a NULL is the same as a NULL, and the first of each set of equal rows is the one that stays, so the order is first-seen order again.

Streaming

One thing makes Distinct different from a HashAggregate. An aggregate cannot hand up a group until it has seen every row, since a later row might add to it. A Distinct has nothing to add: the moment it sees a row it has not seen before, that row is finished. So it hands it up at once, and remembers it.

That keeps the early stop of the limit-offset stage working. select distinct dept from emp limit 2 reads row 1 (eng), row 2 (ops), has its two rows, and stops: rows_examined=2. A Distinct that read everything first would examine all eight.

select distinct dept from emp limit 2

Limit (count=2, offset=0)

↑ 2 rows: eng, ops

new

Distinct

remembers eng, ops; hands each up the moment it is new

↑ 2 rows: eng, ops

Project (cols=[dept])

↑ rows 1 and 2, then never asked again

ran

SeqScan (table=emp)

A Distinct does not block: row 1 (eng) and row 2 (ops) are new, so they go straight up, the Limit has its two rows, and the scan stops at rows_examined=2.

Sorting distinct rows

ORDER BY now has to sort what DISTINCT leaves, so the Sort moves above the Distinct:

droid session

>explain select distinct dept from emp where salary > 50 order by dept limit 2;
[PLAN] select distinct dept from emp where salary > 50 order by dept limit 2
[PLAN]   └── Limit (count=2, offset=0)
[PLAN]       └── Sort (key=dept ASC)
[PLAN]           └── Distinct
[PLAN]               └── Project (cols=[dept])
[PLAN]                   └── Filter (salary > 50)
[PLAN]                       └── SeqScan (table=emp)

Above the Distinct the rows only hold the items, so a key must be one of them: select distinct dept from emp order by salary would have to put "eng" somewhere by a salary it no longer has, one of three. That is 01509. Order by an item, its alias, or the item written the same way.

When there is nothing to remove

A row that includes the table's first column cannot repeat: that column is unique. So when the select list is *, or holds the first column on its own as an item, the planner leaves the Distinct out, and the plan is the one without DISTINCT. This is the planner using a fact about the data, the primary key's uniqueness, to skip work; the Indexes and the Optimizer part does much more of it.

COUNT(DISTINCT e)

Inside COUNT, DISTINCT counts the different values instead of the rows: count(distinct dept) is 3 where count(dept) is 6. NULLs are still skipped. With GROUP BY each group counts its own: the different salaries per department. Only COUNT takes DISTINCT here; sum(distinct salary) is 01506.

The algorithm in words

Run the Distinct operator

Distinct sits right above the Project, so the rows it sees are output rows.

1.Keep a set of the rows handed up so far, compared item by item, with NULL equal to NULL, as GROUP BY compares keys.
2.When asked for a row, ask the child for rows until one is not in the set, or the child runs out.
3.Add that row to the set and hand it up at once.
4.Invariant: every row handed up is different from every earlier one, and rows come out in the order the child first produced them.

Count the different values

COUNT(DISTINCT e) is an aggregate with a set inside its state.

1.Start with an empty set and a count of 0.
2.Step: evaluate e. If it is NULL, skip it. If it is not in the set yet, add it and count one.
3.Finish: the count. With GROUP BY, each group has a set of its own.

Plan it, or leave it out

DISTINCT changes where ORDER BY sorts, and sometimes it is not needed at all.

1.If the select list is *, or holds the table's first column alone as an item, every row is already different: plan no Distinct.
2.Otherwise put a Distinct above the Project.
3.With a Distinct, every ORDER BY key must be an item, an alias or the same expression (01509), and the Sort goes above the Distinct, sorting the rows it hands up. The Limit stays on top.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, section 49.

Input	Output
`select distinct dept from emp;`	`dept`, then `eng`, `ops`, `NULL`, `hr`, `(4 rows)`
`select distinct dept from emp limit 2;`	`eng`, `ops`, `[EXEC] rows_examined=2`
`explain select distinct id, dept from emp;`	`Project (cols=[id, dept])` over `SeqScan`: no Distinct
`select count(distinct dept) from emp;`	header `COUNT(DISTINCT dept)`, value `3`
`ast select distinct dept, salary / 50 from emp;`	`Columns: [dept, salary / 50]`, then `Distinct: true`
`select distinct dept from emp order by salary;`	`[ERROR:01509] <message>`
`select distinct from emp;`	`[ERROR:00302] <message>`
`sum(distinct salary)`, `count(distinct *)`	`[ERROR:01506] <message>`

The Distinct node prints as Distinct, with no fields. Under it the Project; above it the Sort, when there is one, and the Limit.

What you should see when done

shell

$droid --db staff.db
Welcome to droid!
>select distinct dept from emp;
dept
eng
ops
NULL
hr
(4 rows)
[EXEC] rows_examined=8
>select distinct dept from emp order by dept desc limit 2;
dept
ops
hr
(2 rows)
[EXEC] rows_examined=8 sort_runs=1
>select count(distinct dept), count(dept), count(*) from emp;
COUNT(DISTINCT dept) | COUNT(dept) | COUNT(*)
3 | 6 | 8
(1 rows)
[EXEC] rows_examined=8
>select distinct dept from emp order by name;
[ERROR:01509] ORDER BY with DISTINCT must use an item of the select list
>.exit
exiting.. good bye!

The second query had to read every row, because the Sort above the Distinct needs all the distinct rows before it can hand up the first. The messages are yours to word; the tests check only the codes.

Common bugs in this stage

Blocking. A Distinct that collects every row before handing up any gives the right rows and loses LIMIT's early stop.
Rows glued into one string. ('ab', 'c') and ('a', 'bc') collapse into one. Compare items one by one.
NULL never equal. Every NULL row survives. For DISTINCT, as for GROUP BY, NULL equals NULL.
Sorting below the Distinct. It sorts rows that are then thinned out; the order survives, but a key that is not an item is accepted when it must be 01509.
A Distinct over the primary key. Correct, but the plan must leave it out.
COUNT(DISTINCT) counting NULL. NULLs are skipped, as in every aggregate but COUNT(*).

Language notes

The page above is the same for every language. These are the only language-specific hints.

C and C++: reuse the key-tuple hash table from the previous stage, with the whole output row as the key and no aggregate state. In C++, an unordered_set of rows with the same hash.
Rust: a HashSet<Vec<Value>>; insert returns whether the row was new, which is exactly the test this operator needs.
Zig: a std.HashMap with a void value, keyed by the row with the same context as the GROUP BY keys.

Loading starter code…

No run yet

11 tests wait for your first run

Run tests builds your code, drives the binary through every case for this stage, and shows expected and received output side by side here. Failing cases come first.