Ranking Queries & Top-k Algorithms

01 · Motivation

Why “best” needs a definition

In business applications a query has an exact result and every row is equally relevant. In consumer applications there is a notion of preferability — and preferences over several criteria at once rarely agree.

The general problem: given $N$ objects described by $d$ attributes, and some notion of the “goodness” of an object, find the best $k$. It shows up in search engines, e-commerce, recommender systems, and in machine learning as $k$-nearest-neighbours, feature selection and classification.

Two families of answer, and this chapter and the next take one each:

02 · Foundations

Rank aggregation

The oldest version of the problem, from social choice theory: combine several ranked lists into one consensus ranking, when no scores are visible — only positions.

Given $n$ candidates and $m$ voters, who wins? Two classical answers disagree:

• Borda (1770): election by order of merit. First place scores 1 point, second 2, …, $n$-th scores $n$. A candidate’s penalty is the sum; the Borda winner has the lowest penalty.
• Condorcet (1785): the Condorcet winner is the candidate who defeats every other in a pairwise majority contest.

They can pick different winners on the same ballots — the lectures’ example gives Borda to C (penalty 16) while A wins every pairwise contest. Worse, Condorcet’s paradox: with cyclic preferences (voter 1 ranks C B A, voter 2 ranks B A C, voter 3 ranks A C B) no Condorcet winner exists.

The metric approach instead seeks a new ranking $R$ whose total distance to $R_1, \ldots, R_n$ is minimal, for some distance between rankings:

MedRank approximates footrule-optimal aggregation using only positions. It makes sorted accesses one element at a time in each list until $k$ elements have appeared in more than $m/2$ lists; those are the top $k$, ordered by median rank. The maximum number of sorted accesses per list is the algorithm’s depth. In the hotels example, at depth 5 the answer is Novotel (median 3), then Hilton and Ibis (median 5 each).

03 · Theory

Instance optimality

The guarantee that makes some of these algorithms remarkable, and it is considerably stronger than worst-case optimality.

An algorithm $X$ is instance-optimal when there is a constant $m$ — the optimality ratio — such that

The quantifier order is what matters: for every input, not on average and not in the worst case. A worst-case-optimal algorithm may still be beaten arbitrarily badly on particular inputs. Binary search is the standard illustration — it is worst-case optimal at $\Theta(\log n)$ against sequential search’s $\Theta(n)$, but on an input whose target sits in the first position, sequential search costs 1 and binary search costs $\log n$. So binary search is not instance-optimal.

MedRank is not optimal in the absolute sense, but it is instance-optimal among algorithms that access the lists in sorted order, with optimality ratio 2.

04 · SQL

Top-k queries in SQL

Two capabilities are needed — order by score, and stop after k. SQL took until 2008 to standardise the second.

SELECT * FROM USEDCARS
WHERE Vehicle = 'Audi/A4'
ORDER BY 0.8 * Price + 0.2 * Miles
FETCH FIRST 5 ROWS ONLY;          -- SQL:2008; DB2, PostgreSQL, Oracle, SQL Server

with the non-standard spellings still common in the wild: LIMIT k (PostgreSQL, MySQL), ROWNUM <= k (Oracle), SELECT TOP k (SQL Server).

The weights 0.8 and 0.2 are how you say that price matters four times as much as mileage. Their necessity is the point of the following comparison:

-- A: hard threshold                    -- B: rank everything
WHERE Vehicle='Audi/A4'                 WHERE Vehicle='Audi/A4'
  AND Price <= 21000                    ORDER BY 0.8*Price + 0.2*Miles
ORDER BY 0.8*Price + 0.2*Miles

Query A suffers near-miss: a car at €21 500 with exceptionally low mileage is discarded although it may be the best deal. Query B suffers information overload: every Audi A4 in the database comes back. Top-k is the middle path.

Evaluation depends on the access paths available. For a single relation: if the input is already sorted by the scoring function, read the first $k$ tuples and stop. If not, and $k$ is small — the typical case — keep a heap of size $k$ while scanning: the whole input must be read, at cost $O(N \log k)$.

05 · Model

Geometry: distances, weights, and the score space

Seeing scores geometrically explains what weights do, and connects top-k to nearest-neighbour search.

Represent each tuple as a point — say (Price, Mileage). Minimising $0.8 \cdot Price + 0.2 \cdot Mileage$ means looking for points close to the ideal target $(0,0)$. The set of equally-good points for a value $v$ satisfies $0.8 \cdot Price + 0.2 \cdot Mileage = v$, which rearranges to $Mileage = -4 \cdot Price + 5v$: a family of parallel lines of slope −4. Changing the weights rotates the family, and a different point touches it first — which is exactly how weights select a winner.

The target need not be the origin. Looking for a house with a 1000 m² garden and 3 bedrooms makes $(1000, 3)$ the target, and “goodness” becomes distance from the target. That reframes a top-k query as a $k$-nearest-neighbours query: given a target $q$, a relation $R$, an integer $k$ and a distance $d$, find the $k$ tuples closest to $q$.

The distances used are the $L_p$ (Minkowski) norms:

with three cases doing all the work — and each having a characteristic iso-distance shape:

Weights stretch the coordinates, turning circles into ellipsoids, rhombi into rhomboids and squares into rectangles:

so the weighted sum you started with is simply a weighted $L_1$ distance. Note that in the weighted $L_2$ the weights are not squared: $\sqrt{\sum_i w_i \lvert t_i - q_i \rvert^2}$.

