10000 Refactor Optimizer ordering · arangodb/arangodb@d86953c · GitHub
[go: up one dir, main page]
Skip to content

Commit d86953c

Browse files
dothebartdothebart
committed
Refactor Optimizer ordering
 - create enum with the different steps named - unify numbering scheme - deploy enum to all places where int level was used - add passN enum so you can jump to a Pass when calling addPlan useIndexForSort: - remove inline deletion of dependend nodes of our (removed) sortnode - redirect to pass #5 so now possible obsolete CalculaionNodes are removed by the removeUnnecessaryCalculationsRule
1 parent 80f6887 commit d86953c

File tree

3 files changed

+152
-32
lines changed

3 files changed

+152
-32
lines changed

‎arangod/Aql/Optimizer.cpp

Lines changed: 39 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -61,7 +61,7 @@ Optimizer::Optimizer () {
6161
////////////////////////////////////////////////////////////////////////////////
6262

6363
bool Optimizer::addPlan (ExecutionPlan* plan,
64-
int level,
64+
RuleLevel level,
6565
bool wasModified) {
6666
TRI_ASSERT(plan != nullptr);
6767

@@ -303,11 +303,15 @@ void Optimizer::setupRules () {
303303

304304
// move calculations up the dependency chain (to pull them out of
305305
// inner loops etc.)
306-
registerRule("move-calculations-up", moveCalculationsUpRule, 10);
306+
registerRule("move-calculations-up",
307+
moveCalculationsUpRule,
308+
moveCalculationsUpRule_pass1);
307309

308310
// move filters up the dependency chain (to make result sets as small
309311
// as possible as early as possible)
310-
registerRule("move-filters-up", moveFiltersUpRule, 20);
312+
registerRule("move-filters-up",
313+
moveFiltersUpRule,
314+
moveFiltersUpRule_pass1);
311315

312316
//////////////////////////////////////////////////////////////////////////////
313317
/// "Pass 2": try to remove redundant or unnecessary nodes
@@ -317,14 +321,19 @@ void Optimizer::setupRules () {
317321
// remove filters from the query that are not necessary at all
318322
// filters that are always true will be removed entirely
319323
// filters that are always false will be replaced with a NoResults node
320-
registerRule("remove-unnecessary-filters", removeUnnecessaryFiltersRule, 110);
324+
registerRule("remove-unnecessary-filters",
325+
removeUnnecessaryFiltersRule,
326+
removeUnnecessaryFiltersRule_pass2);
321327

322328
// remove calculations that are never necessary
323329
registerRule("remove-unnecessary-calculations",
324-
removeUnnecessaryCalculationsRule, 120);
330+
removeUnnecessaryCalculationsRule,
331+
removeUnnecessaryCalculationsRule_pass2);
325332

326333
// remove redundant sort blocks
327-
registerRule("remove-redundant-sorts", removeRedundantSorts, 130);
334+
registerRule("remove-redundant-sorts",
335+
removeRedundantSorts,
336+
removeRedundantSorts_pass2);
328337

329338
//////////////////////////////////////////////////////////////////////////////
330339
/// "Pass 3": interchange EnumerateCollection nodes in all possible ways
@@ -333,7 +342,8 @@ void Optimizer::setupRules () {
333342
//////////////////////////////////////////////////////////////////////////////
334343

335344
registerRule("interchange-adjacent-enumerations",
336-
interchangeAdjacentEnumerations, 500);
345+
interchangeAdjacentEnumerations,
346+
interchangeAdjacentEnumerations_pass3);
337347

338348
//////////////////////////////////////////////////////////////////////////////
339349
// "Pass 4": moving nodes "up" (potentially outside loops) (second try):
@@ -342,11 +352,15 @@ void Optimizer::setupRules () {
342352

343353
// move calculations up the dependency chain (to pull them out of
344354
// inner loops etc.)
345-
registerRule("move-calculations-up-2", moveCalculationsUpRule, 510);
355+
registerRule("move-calculations-up-2",
356+
moveCalculationsUpRule,
357+
moveCalculationsUpRule_pass4);
346358

347359
// move filters up the dependency chain (to make result sets as small
348360
// as possible as early as possible)
349-
registerRule("move-filters-up-2", moveFiltersUpRule, 520);
361+
registerRule("move-filters-up-2",
362+
moveFiltersUpRule,
363+
moveFiltersUpRule_pass4);
350364

351365
//////////////////////////////////////////////////////////////////////////////
352366
/// "Pass 5": try to remove redundant or unnecessary nodes (second try)
@@ -356,26 +370,36 @@ void Optimizer::setupRules () {
356370
// remove filters from the query that are not necessary at all
357371
// filters that are always true will be removed entirely
358372
// filters that are always false will be replaced with a NoResults node
359-
registerRule("remove-unnecessary-filters-2", removeUnnecessaryFiltersRule, 610);
373+
registerRule("remove-unnecessary-filters-2",
374+
removeUnnecessaryFiltersRule,
375+
removeUnnecessaryFiltersRule_pass5);
360376

361377
// remove calculations that are never necessary
362378
registerRule("remove-unnecessary-calculations-2",
363-
removeUnnecessaryCalculationsRule, 620);
379+
removeUnnecessaryCalculationsRule,
380+
removeUnnecessaryCalculationsRule_pass5);
364381

365382
// remove redundant sort blocks
366-
registerRule("remove-redundant-sorts-2", removeRedundantSorts, 630);
383+
registerRule("remove-redundant-sorts-2",
384+
removeRedundantSorts,
385+
removeRedundantSorts_pass5);
367386

368387
//////////////////////////////////////////////////////////////////////////////
369388
/// "Pass 6": use indexes if possible for FILTER and/or SORT nodes
370389
/// use levels between 701 and 799 for this
371390
//////////////////////////////////////////////////////////////////////////////
372391

373392
// try to find a filter after an enumerate collection and find an index . . .
374-
registerRule("use-index-range", useIndexRange, 710);
393+
registerRule("use-index-range",
394+
useIndexRange,
395+
useIndexRange_pass6);
375396

376397
// try to find sort blocks which are superseeded by indexes
377-
registerRule("use-index-for-sort", useIndexForSort, 720);
378-
398+
registerRule("use-index-for-sort",
399+
useIndexForSort,
400+
useIndexForSort_pass6);
401+
402+
379403
//////////////////////////////////////////////////////////////////////////////
380404
/// END OF OPTIMISATIONS
381405
//////////////////////////////////////////////////////////////////////////////

‎arangod/Aql/Optimizer.h

Lines changed: 102 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -40,6 +40,95 @@ namespace triagens {
4040
// -----------------------------------------------------------------------------
4141

4242
class Optimizer {
43+
44+
public:
45+
46+
enum RuleLevel:int {
47+
// List all the rules in the system here:
48+
// lower level values mean earlier rule execution
49+
50+
// note that levels must be unique
51+
52+
//////////////////////////////////////////////////////////////////////////////
53+
// "Pass 1": moving nodes "up" (potentially outside loops):
54+
// please use levels between 1 and 99 here
55+
//////////////////////////////////////////////////////////////////////////////
56+
57+
// move calculations up the dependency chain (to pull them out of
58+
// inner loops etc.)
59+
pass1 = 100,
60+
moveCalculationsUpRule_pass1 = 110,
61+
62+
// move filters up the dependency chain (to make result sets as small
63+
// as possible as early as possible)
64+
moveFiltersUpRule_pass1 = 120,
65+
66+
//////////////////////////////////////////////////////////////////////////////
67+
/// "Pass 2": try to remove redundant or unnecessary nodes
68+
/// use levels between 101 and 199 for this
69+
//////////////////////////////////////////////////////////////////////////////
70+
pass2 = 200,
71+
// remove filters from the query that are not necessary at all
72+
// filters that are always true will be removed entirely
73+
// filters that are always false will be replaced with a NoResults node
74+
removeUnnecessaryFiltersRule_pass2 = 210,
75+
76+
// remove calculations that are never necessary
77+
removeUnnecessaryCalculationsRule_pass2 = 220,
78+
79+
// remove redundant sort blocks
80+
removeRedundantSorts_pass2 = 230,
81+
82+
//////////////////////////////////////////////////////////////////////////////
83+
/// "Pass 3": interchange EnumerateCollection nodes in all possible ways
84+
/// this is level 500, please never let new plans from higher
85+
/// levels go back to this or lower levels!
86+
//////////////////////////////////////////////////////////////////////////////
87+
pass3 = 500,
88+
interchangeAdjacentEnumerations_pass3 = 510,
89+
90+
//////////////////////////////////////////////////////////////////////////////
91+
// "Pass 4": moving nodes "up" (potentially outside loops) (second try):
92+
// please use levels between 501 and 599 here
93+
//////////////////////////////////////////////////////////////////////////////
94+
pass4 = 600,
95+
// move calculations up the dependency chain (to pull them out of
96+
// inner loops etc.)
97+
moveCalculationsUpRule_pass4 = 610,
98+
99+
// move filters up the dependency chain (to make result sets as small
100+
// as possible as early as possible)
101+
moveFiltersUpRule_pass4 = 620,
102+
103+
//////////////////////////////////////////////////////////////////////////////
104+
/// "Pass 5": try to remove redundant or unnecessary nodes (second try)
105+
/// use levels between 601 and 699 for this
106+
//////////////////////////////////////////////////////////////////////////////
107+
108+
// remove filters from the query that are not necessary at all
109+
// filters that are always true will be removed entirely
110+
// filters that are always false will be replaced with a NoResults node
111+
pass5 = 700,
112+
removeUnnecessaryFiltersRule_pass5 = 710,
113+
114+
// remove calculations that are never necessary
115+
removeUnnecessaryCalculationsRule_pass5 = 720,
116+
117+
// remove redundant sort blocks
118+
removeRedundantSorts_pass5 = 730,
119+
120+
//////////////////////////////////////////////////////////////////////////////
121+
/// "Pass 6": use indexes if possible for FILTER and/or SORT nodes
122+
/// use levels between 701 and 799 for this
123+
//////////////////////////////////////////////////////////////////////////////
124+
pass6 = 800,
125+
// try to find a filter after an enumerate collection and find an index . . .
126+
useIndexRange_pass6 = 810,
127+
128+
// try to find sort blocks which are superseeded by indexes
129+
useIndexForSort_pass6 = 820
130+
131+
};
43132

44133
public:
45134

@@ -64,11 +153,11 @@ namespace triagens {
64153
struct Rule {
65154
std::string name;
66155
RuleFunction func;
67-
int level;
156+
RuleLevel level;
68157

69158
Rule () = delete;
70159

71-
Rule (std::string const& name, RuleFunction func, int level)
160+
Rule (std::string const& name, RuleFunction func, RuleLevel level)
72161
: name(name),
73162
func(func),
74163
level(level) {
@@ -108,6 +197,15 @@ namespace triagens {
108197
}
109198
}
110199

200+
201+
////////////////////////////////////////////////////////////////////////////////
202+
/// @brief get a plan index pointing before the referenced rule, so it can be
203+
/// re-executed
204+
////////////////////////////////////////////////////////////////////////////////
205+
static RuleLevel beforeRule(RuleLevel l) {
206+
return (RuleLevel) (l - 1);
207+
}
208+
111209
////////////////////////////////////////////////////////////////////////////////
112210
/// @brief get number of plans contained
113211
////////////////////////////////////////////////////////////////////////////////
@@ -239,7 +337,7 @@ namespace triagens {
239337
////////////////////////////////////////////////////////////////////////////////
240338

241339
bool addPlan (ExecutionPlan*,
242-
int,
340+
RuleLevel,
243341
bool);
244342

245343
////////////////////////////////////////////////////////////////////////////////
@@ -328,7 +426,7 @@ namespace triagens {
328426

329427
static void registerRule (std::string const& name,
330428
RuleFunction func,
331-
int level) {
429+
RuleLevel level) {
332430
if (_ruleLookup.find(name) != _ruleLookup.end()) {
333431
// duplicate rule names are not allowed
334432
THROW_ARANGO_EXCEPTION_MESSAGE(TRI_ERROR_INTERNAL, "duplicate optimizer rule name");

‎arangod/Aql/OptimizerRules.cpp

Lines changed: 11 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -450,11 +450,14 @@ class FilterToEnumCollFinder : public WalkerWorker<ExecutionNode> {
450450
ExecutionPlan* _plan;
451451
std::unordered_set<VariableId> _varIds;
452452
bool _canThrow;
453-
int _level;
453+
Optimizer::RuleLevel _level;
454454

455455
public:
456456

457-
FilterToEnumCollFinder (Optimizer* opt, ExecutionPlan* plan, Variable const* var, int level)
457+
FilterToEnumCollFinder (Optimizer* opt,
458+
ExecutionPlan* plan,
459+
Variable const* var,
460+
Optimizer::RuleLevel level)
458461
: _opt(opt),
459462
_plan(plan),
460463
_canThrow(false),
@@ -864,12 +867,6 @@ class sortAnalysis {
864867
/// @brief removes the sortNode and its referenced Calculationnodes from the plan.
865868
////////////////////////////////////////////////////////////////////////////////
866869
void removeSortNodeFromPlan (ExecutionPlan *newPlan) {
867-
for (auto idToRemove = _sortNodeData.begin();
868-
idToRemove != _sortNodeData.end();
869-
++idToRemove) {
870-
newPlan->unlinkNode(newPlan->getNodeById((*idToRemove)->calculationNodeID));
871-
}
872-
873870
newPlan->unlinkNode(newPlan->getNodeById(sortNodeID));
874871
}
875872
};
@@ -880,7 +877,7 @@ class sortToIndexNode : public WalkerWorker<ExecutionNode> {
880877
Optimizer* _opt;
881878
ExecutionPlan* _plan;
882879
sortAnalysis* _sortNode;
883-
int _level;
880+
Optimizer::RuleLevel _level;
884881

885882
public:
886883
bool planModified;
@@ -889,7 +886,7 @@ class sortToIndexNode : public WalkerWorker<ExecutionNode> {
889886
sortToIndexNode (Optimizer* opt,
890887
ExecutionPlan* plan,
891888
sortAnalysis* Node,
892-
int level)
889+
Optimizer::RuleLevel level)
893890
: _opt(opt),
894891
_plan(plan),
895892
_sortNode(Node),
@@ -916,7 +913,7 @@ class sortToIndexNode : public WalkerWorker<ExecutionNode> {
916913
/// @brief check whether we can sort via an index.
917914
////////////////////////////////////////////////////////////////////////////////
918915

919-
bool handleEnumerateCollectionNode (EnumerateCollectionNode* node, int level) {
916+
bool handleEnumerateCollectionNode (EnumerateCollectionNode* node, Optimizer::RuleLevel level) {
920917
auto variableName = node->getVariablesSetHere()[0]->name;
921918
auto result = _sortNode->getAttrsForVariableName(variableName);
922919

@@ -1017,8 +1014,9 @@ int triagens::aql::useIndexForSort (Optimizer* opt,
10171014
}
10181015
}
10191016
}
1020-
1021-
opt->addPlan(plan, rule->level, planModified);
1017+
opt->addPlan(plan,
1018+
planModified ? Optimizer::RuleLevel::pass5 : rule->level,
1019+
planModified);
10221020

10231021
return TRI_ERROR_NO_ERROR;
10241022
}

0 commit comments

Comments
 (0)
0