skip to content

Why does pairing a table with itself using a.id <> b.id return every pair twice?

level: middleimportance: should knowfreq 48%

answer

  1. n squared combinations before any predicate
  2. <> only removes the diagonal
  3. both directions of each pair survive
  4. one ordering must be declared canonical
  5. a.id < b.id, not a.id <> b.id

basics

~20 s

The predicate a.id <> b.id keeps both orderings of every pair, so (1,2) and (2,1) both survive. Replacing it with a.id < b.id keeps exactly one ordering, cutting n(n-1) rows to n(n-1)/2 while still excluding self-pairs.

solid answer

~40 s

A self-join over the same n rows starts from n squared ordered combinations. `a.id = b.id` would keep only the n self-pairs; `a.id <> b.id` removes those but keeps both directions of every genuine pair, giving n(n-1) rows in which each unordered pair appears twice with the columns swapped. Because the ids are totally ordered, `a.id < b.id` is the standard fix: for any two distinct rows exactly one of the two orderings satisfies it, so you get n(n-1)/2 rows, each unordered pair once, self-pairs already excluded. Use a column that is unique and comparable — normally the primary key — because the predicate is doing deduplication, not filtering. For a composite key, compare the row values: `(a.k1, a.k2) < (b.k1, b.k2)`.

code

sql · 3 lines
sql
-- n = 4 rows
SELECT COUNT(*) FROM teams a JOIN teams b ON a.team_id <> b.team_id; -- 12
SELECT COUNT(*) FROM teams a JOIN teams b ON a.team_id <  b.team_id; -- 6

go deeper

for a junior

Recall that a join with no restriction pairs every row with every row, and that a.id < b.id is the idiom for listing each pair once. Be able to count the rows for a small table.

for a middle

Explain why <> keeps both orderings and how a total order on a unique key picks one representative per pair. Know to put the business predicate alongside the ordering predicate in ON.

for a senior

Show when canonicalising is wrong because the relationship is asymmetric, and how you narrow the input before an all-pairs comparison instead of pairing a whole table and filtering afterwards.

for a principal

Own the decision of whether an all-pairs comparison belongs in a query at all at the data volumes involved, or whether the pairing should be constrained by a grouping key or precomputed.

## The counting problem Suppose `players` holds n rows and you want every unordered pair of players — a round-robin schedule, a similarity comparison, a "who shares a birthday with whom" report. A self-join with no `ON` restriction produces n squared rows: every row paired with every row, including itself. Three predicate choices carve that square up: - `a.id = b.id` keeps the diagonal: n rows, each row paired with itself. Useless here. - `a.id <> b.id` removes the diagonal: n(n-1) rows. Every genuine pair survives **twice**, once as (A,B) and once as (B,A). - `a.id < b.id` keeps the strict upper triangle: n(n-1)/2 rows, each unordered pair exactly once. For n = 4 those are 4, 12 and 6 rows. The handshake count 6 is the one people expect. ## Why the inequality does the deduplication The trick works because the join key is *totally ordered*: for any two distinct values exactly one of `x < y` and `y < x` is true. So the predicate acts as a tie-break that admits one canonical ordering of each pair and rejects the mirror image. It is not filtering data out of the answer — both mirrored rows carry identical information — it is choosing a representative. ```sql -- each unordered pair of teams exactly once SELECT a.name AS team_a, b.name AS team_b FROM teams AS a JOIN teams AS b ON a.team_id < b.team_id; ``` Because the point is canonicalisation, the column must be **unique** — otherwise two distinct rows sharing the value are neither `<` nor `>` each other and the pair disappears entirely — and it must be **comparable**. The primary key is the obvious candidate. If the key is composite, standard SQL lets you compare row values directly: ```sql ON (a.season, a.team_id) < (b.season, b.team_id) ``` ## Adding real predicates on top The ordering predicate composes with the business condition; both live in `ON`: ```sql -- pairs of bookings for the same room whose time ranges overlap SELECT a.booking_id, b.booking_id FROM bookings AS a JOIN bookings AS b ON a.booking_id < b.booking_id AND a.room_id = b.room_id AND a.starts_at < b.ends_at AND b.starts_at < a.ends_at; ``` This is the canonical overlap-detection self-join. Note how the ordering predicate also saves you from reporting a booking as overlapping itself, which the naive `a.booking_id <> b.booking_id` version would report twice per real conflict — an inflated count that looks alarming in a report. ## When the mirrored row is actually wanted The `<` form is not always right. If the relationship is **asymmetric** — "employees who earn more than their manager", "trades where a is the buyer and b is the seller" — direction carries meaning and you must not canonicalise. Ask yourself whether swapping the two aliases changes the meaning of the row. If it does, keep `<>` or a role-specific predicate; if it does not, use `<`. Sometimes you deliberately want both directions to make a symmetric lookup convenient — for instance a friendship table queried from either side. Then the `<` form generates the canonical set and a `UNION ALL` with the columns swapped materialises the mirror, rather than the join producing it by accident. ## The cost side, stated plainly All-pairs output is quadratic in the number of rows by definition: a thousand rows is half a million pairs, a hundred thousand rows is five billion. The `<` predicate halves it, which is a constant factor, not a change of shape. That is a property of the question being asked, so the practical move is to narrow the input first — restrict by group, date window or status inside a CTE or derived table — before pairing. ## What interviewers are checking They want to see that you can count the result of a join, that you recognise the mirrored-duplicate symptom ("my report shows every conflict twice"), and that you reach for `a.id < b.id` deliberately rather than sprinkling a `DISTINCT` over the output — `DISTINCT` cannot collapse (A,B) and (B,A) anyway, because those are different rows with different column values.

  • Why can't you just add DISTINCT to remove the mirrored duplicates?
    `DISTINCT` compares whole output rows, and (A,B) and (B,A) are different rows — different values in different columns — so it removes nothing. You would have to canonicalise the columns first, for example selecting `LEAST(...)` and `GREATEST(...)` style expressions, which is more work and less clear than putting `a.id < b.id` in the `ON` clause.
  • When is the mirrored row the correct output rather than a duplicate?
    Whenever the pair is asymmetric. "Employees paid more than their manager", "a follows b", "a is the buyer and b the seller" all break if you canonicalise, because swapping the aliases changes the fact being asserted. The test is simple: if exchanging the two aliases yields the same statement, use `<`; if it yields a different statement, keep both directions.
  • What breaks if the column in a.col < b.col is not unique?
    Two distinct rows sharing that value satisfy neither `<` nor `>`, so their pair is dropped from the result entirely — a silent under-count that looks like missing data. Always canonicalise on a unique, comparable column, normally the primary key, or on a row-value comparison of a composite key.

Shaking hands round a table: counting every ordered introduction records each handshake twice, once from each person's point of view. Insisting the person with the lower seat number goes first records each handshake exactly once.

  • Adds DISTINCT and expects mirrored pairs to collapse
  • Uses <> and then divides the count by two afterwards
  • Applies a.id < b.id to an asymmetric relationship
  • Canonicalises on a non-unique column and loses pairs
  • Thinks a WHERE clause after the join can undo the duplication

context