Debian Codegraph @

valkey/commands/graph/execution_plan.py

raw
1 import re
2
3
4 class ProfileStats:
5 """
6 ProfileStats, runtime execution statistics of operation.
7 """
8
9 def __init__(self, records_produced, execution_time):
10 self.records_produced = records_produced
11 self.execution_time = execution_time
12
13
14 class Operation:
15 """
16 Operation, single operation within execution plan.
17 """
18
19 def __init__(self, name, args=None, profile_stats=None):
20 """
21 Create a new operation.
22
23 Args:
24 name: string that represents the name of the operation
25 args: operation arguments
26 profile_stats: profile statistics
27 """
28 self.name = name
29 self.args = args
30 self.profile_stats = profile_stats
31 self.children = []
32
33 def append_child(self, child):
34 if not isinstance(child, Operation) or self is child:
35 raise Exception("child must be Operation")
36
37 self.children.append(child)
38 return self
39
40 def child_count(self):
41 return len(self.children)
42
43 def __eq__(self, o: object) -> bool:
44 if not isinstance(o, Operation):
45 return False
46
47 return self.name == o.name and self.args == o.args
48
49 def __str__(self) -> str:
50 args_str = "" if self.args is None else " | " + self.args
51 return f"{self.name}{args_str}"
52
53
54 class ExecutionPlan:
55 """
56 ExecutionPlan, collection of operations.
57 """
58
59 def __init__(self, plan):
60 """
61 Create a new execution plan.
62
63 Args:
64 plan: array of strings that represents the collection operations
65 the output from GRAPH.EXPLAIN
66 """
67 if not isinstance(plan, list):
68 raise Exception("plan must be an array")
69
70 if isinstance(plan[0], bytes):
71 plan = [b.decode() for b in plan]
72
73 self.plan = plan
74 self.structured_plan = self._operation_tree()
75
76 def _compare_operations(self, root_a, root_b):
77 """
78 Compare execution plan operation tree
79
80 Return: True if operation trees are equal, False otherwise
81 """
82
83 # compare current root
84 if root_a != root_b:
85 return False
86
87 # make sure root have the same number of children
88 if root_a.child_count() != root_b.child_count():
89 return False
90
91 # recursively compare children
92 for i in range(root_a.child_count()):
93 if not self._compare_operations(root_a.children[i], root_b.children[i]):
94 return False
95
96 return True
97
98 def __str__(self) -> str:
99 def aggregate_str(str_children):
100 return "\n".join(
101 [
102 " " + line
103 for str_child in str_children
104 for line in str_child.splitlines()
105 ]
106 )
107
108 def combine_str(x, y):
109 return f"{x}\n{y}"
110
111 return self._operation_traverse(
112 self.structured_plan, str, aggregate_str, combine_str
113 )
114
115 def __eq__(self, o: object) -> bool:
116 """Compares two execution plans
117
118 Return: True if the two plans are equal False otherwise
119 """
120 # make sure 'o' is an execution-plan
121 if not isinstance(o, ExecutionPlan):
122 return False
123
124 # get root for both plans
125 root_a = self.structured_plan
126 root_b = o.structured_plan
127
128 # compare execution trees
129 return self._compare_operations(root_a, root_b)
130
131 def _operation_traverse(self, op, op_f, aggregate_f, combine_f):
132 """
133 Traverse operation tree recursively applying functions
134
135 Args:
136 op: operation to traverse
137 op_f: function applied for each operation
138 aggregate_f: aggregation function applied for all children of a single operation
139 combine_f: combine function applied for the operation result and the children result
140 """ # noqa
141 # apply op_f for each operation
142 op_res = op_f(op)
143 if len(op.children) == 0:
144 return op_res # no children return
145 else:
146 # apply _operation_traverse recursively
147 children = [
148 self._operation_traverse(child, op_f, aggregate_f, combine_f)
149 for child in op.children
150 ]
151 # combine the operation result with the children aggregated result
152 return combine_f(op_res, aggregate_f(children))
153
154 def _operation_tree(self):
155 """Build the operation tree from the string representation"""
156
157 # initial state
158 i = 0
159 level = 0
160 stack = []
161 current = None
162
163 def _create_operation(args):
164 profile_stats = None
165 name = args[0].strip()
166 args.pop(0)
167 if len(args) > 0 and "Records produced" in args[-1]:
168 records_produced = int(
169 re.search("Records produced: (\\d+)", args[-1]).group(1)
170 )
171 execution_time = float(
172 re.search("Execution time: (\\d+.\\d+) ms", args[-1]).group(1)
173 )
174 profile_stats = ProfileStats(records_produced, execution_time)
175 args.pop(-1)
176 return Operation(
177 name, None if len(args) == 0 else args[0].strip(), profile_stats
178 )
179
180 # iterate plan operations
181 while i < len(self.plan):
182 current_op = self.plan[i]
183 op_level = current_op.count(" ")
184 if op_level == level:
185 # if the operation level equal to the current level
186 # set the current operation and move next
187 child = _create_operation(current_op.split("|"))
188 if current:
189 current = stack.pop()
190 current.append_child(child)
191 current = child
192 i += 1
193 elif op_level == level + 1:
194 # if the operation is child of the current operation
195 # add it as child and set as current operation
196 child = _create_operation(current_op.split("|"))
197 current.append_child(child)
198 stack.append(current)
199 current = child
200 level += 1
201 i += 1
202 elif op_level < level:
203 # if the operation is not child of current operation
204 # go back to its parent operation
205 levels_back = level - op_level + 1
206 for _ in range(levels_back):
207 current = stack.pop()
208 level -= levels_back
209 else:
210 raise Exception("corrupted plan")
211 return stack[0]