Branch data Line data Source code
1 : : /** @file multiandpostlist.cc
2 : : * @brief N-way AND postlist
3 : : */
4 : : /* Copyright (C) 2007,2009,2011,2012,2015,2017 Olly Betts
5 : : * Copyright (C) 2009 Lemur Consulting Ltd
6 : : *
7 : : * This program is free software; you can redistribute it and/or
8 : : * modify it under the terms of the GNU General Public License as
9 : : * published by the Free Software Foundation; either version 2 of the
10 : : * License, or (at your option) any later version.
11 : : *
12 : : * This program is distributed in the hope that it will be useful,
13 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : : * GNU General Public License for more details.
16 : : *
17 : : * You should have received a copy of the GNU General Public License
18 : : * along with this program; if not, write to the Free Software
19 : : * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 : : */
21 : :
22 : : #include <config.h>
23 : :
24 : : #include "multiandpostlist.h"
25 : : #include "omassert.h"
26 : : #include "debuglog.h"
27 : :
28 : : using namespace std;
29 : :
30 : : void
31 : 1248 : MultiAndPostList::allocate_plist_and_max_wt()
32 : : {
33 [ + - ]: 1248 : plist = new PostList * [n_kids];
34 : : try {
35 [ + - ][ + - ]: 4208 : max_wt = new double [n_kids]();
[ + + ]
36 : 0 : } catch (...) {
37 [ # # ]: 0 : delete [] plist;
38 : 0 : plist = NULL;
39 : 0 : throw;
40 : : }
41 : 1248 : }
42 : :
43 : 3744 : MultiAndPostList::~MultiAndPostList()
44 : : {
45 [ + - ]: 1248 : if (plist) {
46 [ + + ]: 4208 : for (size_t i = 0; i < n_kids; ++i) {
47 [ + - ]: 2960 : delete plist[i];
48 : : }
49 [ + - ]: 1248 : delete [] plist;
50 : : }
51 [ + - ]: 1248 : delete [] max_wt;
52 [ - + ]: 2496 : }
53 : :
54 : : Xapian::doccount
55 : 486 : MultiAndPostList::get_termfreq_min() const
56 : : {
57 : : // The number of matching documents is minimised when we have the minimum
58 : : // number of matching documents from each sub-postlist, and these are
59 : : // maximally disjoint.
60 : 486 : Xapian::doccount sum = plist[0]->get_termfreq_min();
61 [ + + ]: 486 : if (sum) {
62 [ + + ]: 544 : for (size_t i = 1; i < n_kids; ++i) {
63 : 402 : Xapian::doccount sum_old = sum;
64 : 402 : sum += plist[i]->get_termfreq_min();
65 : : // If sum < sum_old, the calculation overflowed and the true sum
66 : : // must be > db_size. Since we added a value <= db_size,
67 : : // subtracting db_size must un-overflow us.
68 [ + - ][ + + ]: 402 : if (sum >= sum_old && sum <= db_size) {
69 : : // It's possible there's no overlap.
70 : 260 : return 0;
71 : : }
72 : 142 : sum -= db_size;
73 : : }
74 : : AssertRelParanoid(sum,<=,MultiAndPostList::get_termfreq_est());
75 : : }
76 : 226 : return sum;
77 : : }
78 : :
79 : : Xapian::doccount
80 : 1214 : MultiAndPostList::get_termfreq_max() const
81 : : {
82 : : // We can't match more documents than the least of our sub-postlists.
83 : 1214 : Xapian::doccount result = plist[0]->get_termfreq_max();
84 [ + + ]: 2924 : for (size_t i = 1; i < n_kids; ++i) {
85 : 1710 : Xapian::doccount tf = plist[i]->get_termfreq_max();
86 [ + + ]: 1710 : if (tf < result) result = tf;
87 : : }
88 : 1214 : return result;
89 : : }
90 : :
91 : : Xapian::doccount
92 : 1458 : MultiAndPostList::get_termfreq_est() const
93 : : {
94 : : LOGCALL(MATCH, Xapian::doccount, "MultiAndPostList::get_termfreq_est", NO_ARGS);
95 [ + + ]: 1458 : if (rare(db_size == 0))
96 : 37 : RETURN(0);
97 : : // We calculate the estimate assuming independence. With this assumption,
98 : : // the estimate is the product of the estimates for the sub-postlists
99 : : // divided by db_size (n_kids - 1) times.
100 : 1421 : double result = plist[0]->get_termfreq_est();
101 [ + + ]: 3502 : for (size_t i = 1; i < n_kids; ++i) {
102 : 2081 : result = (result * plist[i]->get_termfreq_est()) / db_size;
103 : : }
104 : 1421 : return static_cast<Xapian::doccount>(result + 0.5);
105 : : }
106 : :
107 : : TermFreqs
108 : 48 : MultiAndPostList::get_termfreq_est_using_stats(
109 : : const Xapian::Weight::Internal & stats) const
110 : : {
111 : : LOGCALL(MATCH, TermFreqs, "MultiAndPostList::get_termfreq_est_using_stats", stats);
112 : : // We calculate the estimate assuming independence. With this assumption,
113 : : // the estimate is the product of the estimates for the sub-postlists
114 : : // divided by db_size (n_kids - 1) times.
115 [ + - ]: 48 : TermFreqs freqs(plist[0]->get_termfreq_est_using_stats(stats));
116 : :
117 : 48 : double freqest = double(freqs.termfreq);
118 : 48 : double relfreqest = double(freqs.reltermfreq);
119 : 48 : double collfreqest = double(freqs.collfreq);
120 : :
121 : : // Our caller should have ensured this.
122 : : Assert(stats.collection_size);
123 : :
124 [ + + ]: 128 : for (size_t i = 1; i < n_kids; ++i) {
125 [ + - ]: 80 : freqs = plist[i]->get_termfreq_est_using_stats(stats);
126 : :
127 : : // If the collection is empty, freqest should be 0 already, so leave
128 : : // it alone.
129 : 80 : freqest = (freqest * freqs.termfreq) / stats.collection_size;
130 : 80 : collfreqest = (collfreqest * freqs.collfreq) / stats.total_term_count;
131 : :
132 : : // If the rset is empty, relfreqest should be 0 already, so leave
133 : : // it alone.
134 [ - + ]: 80 : if (stats.rset_size != 0)
135 : 0 : relfreqest = (relfreqest * freqs.reltermfreq) / stats.rset_size;
136 : : }
137 : :
138 : 48 : RETURN(TermFreqs(static_cast<Xapian::doccount>(freqest + 0.5),
139 : : static_cast<Xapian::doccount>(relfreqest + 0.5),
140 : : static_cast<Xapian::termcount>(collfreqest + 0.5)));
141 : : }
142 : :
143 : : Xapian::docid
144 : 4515 : MultiAndPostList::get_docid() const
145 : : {
146 : 4515 : return did;
147 : : }
148 : :
149 : : double
150 : 2114 : MultiAndPostList::get_weight(Xapian::termcount doclen,
151 : : Xapian::termcount unique_terms) const
152 : : {
153 : : Assert(did);
154 : 2114 : double result = 0;
155 [ + + ]: 6799 : for (size_t i = 0; i < n_kids; ++i) {
156 : 4685 : result += plist[i]->get_weight(doclen, unique_terms);
157 : : }
158 : 2114 : return result;
159 : : }
160 : :
161 : : bool
162 : 5401 : MultiAndPostList::at_end() const
163 : : {
164 : 5401 : return (did == 0);
165 : : }
166 : :
167 : : double
168 : 1232 : MultiAndPostList::recalc_maxweight()
169 : : {
170 : 1232 : max_total = 0.0;
171 [ + + ]: 4166 : for (size_t i = 0; i < n_kids; ++i) {
172 : 2934 : double new_max = plist[i]->recalc_maxweight();
173 : 2934 : max_wt[i] = new_max;
174 : 2934 : max_total += new_max;
175 : : }
176 : 1232 : return max_total;
177 : : }
178 : :
179 : : PostList *
180 : 5352 : MultiAndPostList::find_next_match(double w_min)
181 : : {
182 : : advanced_plist0:
183 [ + + ]: 6064 : if (plist[0]->at_end()) {
184 : 1071 : did = 0;
185 : 1071 : return NULL;
186 : : }
187 : 4993 : did = plist[0]->get_docid();
188 [ + + ]: 10857 : for (size_t i = 1; i < n_kids; ++i) {
189 : : bool valid;
190 [ + - ]: 6671 : check_helper(i, did, w_min, valid);
191 [ + + ]: 6671 : if (!valid) {
192 [ + - ]: 15 : next_helper(0, w_min);
193 : 712 : goto advanced_plist0;
194 : : }
195 [ + - ][ + + ]: 6656 : if (plist[i]->at_end()) {
196 : 95 : did = 0;
197 : 95 : return NULL;
198 : : }
199 [ + - ]: 6561 : Xapian::docid new_did = plist[i]->get_docid();
200 [ + + ]: 6561 : if (new_did != did) {
201 [ + - ]: 697 : skip_to_helper(0, new_did, w_min);
202 : 697 : goto advanced_plist0;
203 : : }
204 : : }
205 : 5352 : return NULL;
206 : : }
207 : :
208 : : PostList *
209 : 4739 : MultiAndPostList::next(double w_min)
210 : : {
211 : 4739 : next_helper(0, w_min);
212 : 4739 : return find_next_match(w_min);
213 : : }
214 : :
215 : : PostList *
216 : 613 : MultiAndPostList::skip_to(Xapian::docid did_min, double w_min)
217 : : {
218 : 613 : skip_to_helper(0, did_min, w_min);
219 : 613 : return find_next_match(w_min);
220 : : }
221 : :
222 : : std::string
223 : 0 : MultiAndPostList::get_description() const
224 : : {
225 [ # # ]: 0 : string desc("(");
226 [ # # ][ # # ]: 0 : desc += plist[0]->get_description();
227 [ # # ]: 0 : for (size_t i = 1; i < n_kids; ++i) {
228 [ # # ]: 0 : desc += " AND ";
229 [ # # ][ # # ]: 0 : desc += plist[i]->get_description();
230 : : }
231 [ # # ]: 0 : desc += ')';
232 : 0 : return desc;
233 : : }
234 : :
235 : : Xapian::termcount
236 : 28 : MultiAndPostList::get_wdf() const
237 : : {
238 : 28 : Xapian::termcount totwdf = 0;
239 [ + + ]: 112 : for (size_t i = 0; i < n_kids; ++i) {
240 : 84 : totwdf += plist[i]->get_wdf();
241 : : }
242 : 28 : return totwdf;
243 : : }
244 : :
245 : : Xapian::termcount
246 : 695 : MultiAndPostList::count_matching_subqs() const
247 : : {
248 : 695 : Xapian::termcount total = 0;
249 [ + + ]: 2368 : for (size_t i = 0; i < n_kids; ++i) {
250 : 1673 : total += plist[i]->count_matching_subqs();
251 : : }
252 : 695 : return total;
253 : : }
254 : :
255 : : void
256 : 0 : MultiAndPostList::gather_position_lists(OrPositionList* orposlist)
257 : : {
258 [ # # ]: 0 : for (size_t i = 0; i < n_kids; ++i) {
259 : 0 : plist[i]->gather_position_lists(orposlist);
260 : : }
261 : 0 : }
|