For the middleware setting the model is normalised. Each object $o$ returned by input list $L_j$ has a local score $p_j(o) \in [0,1]$ where higher is better; the hypercube $[0,1]^m$ is the score space, and the global score is $S(o) = S(p_1(o), \ldots, p_m(o))$. The common scoring functions:

In every case we want the $k$ objects with the highest global score — even for MIN.

06 · Algorithms

B0 and Fagin’s Algorithm

The middleware setting: the data is vertically distributed, each source can be read in descending score order (sorted access) or probed by object id ( random access), and we want the top k without reading everything.

The simplest case is MAX, and Fagin’s 1996 answer is almost embarrassing:

It works because after $k$ rounds there are at least $k$ objects whose score is at least the last value seen; any object not yet retrieved has every partial score below that, so its MAX is too. The same argument collapses for any other function — with MIN and $k = 1$, the sorted phase gives no lower bound at all on the retrieved objects’ global scores, so an unseen object can still win. Even completing the seen objects with random accesses does not fix it.

Fagin’s Algorithm (FA) handles any monotone $S$:

1. Extract the same number of objects by sorted access in each list, until at least $k$ objects have been seen in all lists.
2. For every object seen, complete its score with random accesses wherever needed.
3. Output the $k$ objects with the best overall score.

Its complexity is sub-linear, $O(N^{(m-1)/m} k^{1/m})$ — proportional to $\sqrt{N}$ for two lists. But note the shape of the stopping rule: it counts objects in common, so it is independent of the scoring function. That is FA’s weakness — it cannot adapt to how the function actually behaves — and it is why FA is not instance-optimal. It must also buffer every object seen under sorted access.

07 · Algorithms

The Threshold Algorithm

Change the stopping condition so that it depends on the scoring function, and you get an algorithm that is instance-optimal — work its authors received the Gödel Prize for in 2014.

TA interleaves the two access types:

1. Do a sorted access in parallel in each list $R_i$.
2. For each object $o$ seen, do random accesses in the other lists to complete its score.
3. Compute $S(o)$; if it is among the $k$ highest so far, keep it in the buffer.
4. Let $s_{L_i}$ be the last score seen under sorted access in $R_i$.
5. Define the threshold $T = S(s_{L_1}, \ldots, s_{L_m})$ — the score of the threshold point $\tau$.
6. If the $k$-th best object’s score is worse than $T$, go back to step 1.
7. Otherwise return the current top $k$.

The correctness argument is one sentence: no unseen object can have a partial score above $s_{L_i}$ in any list, so by monotonicity none can score above $T$; once $k$ objects beat $T$, the answer is fixed.

Cost is measured by the middleware cost model:

with $SA$, $RA$ the numbers of sorted and random accesses and $c_{SA}$, $c_{RA}$ their unit costs. In the basic setting both are 1. For web sources typically $c_{RA} > c_{SA}$, with the limiting case $c_{RA} = \infty$ — random access impossible, which motivates the next algorithm. A source with no index gives $c_{SA} = \infty$.

08 · Algorithms

NRA — when random access is impossible

Some sources cannot be probed by id at all. NRA returns the right top k using sorted access only — at the price of not always knowing the winners’ exact scores.

The idea is to maintain, for every object seen, a lower bound $S^-(o)$ (computed by treating the unknown partial scores as their worst possible values) and an upper bound $S^+(o)$ (treating them as the best still possible — the last value seen in each unseen list). The buffer $B$ is unbounded and kept sorted by decreasing lower bound.

NRA is instance-optimal among algorithms making no random accesses, with optimality ratio $m$. Two properties surprise people:

• The returned objects are correct, but their scores may remain uncertain — a lower bound below an upper bound. That is by design.
• Cost is not monotone in $k$: finding the top-2 can be cheaper than finding the top-1. The lectures’ example needs to reach depth $N-1$ for $k=1$ but only 3 rounds for $k=2$.

The four algorithms, side by side — the summary the exam expects you to be able to reconstruct:

Now run it yourself. The stepper opens on exactly this scenario — the same three lists, $f = 4A + 2B + C$, $k = 2$ — so you can replay the trace above one round at a time. Then switch the algorithm to FA to watch the extra accesses pile up, change $k$, or swap in the hockey dataset from the February 2026 paper to practise TA with its falling threshold.

09 · Caveat

When the scoring function is not monotone

Every guarantee above — FA’s correctness, TA’s stopping rule, NRA’s bounds — assumes $S$ is monotone. One paper builds an entire exercise on removing that assumption.

June 2024 asks for a meeting point between Milan and Como, scored by

$f(x,y) = m + s, \qquad m = \tfrac{x+y}{2}, \qquad s = \sqrt{(x-m)^2 + (y-m)^2}$

— the mean travel time plus a penalty for imbalance, $s$ being the distance from the bisector $x = y$. Lower is better. It is not monotone: increasing one coordinate can reduce $f$ by making the pair more balanced.

What happens is instructive:

• TA runs to depth 3 and returns C, which is not in the skyline. That is legal — the skyline is the set of top-1 candidates for monotone functions, and $f$ is not one.
• FA stops at depth 2, having seen only A and B in both lists, and returns one of them. This answer is simply wrong: the unseen C beats both. FA’s correctness proof needs monotonicity, and without it an unseen object can outscore every fully-seen one.

A second paper, July 2025, plays the opposite trick: the CPU dataset scores $erp = -100\,MYCT + 10\,MMIN + MMAX + CACH$, with a negative coefficient. Here TA does apply — because MYCT is listed in ascending order, so descending that list still decreases utility, exactly as for the other three. Monotonicity in the access order is what the algorithms need, not positive coefficients.