LCOV - code coverage report
Current view: top level - matcher - multixorpostlist.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core c2b6f1024d3a Lines: 133 175 76.0 %
Date: 2019-05-16 09:13:18 Functions: 12 14 85.7 %
Branches: 96 162 59.3 %

           Branch data     Line data    Source code
       1                 :            : /** @file multixorpostlist.cc
       2                 :            :  * @brief N-way XOR postlist
       3                 :            :  */
       4                 :            : /* Copyright (C) 2007,2009,2010,2011,2012,2016,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 "multixorpostlist.h"
      25                 :            : 
      26                 :            : #include "debuglog.h"
      27                 :            : #include "omassert.h"
      28                 :            : 
      29                 :            : #include <algorithm>
      30                 :            : 
      31                 :            : using namespace std;
      32                 :            : 
      33                 :        336 : MultiXorPostList::~MultiXorPostList()
      34                 :            : {
      35         [ +  - ]:        112 :     if (plist) {
      36         [ +  + ]:        192 :         for (size_t i = 0; i < n_kids; ++i) {
      37         [ +  - ]:         80 :             delete plist[i];
      38                 :            :         }
      39         [ +  - ]:        112 :         delete [] plist;
      40                 :            :     }
      41         [ -  + ]:        224 : }
      42                 :            : 
      43                 :            : Xapian::doccount
      44                 :        112 : MultiXorPostList::get_termfreq_min() const
      45                 :            : {
      46                 :        112 :     Xapian::doccount result = 0;
      47         [ +  - ]:        112 :     Xapian::doccount max = plist[0]->get_termfreq_max();
      48                 :        112 :     Xapian::doccount sum = max;
      49         [ +  - ]:        112 :     bool all_exact = (max == plist[0]->get_termfreq_min());
      50                 :        112 :     unsigned overflow = 0;
      51         [ +  + ]:        312 :     for (size_t i = 1; i < n_kids; ++i) {
      52         [ +  - ]:        200 :         Xapian::doccount tf_max = plist[i]->get_termfreq_max();
      53         [ +  + ]:        200 :         if (tf_max > max) max = tf_max;
      54                 :            : 
      55                 :        200 :         Xapian::doccount old_sum = sum;
      56                 :        200 :         sum += tf_max;
      57                 :            :         // Track how many times we overflow the type.
      58         [ -  + ]:        200 :         if (sum < old_sum)
      59                 :          0 :             ++overflow;
      60         [ +  + ]:        200 :         if (all_exact)
      61         [ +  - ]:        179 :             all_exact = (tf_max == plist[i]->get_termfreq_min());
      62                 :            :     }
      63                 :            : 
      64                 :            :     // If tf_min(i) > sum(j!=i)(tf_max(j)) then all the other subqueries
      65                 :            :     // can't cancel out subquery i.  If we overflowed more than once,
      66                 :            :     // then the sum on the right is greater than the maximum possible
      67                 :            :     // tf, so there's no point checking.
      68         [ +  - ]:        112 :     if (overflow <= 1) {
      69         [ +  + ]:        424 :         for (size_t i = 0; i < n_kids; ++i) {
      70         [ +  - ]:        312 :             Xapian::doccount tf_min = plist[i]->get_termfreq_min();
      71         [ +  - ]:        312 :             Xapian::doccount tf_max = plist[i]->get_termfreq_max();
      72                 :            : 
      73                 :        312 :             Xapian::doccount all_the_rest = sum - tf_max;
      74                 :            :             // If no overflow, or we un-overflowed again...
      75 [ -  + ][ #  # ]:        312 :             if (overflow == 0 || all_the_rest > sum) {
      76         [ +  + ]:        312 :                 if (tf_min > all_the_rest) {
      77                 :         78 :                     result = std::max(result, tf_min - all_the_rest);
      78                 :            :                 }
      79                 :            :             }
      80                 :            :         }
      81                 :            :     }
      82                 :            : 
      83 [ +  + ][ +  + ]:        112 :     if (all_exact && result == 0) {
      84                 :            :         // If SUM odd, then the XOR can't be 0, so min XOR is 1 if we didn't
      85                 :            :         // already calculate a minimum.
      86                 :         34 :         result = sum & 1;
      87                 :            :     }
      88                 :            : 
      89                 :        112 :     return result;
      90                 :            : }
      91                 :            : 
      92                 :            : Xapian::doccount
      93                 :        128 : MultiXorPostList::get_termfreq_max() const
      94                 :            : {
      95                 :            :     // Maximum is if all sub-postlists are disjoint.
      96                 :        128 :     Xapian::doccount result = plist[0]->get_termfreq_max();
      97                 :        128 :     bool all_exact = (result == plist[0]->get_termfreq_min());
      98                 :        128 :     bool overflow = false;
      99         [ +  + ]:        344 :     for (size_t i = 1; i < n_kids; ++i) {
     100                 :        216 :         Xapian::doccount tf_max = plist[i]->get_termfreq_max();
     101                 :        216 :         Xapian::doccount old_result = result;
     102                 :        216 :         result += tf_max;
     103                 :            :         // Catch overflowing the type too.
     104         [ -  + ]:        216 :         if (result < old_result)
     105                 :          0 :             overflow = true;
     106         [ +  + ]:        216 :         if (all_exact)
     107                 :        195 :             all_exact = (tf_max == plist[i]->get_termfreq_min());
     108 [ +  + ][ +  - ]:        216 :         if (!all_exact && (overflow || result >= db_size))
                 [ -  + ]
     109                 :          0 :             return db_size;
     110                 :            :     }
     111 [ +  + ][ +  - ]:        128 :     if (all_exact && (overflow || result > db_size)) {
                 [ +  + ]
     112                 :            :         // If the sub-postlist tfs are all exact, then if the sum of them has
     113                 :            :         // a different odd/even-ness to db_size then max tf of the XOR can't
     114                 :            :         // achieve db_size.
     115                 :         49 :         return db_size - ((result & 1) != (db_size & 1));
     116                 :            :     }
     117                 :         79 :     return result;
     118                 :            : }
     119                 :            : 
     120                 :            : Xapian::doccount
     121                 :        120 : MultiXorPostList::get_termfreq_est() const
     122                 :            : {
     123                 :            :     LOGCALL(MATCH, Xapian::doccount, "MultiXorPostList::get_termfreq_est", NO_ARGS);
     124         [ +  + ]:        120 :     if (rare(db_size == 0))
     125                 :          8 :         RETURN(0);
     126                 :            :     // We calculate the estimate assuming independence.  The simplest
     127                 :            :     // way to calculate this seems to be a series of (n_kids - 1) pairwise
     128                 :            :     // calculations, which gives the same answer regardless of the order.
     129                 :        112 :     double scale = 1.0 / db_size;
     130                 :        112 :     double P_est = plist[0]->get_termfreq_est() * scale;
     131         [ +  + ]:        312 :     for (size_t i = 1; i < n_kids; ++i) {
     132                 :        200 :         double P_i = plist[i]->get_termfreq_est() * scale;
     133                 :        200 :         P_est += P_i - 2.0 * P_est * P_i;
     134                 :            :     }
     135                 :        112 :     return static_cast<Xapian::doccount>(P_est * db_size + 0.5);
     136                 :            : }
     137                 :            : 
     138                 :            : TermFreqs
     139                 :         16 : MultiXorPostList::get_termfreq_est_using_stats(
     140                 :            :         const Xapian::Weight::Internal & stats) const
     141                 :            : {
     142                 :            :     LOGCALL(MATCH, TermFreqs, "MultiXorPostList::get_termfreq_est_using_stats", stats);
     143                 :            :     // We calculate the estimate assuming independence.  The simplest
     144                 :            :     // way to calculate this seems to be a series of (n_kids - 1) pairwise
     145                 :            :     // calculations, which gives the same answer regardless of the order.
     146         [ +  - ]:         16 :     TermFreqs freqs(plist[0]->get_termfreq_est_using_stats(stats));
     147                 :            : 
     148                 :            :     // Our caller should have ensured this.
     149                 :            :     Assert(stats.collection_size);
     150                 :         16 :     double scale = 1.0 / stats.collection_size;
     151                 :         16 :     double P_est = freqs.termfreq * scale;
     152                 :         16 :     double rtf_scale = 0.0;
     153         [ -  + ]:         16 :     if (stats.rset_size != 0) {
     154                 :          0 :         rtf_scale = 1.0 / stats.rset_size;
     155                 :            :     }
     156                 :         16 :     double Pr_est = freqs.reltermfreq * rtf_scale;
     157                 :         16 :     double cf_scale = 1.0 / stats.total_term_count;
     158                 :         16 :     double Pc_est = freqs.collfreq * cf_scale;
     159                 :            : 
     160         [ +  + ]:         32 :     for (size_t i = 1; i < n_kids; ++i) {
     161         [ +  - ]:         16 :         freqs = plist[i]->get_termfreq_est_using_stats(stats);
     162                 :         16 :         double P_i = freqs.termfreq * scale;
     163                 :         16 :         P_est += P_i - 2.0 * P_est * P_i;
     164                 :         16 :         double Pc_i = freqs.collfreq * cf_scale;
     165                 :         16 :         Pc_est += Pc_i - 2.0 * Pc_est * Pc_i;
     166                 :            :         // If the rset is empty, Pr_est should be 0 already, so leave
     167                 :            :         // it alone.
     168         [ -  + ]:         16 :         if (stats.rset_size != 0) {
     169                 :          0 :             double Pr_i = freqs.reltermfreq * rtf_scale;
     170                 :          0 :             Pr_est += Pr_i - 2.0 * Pr_est * Pr_i;
     171                 :            :         }
     172                 :            :     }
     173                 :         16 :     RETURN(TermFreqs(Xapian::doccount(P_est * stats.collection_size + 0.5),
     174                 :            :                      Xapian::doccount(Pr_est * stats.rset_size + 0.5),
     175                 :            :                      Xapian::termcount(Pc_est * stats.total_term_count + 0.5)));
     176                 :            : }
     177                 :            : 
     178                 :            : Xapian::docid
     179                 :       2127 : MultiXorPostList::get_docid() const
     180                 :            : {
     181                 :       2127 :     return did;
     182                 :            : }
     183                 :            : 
     184                 :            : double
     185                 :        996 : MultiXorPostList::get_weight(Xapian::termcount doclen,
     186                 :            :                              Xapian::termcount unique_terms) const
     187                 :            : {
     188                 :            :     Assert(did);
     189                 :        996 :     double result = 0;
     190         [ +  + ]:       3105 :     for (size_t i = 0; i < n_kids; ++i) {
     191         [ +  + ]:       2109 :         if (plist[i]->get_docid() == did)
     192                 :       1052 :             result += plist[i]->get_weight(doclen, unique_terms);
     193                 :            :     }
     194                 :        996 :     return result;
     195                 :            : }
     196                 :            : 
     197                 :            : bool
     198                 :       1378 : MultiXorPostList::at_end() const
     199                 :            : {
     200                 :       1378 :     return (did == 0);
     201                 :            : }
     202                 :            : 
     203                 :            : double
     204                 :         98 : MultiXorPostList::recalc_maxweight()
     205                 :            : {
     206                 :            :     LOGCALL(MATCH, double, "MultiXorPostList::recalc_maxweight", NO_ARGS);
     207                 :         98 :     double max_total = plist[0]->recalc_maxweight();
     208                 :         98 :     double min_max = max_total;
     209         [ +  + ]:        284 :     for (size_t i = 1; i < n_kids; ++i) {
     210                 :        186 :         double new_max = plist[i]->recalc_maxweight();
     211         [ +  + ]:        186 :         if (new_max < min_max)
     212                 :         50 :             min_max = new_max;
     213                 :        186 :         max_total += new_max;
     214                 :            :     }
     215         [ +  + ]:         98 :     if ((n_kids & 1) == 0) {
     216                 :            :         // If n_kids is even, we omit the child with the smallest maxweight.
     217                 :         74 :         max_total -= min_max;
     218                 :            :     }
     219                 :         98 :     RETURN(max_total);
     220                 :            : }
     221                 :            : 
     222                 :            : PostList *
     223                 :       1572 : MultiXorPostList::next(double w_min)
     224                 :            : {
     225                 :            :     LOGCALL(MATCH, PostList *, "MultiXorPostList::next", w_min);
     226                 :       1572 :     Xapian::docid old_did = did;
     227                 :       1572 :     did = 0;
     228                 :       1572 :     size_t matching_count = 0;
     229         [ +  + ]:       4961 :     for (size_t i = 0; i < n_kids; ++i) {
     230 [ +  + ][ +  + ]:       3389 :         if (old_did == 0 || plist[i]->get_docid() <= old_did) {
                 [ +  + ]
     231                 :            :             // FIXME: calculate the min weight required here...
     232                 :       1922 :             PostList * res = plist[i]->next(0);
     233         [ +  + ]:       1922 :             if (res) {
     234         [ +  - ]:         10 :                 delete plist[i];
     235                 :         10 :                 plist[i] = res;
     236                 :         10 :                 matcher->force_recalc();
     237                 :            :             }
     238                 :            : 
     239         [ +  + ]:       1922 :             if (plist[i]->at_end()) {
     240                 :        160 :                 erase_sublist(i--);
     241                 :       1922 :                 continue;
     242                 :            :             }
     243                 :            :         }
     244                 :            : 
     245                 :       3229 :         Xapian::docid new_did = plist[i]->get_docid();
     246 [ +  + ][ +  + ]:       3229 :         if (did == 0 || new_did < did) {
     247                 :       2646 :             did = new_did;
     248                 :       2646 :             matching_count = 1;
     249         [ +  + ]:        583 :         } else if (new_did == did) {
     250                 :        206 :             ++matching_count;
     251                 :            :         }
     252                 :            :     }
     253                 :            : 
     254         [ +  + ]:       1572 :     if (n_kids == 1) {
     255                 :         72 :         n_kids = 0;
     256                 :         72 :         RETURN(plist[0]);
     257                 :            :     }
     258                 :            : 
     259                 :            :     // We've reached the end of all posting lists.
     260         [ +  + ]:       1500 :     if (did == 0)
     261                 :         16 :         RETURN(NULL);
     262                 :            : 
     263                 :            :     // An odd number of sub-postlists match this docid, so the XOR matches.
     264         [ +  + ]:       1484 :     if (matching_count & 1)
     265                 :       1362 :         RETURN(NULL);
     266                 :            : 
     267                 :            :     // An even number of sub-postlists match this docid, so advance again.
     268                 :        122 :     RETURN(next(w_min));
     269                 :            : }
     270                 :            : 
     271                 :            : PostList *
     272                 :          0 : MultiXorPostList::skip_to(Xapian::docid did_min, double w_min)
     273                 :            : {
     274                 :            :     LOGCALL(MATCH, PostList *, "MultiXorPostList::skip_to", did_min | w_min);
     275                 :          0 :     Xapian::docid old_did = did;
     276                 :          0 :     did = 0;
     277                 :          0 :     size_t matching_count = 0;
     278         [ #  # ]:          0 :     for (size_t i = 0; i < n_kids; ++i) {
     279 [ #  # ][ #  # ]:          0 :         if (old_did == 0 || plist[i]->get_docid() < did_min) {
                 [ #  # ]
     280                 :            :             // FIXME: calculate the min weight required here...
     281                 :          0 :             PostList * res = plist[i]->skip_to(did_min, 0);
     282         [ #  # ]:          0 :             if (res) {
     283         [ #  # ]:          0 :                 delete plist[i];
     284                 :          0 :                 plist[i] = res;
     285                 :          0 :                 matcher->force_recalc();
     286                 :            :             }
     287                 :            : 
     288         [ #  # ]:          0 :             if (plist[i]->at_end()) {
     289                 :          0 :                 erase_sublist(i--);
     290                 :          0 :                 continue;
     291                 :            :             }
     292                 :            :         }
     293                 :            : 
     294                 :          0 :         Xapian::docid new_did = plist[i]->get_docid();
     295 [ #  # ][ #  # ]:          0 :         if (did == 0 || new_did < did) {
     296                 :          0 :             did = new_did;
     297                 :          0 :             matching_count = 1;
     298         [ #  # ]:          0 :         } else if (new_did == did) {
     299                 :          0 :             ++matching_count;
     300                 :            :         }
     301                 :            :     }
     302                 :            : 
     303         [ #  # ]:          0 :     if (n_kids == 1) {
     304                 :            :         AssertEq(matching_count, 1);
     305                 :          0 :         n_kids = 0;
     306                 :          0 :         RETURN(plist[0]);
     307                 :            :     }
     308                 :            : 
     309                 :            :     // We've reached the end of all posting lists.
     310         [ #  # ]:          0 :     if (did == 0)
     311                 :          0 :         RETURN(NULL);
     312                 :            : 
     313                 :            :     // An odd number of sub-postlists match this docid, so the XOR matches.
     314         [ #  # ]:          0 :     if (matching_count & 1)
     315                 :          0 :         RETURN(NULL);
     316                 :            : 
     317                 :            :     // An even number of sub-postlists match this docid, so call next.
     318                 :          0 :     RETURN(next(w_min));
     319                 :            : }
     320                 :            : 
     321                 :            : string
     322                 :          0 : MultiXorPostList::get_description() const
     323                 :            : {
     324         [ #  # ]:          0 :     string desc("(");
     325 [ #  # ][ #  # ]:          0 :     desc += plist[0]->get_description();
     326         [ #  # ]:          0 :     for (size_t i = 1; i < n_kids; ++i) {
     327         [ #  # ]:          0 :         desc += " XOR ";
     328 [ #  # ][ #  # ]:          0 :         desc += plist[i]->get_description();
     329                 :            :     }
     330         [ #  # ]:          0 :     desc += ')';
     331                 :          0 :     return desc;
     332                 :            : }
     333                 :            : 
     334                 :            : Xapian::termcount
     335                 :        352 : MultiXorPostList::get_wdf() const
     336                 :            : {
     337                 :        352 :     Xapian::termcount totwdf = 0;
     338         [ +  + ]:       1056 :     for (size_t i = 0; i < n_kids; ++i) {
     339         [ +  + ]:        704 :         if (plist[i]->get_docid() == did)
     340                 :        352 :             totwdf += plist[i]->get_wdf();
     341                 :            :     }
     342                 :        352 :     return totwdf;
     343                 :            : }
     344                 :            : 
     345                 :            : Xapian::termcount
     346                 :        131 : MultiXorPostList::count_matching_subqs() const
     347                 :            : {
     348                 :        131 :     Xapian::termcount total = 0;
     349         [ +  + ]:        478 :     for (size_t i = 0; i < n_kids; ++i) {
     350         [ +  + ]:        347 :         if (plist[i]->get_docid() == did)
     351                 :        185 :             total += plist[i]->count_matching_subqs();
     352                 :            :     }
     353                 :        131 :     return total;
     354                 :            : }

Generated by: LCOV version 1.11