xapian-core/matcher/collapser.h

   1 /** @file collapser.h
   2  * @brief Collapse documents with the same collapse key during the match.
   3  */
   4 /* Copyright (C) 2009,2011,2017 Olly Betts
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public License as
   8  * published by the Free Software Foundation; either version 2 of the
   9  * License, or (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
  19  */
  20
  21 #ifndef XAPIAN_INCLUDED_COLLAPSER_H
  22 #define XAPIAN_INCLUDED_COLLAPSER_H
  23
  24 #include "backends/documentinternal.h"
  25 #include "msetcmp.h"
  26 #include "api/postlist.h"
  27 #include "api/result.h"
  28
  29 #include <unordered_map>
  30 #include <vector>
  31
  32 /// Enumeration reporting how a document was handled by the Collapser.
  33 typedef enum {
  34     EMPTY,
  35     ADDED,
  36     REJECTED,
  37     REPLACED
  38 } collapse_result;
  39
  40 /// Class tracking information for a given value of the collapse key.
  41 class CollapseData {
  42     /** Currently kept MSet entries for this value of the collapse key.
  43      *
  44      *  If collapse_max > 1, then this is a min-heap once collapse_count > 0.
  45      *
  46      *  FIXME: We expect collapse_max to be small, so perhaps we should
  47      *  preallocate space for that many entries and/or allocate space in
  48      *  larger blocks to divvy up?
  49      */
  50     std::vector<Result> items;
  51
  52     /// The highest weight of a document we've rejected.
  53     double next_best_weight;
  54
  55     /// The number of documents we've rejected.
  56     Xapian::doccount collapse_count;
  57
  58   public:
  59     /// Construct with the given Result @a item.
  60     explicit CollapseData(const Result& item)
  61         : items(1, item), next_best_weight(0), collapse_count(0) {
  62         items[0].set_collapse_key(std::string());
  63     }
  64
  65     /** Handle a new Result with this collapse key value.
  66      *
  67      *  @param item             The new item.
  68      *  @param collapse_max     Max no. of items for each collapse key value.
  69      *  @param mcmp             Result comparison functor.
  70      *  @param[out] old_item    Replaced item (when REPLACED is returned).
  71      *
  72      *  @return How @a item was handled: ADDED, REJECTED or REPLACED.
  73      */
  74     collapse_result add_item(const Result& item,
  75                              Xapian::doccount collapse_max,
  76                              const MSetCmp & mcmp,
  77                              Result& old_item);
  78
  79     /// The highest weight of a document we've rejected.
  80     double get_next_best_weight() const { return next_best_weight; }
  81
  82     /// The number of documents we've rejected.
  83     Xapian::doccount get_collapse_count() const { return collapse_count; }
  84 };
  85
  86 /// The Collapser class tracks collapse keys and the documents they match.
  87 class Collapser {
  88     /// Map from collapse key values to the items we're keeping for them.
  89     std::unordered_map<std::string, CollapseData> table;
  90
  91     /// How many items we're currently keeping in @a table.
  92     Xapian::doccount entry_count = 0;
  93
  94     /** How many documents have we seen without a collapse key?
  95      *
  96      *  We use this statistic to improve matches_lower_bound.
  97      */
  98     Xapian::doccount no_collapse_key = 0;
  99
 100     /** How many documents with duplicate collapse keys we have ignored.
 101      *
 102      *  We use this statistic to improve matches_estimated (by considering
 103      *  the rate of collapsing) and matches_upper_bound.
 104      */
 105     Xapian::doccount dups_ignored = 0;
 106
 107     /** How many documents we've considered for collapsing.
 108      *
 109      *  We use this statistic to improve matches_estimated (by considering
 110      *  the rate of collapsing).
 111      */
 112     Xapian::doccount docs_considered = 0;
 113
 114     /** The value slot we're getting collapse keys from. */
 115     Xapian::valueno slot;
 116
 117     /** The maximum number of items to keep for each collapse key value. */
 118     Xapian::doccount collapse_max;
 119
 120   public:
 121     /// Replaced item when REPLACED is returned by @a collapse().
 122     Result old_item;
 123
 124     Collapser(Xapian::valueno slot_, Xapian::doccount collapse_max_)
 125         : slot(slot_), collapse_max(collapse_max_), old_item(0, 0) { }
 126
 127     /// Return true if collapsing is active for this match.
 128     operator bool() const { return collapse_max != 0; }
 129
 130     /** Handle a new Result.
 131      *
 132      *  @param item     The new item.
 133      *  @param key_ptr  If non-NULL, points to the collapse key (this happens
 134      *                  for a remote match).
 135      *  @param doc      Document for getting values.
 136      *  @param mcmp     Result comparison functor.
 137      *
 138      *  @return How @a item was handled: EMPTY, ADDED, REJECTED or REPLACED.
 139      */
 140     collapse_result process(Result& item,
 141                             const std::string* key_ptr,
 142                             Xapian::Document::Internal & vsdoc,
 143                             const MSetCmp & mcmp);
 144
 145     Xapian::doccount get_collapse_count(const std::string & collapse_key,
 146                                         int percent_cutoff,
 147                                         double min_weight) const;
 148
 149     Xapian::doccount get_docs_considered() const { return docs_considered; }
 150
 151     Xapian::doccount get_dups_ignored() const { return dups_ignored; }
 152
 153     Xapian::doccount get_entries() const { return entry_count; }
 154
 155     Xapian::doccount get_matches_lower_bound() const;
 156
 157     bool empty() const { return table.empty(); }
 158 };
 159
 160 #endif // XAPIAN_INCLUDED_COLLAPSER_H