| 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] |