While reading in IDE realized (*it) resolves to PostingIterator** I got a little dizzy at first, then started to play with this code and came up with this.
In Constructor:

for (PostingIterator* it : m_iterators) {
  if (it == nullptr) {
    m_iterators.erase(&it);
   } else {
     auto docId = it->next();
     if (docId && (docId < m_nextId || m_nextId == 0)) {
       m_nextId = docId;
     }
  }
}

In OrPostingIterator::next()

for (PostingIterator* it : m_iterators) {
    auto docId = it->docId();
    if (docId <= m_docId) {
        docId = it->next();
        if (docId == 0) {
            m_iterators.erase(&it);
            continue;
        }
    }
    m_nextId = m_nextId ? qMin(docId , m_nextId) : docId;
}

I'm not 100% sure if this does exactly the same. But if it does, for readers of my skill level this code will be easier to understand, I guess.
BTW, &it also makes me dizzy :-)

I'm not very familiar with the concept of iterators (yet). To me it looks like auto i = new OrPostingIterator(iters); i->docId(); will return 0 and i->next() returns a valid docId. After that i->docId(); is also valid.
Is this how iterators work? Naively I would expect i->docId(); to be valid after construction or both i->docId(); and i->next() to be invalid.

I have to admit, it's very difficult to understand (and I don't, really) what baloo is doing here with all this iterating over vectors of inherited iterator classes, pointer-to-pointer stuff of which some might not even exist. My brain hurts, terribly! All I can presently do is ask some simple questions. Sorry, I'm of no help here. Please take my comments as a device for better understanding and I hope it's not to much of a bother.

In D11828#242372, @michaelh wrote:

While reading in IDE realized (*it) resolves to PostingIterator** I got a little dizzy at first, then started to play with this code and came up with this.
In Constructor:

for (PostingIterator* it : m_iterators) {
  if (it == nullptr) {
    m_iterators.erase(&it);

Thats not how QVector<>::iterator works

• you can not create an QVector<>::iterator from an PostingIterator*. The latter is just a (pointer to) a PostingIterator, it does not know about the container (QVector) it is member of [1]
• deleting an element from a container using .erase(it) typically invalidates the it, thats the reason .erase(it) returns an iterator to the next element
• it = m_iterators.erase(it) thus implicitly moves the iterator forward

 } else {
   auto docId = it->next();
   if (docId && (docId < m_nextId || m_nextId == 0)) {
     m_nextId = docId;
   }
}

}

In `OrPostingIterator::next()`

does not work for the same reason ...

What could work is deleting the PostingIterator immediately and setting the iterator value to nullptr, and then do a cleanup pass afterwards with QVector<>::removeAll(nullptr).

:-) Thank you for the lesson.

In D11828#242402, @michaelh wrote:

I'm not very familiar with the concept of iterators (yet). To me it looks like auto i = new OrPostingIterator(iters); i->docId(); will return 0 and i->next() returns a valid docId. After that i->docId(); is also valid.
Is this how iterators work? Naively I would expect i->docId(); to be valid after construction or both i->docId(); and i->next() to be invalid.

I have to admit, it's very difficult to understand (and I don't, really) what baloo is doing here with all this iterating over vectors of inherited iterator classes, pointer-to-pointer stuff of which some might not even exist. My brain hurts, terribly! All I can presently do is ask some simple questions. Sorry, I'm of no help here. Please take my comments as a device for better understanding and I hope it's not to much of a bother.

Each PostingIterator represents a "set" of document ids. PostingIterators are not related to STL or Qt container iterators (although the "subiterators" are implemented using QVectors<>).

The PI::next() call returns the smallest element and removes it from the set, PI::docId() just returns the smallest element.

The result set of the OrPostingIterator is the union of its "subsets" (represented by its "subiterators", i.e. the QVector<PostingIterator*> constructor argument). Or works a little bit like an insertion sort. To return the smallest element, it creates the union of the smallest element of all subsets, and yields the smallest element of the union. It then calls PI::next() on all subsets which returned the smallest element, removing it from all subsets and thus from the union.

In C++, you can use iterators in two different ways, either PreIncrement or PostIncrement. PostingIterator::next() will behave like *(++it), i.e. it is incremented first, then the current value is returned.

I don't know the original justification for this design. One possible idea is to delay the actual database query until next() is called the first time. For e.g. a query "a AND b AND c", one can execute "a", if not empty do "b", intersect (i.e. calling the Iterators of Result("a") and Result("b") until both return the same value), and if the intersection is non-empty, do "c".

Currently, it does not implement this optimization. D12025 implements one case, i.e. stopping if a leaf query returns an empty set, and propagating it upwards.

Thank you once more. This is complicated stuff (for me), it will take some time to sink in.

Can someone please review this change?

Ping!

Looks fine to me. But do we really need to optimize it? I mean, I didn't see it running more than ~20 ms, and with this patch for small queries it runs like ~16 ms. Worst case is when user types something in KRunner, but again, the lag is negligible there.

In D11828#339379, @poboiko wrote:

Looks fine to me. But do we really need to optimize it? I mean, I didn't see it running more than ~20 ms, and with this patch for small queries it runs like ~16 ms. Worst case is when user types something in KRunner, but again, the lag is negligible there.

KRunner currently executes each search term 8 times, once for each of type in [ Audio, Video, Document, ...]. I think especially for krunner lower latency is important, as it does search-as-you-type.

Ping!

Ping ...