Interview drills: 'all', 'none' and division

Relational division finds the rows that are related to every member of a set: the students who applied to every drive of one recruiter, the customers who bought every product of a category. SQL has no division operator, so the answer is written in one of three ways: as a double negative (there is no drive the student did not apply to), as a count (the student’s distinct drives equal the recruiter’s), or as a set difference with EXCEPT. Two relatives share the interview round. “Only” means a match and nothing else, and “never” is an anti-join, the rows with no match at all. All three are short to state and easy to get subtly wrong, because duplicate rows, rows of other groups, a NULL in a subquery and an empty set each change the answer.

Two problems on one table of applications

Problem A: every. An invented hiring portal has students(id, name), recruiters(id, name), drives(id, recruiter_id, role) and applications(student_id, drive_id). Return the students who applied to every drive of Kaveri Analytics, an invented recruiter with three drives. A student may apply to the same drive twice, and a walk-in candidate without an account has a NULL student_id. At full size there are 1 million students, 400 drives for the largest recruiter and 30 million applications.

Problem B: only and never. Return the students who applied only to Kaveri drives, at least once and nowhere else, and the students who never applied to a Kaveri drive, including the students who applied to nothing.

The brute force, and why it fails at full size

Problem A’s literal translation pairs every student with every Kaveri drive and looks each pair up:

-- An invented hiring portal: students, recruiters, their drives and the applications.
CREATE TABLE students (id INTEGER PRIMARY KEY, name TEXT NOT NULL);
INSERT INTO students VALUES
  (1, 'Aarav'), (2, 'Bhavna'), (3, 'Charan'), (4, 'Divya'), (5, 'Esha'), (6, 'Farid');
CREATE TABLE recruiters (id INTEGER PRIMARY KEY, name TEXT NOT NULL);
INSERT INTO recruiters VALUES (1, 'Kaveri Analytics'), (2, 'Narmada Systems'), (3, 'Godavari Labs');
CREATE TABLE drives (id INTEGER PRIMARY KEY, recruiter_id INTEGER NOT NULL, role TEXT NOT NULL);
INSERT INTO drives VALUES
  (11, 1, 'data analyst'), (12, 1, 'data engineer'), (13, 1, 'BI developer'),
  (21, 2, 'backend developer'), (22, 2, 'QA engineer');
-- Godavari Labs has not announced a drive yet.
CREATE TABLE applications (
  student_id INTEGER,                 -- NULL: a walk-in candidate without an account
  drive_id   INTEGER NOT NULL
);
INSERT INTO applications VALUES
  (1, 11), (1, 12), (1, 13), (1, 22),           -- Aarav: every Kaveri drive, and one more
  (2, 11), (2, 13), (2, 13),                    -- Bhavna: two Kaveri drives, one of them twice
  (3, 11), (3, 12), (3, 13), (3, 12),           -- Charan: every Kaveri drive, one twice
  (4, 11), (4, 12), (4, 21),                    -- Divya: two Kaveri drives and a Narmada one
  (6, 21), (6, 22),                             -- Farid: both Narmada drives
  (NULL, 12);                                   -- a walk-in for the data engineer drive
-- Esha has not applied to anything.

-- Problem A, the literal translation: pair every student with every Kaveri drive and look
-- for each pair in applications. The student qualifies when every pair is found.
SELECT s.id, s.name
FROM students AS s
CROSS JOIN drives AS d
WHERE d.recruiter_id = 1
GROUP BY s.id, s.name
HAVING min(EXISTS (SELECT 1 FROM applications AS a
                   WHERE a.student_id = s.id AND a.drive_id = d.id)) = 1
ORDER BY s.id;

-- Problem B2, the first attempt: count the students whose id is not among the Kaveri applicants.
SELECT count(*) AS never_applied_to_kaveri
FROM students
WHERE id NOT IN (SELECT a.student_id
                 FROM applications AS a
                 JOIN drives AS d ON d.id = a.drive_id
                 WHERE d.recruiter_id = 1);

┌────┬────────┐
│ id │  name  │
├────┼────────┤
│ 1  │ Aarav  │
│ 3  │ Charan │
└────┴────────┘
┌─────────────────────────┐
│ never_applied_to_kaveri │
├─────────────────────────┤
│ 0                       │
└─────────────────────────┘

The first result, Aarav and Charan, is right. At full size the query builds 1,000,000 × 400 = 4 × 10⁸ pairs and runs a subquery for each, where one pass over 30 million applications would do. The second result is a first attempt at Problem B: NOT IN against the list of Kaveri applicants. It counts 0 students, although Esha and Farid never applied, because the walk-in’s NULL is in the list.

What to notice

• “Every” is a double negative: a student qualifies when no Kaveri drive lacks their application.
• A count works too, if it counts distinct drives and only the recruiter’s drives.
• EXCEPT removes the students who have a missing pair of student and drive.
• “Only” is “has one” plus “has nothing else”, and “never” is an anti-join with NOT EXISTS.
• NOT IN is never true once its list holds a NULL.
• Ask what an empty set means: a recruiter that has no drives yet.

Three ways to divide, on the same rows Pro: opens with a Pro, Premium or Ultimate pass