Indexing for a Per-Group Top N

Concepts covered: Lateral Joins, Row Limiting, Sorting Results, Storage Optimization

The infrastructure probe arrives as a number. "Production Postgres, 3.2 million employee rows, and the HR portal's org page shows every department's top 3 in under 50 milliseconds. What index?" "An index on salary" finds the company's top 3; "an index on department_id" finds a department and then sorts it. The query needs each group's rows already in rank order and a way to stop after N, and an index supplies the order only when its key starts with the group column and continues with the ORDER BY.

The index is (department_id, salary DESC, hire_date ASC, employee_id ASC). The leading column locates the group's entries as 1 contiguous range. The following columns are the ORDER BY, so within that range the entries are already in rank order and no sort runs. The tail is the tiebreaker, which makes the index order total: 2 employees with the same salary and hire date sit in a fixed position in the index, the same position the query promised. Say the 3 parts in that sequence, because an index that puts salary first serves a different query.

ROW_NUMBER cannot stop early

The part most candidates miss is that the window query gets no stop from the index. In Postgres rn <= 3 sits above the WindowAgg; version 15 adds a run condition that stops computing row numbers past 3, but the operator still reads every remaining row of the partition to reach the next department. The plan is an ordered scan of all 3.2 million entries with 3,194,600 thrown away. Oracle's pushed rank and Spark 3.5's group limit cut rows earlier, and none of them jumps to the next group inside the index. The index saved the sort, not the read. The form that stops is a per-group LIMIT: LATERAL in Postgres, CROSS APPLY in SQL Server.

-- Per-group LIMIT: the planner runs the inner query once per department
SELECT d.department_id, t.employee_id, t.salary
FROM departments d
CROSS JOIN LATERAL (
  SELECT e.employee_id, e.salary
  FROM employees e
  WHERE e.department_id = d.department_id
  ORDER BY e.salary DESC, e.hire_date ASC, e.employee_id ASC
  LIMIT 3
) t;

That is 1 descent and 3 entries per department, a few milliseconds for the whole page. For a single department the stop needs no LATERAL: WHERE department_id = ? ORDER BY salary DESC, hire_date, employee_id LIMIT 3 reads 3 entries on its own, and LATERAL is that query run once per group. Say "the index gives order, the per-group LIMIT gives the stop," and expect the next question: can the index skip the table?

It can when every returned column is in the index: INCLUDE (employee_name) in Postgres 11 or later keeps the scan off the heap, where a department's 3 rows sit on 3 different pages. The trade is a wider entry on every insert, which shows up in HR's 40,000-row upload on the first of the month.

When the index does not pay

• A predicate outside the key: top 3 active employees needs is_active before salary, or a partial index WHERE is_active
• N close to the group size: a team of 5 with N = 3 reads 60% of the group, and the stop saves little
• Many tiny groups: 1.5 million groups of 2 rows cost 1.5 million index descents; 1 sort can be cheaper
• A rank key from another table: ordering by a joined bonus amount gives the employees index no order to read
• A columnar warehouse, which has no B-tree at all

That last item is where the round goes at a Snowflake or BigQuery shop. On a warehouse the work moves to layout: cluster by department_id so pruning reads a handful of micro-partitions, and accept a window over every row of those partitions. The sentence to say: "On a warehouse I would promise clustering by department and a window over the pruned scan; if 50 milliseconds is the requirement, the answer is the stored table served from a row store."

About this lesson

This section is part of the Top N Per Group: Advanced lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.