Opened 31 hours ago
#858 new enhancement
Optimise AND_NOT when RHS is contiguous range covering LHS
| Reported by: | Olly Betts | Owned by: | Olly Betts |
|---|---|---|---|
| Priority: | normal | Milestone: | 2.x |
| Component: | Matcher | Version: | 2.1.0 |
| Severity: | normal | Keywords: | |
| Cc: | Blocked By: | ||
| Blocking: | Operating System: | All |
Description
We know the first and last docids (though they may not be tight) so we could use that and the term frequency to see when the RHS is a contiguous range.
If it is and the range is at least as wide as the first:last range of the LHS then we know the AND_NOT can't match anything.
This is probably not very common, but the check should be cheap and it would allow us to collapse filters in some situations which could save significant work when it happens.
I had a quick look at implementing it, and it's a little bit fiddly and I'm in the middle of trying to do something else, so creating an issue so we don't forget about it.
Here's a hacky WIP patch:
--- a/xapian-core/api/queryinternal.cc
+++ b/xapian-core/api/queryinternal.cc
@@ -59,6 +59,8 @@
#include "unicode/description_append.h"
#include <algorithm>
+#include <cstdlib>
+#include <iostream>
#include <limits>
#include <list>
#include <memory>
@@ -852,6 +854,22 @@ AndContext::postlist(TermFreqs* termfreqs)
TermFreqs r_freqs;
auto [rhs, rhs_est] =
not_ctx->postlist(termfreqs ? &r_freqs : nullptr, true);
+#if 0 // FIXME: The idea here is good, but r_freqs isn't currently filled in if
+ // termfreqs is NULL. We could fill it in for this check too, but that
+ // needs more careful analysis to make sure it doesn't have unwanted
+ // side-effects.
+ auto range = not_ctx->get_last() - not_ctx->get_first() + 1;
+ std::cerr << "RHS range = " << range << " [" << not_ctx->get_first() << ":" << not_ctx->get_last() << "] r_freqs.termfreq = " << r_freqs.termfreq << " LHS range = [" << first << ":" << last << "]\n";
+ if (r_freqs.termfreq <= range &&
+ not_ctx->get_first() <= first &&
+ not_ctx->get_last() >= last) {
+ // The "not"'s rhs matches a contiguous range of documents
+ // which is a superset of the range that this AndContext can
+ // match, which means that this AndContext can't match
+ // anything.
+ return {};
+ }
+#endif
if (termfreqs) {
TermFreqs& freqs = *termfreqs;
auto& stats = *qopt->get_stats();
