Branch data Line data Source code
1 : : #include <mutable/storage/Index.hpp>
2 : :
3 : : #include <mutable/catalog/Schema.hpp>
4 : : #include <mutable/catalog/Type.hpp>
5 : : #include <mutable/mutable.hpp>
6 : : #include <mutable/Options.hpp>
7 : : #include <mutable/util/Timer.hpp>
8 : : #include <sstream>
9 : :
10 : :
11 : : using namespace m;
12 : : using namespace m::idx;
13 : :
14 : : namespace {
15 : :
16 : : namespace options {
17 : :
18 : : /** Which ratio of linear models to index entries should be used for `idx::RecursiveModelIndex`. */
19 : : double rmi_model_entry_ratio = 0.01;
20 : :
21 : : }
22 : :
23 : : __attribute__((constructor(201)))
24 : 1 : static void add_index_args()
25 : : {
26 : 1 : Catalog &C = Catalog::Get();
27 : :
28 : : /*----- Command-line arguments -----*/
29 : 1 : C.arg_parser().add<double>(
30 : : /* group= */ "Index",
31 : : /* short= */ nullptr,
32 : : /* long= */ "--rmi-model-entry-ratio",
33 : : /* description= */ "specify the ratio of linear models to index entries for recursive model indexes",
34 : 0 : /* callback= */ [](double rmi_model_entry_ratio){ options::rmi_model_entry_ratio = rmi_model_entry_ratio; }
35 : : );
36 : 1 : }
37 : :
38 : : }
39 : :
40 : 6 : std::string IndexBase::build_query(const Table &table, const Schema &schema)
41 : : {
42 : 6 : std::ostringstream oss;
43 [ + - ]: 6 : oss << "SELECT ";
44 [ + - + + ]: 12 : for (std::size_t i = 0; i != schema.num_entries(); ++i) {
45 [ - + # # ]: 6 : if (i != 0) oss << ", ";
46 [ + - + - ]: 6 : oss << schema.at(i).id;
47 : 6 : }
48 [ + - + - : 6 : oss << " FROM " << table.name() << ';';
+ - + - ]
49 [ + - ]: 6 : return oss.str();
50 : 6 : }
51 : :
52 : : template<typename Key>
53 : 6 : void ArrayIndex<Key>::bulkload(const Table &table, const Schema &key_schema)
54 : : {
55 : : /* XXX: Disable timer during execution to not print times for query that is performed as part of bulkloading. */
56 : 6 : const auto &old_timer = std::exchange(Catalog::Get().timer(), Timer());
57 : :
58 : : /* Check that key schema contains a single entry. */
59 [ # # # # : 6 : if (key_schema.num_entries() != 1)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - #
# # # ]
60 [ # # # # : 0 : throw invalid_argument("Key schema should contain exactly one entry.");
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ]
61 [ # # # # : 6 : auto entry = key_schema.at(0);
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - #
# # # ]
62 : :
63 : : /* Check that key type and attribute type match. */
64 : 6 : auto attribute_type = entry.type;
65 : : #define CHECK(TYPE) \
66 : : if constexpr(not std::same_as<key_type, TYPE>) \
67 : 0 : throw invalid_argument("Key type and attribute type do not match."); \
68 : : return
69 : :
70 [ # # + - : 6 : visit(overloaded {
+ - + - +
- + - + -
# # ]
71 [ # # # # : 0 : [](const Boolean&) { CHECK(bool); },
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
72 : 6 : [](const Numeric &n) {
73 [ # # # - : 6 : switch (n.kind) {
+ - - + -
- + - - +
- - + - -
+ - # #
# ]
74 : 1 : case Numeric::N_Int:
75 : : case Numeric::N_Decimal:
76 [ # # # # : 4 : switch (n.size()) {
# + - - -
- + - - -
- + - - -
- + - - -
- # # # #
# # # # #
# # # # #
# ]
77 : 0 : default: M_unreachable("invalid size");
78 [ # # # # : 1 : case 8: CHECK(int8_t);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
79 [ # # # # : 1 : case 16: CHECK(int16_t);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
80 [ # # # # : 1 : case 32: CHECK(int32_t);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
81 [ # # # # : 1 : case 64: CHECK(int64_t);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
82 : : }
83 : : case Numeric::N_Float:
84 [ # # # # : 2 : switch (n.size()) {
# # # # #
# # # # #
# + - - +
- - # #
# ]
85 : 0 : default: M_unreachable("invalid size");
86 [ # # # # : 1 : case 32: CHECK(float);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
87 [ # # # # : 1 : case 64: CHECK(double);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
88 : : }
89 : : }
90 : 6 : },
91 [ # # # # : 0 : [](const CharacterSequence&) { CHECK(const char*); },
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
92 [ # # # # : 0 : [](const Date&) { CHECK(int32_t); },
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
93 [ # # # # : 0 : [](const DateTime&) { CHECK(int64_t); },
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
94 : 0 : [](auto&&) { M_unreachable("invalid type"); },
95 : 6 : }, *attribute_type);
96 : : #undef CHECk
97 : :
98 : : /* Build the query to retrieve keys. */
99 [ # # + - : 6 : auto query = build_query(table, key_schema);
+ - + - +
- + - + -
# # ]
100 : :
101 : : /* Create the diagnostics object. */
102 [ # # # # : 6 : Diagnostic diag(Options::Get().has_color, std::cout, std::cerr);
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - #
# # # ]
103 : :
104 : : /* Compute statement from query string. */
105 [ # # + - : 6 : auto stmt = statement_from_string(diag, query);
+ - + - +
- + - + -
# # ]
106 : :
107 : : /* Define get function based on key_type. */
108 : 6 : std::function<key_type(const Tuple&)> fn_get;
109 : : if constexpr(integral<key_type>)
110 : 16 : fn_get = [](const Tuple &t) { return static_cast<key_type>(t.get(0).as<int64_t>()); };
111 : : else // bool, float, double, const char*
112 : 8 : fn_get = [](const Tuple &t) { return t.get(0).as<key_type>(); };
113 : :
114 : : /* Define callback operator to add keys to index. */
115 : 6 : std::size_t tuple_id = 0;
116 : 30 : auto fn_add = [&](const Schema&, const Tuple &tuple) {
117 [ # # + + : 24 : if (not tuple.is_null(0))
+ + + + +
+ + + + +
# # ]
118 : 18 : this->add(fn_get(tuple), tuple_id);
119 : 24 : tuple_id++;
120 : 24 : };
121 [ # # + - : 6 : auto consumer = std::make_unique<CallbackOperator>(fn_add);
+ - + - +
- + - + -
# # ]
122 : :
123 : : /* Create backend on which the query is exectued. We are using the `Interpreter` as the `wasm::Scan` might have
124 : : * been deactivated via CLI which results in not finding a plan for the query.
125 : : * TODO: We plan on using the default `Backend` set in the `Catalog` with temporarily adjusting the options to make
126 : : * sure `wasm::Scan` is available. */
127 [ # # - + : 6 : static thread_local std::unique_ptr<Backend> backend;
- + - + -
+ - + - +
# # ]
128 [ # # + - : 6 : if (not backend)
+ - + - +
- + - + -
# # ]
129 [ # # # # : 6 : backend = Catalog::Get().create_backend(Catalog::Get().pool("Interpreter"));
# # # # +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - # # #
# # # #
# ]
130 : :
131 : : /* Execute query to insert tuples. */
132 [ # # # # : 6 : m::execute_query(diag, as<ast::SelectStmt>(*stmt), std::move(consumer), *backend);
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - #
# # # ]
133 : :
134 : : /* Finalize index. */
135 [ # # + - : 6 : finalize();
+ - + - +
- + - + -
# # ]
136 : :
137 : : /* XXX: Reenable timer. */
138 [ # # # # : 6 : std::exchange(Catalog::Get().timer(), std::move(old_timer));
# # + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - # #
# # # # ]
139 : 6 : }
140 : :
141 : : template<typename Key>
142 : 37 : void ArrayIndex<Key>::add(const key_type key, const value_type value)
143 : : {
144 : : if constexpr(std::same_as<key_type, const char*>) {
145 : 0 : Catalog &C = Catalog::Get();
146 [ # # ]: 0 : data_.emplace_back(C.pool(key), value);
147 : : } else {
148 : 37 : data_.emplace_back(key, value);
149 : : }
150 : 37 : finalized_ = false;
151 : 37 : }
152 : :
153 : : template<arithmetic Key>
154 : 0 : void RecursiveModelIndex<Key>::finalize()
155 : : {
156 : : /* Sort data. */
157 : 0 : std::sort(base_type::data_.begin(), base_type::data_.end(), base_type::cmp);
158 : :
159 : : /* Compute number of models. */
160 : 0 : auto begin = base_type::begin();
161 : 0 : auto end = base_type::end();
162 : 0 : std::size_t n_keys = std::distance(begin, end);
163 : 0 : std::size_t n_models = std::max<std::size_t>(1, n_keys * options::rmi_model_entry_ratio);
164 : 0 : models_.reserve(n_models + 1);
165 : :
166 : : /* Train first layer. */
167 : 0 : models_.emplace_back(
168 : 0 : LinearModel::train_linear_spline(
169 : 0 : /* begin= */ begin,
170 : 0 : /* end= */ end,
171 : : /* offset= */ 0,
172 : 0 : /* compression_factor= */ static_cast<double>(n_models) / n_keys
173 : : )
174 : : );
175 : :
176 : : /* Train second layer. */
177 : 0 : auto get_segment_id = [&](entry_type e) { return std::clamp<double>(models_[0](e.first), 0, n_models - 1); };
178 : 0 : std::size_t segment_start = 0;
179 : 0 : std::size_t segment_id = 0;
180 [ # # # # : 0 : for (std::size_t i = 0; i != n_keys; ++i) {
# # # # #
# # # ]
181 : 0 : auto pos = begin + i;
182 : 0 : std::size_t pred_segment_id = get_segment_id(*pos);
183 [ # # # # : 0 : if (pred_segment_id > segment_id) {
# # # # #
# # # ]
184 : 0 : models_.emplace_back(
185 : 0 : LinearModel::train_linear_regression(
186 : 0 : /* begin= */ begin + segment_start,
187 : 0 : /* end= */ pos,
188 : 0 : /* offset= */ segment_start
189 : : )
190 : : );
191 [ # # # # : 0 : for (std::size_t j = segment_id + 1; j < pred_segment_id; ++j) {
# # # # #
# # # ]
192 : 0 : models_.emplace_back(
193 : 0 : LinearModel::train_linear_regression(
194 : 0 : /* begin= */ pos - 1,
195 : 0 : /* end= */ pos,
196 : 0 : /* offset= */ i - 1
197 : : )
198 : : );
199 : 0 : }
200 : 0 : segment_id = pred_segment_id;
201 : 0 : segment_start = i;
202 : :
203 : 0 : }
204 : 0 : }
205 : 0 : models_.emplace_back(
206 : 0 : LinearModel::train_linear_regression(
207 : 0 : /* begin= */ begin + segment_start,
208 : 0 : /* end= */ end,
209 : 0 : /* offset= */ segment_start
210 : : )
211 : : );
212 [ # # # # : 0 : for (std::size_t j = segment_id + 1; j < n_models; ++j) {
# # # # #
# # # ]
213 : 0 : models_.emplace_back(
214 : 0 : LinearModel::train_linear_regression(
215 : 0 : /* begin= */ end - 1,
216 : 0 : /* end= */ end,
217 : 0 : /* offset= */ n_keys - 1
218 : : )
219 : : );
220 : 0 : }
221 : :
222 : : /* Mark index as finalized. */
223 : 0 : base_type::finalized_ = true;
224 : 0 : };
225 : :
226 : : // explicit instantiations to prevent linker errors
227 : : #define INSTANTIATE(CLASS) \
228 : : template struct CLASS;
229 : : M_INDEX_LIST_TEMPLATED(INSTANTIATE)
230 : : #undef INSTANTIATE
|
