Lucene 2.9.2: How to show results in random order?

Question

By default, Lucene returns the query results in order of relevance (rating). You can pass a sort field (or several), then the results will be sorted by this field.

Now I am looking for a good solution to get search results in random order .

Bad approach:
Of course, I could take ALL the results and then shuffle the collection, but in the case of 5 Mio search results that do not work well.

Elegant paging approach:
With this approach, you could tell Lucene the following:
a) Give me 1 to 10 out of 5 Mio results in random order
b) Then give me 11 to 20 (based on the same random sequence as in a) .
c) To clarify: if you call a) twice, you get the same random elements.

How can you implement this approach?

---

Update Jul27 2012: keep in mind that the solution described here for Lucene 2.9.x does not work correctly. Use RandomOrderScoreDocComparatorwill result in certain results being doubled in the resulting list.

Answer 1

FieldComparator:

public class RandomOrderFieldComparator extends FieldComparator<Integer> {

    private final Random random = new Random();

    @Override
    public int compare(int slot1, int slot2) {
        return random.nextInt();
    }

    @Override
    public int compareBottom(int doc) throws IOException {
        return random.nextInt();
    }

    @Override
    public void copy(int slot, int doc) throws IOException {
    }

    @Override
    public void setBottom(int bottom) {
    }

    @Override
    public void setNextReader(IndexReader reader, int docBase) throws IOException {
    }

    @Override
    public Integer value(int slot) {
        return random.nextInt();
    }

}

/ . , , :

public static void main(String... args) throws Exception {
    RAMDirectory directory = new RAMDirectory();

    Analyzer analyzer = new StandardAnalyzer(Version.LUCENE_33);

    IndexWriter writer = new IndexWriter(
            directory,
            new IndexWriterConfig(Version.LUCENE_33, analyzer).setOpenMode(OpenMode.CREATE_OR_APPEND)
        );

    Document alice = new Document();
    alice.add( new Field("name", "Alice", Field.Store.YES, Field.Index.ANALYZED) );
    writer.addDocument( alice );

    Document bob = new Document();
    bob.add( new Field("name", "Bob", Field.Store.YES, Field.Index.ANALYZED) );
    writer.addDocument( bob );

    Document chris = new Document();
    chris.add( new Field("name", "Chris", Field.Store.YES, Field.Index.ANALYZED) );
    writer.addDocument( chris );

    writer.close();


    IndexSearcher searcher = new IndexSearcher( directory );



    for (int pass = 1; pass <= 10; pass++) {
        Query query = new MatchAllDocsQuery();

        Sort sort = new Sort(
                new SortField(
                        "",
                        new FieldComparatorSource() {

                            @Override
                            public FieldComparator<Integer> newComparator(String fieldname, int numHits, int sortPos, boolean reversed) throws IOException {
                                return new RandomOrderFieldComparator();
                            }

                        }
                    )
            );

        TopFieldDocs topFieldDocs = searcher.search( query, 10, sort );

        System.out.print("Pass #" + pass + ":");
        for (int i = 0; i < topFieldDocs.totalHits; i++) {
            System.out.print( " " + topFieldDocs.scoreDocs[i].doc );
        }
        System.out.println();
    }
}

:

Pass #1: 1 0 2
Pass #2: 1 0 2
Pass #3: 0 1 2
Pass #4: 0 1 2
Pass #5: 0 1 2
Pass #6: 1 0 2
Pass #7: 0 2 1
Pass #8: 1 2 0
Pass #9: 2 0 1
Pass #10: 0 2 1

! , Lucene 2

public class RandomOrderScoreDocComparator implements ScoreDocComparator {

    private final Random random = new Random();

    public int compare(ScoreDoc i, ScoreDoc j) {
        return random.nextInt();
    }

    public Comparable<?> sortValue(ScoreDoc i) {
        return Integer.valueOf( random.nextInt() );
    }

    public int sortType() {
        return SortField.CUSTOM;
    }

}

, , Sort:

Sort sort = new Sort(
    new SortField(
        "",
        new SortComparatorSource() {
            public ScoreDocComparator newComparator(IndexReader reader, String fieldName) throws IOException {
                return new RandomOrderScoreDocComparator();
            }
        }
    )
);

Answer 2

, , . # ( Lucene.Net), Java, .

, , , , . , . , , . seed RandomOrderFieldComparatorSource ( ID.GetHashCode()).

, , docId , .

: , , , .

public class RandomOrderFieldComparator : FieldComparator
{
    Random random;
    List<int> slots = new List<int>();
    Dictionary<int, int> docSortIndeces = new Dictionary<int, int>();

    public RandomOrderFieldComparator(int? seed)
    {
        random = seed == null ? new Random() : new Random(seed.Value);
    }

    private int bottom; // Value of bottom of queue

    public override int Compare(int slot1, int slot2)
    {
        // TODO: there are sneaky non-branch ways to compute
        // -1/+1/0 sign
        // Cannot return values[slot1] - values[slot2] because that
        // may overflow
        int v1 = slots[slot1];
        int v2 = slots[slot2];
        if (v1 > v2) {
            return 1;
        } else if (v1 < v2) {
            return -1;
        } else {
            return 0;
        }
    }

    public override int CompareBottom(int doc)
    {
        // TODO: there are sneaky non-branch ways to compute
        // -1/+1/0 sign
        // Cannot return bottom - values[slot2] because that
        // may overflow
        int v2 = GetDocSortingIndex(doc);
        if (bottom > v2) {
            return 1;
        } else if (bottom < v2) {
            return -1;
        } else {
            return 0;
        }
    }

    public override void Copy(int slot, int doc)
    {
        if (slots.Count > slot) {
            slots[slot] = GetDocSortingIndex(doc);
        } else {
            slots.Add(GetDocSortingIndex(doc));
        }
        //slots[slot] = GetDocSortingIndex(doc);
    }

    public override void SetBottom(int bottom)
    {
        this.bottom = slots[bottom];
    }

    public override System.IComparable Value(int slot)
    {
        return (System.Int32)slots[slot];
    }

    public override void SetNextReader(IndexReader reader, int docBase)
    {
    }

    int GetDocSortingIndex(int docId)
    {
        if (!docSortIndeces.ContainsKey(docId))
            docSortIndeces[docId] = random.Next(int.MinValue, int.MaxValue);

        return docSortIndeces[docId];
    }
}