[AndPostingIterator] Replace recursive next() implementation
ClosedPublic

Authored by bruns on Apr 14 2020, 9:01 PM.

Details

Summary

The next() call will recurse once for each document in the first set
until all iterators align, which is especially bad when the first term
is common. It will only advance the first iterator just by one, although
it could skip to the largest id in the set.

Use skipTo on each iterator until none of the iterators moves forward,
and in case the iterator has moved use the new position as new lower
bound. If one of of the iterators only contains a small set, the
iterators on average will be moved much further in each round.

As skipTo(...) and next() are mostly identical with this approach next()
can be trivially implemented with skipTo.

Depends on D28839

Diff Detail

Repository
R293 Baloo
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
bruns created this revision.Apr 14 2020, 9:01 PM
Restricted Application added projects: Frameworks, Baloo. · View Herald TranscriptApr 14 2020, 9:01 PM
Restricted Application added a subscriber: kde-frameworks-devel. · View Herald Transcript
bruns requested review of this revision.Apr 14 2020, 9:01 PM
ngraham accepted this revision.Apr 15 2020, 6:04 PM
This revision is now accepted and ready to land.Apr 15 2020, 6:04 PM