For a link table holding two foreign keys, how do you choose between a composite primary key on those keys and a separate surrogate id, and what indexes does the table need so lookups are fast from both sides?

## The two candidate keys A link table `membership(user_id, group_id)` can be keyed two ways. **Composite natural key:** `PRIMARY KEY (user_id, group_id)`. Identity is the pair. Two identical links are impossible by construction. **Surrogate key:** `id` as primary key, with `user_id` and `group_id` as ordinary foreign-key columns. Identity is artificial; uniqueness of the pair must be added separately with a unique constraint. ## Why the composite key is the default - It states the truth of the model: a link *is* the pair. - It enforces the most important invariant of a link table — no duplicate relationships — with zero extra objects. - It costs one index instead of two (a surrogate key needs its own index plus a unique index on the pair to be equally safe). - Narrower rows and fewer indexes mean less write amplification and a smaller table, which matters because link tables are often the largest tables in a schema. - In engines with clustered/index-organised storage, the composite key also determines physical ordering, so rows for the same `user_id` sit together and range scans are near-sequential. ## When a surrogate key earns its place 1. **Something references an individual link.** If each membership has audit rows, approvals, or attachments, those tables would otherwise have to carry both columns of the composite key. One column is easier and narrower, and it stays stable if the pair definition ever changes. 2. **The pair may legitimately repeat.** A student re-taking a course, an employee re-joining a team, a subscription cancelled and restarted. The composite key forbids the second row outright. Here you either add a surrogate key with a unique constraint on `(a_id, b_id, valid_from)`, or key on the pair plus the start date. 3. **The natural key is wide.** Two 36-character identifiers propagated into three dependent tables is a real storage and index-size cost. 4. **Tooling constraints.** Some ORMs and change-data-capture or replication tools handle single-column keys far better than composite ones. This is a legitimate but secondary reason; note that it is a tooling accommodation, not a modelling improvement. What a surrogate key does **not** buy you is correctness. `id` makes every row distinct, so without `UNIQUE (a_id, b_id)` the table will accumulate duplicate links, and every `COUNT`, every join and every permission check built on it becomes subtly wrong. If you take the surrogate, the unique constraint is mandatory, not optional. ## Index design and the leading-column rule A B-tree index on `(a_id, b_id)` is sorted by `a_id` first. The engine can seek into it only if `a_id` is constrained. Queries filtering on `b_id` alone must either scan the whole index or scan the table. Since link tables are almost always traversed in both directions — "groups for this user" and "users in this group" — you need two indexes: - `PRIMARY KEY (user_id, group_id)` - `INDEX (group_id, user_id)` The second index is deliberately the reversed pair rather than `(group_id)` alone, because including the other column makes it **covering**: the join or existence check can be answered from the index without a table lookup, which on a hot permissions table is a large win. Column order in the primary key should follow the more selective or more frequent access path, especially in clustered engines where it dictates physical layout. If 95% of traffic is "list groups for a user", lead with `user_id`. A further reason for the reverse index: many engines must check child rows when a parent is deleted or its key updated. Without an index on `group_id`, deleting a group scans the entire link table, and in some engines takes locks while doing so. ## Extra columns and their effect If the link carries attributes — role, joined_at, quantity — they sit in the row and do not change the key choice, unless one of them participates in identity (a validity date, as above). Beware of adding wide attributes to a link table that is otherwise index-covered: once the row is wide, index-only access still works for the key columns, but any query selecting the attribute pays the table lookup. ## Soft deletes A `deleted_at` column interacts badly with the composite key: once a link is soft-deleted, re-creating it violates the primary key. Either hard-delete link rows (usually right — a relationship that ended can be recorded as an event elsewhere), or move to the surrogate key with a uniqueness rule that applies only to live rows (a partial/filtered unique index where supported, or a computed column trick where not). ## Review checklist Does the table forbid duplicate pairs? Are both foreign keys NOT NULL? Is there an index usable from each direction? Are the delete actions declared? Is the key choice justified by something concrete, or copied from a template?