Class AbstractIntersectionDocumentIterator

  • All Implemented Interfaces:
    Direct Known Subclasses:
    AbstractOrderedIntervalDocumentIterator, AndDocumentIterator

    public abstract class AbstractIntersectionDocumentIterator
    extends AbstractCompositeDocumentIterator
    An abstract iterator on documents, generating the intersection of the documents returned by a number of document iterators.

    The important invariant is that only after a call to DocumentIterator.nextDocument(), a call to DocumentIterator.intervalIterator(Index) will return an interval iterator over the document just returned, and that for at least one index in AbstractIntervalDocumentIterator.indices() the iterator will not be empty or TRUE.

    The intersection algorithm

    Since MG4J 1.1, this class implements a new intersection algorithm that should be significantly faster than the previous one. The main idea is that of letting sparser iterator interact as much as possible to obtain a candidate common document, and then trying to align the others. At construction time, the component iterators are sorted so that index iterators are separated, and sorted by frequency. Then, each time we have to align the iterators we align them greedily starting from the index iterators, in frequency order. This has the effect of skipping very quickly (and usually by large jumps, which are handled nicely by indices with skips), as the main interaction happens between low-frequency index iterators.

    Moreover, this class treats in a special way index iterators coming from payload-based indices. Such iterators are checked at the end of the alignment process, after all standard index iterators (and general document iterators) are aligned. At that point, the special method PayloadPredicateDocumentIterator.skipUnconditionallyTo(long) is used to position unconditionally such iterators and check whether the payload predicate is satisfied. If this doesn't happen, the current candidate (obtained by alignment of standard iterators) is increased and the whole process is restarted. This procedure guarantees that we will never search exhaustively in a payload-based index a document record satisfying the predicate (unless, of course, we have a query containing just PayloadPredicateDocumentIterators), which is very efficient if the payload-based index uses skipping.