Boolean OR could be optimised further
|Reported by:||Richard Boulton||Owned by:||Vaibhav Kansagara|
|Cc:||harisaicharan111.challa@…, vaibhavkansagara249@…||Blocked By:|
Description (last modified by )
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.)
Change History (14)
comment:4 by , 14 years ago
|Status:||assigned → new|