[OrpostingIterator] Allow skipping elements, implement skipTo
ClosedPublic

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

Details

Summary

In case an OrPostingIterator is below and AndPostingIterator, which is
the common case when using atleast two term, most of the documents will
be skipped.

Instead of skipping by repeatedly calling OrPostingIterator::next()
implement the skipTo method. This removes the overhead of looping over
the subsets for each next call.

When skipTo is implemented in the AndPostingIterator and
OrPostingIterator, the instruction count is significantly reduced,
e.g. a query for "the fox" goes down from 20M to 4.5M instructions
(query time 6ms vs 1.5ms), on a DB with 4.600 documents.

Depends on D28839

Test Plan
  • ctest
  • valgrind baloosearch some words

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:08 PM
Restricted Application added projects: Frameworks, Baloo. · View Herald TranscriptApr 14 2020, 9:09 PM
Restricted Application added a subscriber: kde-frameworks-devel. · View Herald Transcript
bruns requested review of this revision.Apr 14 2020, 9:09 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
This revision was automatically updated to reflect the committed changes.