1#include "duckdb/optimizer/index_scan.hpp"
2#include "duckdb/optimizer/matcher/expression_matcher.hpp"
3
4#include "duckdb/parser/expression/comparison_expression.hpp"
5
6#include "duckdb/planner/expression/bound_columnref_expression.hpp"
7#include "duckdb/planner/expression/bound_comparison_expression.hpp"
8#include "duckdb/planner/expression/bound_constant_expression.hpp"
9#include "duckdb/planner/expression_iterator.hpp"
10#include "duckdb/planner/operator/logical_filter.hpp"
11#include "duckdb/planner/operator/logical_get.hpp"
12#include "duckdb/planner/operator/logical_index_scan.hpp"
13
14#include "duckdb/storage/data_table.hpp"
15using namespace duckdb;
16using namespace std;
17
18unique_ptr<LogicalOperator> IndexScan::Optimize(unique_ptr<LogicalOperator> op) {
19 if (op->type == LogicalOperatorType::FILTER && op->children[0]->type == LogicalOperatorType::GET) {
20 return TransformFilterToIndexScan(move(op));
21 }
22 for (auto &child : op->children) {
23 child = Optimize(move(child));
24 }
25 return op;
26}
27
28static void RewriteIndexExpression(Index &index, LogicalGet &get, Expression &expr, bool &rewrite_possible) {
29 if (expr.type == ExpressionType::BOUND_COLUMN_REF) {
30 auto &bound_colref = (BoundColumnRefExpression &)expr;
31 // bound column ref: rewrite to fit in the current set of bound column ids
32 bound_colref.binding.table_index = get.table_index;
33 column_t referenced_column = index.column_ids[bound_colref.binding.column_index];
34 // search for the referenced column in the set of column_ids
35 for (idx_t i = 0; i < get.column_ids.size(); i++) {
36 if (get.column_ids[i] == referenced_column) {
37 bound_colref.binding.column_index = i;
38 return;
39 }
40 }
41 // column id not found in bound columns in the LogicalGet: rewrite not possible
42 rewrite_possible = false;
43 }
44 ExpressionIterator::EnumerateChildren(
45 expr, [&](Expression &child) { RewriteIndexExpression(index, get, child, rewrite_possible); });
46}
47
48unique_ptr<LogicalOperator> IndexScan::TransformFilterToIndexScan(unique_ptr<LogicalOperator> op) {
49 assert(op->type == LogicalOperatorType::FILTER);
50 auto &filter = (LogicalFilter &)*op;
51 auto get = (LogicalGet *)op->children[0].get();
52
53 if (!get->table) {
54 return op;
55 }
56
57 auto &storage = *get->table->storage;
58
59 if (storage.info->indexes.size() == 0) {
60 // no indexes on the table, can't rewrite
61 return op;
62 }
63
64 // check all the indexes
65 for (size_t j = 0; j < storage.info->indexes.size(); j++) {
66 auto &index = storage.info->indexes[j];
67
68 // assert(index->unbound_expressions.size() == 1);
69 // first rewrite the index expression so the ColumnBindings align with the column bindings of the current table
70 if (index->unbound_expressions.size() > 1)
71 continue;
72 auto index_expression = index->unbound_expressions[0]->Copy();
73 bool rewrite_possible = true;
74 RewriteIndexExpression(*index, *get, *index_expression, rewrite_possible);
75 if (!rewrite_possible) {
76 // could not rewrite!
77 continue;
78 }
79
80 Value low_value, high_value, equal_value;
81 // try to find a matching index for any of the filter expressions
82 auto expr = filter.expressions[0].get();
83 auto low_comparison_type = expr->type;
84 auto high_comparison_type = expr->type;
85 for (idx_t i = 0; i < filter.expressions.size(); i++) {
86 expr = filter.expressions[i].get();
87 // create a matcher for a comparison with a constant
88 ComparisonExpressionMatcher matcher;
89 // match on a comparison type
90 matcher.expr_type = make_unique<ComparisonExpressionTypeMatcher>();
91 // match on a constant comparison with the indexed expression
92 matcher.matchers.push_back(make_unique<ExpressionEqualityMatcher>(index_expression.get()));
93 matcher.matchers.push_back(make_unique<ConstantExpressionMatcher>());
94
95 matcher.policy = SetMatcher::Policy::UNORDERED;
96
97 vector<Expression *> bindings;
98 if (matcher.Match(expr, bindings)) {
99 // range or equality comparison with constant value
100 // we can use our index here
101 // bindings[0] = the expression
102 // bindings[1] = the index expression
103 // bindings[2] = the constant
104 auto comparison = (BoundComparisonExpression *)bindings[0];
105 assert(bindings[0]->GetExpressionClass() == ExpressionClass::BOUND_COMPARISON);
106 assert(bindings[2]->type == ExpressionType::VALUE_CONSTANT);
107
108 auto constant_value = ((BoundConstantExpression *)bindings[2])->value;
109 auto comparison_type = comparison->type;
110 if (comparison->left->type == ExpressionType::VALUE_CONSTANT) {
111 // the expression is on the right side, we flip them around
112 comparison_type = FlipComparisionExpression(comparison_type);
113 }
114 if (comparison_type == ExpressionType::COMPARE_EQUAL) {
115 // equality value
116 // equality overrides any other bounds so we just break here
117 equal_value = constant_value;
118 break;
119 } else if (comparison_type == ExpressionType::COMPARE_GREATERTHANOREQUALTO ||
120 comparison_type == ExpressionType::COMPARE_GREATERTHAN) {
121 // greater than means this is a lower bound
122 low_value = constant_value;
123 low_comparison_type = comparison_type;
124 } else {
125 // smaller than means this is an upper bound
126 high_value = constant_value;
127 high_comparison_type = comparison_type;
128 }
129 }
130 }
131 if (!equal_value.is_null || !low_value.is_null || !high_value.is_null) {
132 auto logical_index_scan = make_unique<LogicalIndexScan>(*get->table, *get->table->storage, *index,
133 get->column_ids, get->table_index);
134 if (!equal_value.is_null) {
135 logical_index_scan->equal_value = equal_value;
136 logical_index_scan->equal_index = true;
137 }
138 if (!low_value.is_null) {
139 logical_index_scan->low_value = low_value;
140 logical_index_scan->low_index = true;
141 logical_index_scan->low_expression_type = low_comparison_type;
142 }
143 if (!high_value.is_null) {
144 logical_index_scan->high_value = high_value;
145 logical_index_scan->high_index = true;
146 logical_index_scan->high_expression_type = high_comparison_type;
147 }
148 op->children[0] = move(logical_index_scan);
149 break;
150 }
151 }
152 return op;
153}
154