Branch data Line data Source code
1 : : /* orpostlist.cc: OR of two posting lists
2 : : *
3 : : * Copyright 1999,2000,2001 BrightStation PLC
4 : : * Copyright 2001,2002 Ananova Ltd
5 : : * Copyright 2003,2004,2007,2008,2009,2010 Olly Betts
6 : : * Copyright 2009 Lemur Consulting Ltd
7 : : * Copyright 2010 Richard Boulton
8 : : *
9 : : * This program is free software; you can redistribute it and/or
10 : : * modify it under the terms of the GNU General Public License as
11 : : * published by the Free Software Foundation; either version 2 of the
12 : : * License, or (at your option) any later version.
13 : : *
14 : : * This program is distributed in the hope that it will be useful,
15 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 : : * GNU General Public License for more details.
18 : : *
19 : : * You should have received a copy of the GNU General Public License
20 : : * along with this program; if not, write to the Free Software
21 : : * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301
22 : : * USA
23 : : */
24 : :
25 : : #include <config.h>
26 : : #include "orpostlist.h"
27 : :
28 : : #include "debuglog.h"
29 : : #include "multiandpostlist.h"
30 : : #include "andmaybepostlist.h"
31 : : #include "omassert.h"
32 : :
33 : : #include <algorithm>
34 : :
35 : 234094 : OrPostList::OrPostList(PostList *left_,
36 : : PostList *right_,
37 : : MultiMatch *matcher_,
38 : : Xapian::doccount dbsize_)
39 : : : BranchPostList(left_, right_, matcher_),
40 : : lhead(0), rhead(0), lvalid(false), rvalid(false),
41 : 234094 : lmax(0), rmax(0), minmax(0), dbsize(dbsize_)
42 : : {
43 : : LOGCALL_CTOR(MATCH, "OrPostList", left_ | right_ | matcher_ | dbsize_);
44 : : AssertRel(left_->get_termfreq_est(),>=,right_->get_termfreq_est());
45 : 234094 : }
46 : :
47 : : PostList *
48 : 43105843 : OrPostList::next(Xapian::weight w_min)
49 : : {
50 : : LOGCALL(MATCH, PostList *, "OrPostList::next", w_min);
51 [ + + ]: 43105843 : if (w_min > minmax) {
52 : : // we can replace the OR with another operator
53 : : PostList *ret;
54 [ + + ]: 198 : if (w_min > lmax) {
55 [ + + ]: 172 : if (w_min > rmax) {
56 : : LOGLINE(MATCH, "OR -> AND");
57 : 66 : ret = new MultiAndPostList(l, r, lmax, rmax, matcher, dbsize);
58 : 66 : Xapian::docid newdocid = std::max(lhead, rhead);
59 [ + + + - ]: 66 : if (newdocid == 0 || (lvalid && rvalid && lhead == rhead)) {
[ + - ][ + + ]
60 : 64 : ++newdocid;
61 : : }
62 : 66 : skip_to_handling_prune(ret, newdocid, w_min, matcher);
63 : : } else {
64 : : LOGLINE(MATCH, "OR -> AND MAYBE (1)");
65 : : AndMaybePostList * ret2 =
66 : 106 : new AndMaybePostList(r, l, matcher, dbsize, rhead, lhead);
67 : 106 : ret = ret2;
68 : : // Advance the AndMaybePostList unless the old RHS postlist was
69 : : // already ahead of the current docid.
70 [ + + ]: 106 : if (rhead <= lhead) {
71 : 103 : next_handling_prune(ret, w_min, matcher);
72 : : } else {
73 : 3 : handle_prune(ret, ret2->sync_rhs(w_min));
74 : : }
75 : : }
76 : : } else {
77 : : // w_min > rmax since w_min > minmax but not (w_min > lmax)
78 : : Assert(w_min > rmax);
79 : : LOGLINE(MATCH, "OR -> AND MAYBE (2)");
80 : : AndMaybePostList * ret2 =
81 : 26 : new AndMaybePostList(l, r, matcher, dbsize, lhead, rhead);
82 : 26 : ret = ret2;
83 [ + - ]: 26 : if (lhead <= rhead) {
84 : 26 : next_handling_prune(ret, w_min, matcher);
85 : : } else {
86 : 0 : handle_prune(ret, ret2->sync_rhs(w_min));
87 : : }
88 : : }
89 : :
90 : 198 : l = r = NULL;
91 : 198 : RETURN(ret);
92 : : }
93 : :
94 : 43105645 : bool ldry = false;
95 : 43105645 : bool rnext = !rvalid;
96 : :
97 [ + + ][ + + ]: 86208781 : if (!lvalid || lhead <= rhead) {
98 [ + + ]: 43103136 : if (lhead == rhead) rnext = true;
99 : 43103136 : next_handling_prune(l, w_min - rmax, matcher);
100 : 43103136 : lvalid = true;
101 [ + + ]: 43103136 : if (l->at_end()) ldry = true;
102 : : } else {
103 : 2509 : rnext = true;
104 : : }
105 : :
106 [ + + ]: 43105645 : if (rnext) {
107 : 560326 : next_handling_prune(r, w_min - lmax, matcher);
108 : 560326 : rvalid = true;
109 [ + + ]: 560326 : if (r->at_end()) {
110 : 231119 : PostList *ret = l;
111 : 231119 : l = NULL;
112 : 231119 : RETURN(ret);
113 : : }
114 : 329207 : rhead = r->get_docid();
115 : : }
116 : :
117 [ + + ]: 42874526 : if (!ldry) {
118 : 42874026 : lhead = l->get_docid();
119 : 42874026 : RETURN(NULL);
120 : : }
121 : :
122 : 500 : PostList *ret = r;
123 : 500 : r = NULL;
124 : 43105843 : RETURN(ret);
125 : : }
126 : :
127 : : PostList *
128 : 92 : OrPostList::skip_to(Xapian::docid did, Xapian::weight w_min)
129 : : {
130 : : LOGCALL(MATCH, PostList *, "OrPostList::skip_to", did | w_min);
131 [ - + ]: 92 : if (w_min > minmax) {
132 : : // we can replace the OR with another operator
133 : : PostList *ret;
134 [ # # ]: 0 : if (w_min > lmax) {
135 [ # # ]: 0 : if (w_min > rmax) {
136 : : LOGLINE(MATCH, "OR -> AND (in skip_to)");
137 : 0 : ret = new MultiAndPostList(l, r, lmax, rmax, matcher, dbsize);
138 : 0 : did = std::max(did, std::max(lhead, rhead));
139 : : } else {
140 : : LOGLINE(MATCH, "OR -> AND MAYBE (in skip_to) (1)");
141 : : AndMaybePostList * ret2 =
142 : 0 : new AndMaybePostList(r, l, matcher, dbsize, rhead, lhead);
143 : 0 : ret = ret2;
144 : 0 : handle_prune(ret, ret2->sync_rhs(w_min));
145 : 0 : did = std::max(did, rhead);
146 : : }
147 : : } else {
148 : : // w_min > rmax since w_min > minmax but not (w_min > lmax)
149 : : Assert(w_min > rmax);
150 : : LOGLINE(MATCH, "OR -> AND MAYBE (in skip_to) (2)");
151 : : AndMaybePostList * ret2 =
152 : 0 : new AndMaybePostList(l, r, matcher, dbsize, lhead, rhead);
153 : 0 : ret = ret2;
154 : 0 : handle_prune(ret, ret2->sync_rhs(w_min));
155 : 0 : did = std::max(did, lhead);
156 : : }
157 : :
158 : 0 : l = r = NULL;
159 : 0 : skip_to_handling_prune(ret, did, w_min, matcher);
160 : 0 : RETURN(ret);
161 : : }
162 : :
163 : 92 : bool ldry = false;
164 [ + + ]: 92 : if (lhead < did) {
165 : 72 : skip_to_handling_prune(l, did, w_min - rmax, matcher);
166 : 72 : lvalid = true;
167 : 72 : ldry = l->at_end();
168 : : }
169 : :
170 [ + + ]: 92 : if (rhead < did) {
171 : 20 : skip_to_handling_prune(r, did, w_min - lmax, matcher);
172 : 20 : rvalid = true;
173 : :
174 [ + - ]: 20 : if (r->at_end()) {
175 : 20 : PostList *ret = l;
176 : 20 : l = NULL;
177 : 20 : RETURN(ret);
178 : : }
179 : 0 : rhead = r->get_docid();
180 : : }
181 : :
182 [ + + ]: 72 : if (!ldry) {
183 : 66 : lhead = l->get_docid();
184 : 66 : RETURN(NULL);
185 : : }
186 : :
187 : 6 : PostList *ret = r;
188 : 6 : r = NULL;
189 : 92 : RETURN(ret);
190 : : }
191 : :
192 : : PostList *
193 : 75 : OrPostList::check(Xapian::docid did, Xapian::weight w_min, bool &valid)
194 : : {
195 : : LOGCALL(MATCH, PostList *, "OrPostList::check", did | w_min);
196 [ - + ]: 75 : if (w_min > minmax) {
197 : : // we can replace the OR with another operator
198 : : PostList *ret;
199 [ # # ]: 0 : if (w_min > lmax) {
200 [ # # ]: 0 : if (w_min > rmax) {
201 : : LOGLINE(MATCH, "OR -> AND (in check)");
202 : 0 : ret = new MultiAndPostList(l, r, lmax, rmax, matcher, dbsize);
203 : 0 : did = std::max(did, std::max(lhead, rhead));
204 : : } else {
205 : : LOGLINE(MATCH, "OR -> AND MAYBE (in check) (1)");
206 : 0 : AndMaybePostList * ret2 = new AndMaybePostList(r, l, matcher, dbsize, rhead, lhead);
207 : 0 : ret = ret2;
208 : 0 : handle_prune(ret, ret2->sync_rhs(w_min));
209 : 0 : did = std::max(did, rhead);
210 : : }
211 : : } else {
212 : : // w_min > rmax since w_min > minmax but not (w_min > lmax)
213 : : Assert(w_min > rmax);
214 : : LOGLINE(MATCH, "OR -> AND MAYBE (in check) (2)");
215 : 0 : AndMaybePostList * ret2 = new AndMaybePostList(l, r, matcher, dbsize, lhead, rhead);
216 : 0 : ret = ret2;
217 : 0 : handle_prune(ret, ret2->sync_rhs(w_min));
218 : 0 : did = std::max(did, lhead);
219 : : }
220 : :
221 : 0 : l = r = NULL;
222 : 0 : check_handling_prune(ret, did, w_min, matcher, valid);
223 : 0 : RETURN(ret);
224 : : }
225 : :
226 : 75 : bool ldry = false;
227 [ + + ][ + + ]: 75 : if (!lvalid || lhead < did) {
228 : 51 : lvalid = false;
229 : 51 : check_handling_prune(l, did, w_min - rmax, matcher, lvalid);
230 : 51 : ldry = l->at_end();
231 : : }
232 : :
233 [ + + ][ + + ]: 75 : if (!rvalid || rhead <= did) {
234 : 64 : rvalid = false;
235 : 64 : check_handling_prune(r, did, w_min - lmax, matcher, rvalid);
236 : :
237 [ - + ]: 64 : if (r->at_end()) {
238 : 0 : PostList *ret = l;
239 : 0 : l = NULL;
240 : 0 : valid = lvalid;
241 : 0 : RETURN(ret);
242 : : }
243 [ + + ]: 64 : if (rvalid) {
244 : 51 : rhead = r->get_docid();
245 : : } else {
246 : 13 : rhead = did + 1;
247 : : }
248 : : }
249 : :
250 [ + - ]: 75 : if (!ldry) {
251 [ + - ]: 75 : if (lvalid) {
252 : 75 : lhead = l->get_docid();
253 : : } else {
254 : 0 : lhead = did + 1;
255 : : }
256 : :
257 [ + + ]: 75 : if (lhead < rhead) {
258 : 20 : valid = lvalid;
259 [ + + ]: 55 : } else if (rhead < lhead) {
260 : 22 : valid = rvalid;
261 : : } else {
262 [ - + ][ # # ]: 33 : valid = lvalid || rvalid;
263 : : }
264 : 75 : RETURN(NULL);
265 : : }
266 : :
267 : 0 : PostList *ret = r;
268 : 0 : r = NULL;
269 : 0 : valid = rvalid;
270 : 75 : RETURN(ret);
271 : : }
272 : :
273 : : Xapian::doccount
274 : 234094 : OrPostList::get_termfreq_max() const
275 : : {
276 : : LOGCALL(MATCH, Xapian::doccount, "OrPostList::get_termfreq_max", NO_ARGS);
277 : 234094 : RETURN(std::min(l->get_termfreq_max() + r->get_termfreq_max(), dbsize));
278 : : }
279 : :
280 : : Xapian::doccount
281 : 234094 : OrPostList::get_termfreq_min() const
282 : : {
283 : : LOGCALL(MATCH, Xapian::doccount, "OrPostList::get_termfreq_min", NO_ARGS);
284 : 234094 : RETURN(std::max(l->get_termfreq_min(), r->get_termfreq_min()));
285 : : }
286 : :
287 : : Xapian::doccount
288 : 236364 : OrPostList::get_termfreq_est() const
289 : : {
290 : : LOGCALL(MATCH, Xapian::doccount, "OrPostList::get_termfreq_est", NO_ARGS);
291 : : // Estimate assuming independence:
292 : : // P(l or r) = P(l) + P(r) - P(l) . P(r)
293 : 236364 : double lest = static_cast<double>(l->get_termfreq_est());
294 : 236364 : double rest = static_cast<double>(r->get_termfreq_est());
295 : 236364 : double est = lest + rest - (lest * rest / dbsize);
296 : 236364 : RETURN(static_cast<Xapian::doccount>(est + 0.5));
297 : : }
298 : :
299 : : TermFreqs
300 : 896 : OrPostList::get_termfreq_est_using_stats(
301 : : const Xapian::Weight::Internal & stats) const
302 : : {
303 : : LOGCALL(MATCH, TermFreqs, "OrPostList::get_termfreq_est_using_stats", stats);
304 : : // Estimate assuming independence:
305 : : // P(l or r) = P(l) + P(r) - P(l) . P(r)
306 : 896 : TermFreqs lfreqs(l->get_termfreq_est_using_stats(stats));
307 : 896 : TermFreqs rfreqs(r->get_termfreq_est_using_stats(stats));
308 : :
309 : : double freqest, relfreqest;
310 : :
311 : : // Our caller should have ensured this.
312 : : Assert(stats.collection_size);
313 : :
314 : : freqest = lfreqs.termfreq + rfreqs.termfreq -
315 : 896 : (lfreqs.termfreq * rfreqs.termfreq / stats.collection_size);
316 : :
317 [ + - ]: 896 : if (stats.rset_size == 0) {
318 : 896 : relfreqest = 0;
319 : : } else {
320 : : relfreqest = lfreqs.reltermfreq + rfreqs.reltermfreq -
321 : 0 : (lfreqs.reltermfreq * rfreqs.reltermfreq / stats.rset_size);
322 : : }
323 : :
324 : 896 : RETURN(TermFreqs(static_cast<Xapian::doccount>(freqest + 0.5),
325 : : static_cast<Xapian::doccount>(relfreqest + 0.5)));
326 : : }
327 : :
328 : : Xapian::docid
329 : 35089412 : OrPostList::get_docid() const
330 : : {
331 : : LOGCALL(MATCH, Xapian::docid, "OrPostList::get_docid", NO_ARGS);
332 : : Assert(lhead != 0 && rhead != 0); // check we've started
333 : 35089412 : RETURN(std::min(lhead, rhead));
334 : : }
335 : :
336 : : // only called if we are doing a probabilistic OR
337 : : Xapian::weight
338 : 42860165 : OrPostList::get_weight() const
339 : : {
340 : : LOGCALL(MATCH, Xapian::weight, "OrPostList::get_weight", NO_ARGS);
341 : : Assert(lhead != 0 && rhead != 0); // check we've started
342 [ + + ]: 42860165 : if (lhead < rhead) RETURN(l->get_weight());
343 [ + + ]: 324999 : if (lhead > rhead) RETURN(r->get_weight());
344 : 42860165 : RETURN(l->get_weight() + r->get_weight());
345 : : }
346 : :
347 : : // only called if we are doing a probabilistic operation
348 : : Xapian::weight
349 : 11341275 : OrPostList::get_maxweight() const
350 : : {
351 : : LOGCALL(MATCH, Xapian::weight, "OrPostList::get_maxweight", NO_ARGS);
352 : 11341275 : RETURN(lmax + rmax);
353 : : }
354 : :
355 : : Xapian::weight
356 : 297486 : OrPostList::recalc_maxweight()
357 : : {
358 : : LOGCALL(MATCH, Xapian::weight, "OrPostList::recalc_maxweight", NO_ARGS);
359 : : // l and r cannot be NULL here, because the only place where they get set
360 : : // to NULL is when the tree is decaying, and the OrPostList is then
361 : : // immediately replaced.
362 : 297486 : lmax = l->recalc_maxweight();
363 : 297486 : rmax = r->recalc_maxweight();
364 : 297486 : minmax = std::min(lmax, rmax);
365 : 297486 : RETURN(OrPostList::get_maxweight());
366 : : }
367 : :
368 : : bool
369 : 42874202 : OrPostList::at_end() const
370 : : {
371 : : LOGCALL(MATCH, bool, "OrPostList::at_end", NO_ARGS);
372 : : // Can never really happen - OrPostList next/skip_to autoprune
373 : : AssertParanoid(!(l->at_end()) && !(r->at_end()));
374 : 42874202 : RETURN(false);
375 : : }
376 : :
377 : : std::string
378 : 0 : OrPostList::get_description() const
379 : : {
380 : 0 : return "(" + l->get_description() + " Or " + r->get_description() + ")";
381 : : }
382 : :
383 : : Xapian::termcount
384 : 13544 : OrPostList::get_doclength() const
385 : : {
386 : : LOGCALL(MATCH, Xapian::termcount, "OrPostList::get_doclength", NO_ARGS);
387 : : Xapian::termcount doclength;
388 : :
389 : : Assert(lhead != 0 && rhead != 0); // check we've started
390 [ + + ]: 13544 : if (lhead > rhead) {
391 : 1381 : doclength = r->get_doclength();
392 : : LOGLINE(MATCH, "OrPostList::get_doclength() [right docid=" << rhead <<
393 : : "] = " << doclength);
394 : : } else {
395 : 12163 : doclength = l->get_doclength();
396 : : LOGLINE(MATCH, "OrPostList::get_doclength() [left docid=" << lhead <<
397 : : "] = " << doclength);
398 : : }
399 : :
400 : 13544 : RETURN(doclength);
401 : : }
402 : :
403 : : Xapian::termcount
404 : 13761 : OrPostList::get_wdf() const
405 : : {
406 : : LOGCALL(MATCH, Xapian::termcount, "OrPostList::get_wdf", NO_ARGS);
407 [ + + ]: 13761 : if (lhead < rhead) RETURN(l->get_wdf());
408 [ + + ]: 3692 : if (lhead > rhead) RETURN(r->get_wdf());
409 : 13761 : RETURN(l->get_wdf() + r->get_wdf());
410 : : }
411 : :
412 : : Xapian::termcount
413 : 1073943 : OrPostList::count_matching_subqs() const
414 : : {
415 : : LOGCALL(MATCH, Xapian::termcount, "OrPostList::count_matching_subqs", NO_ARGS);
416 [ + + ]: 1073943 : if (lhead < rhead) RETURN(l->count_matching_subqs());
417 [ + + ]: 320836 : if (lhead > rhead) RETURN(r->count_matching_subqs());
418 : 1073943 : RETURN(l->count_matching_subqs() + r->count_matching_subqs());
419 : : }
|
