How do search engines efficiently retrieve documents in a sorted (e.g. page rank) order from an already sorted (by document id) inverted index?

Question

The standard way a search engine retrieves documents is by using an inverse index from words in the query to document ids. Since the ids are sorted, a query like "word1 AND word2" would fetch the lists of document ids two for word1 and word2, and find the intersection in linear time (similar to merge in merge sort).

But how would the search engine efficiently retrieve documents in some specified order , like page rank for example? Since the inverse indices for each word are already sorted by document id (to enable the merging described above), there seems to be no way to sort them also by page rank. (For instance, for "word1" the index might have ids : 5, 11, 19 where these documents have page ranks 3, 1, 2 respectively).

Retrieving the documents by document id first and then sorting by page rank at query time can be impractical if the number of documents to sort is large (say, millions), and especially if the user just wants the top page or two.

Answer 1

I don't know what search engines actually do, but one approach would be sort by decreasing pagerank, resolving ties using the document ID. (In other words, the primary sorting key is the page rank, and the secondary sorting key is the document ID.)

This still allows the merge operation. It also ensures that results are generated in decreasing pagerank order, i.e., the top-ranked results are generated first. Note that if two documents have the same document ID, then they'll definitely have the same pagerank, too, which is why this approach works.

Answer 2

One solution is to store a quantization of the pagerank in a direct access (by docid) memory mapped array together with the other scoring values like the page length. The term relevance score is immediately combined with the query-independent document score (pagerank,page length,...) and the new score inserted into the results priority queue (heap).