Boolean OR could be optimised further

[Richard Boulton]

For a boolean OR of several terms, we don't care how many of the terms match - we just care whether any of them do. Therefore, when we find that one of the terms matches, we shouldn't waste effort trying to move the other posting lists to the same position.

Instead, we should hold the posting lists in order of termfrequency, highest termfrequency first. To perform a skip_to() operation with ID "minid", we'd call skip_to(minid) on each of the sub-postlists until one of them moved to minid. At that point, there would be no need to call skip_t() on the remaining sub-postlists.

We'd need to keep track of which sub-postlists have been moved up to the current position, and which haven't. When next() is called, we'd call next() on any sub-postlists which are up-to-date, but we would need to call skip_to() on any other sub-postlists which are further behind.

We could implement this by introducing special BooleanOrPostingList to handle this particular case.

I'm not sure that it would lead to much improvement for common cases, but it is easy to make up cases where it would make a huge improvement (eg, a boolean OR in which one of the terms is a MatchAll term - none of the other postlists would need to be moved in this case.)

[Olly Betts]

I don't see a common case this helps (the only "big OR" boolean filters I can think of have disjoint terms - e.g. Ttext/html OR Ttext/pdf, Omega's date range searches) but it would be easy to implement in the queryoptimiser framework so it's worth trying at some point.

[Olly Betts]

Hmm, if weights are coming from an external source, then this becomes more interesting...

[Richard Boulton]

PostingSource has a get_maxweight() method - if this returns 0, or if the PostingSource is under a "OP_MULT_WEIGHT 0" (or the boolean part of an OP_FILTER), we can ignore the weights returned by it. I don't see why it would be any harder to do this with weights from an external source, therefore.

[Olly Betts]

Sorry, I phrased that badly. I meant to say:

In the case of a boolean OR with weight information coming purely from an external source, then this optimisation becomes potentially much more profitable.

[Olly Betts]

This is a purely internal change, so no API or ABI repercussions, so marking for 1.4.x.

[charan]

i want to work on this bug

[Olly Betts]

Sure.

[Olly Betts]

754f6bd1ea5c6cd48d692b59296f980920b01df9 added a BoolOrPostList class, but it doesn't currently use the optimisation proposed here.

[Olly Betts]

A somewhat common case where we get a potentially large boolean OR is for a wildcard weighted by OP_SYNONYM (the default).

[Olly Betts]

A somewhat common case where we get a potentially large boolean OR is for a wildcard weighted by OP_SYNONYM (the default).

Except that in this case we do need all the subpostlists to be moved to the matching document so that the SynonymPostList can call get_wdf().

[Olly Betts]

I'm not sure that it would lead to much improvement for common cases, but it is easy to make up cases where it would make a huge improvement (eg, a boolean OR in which one of the terms is a MatchAll term - none of the other postlists would need to be moved in this case.)

While the optimisation here is worth trying, this particular case would actually be better handled by the query optimiser just reducing it to a MatchAll query. I tested and that doesn't currently happen.

Vaibhav: Are you still interested in working on this? If not, we should unassign.