1#include "duckdb/optimizer/filter_combiner.hpp"
2
3#include "duckdb/execution/expression_executor.hpp"
4#include "duckdb/planner/expression/bound_between_expression.hpp"
5#include "duckdb/planner/expression/bound_comparison_expression.hpp"
6#include "duckdb/planner/expression/bound_constant_expression.hpp"
7#include "duckdb/planner/expression/bound_function_expression.hpp"
8#include "duckdb/planner/operator/logical_empty_result.hpp"
9#include "duckdb/planner/operator/logical_filter.hpp"
10#include "duckdb/planner/expression/bound_columnref_expression.hpp"
11#include "duckdb/planner/expression.hpp"
12using namespace duckdb;
13using namespace std;
14
15using ExpressionValueInformation = FilterCombiner::ExpressionValueInformation;
16
17ValueComparisonResult CompareValueInformation(ExpressionValueInformation &left, ExpressionValueInformation &right);
18
19Expression *FilterCombiner::GetNode(Expression *expr) {
20 auto entry = stored_expressions.find(expr);
21 if (entry != stored_expressions.end()) {
22 // expression already exists: return a reference to the stored expression
23 return entry->second.get();
24 }
25 // expression does not exist yet: create a copy and store it
26 auto copy = expr->Copy();
27 auto pointer_copy = copy.get();
28 stored_expressions.insert(make_pair(pointer_copy, move(copy)));
29 return pointer_copy;
30}
31
32idx_t FilterCombiner::GetEquivalenceSet(Expression *expr) {
33 assert(stored_expressions.find(expr) != stored_expressions.end());
34 assert(stored_expressions.find(expr)->second.get() == expr);
35
36 auto entry = equivalence_set_map.find(expr);
37 if (entry == equivalence_set_map.end()) {
38 idx_t index = set_index++;
39 equivalence_set_map[expr] = index;
40 equivalence_map[index].push_back(expr);
41 constant_values.insert(make_pair(index, vector<ExpressionValueInformation>()));
42 return index;
43 } else {
44 return entry->second;
45 }
46}
47
48FilterResult FilterCombiner::AddConstantComparison(vector<ExpressionValueInformation> &info_list,
49 ExpressionValueInformation info) {
50 for (idx_t i = 0; i < info_list.size(); i++) {
51 auto comparison = CompareValueInformation(info_list[i], info);
52 switch (comparison) {
53 case ValueComparisonResult::PRUNE_LEFT:
54 // prune the entry from the info list
55 info_list.erase(info_list.begin() + i);
56 i--;
57 break;
58 case ValueComparisonResult::PRUNE_RIGHT:
59 // prune the current info
60 return FilterResult::SUCCESS;
61 case ValueComparisonResult::UNSATISFIABLE_CONDITION:
62 // combination of filters is unsatisfiable: prune the entire branch
63 return FilterResult::UNSATISFIABLE;
64 default:
65 // prune nothing, move to the next condition
66 break;
67 }
68 }
69 // finally add the entry to the list
70 info_list.push_back(info);
71 return FilterResult::SUCCESS;
72}
73
74FilterResult FilterCombiner::AddFilter(unique_ptr<Expression> expr) {
75 // try to push the filter into the combiner
76 auto result = AddFilter(expr.get());
77 if (result == FilterResult::UNSUPPORTED) {
78 // unsupported filter, push into remaining filters
79 remaining_filters.push_back(move(expr));
80 return FilterResult::SUCCESS;
81 }
82 return result;
83}
84
85void FilterCombiner::GenerateFilters(std::function<void(unique_ptr<Expression> filter)> callback) {
86 // first loop over the remaining filters
87 for (auto &filter : remaining_filters) {
88 callback(move(filter));
89 }
90 remaining_filters.clear();
91 // now loop over the equivalence sets
92 for (auto &entry : equivalence_map) {
93 auto equivalence_set = entry.first;
94 auto &entries = entry.second;
95 auto &constant_list = constant_values.find(equivalence_set)->second;
96 // for each entry generate an equality expression comparing to each other
97 for (idx_t i = 0; i < entries.size(); i++) {
98 for (idx_t k = i + 1; k < entries.size(); k++) {
99 auto comparison = make_unique<BoundComparisonExpression>(ExpressionType::COMPARE_EQUAL,
100 entries[i]->Copy(), entries[k]->Copy());
101 callback(move(comparison));
102 }
103 // for each entry also create a comparison with each constant
104 int lower_index = -1, upper_index = -1;
105 bool lower_inclusive, upper_inclusive;
106 for (idx_t k = 0; k < constant_list.size(); k++) {
107 auto &info = constant_list[k];
108 if (info.comparison_type == ExpressionType::COMPARE_GREATERTHAN ||
109 info.comparison_type == ExpressionType::COMPARE_GREATERTHANOREQUALTO) {
110 lower_index = k;
111 lower_inclusive = info.comparison_type == ExpressionType::COMPARE_GREATERTHANOREQUALTO;
112 } else if (info.comparison_type == ExpressionType::COMPARE_LESSTHAN ||
113 info.comparison_type == ExpressionType::COMPARE_LESSTHANOREQUALTO) {
114 upper_index = k;
115 upper_inclusive = info.comparison_type == ExpressionType::COMPARE_LESSTHANOREQUALTO;
116 } else {
117 auto constant = make_unique<BoundConstantExpression>(info.constant);
118 auto comparison = make_unique<BoundComparisonExpression>(info.comparison_type, entries[i]->Copy(),
119 move(constant));
120 callback(move(comparison));
121 }
122 }
123 if (lower_index >= 0 && upper_index >= 0) {
124 // found both lower and upper index, create a BETWEEN expression
125 auto lower_constant = make_unique<BoundConstantExpression>(constant_list[lower_index].constant);
126 auto upper_constant = make_unique<BoundConstantExpression>(constant_list[upper_index].constant);
127 auto between = make_unique<BoundBetweenExpression>(
128 entries[i]->Copy(), move(lower_constant), move(upper_constant), lower_inclusive, upper_inclusive);
129 callback(move(between));
130 } else if (lower_index >= 0) {
131 // only lower index found, create simple comparison expression
132 auto constant = make_unique<BoundConstantExpression>(constant_list[lower_index].constant);
133 auto comparison = make_unique<BoundComparisonExpression>(constant_list[lower_index].comparison_type,
134 entries[i]->Copy(), move(constant));
135 callback(move(comparison));
136 } else if (upper_index >= 0) {
137 // only upper index found, create simple comparison expression
138 auto constant = make_unique<BoundConstantExpression>(constant_list[upper_index].constant);
139 auto comparison = make_unique<BoundComparisonExpression>(constant_list[upper_index].comparison_type,
140 entries[i]->Copy(), move(constant));
141 callback(move(comparison));
142 }
143 }
144 }
145 stored_expressions.clear();
146 equivalence_set_map.clear();
147 constant_values.clear();
148 equivalence_map.clear();
149}
150
151bool FilterCombiner::HasFilters() {
152 bool has_filters = false;
153 GenerateFilters([&](unique_ptr<Expression> child) { has_filters = true; });
154 return has_filters;
155}
156
157vector<TableFilter>
158FilterCombiner::GenerateTableScanFilters(std::function<void(unique_ptr<Expression> filter)> callback,
159 vector<idx_t> &column_ids) {
160 vector<TableFilter> tableFilters;
161 //! First, we figure the filters that have constant expressions that we can push down to the table scan
162 for (auto &constant_value : constant_values) {
163 if (constant_value.second.size() > 0) {
164 // for (idx_t i = 0; i < constant_value.second.size(); ++i) {
165 auto filter_exp = equivalence_map.end();
166 if ((constant_value.second[0].comparison_type == ExpressionType::COMPARE_EQUAL ||
167 constant_value.second[0].comparison_type == ExpressionType::COMPARE_GREATERTHAN ||
168 constant_value.second[0].comparison_type == ExpressionType::COMPARE_GREATERTHANOREQUALTO ||
169 constant_value.second[0].comparison_type == ExpressionType::COMPARE_LESSTHAN ||
170 constant_value.second[0].comparison_type == ExpressionType::COMPARE_LESSTHANOREQUALTO) &&
171 (TypeIsNumeric(constant_value.second[0].constant.type) ||
172 constant_value.second[0].constant.type == TypeId::VARCHAR)) {
173 //! Here we check if these filters are column references
174 filter_exp = equivalence_map.find(constant_value.first);
175 if (filter_exp->second.size() == 1 && filter_exp->second[0]->type == ExpressionType::BOUND_COLUMN_REF) {
176 auto filter_col_exp = static_cast<BoundColumnRefExpression *>(filter_exp->second[0]);
177 if (column_ids[filter_col_exp->binding.column_index] == COLUMN_IDENTIFIER_ROW_ID) {
178 break;
179 }
180 auto equivalence_set = filter_exp->first;
181 auto &entries = filter_exp->second;
182 auto &constant_list = constant_values.find(equivalence_set)->second;
183 // for each entry generate an equality expression comparing to each other
184 for (idx_t i = 0; i < entries.size(); i++) {
185 for (idx_t k = i + 1; k < entries.size(); k++) {
186 auto comparison = make_unique<BoundComparisonExpression>(
187 ExpressionType::COMPARE_EQUAL, entries[i]->Copy(), entries[k]->Copy());
188 callback(move(comparison));
189 }
190 // for each entry also create a comparison with each constant
191 int lower_index = -1, upper_index = -1;
192 for (idx_t k = 0; k < constant_list.size(); k++) {
193 tableFilters.push_back(TableFilter(constant_value.second[k].constant,
194 constant_value.second[k].comparison_type,
195 filter_col_exp->binding.column_index));
196 auto &info = constant_list[k];
197 if (info.comparison_type == ExpressionType::COMPARE_GREATERTHAN ||
198 info.comparison_type == ExpressionType::COMPARE_GREATERTHANOREQUALTO) {
199 lower_index = k;
200
201 } else if (info.comparison_type == ExpressionType::COMPARE_LESSTHAN ||
202 info.comparison_type == ExpressionType::COMPARE_LESSTHANOREQUALTO) {
203 upper_index = k;
204 } else {
205 auto constant = make_unique<BoundConstantExpression>(info.constant);
206 auto comparison = make_unique<BoundComparisonExpression>(
207 info.comparison_type, entries[i]->Copy(), move(constant));
208 callback(move(comparison));
209 }
210 }
211 if (lower_index >= 0) {
212 // only lower index found, create simple comparison expression
213 auto constant = make_unique<BoundConstantExpression>(constant_list[lower_index].constant);
214 auto comparison = make_unique<BoundComparisonExpression>(
215 constant_list[lower_index].comparison_type, entries[i]->Copy(), move(constant));
216 callback(move(comparison));
217 }
218 if (upper_index >= 0) {
219 // only upper index found, create simple comparison expression
220 auto constant = make_unique<BoundConstantExpression>(constant_list[upper_index].constant);
221 auto comparison = make_unique<BoundComparisonExpression>(
222 constant_list[upper_index].comparison_type, entries[i]->Copy(), move(constant));
223 callback(move(comparison));
224 }
225 }
226 equivalence_map.erase(filter_exp);
227 }
228 }
229 }
230 }
231 //! Here we look for LIKE filters with a prefix to use them to skip partitions
232 for (auto &remaining_filter : remaining_filters) {
233 if (remaining_filter->expression_class == ExpressionClass::BOUND_FUNCTION) {
234 auto &func = (BoundFunctionExpression &)*remaining_filter;
235 if (func.function.name == "prefix" &&
236 func.children[0]->expression_class == ExpressionClass::BOUND_COLUMN_REF &&
237 func.children[1]->type == ExpressionType::VALUE_CONSTANT) {
238 //! This is a like function.
239 auto &column_ref = (BoundColumnRefExpression &)*func.children[0].get();
240 auto &constant_value_expr = (BoundConstantExpression &)*func.children[1].get();
241 string like_string = constant_value_expr.value.str_value;
242 if (like_string.empty()) {
243 continue;
244 }
245 auto const_value = constant_value_expr.value.Copy();
246 const_value.str_value = like_string;
247 //! Here the like must be transformed to a BOUND COMPARISON geq le
248 tableFilters.push_back(TableFilter(const_value, ExpressionType::COMPARE_GREATERTHANOREQUALTO,
249 column_ref.binding.column_index));
250 const_value.str_value[const_value.str_value.size() - 1]++;
251 tableFilters.push_back(
252 TableFilter(const_value, ExpressionType::COMPARE_LESSTHAN, column_ref.binding.column_index));
253 }
254 if (func.function.name == "~~" && func.children[0]->expression_class == ExpressionClass::BOUND_COLUMN_REF &&
255 func.children[1]->type == ExpressionType::VALUE_CONSTANT) {
256 //! This is a like function.
257 auto &column_ref = (BoundColumnRefExpression &)*func.children[0].get();
258 auto &constant_value_expr = (BoundConstantExpression &)*func.children[1].get();
259 string like_string = constant_value_expr.value.str_value;
260 auto const_value = constant_value_expr.value.Copy();
261 if (like_string[0] == '%' || like_string[0] == '_') {
262 //! We have no prefix so nothing to pushdown
263 break;
264 }
265 string prefix;
266 bool equality = true;
267 for (char const &c : like_string) {
268 if (c == '%' || c == '_') {
269 equality = false;
270 break;
271 }
272 prefix += c;
273 }
274 const_value.str_value = prefix;
275 if (equality) {
276 //! Here the like can be transformed to an equality query
277 tableFilters.push_back(
278 TableFilter(const_value, ExpressionType::COMPARE_EQUAL, column_ref.binding.column_index));
279 } else {
280 //! Here the like must be transformed to a BOUND COMPARISON geq le
281 tableFilters.push_back(TableFilter(const_value, ExpressionType::COMPARE_GREATERTHANOREQUALTO,
282 column_ref.binding.column_index));
283 const_value.str_value[const_value.str_value.size() - 1]++;
284 tableFilters.push_back(
285 TableFilter(const_value, ExpressionType::COMPARE_LESSTHAN, column_ref.binding.column_index));
286 }
287 }
288 }
289 }
290
291 return tableFilters;
292}
293
294FilterResult FilterCombiner::AddFilter(Expression *expr) {
295 if (expr->HasParameter()) {
296 return FilterResult::UNSUPPORTED;
297 }
298 if (expr->IsFoldable()) {
299 // scalar condition, evaluate it
300 auto result = ExpressionExecutor::EvaluateScalar(*expr).CastAs(TypeId::BOOL);
301 // check if the filter passes
302 if (result.is_null || !result.value_.boolean) {
303 // the filter does not pass the scalar test, create an empty result
304 return FilterResult::UNSATISFIABLE;
305 } else {
306 // the filter passes the scalar test, just remove the condition
307 return FilterResult::SUCCESS;
308 }
309 }
310 assert(!expr->IsFoldable());
311 if (expr->GetExpressionClass() == ExpressionClass::BOUND_BETWEEN) {
312 auto &comparison = (BoundBetweenExpression &)*expr;
313 //! check if one of the sides is a scalar value
314 bool left_is_scalar = comparison.lower->IsFoldable();
315 bool right_is_scalar = comparison.upper->IsFoldable();
316 if (left_is_scalar || right_is_scalar) {
317 //! comparison with scalar
318 auto node = GetNode(comparison.input.get());
319 idx_t equivalence_set = GetEquivalenceSet(node);
320 auto scalar = comparison.lower.get();
321 auto constant_value = ExpressionExecutor::EvaluateScalar(*scalar);
322
323 // create the ExpressionValueInformation
324 ExpressionValueInformation info;
325 if (comparison.lower_inclusive) {
326 info.comparison_type = ExpressionType::COMPARE_GREATERTHANOREQUALTO;
327 } else {
328 info.comparison_type = ExpressionType::COMPARE_GREATERTHAN;
329 }
330 info.constant = constant_value;
331
332 // get the current bucket of constant values
333 assert(constant_values.find(equivalence_set) != constant_values.end());
334 auto &info_list = constant_values.find(equivalence_set)->second;
335 // check the existing constant comparisons to see if we can do any pruning
336 AddConstantComparison(info_list, info);
337 scalar = comparison.upper.get();
338 constant_value = ExpressionExecutor::EvaluateScalar(*scalar);
339
340 // create the ExpressionValueInformation
341 if (comparison.upper_inclusive) {
342 info.comparison_type = ExpressionType::COMPARE_LESSTHANOREQUALTO;
343 } else {
344 info.comparison_type = ExpressionType::COMPARE_LESSTHAN;
345 }
346 info.constant = constant_value;
347
348 // get the current bucket of constant values
349 assert(constant_values.find(equivalence_set) != constant_values.end());
350 // check the existing constant comparisons to see if we can do any pruning
351 return AddConstantComparison(constant_values.find(equivalence_set)->second, info);
352 }
353 } else if (expr->GetExpressionClass() == ExpressionClass::BOUND_COMPARISON) {
354 auto &comparison = (BoundComparisonExpression &)*expr;
355 if (comparison.type != ExpressionType::COMPARE_LESSTHAN &&
356 comparison.type != ExpressionType::COMPARE_LESSTHANOREQUALTO &&
357 comparison.type != ExpressionType::COMPARE_GREATERTHAN &&
358 comparison.type != ExpressionType::COMPARE_GREATERTHANOREQUALTO &&
359 comparison.type != ExpressionType::COMPARE_EQUAL && comparison.type != ExpressionType::COMPARE_NOTEQUAL) {
360 // only support [>, >=, <, <=, ==] expressions
361 return FilterResult::UNSUPPORTED;
362 }
363 // check if one of the sides is a scalar value
364 bool left_is_scalar = comparison.left->IsFoldable();
365 bool right_is_scalar = comparison.right->IsFoldable();
366 if (left_is_scalar || right_is_scalar) {
367 // comparison with scalar
368 auto node = GetNode(left_is_scalar ? comparison.right.get() : comparison.left.get());
369 idx_t equivalence_set = GetEquivalenceSet(node);
370 auto scalar = left_is_scalar ? comparison.left.get() : comparison.right.get();
371 auto constant_value = ExpressionExecutor::EvaluateScalar(*scalar);
372
373 // create the ExpressionValueInformation
374 ExpressionValueInformation info;
375 info.comparison_type = left_is_scalar ? FlipComparisionExpression(comparison.type) : comparison.type;
376 info.constant = constant_value;
377
378 // get the current bucket of constant values
379 assert(constant_values.find(equivalence_set) != constant_values.end());
380 auto &info_list = constant_values.find(equivalence_set)->second;
381 // check the existing constant comparisons to see if we can do any pruning
382 return AddConstantComparison(info_list, info);
383 } else {
384 // comparison between two non-scalars
385 // only handle comparisons for now
386 if (expr->type != ExpressionType::COMPARE_EQUAL) {
387 return FilterResult::UNSUPPORTED;
388 }
389 // get the LHS and RHS nodes
390 auto left_node = GetNode(comparison.left.get());
391 auto right_node = GetNode(comparison.right.get());
392 if (BaseExpression::Equals(left_node, right_node)) {
393 return FilterResult::UNSUPPORTED;
394 }
395 // get the equivalence sets of the LHS and RHS
396 auto left_equivalence_set = GetEquivalenceSet(left_node);
397 auto right_equivalence_set = GetEquivalenceSet(right_node);
398 if (left_equivalence_set == right_equivalence_set) {
399 // this equality filter already exists, prune it
400 return FilterResult::SUCCESS;
401 }
402 // add the right bucket into the left bucket
403 assert(equivalence_map.find(left_equivalence_set) != equivalence_map.end());
404 assert(equivalence_map.find(right_equivalence_set) != equivalence_map.end());
405
406 auto &left_bucket = equivalence_map.find(left_equivalence_set)->second;
407 auto &right_bucket = equivalence_map.find(right_equivalence_set)->second;
408 for (idx_t i = 0; i < right_bucket.size(); i++) {
409 // rewrite the equivalence set mapping for this node
410 equivalence_set_map[right_bucket[i]] = left_equivalence_set;
411 // add the node to the left bucket
412 left_bucket.push_back(right_bucket[i]);
413 }
414 // now add all constant values from the right bucket to the left bucket
415 assert(constant_values.find(left_equivalence_set) != constant_values.end());
416 assert(constant_values.find(right_equivalence_set) != constant_values.end());
417 auto &left_constant_bucket = constant_values.find(left_equivalence_set)->second;
418 auto &right_constant_bucket = constant_values.find(right_equivalence_set)->second;
419 for (idx_t i = 0; i < right_constant_bucket.size(); i++) {
420 if (AddConstantComparison(left_constant_bucket, right_constant_bucket[i]) ==
421 FilterResult::UNSATISFIABLE) {
422 return FilterResult::UNSATISFIABLE;
423 }
424 }
425 }
426 return FilterResult::SUCCESS;
427 }
428 // only comparisons supported for now
429 return FilterResult::UNSUPPORTED;
430}
431
432static bool IsGreaterThan(ExpressionType type) {
433 return type == ExpressionType::COMPARE_GREATERTHAN || type == ExpressionType::COMPARE_GREATERTHANOREQUALTO;
434}
435
436static bool IsLessThan(ExpressionType type) {
437 return type == ExpressionType::COMPARE_LESSTHAN || type == ExpressionType::COMPARE_LESSTHANOREQUALTO;
438}
439
440ValueComparisonResult InvertValueComparisonResult(ValueComparisonResult result) {
441 if (result == ValueComparisonResult::PRUNE_RIGHT) {
442 return ValueComparisonResult::PRUNE_LEFT;
443 }
444 if (result == ValueComparisonResult::PRUNE_LEFT) {
445 return ValueComparisonResult::PRUNE_RIGHT;
446 }
447 return result;
448}
449
450ValueComparisonResult CompareValueInformation(ExpressionValueInformation &left, ExpressionValueInformation &right) {
451 if (left.comparison_type == ExpressionType::COMPARE_EQUAL) {
452 // left is COMPARE_EQUAL, we can either
453 // (1) prune the right side or
454 // (2) return UNSATISFIABLE
455 bool prune_right_side = false;
456 switch (right.comparison_type) {
457 case ExpressionType::COMPARE_LESSTHAN:
458 prune_right_side = left.constant < right.constant;
459 break;
460 case ExpressionType::COMPARE_LESSTHANOREQUALTO:
461 prune_right_side = left.constant <= right.constant;
462 break;
463 case ExpressionType::COMPARE_GREATERTHAN:
464 prune_right_side = left.constant > right.constant;
465 break;
466 case ExpressionType::COMPARE_GREATERTHANOREQUALTO:
467 prune_right_side = left.constant >= right.constant;
468 break;
469 case ExpressionType::COMPARE_NOTEQUAL:
470 prune_right_side = left.constant != right.constant;
471 break;
472 default:
473 assert(right.comparison_type == ExpressionType::COMPARE_EQUAL);
474 prune_right_side = left.constant == right.constant;
475 break;
476 }
477 if (prune_right_side) {
478 return ValueComparisonResult::PRUNE_RIGHT;
479 } else {
480 return ValueComparisonResult::UNSATISFIABLE_CONDITION;
481 }
482 } else if (right.comparison_type == ExpressionType::COMPARE_EQUAL) {
483 // right is COMPARE_EQUAL
484 return InvertValueComparisonResult(CompareValueInformation(right, left));
485 } else if (left.comparison_type == ExpressionType::COMPARE_NOTEQUAL) {
486 // left is COMPARE_NOTEQUAL, we can either
487 // (1) prune the left side or
488 // (2) not prune anything
489 bool prune_left_side = false;
490 switch (right.comparison_type) {
491 case ExpressionType::COMPARE_LESSTHAN:
492 prune_left_side = left.constant >= right.constant;
493 break;
494 case ExpressionType::COMPARE_LESSTHANOREQUALTO:
495 prune_left_side = left.constant > right.constant;
496 break;
497 case ExpressionType::COMPARE_GREATERTHAN:
498 prune_left_side = left.constant <= right.constant;
499 break;
500 case ExpressionType::COMPARE_GREATERTHANOREQUALTO:
501 prune_left_side = left.constant < right.constant;
502 break;
503 default:
504 assert(right.comparison_type == ExpressionType::COMPARE_NOTEQUAL);
505 prune_left_side = left.constant == right.constant;
506 break;
507 }
508 if (prune_left_side) {
509 return ValueComparisonResult::PRUNE_LEFT;
510 } else {
511 return ValueComparisonResult::PRUNE_NOTHING;
512 }
513 } else if (right.comparison_type == ExpressionType::COMPARE_NOTEQUAL) {
514 return InvertValueComparisonResult(CompareValueInformation(right, left));
515 } else if (IsGreaterThan(left.comparison_type) && IsGreaterThan(right.comparison_type)) {
516 // both comparisons are [>], we can either
517 // (1) prune the left side or
518 // (2) prune the right side
519 if (left.constant > right.constant) {
520 // left constant is more selective, prune right
521 return ValueComparisonResult::PRUNE_RIGHT;
522 } else if (left.constant < right.constant) {
523 // right constant is more selective, prune left
524 return ValueComparisonResult::PRUNE_LEFT;
525 } else {
526 // constants are equivalent
527 // however we can still have the scenario where one is [>=] and the other is [>]
528 // we want to prune the [>=] because [>] is more selective
529 // if left is [>=] we prune the left, else we prune the right
530 if (left.comparison_type == ExpressionType::COMPARE_GREATERTHANOREQUALTO) {
531 return ValueComparisonResult::PRUNE_LEFT;
532 } else {
533 return ValueComparisonResult::PRUNE_RIGHT;
534 }
535 }
536 } else if (IsLessThan(left.comparison_type) && IsLessThan(right.comparison_type)) {
537 // both comparisons are [<], we can either
538 // (1) prune the left side or
539 // (2) prune the right side
540 if (left.constant < right.constant) {
541 // left constant is more selective, prune right
542 return ValueComparisonResult::PRUNE_RIGHT;
543 } else if (left.constant > right.constant) {
544 // right constant is more selective, prune left
545 return ValueComparisonResult::PRUNE_LEFT;
546 } else {
547 // constants are equivalent
548 // however we can still have the scenario where one is [<=] and the other is [<]
549 // we want to prune the [<=] because [<] is more selective
550 // if left is [<=] we prune the left, else we prune the right
551 if (left.comparison_type == ExpressionType::COMPARE_LESSTHANOREQUALTO) {
552 return ValueComparisonResult::PRUNE_LEFT;
553 } else {
554 return ValueComparisonResult::PRUNE_RIGHT;
555 }
556 }
557 } else if (IsLessThan(left.comparison_type)) {
558 assert(IsGreaterThan(right.comparison_type));
559 // left is [<] and right is [>], in this case we can either
560 // (1) prune nothing or
561 // (2) return UNSATISFIABLE
562 // the SMALLER THAN constant has to be greater than the BIGGER THAN constant
563 if (left.constant >= right.constant) {
564 return ValueComparisonResult::PRUNE_NOTHING;
565 } else {
566 return ValueComparisonResult::UNSATISFIABLE_CONDITION;
567 }
568 } else {
569 // left is [>] and right is [<] or [!=]
570 assert(IsLessThan(right.comparison_type) && IsGreaterThan(left.comparison_type));
571 return InvertValueComparisonResult(CompareValueInformation(right, left));
572 }
573}
574