5.3.6 Ordering
So far, we have assumed that the postings of each inverted list would be ordered
by document number. Although this is the most popular option, this is not the
only way to order an inverted list. An inverted list can also be ordered by score,
so that the highest-scoring documents come first. This makes sense only when the
lists already store the score, or when only one kind of score is likely to be computed from the inverted list. By storing scores instead of documents, the query
processing engine can focus only on the top part of each inverted list, where the
highest-scoring documents are recorded. This is especially useful for queries consisting of a single word. In a traditional document-ordered inverted list, the query
processing engine would need to scan the whole list to find the top k scoring documents, whereas it would only need to read the first k postings in a score-sorted
list.