Line data Source code
1 : //! The plan layout.
2 : //!
3 : //! This layouting algorithm is based on two papers:
4 : //! - A Node-Positioning Algorithm for General Trees:
5 : //! 1990 by Walker
6 : //! https://www.cs.unc.edu/techreports/89-034.pdf
7 : //! This is the original tree layouting algorithm that many are using
8 : //! - Improving Walker's Algorithm to Run in Linear Time
9 : //! 2002 by Buchheim-Juenger-Leipert
10 : //! https://www.researchgate.net/publication/30508504_Improving_Walker%27s_Algorithm_to_Run_in_Linear_Time
11 : //! This is an updated version that fixes quadratic runtime in the original paper.
12 : //!
13 : //! A plan grows top-down or left-to-right (`ProfileLayoutOrientation`). Walker places the siblings along one axis and
14 : //! the levels along the other one, a left-to-right plan swaps the axes after the walks. Its levels become columns that
15 : //! are as wide as their widest node with left-aligned nodes, and a node shares its row with its first child instead of being centered above
16 : //! its children. Nothing is placed above the root then, the plan grows to the right and downwards.
17 : //!
18 : //! The floating point operations keep their order, since reordering them changes the last bits of positions.
19 : //! Minimum and maximum keep the first argument unless the second one is strictly smaller or larger, which differs
20 : //! from `f64::min` and `f64::max` for NaN and signed zeros, see `cpp_min` and `cpp_max`.
21 :
22 : use super::query_profile::{OperatorNode, QueryProfile};
23 : use dashql_buffers::profile as fb;
24 :
25 : /// The minimum, `a` unless `b` is smaller
26 1599 : fn cpp_min(a: f64, b: f64) -> f64 {
27 1599 : if b < a {
28 665 : b
29 : } else {
30 934 : a
31 : }
32 1599 : }
33 :
34 : /// The maximum, `a` unless `b` is larger
35 3247 : fn cpp_max(a: f64, b: f64) -> f64 {
36 3247 : if a < b {
37 638 : b
38 : } else {
39 2609 : a
40 : }
41 3247 : }
42 :
43 : /// Compute the rendered width of an operator node
44 1066 : fn compute_node_width(op: &OperatorNode, layout_config: &fb::ProfileLayoutConfig) -> f64 {
45 1066 : let content_width = if shows_symbol(op) && layout_config.symbol_width() > 0.0 {
46 2 : layout_config.symbol_width()
47 : } else {
48 1064 : let label = op.operator_label.as_deref().or(op.operator_type.as_deref()).unwrap_or("");
49 1064 : let label_chars = label.chars().count().min(layout_config.max_label_chars() as usize);
50 1064 : label_chars as f64 * layout_config.width_per_label_char()
51 : };
52 1066 : cpp_max(
53 1066 : layout_config.node_padding_left()
54 1066 : + layout_config.icon_width()
55 1066 : + layout_config.icon_margin_right()
56 1066 : + content_width
57 1066 : + layout_config.node_padding_right(),
58 1066 : layout_config.node_min_width(),
59 : )
60 1066 : }
61 :
62 : /// Does an operator show the symbol of its kind instead of its type name?
63 : /// An operator with a label of its own (a table, a CTE) shows the label, and the kind `OTHER` has no symbol.
64 1066 : fn shows_symbol(op: &OperatorNode) -> bool {
65 1066 : op.operator_type.is_some()
66 1066 : && (op.operator_label.is_none() || op.operator_label == op.operator_type)
67 766 : && op.kind != fb::ProfileOperatorKind::OTHER
68 1066 : }
69 :
70 : /// A node for the layouter
71 : #[derive(Clone, Debug, Default)]
72 : struct ProfileLayoutNode {
73 : /// The parent (if any)
74 : parent: Option<usize>,
75 : /// The children
76 : children_begin: usize,
77 : /// The number of children
78 : children_count: usize,
79 : /// The rendered node width
80 : width: f64,
81 : /// The node index among its siblings
82 : sibling_index: usize,
83 :
84 : /// Walker - The current node's preliminary x-coordinate
85 : prelim: f64,
86 : /// Walker - The current node's modifier value.
87 : ///
88 : /// We track shifting only at subtree roots instead of eagerly updating the x-coordinates within the tree.
89 : /// `mod` is a value that is to be added to all preliminary x-coordinates in the subtree rooted at v, except for v
90 : /// itself.
91 : ///
92 : /// The actual x-coordinate of a node is the own preliminary position `prelim` plus all `mod` values on the path to
93 : /// the root, also called `modsum` in the paper. We traverse top-down in a dedicated pass at the end to compute the
94 : /// final position in O(n).
95 : ///
96 : /// For leafs v with a thread to w, `mod` stores `modsum(v) - modsum(w)`.
97 : modifier: f64,
98 : /// Walker - The current node's x-coordinate
99 : x: f64,
100 : /// Walker - The current node's y-coordinate
101 : y: f64,
102 : /// The depth of the node below its root
103 : level: usize,
104 : /// Buchheim - The current node's shifting.
105 : /// Buchheim memoizes the node shifting to shift non-current subtrees in a single pass.
106 : /// This is needed to make the central positioning of parents above the children non-quadratic.
107 : shift: f64,
108 : /// Buchheim - The current node's change.
109 : change: f64,
110 : /// A corrective subtree shift applied by the final level sweep.
111 : layout_shift: f64,
112 : /// Buchheim - Save a node's ancestor.
113 : ancestor: usize,
114 : /// Reingold - The node's thread
115 : thread: Option<usize>,
116 : }
117 :
118 : impl ProfileLayoutNode {
119 : /// Is a leaf?
120 2773 : fn is_leaf(&self) -> bool {
121 2773 : self.children_count == 0
122 2773 : }
123 : /// Walker - The current node's leftmost offspring. Must not be a leaf.
124 923 : fn left_most_child(&self) -> usize {
125 923 : debug_assert!(!self.is_leaf());
126 923 : self.children_begin
127 923 : }
128 : /// Walker - The current node's rightmost offspring. Must not be a leaf.
129 459 : fn right_most_child(&self) -> usize {
130 459 : debug_assert!(!self.is_leaf());
131 459 : self.children_begin + self.children_count - 1
132 459 : }
133 : /// Traverse the right contour.
134 : /// If we're an inner node, we traverse to the right-most child.
135 : /// If we're a leaf, we traverse to our thread.
136 429 : fn next_along_right_contour(&self) -> Option<usize> {
137 429 : if !self.is_leaf() {
138 162 : Some(self.right_most_child())
139 : } else {
140 267 : self.thread
141 : }
142 429 : }
143 : /// Traverse the left contour.
144 : /// If we're an inner node, we traverse to the left-most child.
145 : /// If we're a leaf, we traverse to our thread.
146 429 : fn next_along_left_contour(&self) -> Option<usize> {
147 429 : if !self.is_leaf() {
148 136 : Some(self.left_most_child())
149 : } else {
150 293 : self.thread
151 : }
152 429 : }
153 : /// The children
154 2793 : fn children(&self) -> std::ops::Range<usize> {
155 2793 : self.children_begin..self.children_begin + self.children_count
156 2793 : }
157 : }
158 :
159 : /// The tree layouter that positions the operators of a plan
160 : struct ProfileLayouter<'a> {
161 : /// The plan layout nodes
162 : nodes: Vec<ProfileLayoutNode>,
163 : /// The root operators
164 : root_operators: &'a [u32],
165 : /// The plan layout config
166 : layout_config: fb::ProfileLayoutConfig,
167 : }
168 :
169 : impl<'a> ProfileLayouter<'a> {
170 73 : fn new(view_model: &'a QueryProfile, layout_config: &fb::DerivedProfileLayoutConfig) -> Self {
171 73 : let input = *layout_config.input();
172 73 : let mut nodes = vec![ProfileLayoutNode::default(); view_model.operators.len()];
173 533 : for (i, op) in view_model.operators.iter().enumerate() {
174 533 : nodes[i].parent = op.parent;
175 533 : nodes[i].children_begin = op.children_begin;
176 533 : nodes[i].children_count = op.children_count;
177 533 : nodes[i].width = compute_node_width(op, &input);
178 533 : nodes[i].ancestor = i;
179 533 : for child_index in 0..op.children_count {
180 458 : nodes[op.children_begin + child_index].sibling_index = child_index;
181 458 : }
182 : }
183 73 : Self { nodes, root_operators: &view_model.root_operators, layout_config: input }
184 73 : }
185 :
186 : /// Does the plan grow from left to right?
187 : /// Walker then places siblings along the y-axis, and the levels become columns along the x-axis.
188 2526 : fn is_left_to_right(&self) -> bool {
189 2526 : self.layout_config.orientation() == fb::ProfileLayoutOrientation::LEFT_TO_RIGHT
190 2526 : }
191 :
192 : /// The extent of a node along the axis of its siblings
193 1899 : fn breadth(&self, node: usize) -> f64 {
194 1899 : if self.is_left_to_right() {
195 175 : self.layout_config.node_height()
196 : } else {
197 1724 : self.nodes[node].width
198 : }
199 1899 : }
200 :
201 : /// The margin between siblings
202 298 : fn sibling_margin(&self) -> f64 {
203 298 : if self.is_left_to_right() {
204 25 : self.layout_config.node_margin_vertical()
205 : } else {
206 273 : self.layout_config.node_margin_horizontal()
207 : }
208 298 : }
209 :
210 : /// Compute the required center-to-center distance between two nodes
211 150 : fn separation(&self, left: usize, right: usize) -> f64 {
212 150 : self.breadth(left) / 2.0 + self.sibling_margin() + self.breadth(right) / 2.0
213 150 : }
214 :
215 : /// Perform the first walk over the tree
216 533 : fn first_walk(&mut self, node: usize, left_sibling: Option<usize>) {
217 533 : if !self.nodes[node].is_leaf() {
218 : // The default ancestor is the left-most child.
219 329 : let mut default_ancestor = self.nodes[node].left_most_child();
220 : // Track the left sibling
221 329 : let mut current_left_sibling = None;
222 :
223 458 : for child in self.nodes[node].children() {
224 458 : self.first_walk(child, current_left_sibling);
225 458 : default_ancestor = self.apportion(child, current_left_sibling, default_ancestor);
226 458 : current_left_sibling = Some(child);
227 458 : }
228 :
229 : // Execute the shifts at a node
230 329 : self.execute_shifts(node);
231 : // Compute the mid-point.
232 : // A left-to-right plan aligns a node with its first child instead, the plan then grows only downwards.
233 329 : let n = &self.nodes[node];
234 329 : let midpoint = if self.is_left_to_right() {
235 32 : self.nodes[n.left_most_child()].prelim
236 : } else {
237 297 : (self.nodes[n.left_most_child()].prelim + self.nodes[n.right_most_child()].prelim) / 2.0
238 : };
239 :
240 : // Is there a left sibling?
241 329 : if let Some(left_sibling) = left_sibling {
242 28 : let prelim = self.nodes[left_sibling].prelim + self.separation(left_sibling, node);
243 28 : self.nodes[node].prelim = prelim;
244 28 : self.nodes[node].modifier = prelim - midpoint;
245 301 : } else {
246 301 : self.nodes[node].prelim = midpoint;
247 301 : }
248 : } else {
249 : // Is there a left sibling?
250 204 : if let Some(left_sibling) = left_sibling {
251 101 : self.nodes[node].prelim = self.nodes[left_sibling].prelim + self.separation(left_sibling, node);
252 109 : } else {
253 103 : self.nodes[node].prelim = 0.0;
254 103 : }
255 : }
256 533 : }
257 :
258 : /// Perform the second walk over the tree
259 533 : fn second_walk(&mut self, node: usize, m: f64, level: usize) {
260 533 : self.nodes[node].x = self.nodes[node].prelim + m;
261 533 : self.nodes[node].y = level as f64 * self.layout_config.level_height();
262 533 : self.nodes[node].level = level;
263 533 : let modifier = self.nodes[node].modifier;
264 533 : for child in self.nodes[node].children() {
265 458 : self.second_walk(child, m + modifier, level + 1);
266 458 : }
267 533 : }
268 :
269 : /// Find the greatest distinct ancestor betweeen nodes
270 17 : fn find_greatest_distinct_ancestor(&self, left: usize, right: usize, default_ancestor: usize) -> usize {
271 17 : let ancestor = self.nodes[left].ancestor;
272 17 : if self.nodes[ancestor].parent == self.nodes[right].parent {
273 1 : ancestor
274 : } else {
275 16 : default_ancestor
276 : }
277 17 : }
278 :
279 : /// Apportion routine of Walker's algorithm
280 458 : fn apportion(&mut self, root: usize, left_sibling_of_root: Option<usize>, default_ancestor: usize) -> usize {
281 : //
282 : // [-] [+] o: Outside contour.
283 : // . . i: Inside contour.
284 : // / \ / \ ll: Left-tree(s) Left-most-contour.
285 : // /___\ /___\ lr: Left-tree(s) Right-most-contour.
286 : // o i i o rl: Right-tree Left-contour.
287 : // ll lr rl rr rr: Right-tree Right-contour.
288 : //
289 458 : let mut new_default_ancestor = default_ancestor;
290 :
291 458 : if let Some(left_sibling) = left_sibling_of_root {
292 129 : let mut rl = root;
293 129 : let mut rr = root;
294 129 : let mut lr = left_sibling;
295 129 : let parent = self.nodes[rl].parent.expect("apportioned node must have a parent");
296 129 : let mut ll = self.nodes[parent].left_most_child();
297 :
298 129 : let mut ll_mod = self.nodes[ll].modifier;
299 129 : let mut lr_mod = self.nodes[lr].modifier;
300 129 : let mut rl_mod = self.nodes[rl].modifier;
301 129 : let mut rr_mod = self.nodes[rr].modifier;
302 :
303 : // Traverse down the "seam".
304 : // Left subtree, traverse along right contour.
305 : // Right subtree, traverse along left contour.
306 21 : while let (Some(next_lr), Some(next_rl)) =
307 150 : (self.nodes[lr].next_along_right_contour(), self.nodes[rl].next_along_left_contour())
308 : {
309 21 : ll = self.nodes[ll].next_along_left_contour().expect("left contour ends early");
310 21 : lr = next_lr;
311 21 : rl = next_rl;
312 21 : rr = self.nodes[rr].next_along_right_contour().expect("right contour ends early");
313 :
314 : // Maintain the ancestor of the right contour to be the common root.
315 : // This allows us to resolve our ancestor in O(1) while going over the tree left-to-right.
316 21 : self.nodes[rr].ancestor = root;
317 :
318 : // Compute the current shift as the difference between the left contour and the right contour along
319 : // the seam. Section 4 in the Buchheim paper does a good job explain the fractional spacing approach.
320 21 : let shift =
321 21 : (self.nodes[lr].prelim + lr_mod) - (self.nodes[rl].prelim + rl_mod) + self.separation(lr, rl);
322 :
323 21 : if shift > 0.0 {
324 17 : let ancestor = self.find_greatest_distinct_ancestor(lr, root, default_ancestor);
325 17 : self.move_subtree(ancestor, root, shift);
326 17 : rl_mod += shift;
327 17 : rr_mod += shift;
328 17 : }
329 :
330 21 : ll_mod += self.nodes[ll].modifier;
331 21 : lr_mod += self.nodes[lr].modifier;
332 21 : rl_mod += self.nodes[rl].modifier;
333 21 : rr_mod += self.nodes[rr].modifier;
334 : }
335 :
336 : // Still have contour nodes at the seam from the left subtree?
337 129 : let lr_next = self.nodes[lr].next_along_right_contour();
338 129 : let rr_next = self.nodes[rr].next_along_right_contour();
339 129 : if lr_next.is_some() && rr_next.is_none() {
340 61 : // Let thread of RR point to LRs right contour starting at next level.
341 61 : self.nodes[rr].thread = lr_next;
342 61 : self.nodes[rr].modifier += lr_mod - rr_mod;
343 68 : }
344 :
345 : // Still have contour nodes at the seam from the right subtree?
346 129 : let rl_next = self.nodes[rl].next_along_left_contour();
347 129 : let ll_next = self.nodes[ll].next_along_left_contour();
348 129 : if rl_next.is_some() && ll_next.is_none() {
349 17 : // Let thread of LL point to RLs left contour starting at next level.
350 17 : self.nodes[ll].thread = rl_next;
351 17 : self.nodes[ll].modifier += rl_mod - ll_mod;
352 17 : new_default_ancestor = root;
353 112 : }
354 329 : }
355 :
356 458 : new_default_ancestor
357 458 : }
358 :
359 : /// Execute shifts for a layout node
360 329 : fn execute_shifts(&mut self, v: usize) {
361 329 : let mut shift = 0.0;
362 329 : let mut change = 0.0;
363 458 : for child in self.nodes[v].children().rev() {
364 458 : let child = &mut self.nodes[child];
365 458 : child.prelim += shift;
366 458 : child.modifier += shift;
367 458 : change += child.change;
368 458 : shift += child.shift + change;
369 458 : }
370 329 : }
371 :
372 : /// Helper to move a subtree
373 17 : fn move_subtree(&mut self, w0: usize, w1: usize, shift: f64) {
374 17 : debug_assert!(self.nodes[w0].parent.is_some());
375 17 : debug_assert!(self.nodes[w1].parent == self.nodes[w0].parent);
376 17 : debug_assert!(self.nodes[w1].sibling_index > self.nodes[w0].sibling_index);
377 17 : let subtrees = self.nodes[w1].sibling_index.wrapping_sub(self.nodes[w0].sibling_index) as f64;
378 :
379 17 : self.nodes[w1].change -= shift / subtrees;
380 17 : self.nodes[w1].shift += shift;
381 17 : self.nodes[w0].change += shift / subtrees;
382 17 : self.nodes[w1].prelim += shift;
383 17 : self.nodes[w1].modifier += shift;
384 17 : }
385 :
386 : /// Enforce the spacing invariant among all nodes on each level
387 75 : fn resolve_level_overlaps(&mut self, root: usize) {
388 75 : let margin = self.sibling_margin();
389 75 : let mut level: Vec<(usize, f64)> = vec![(root, 0.0)];
390 458 : while !level.is_empty() {
391 383 : let mut next_level = Vec::new();
392 383 : let mut right_edge: Option<f64> = None;
393 533 : for (node, inherited_shift) in level {
394 533 : let mut shift = inherited_shift + self.nodes[node].layout_shift;
395 533 : let left_edge = self.nodes[node].x + shift - self.breadth(node) / 2.0;
396 533 : if let Some(right_edge) = right_edge {
397 150 : let correction = right_edge + margin - left_edge;
398 150 : if correction > 0.0 {
399 0 : self.nodes[node].layout_shift += correction;
400 0 : shift += correction;
401 150 : }
402 383 : }
403 533 : right_edge = Some(self.nodes[node].x + shift + self.breadth(node) / 2.0);
404 533 : next_level.extend(self.nodes[node].children().map(|child| (child, shift)));
405 : }
406 383 : level = next_level;
407 : }
408 :
409 75 : let mut pending: Vec<(usize, f64)> = vec![(root, 0.0)];
410 608 : while let Some((node, inherited_shift)) = pending.pop() {
411 533 : let shift = inherited_shift + self.nodes[node].layout_shift;
412 533 : self.nodes[node].x += shift;
413 533 : pending.extend(self.nodes[node].children().map(|child| (child, shift)));
414 : }
415 75 : }
416 :
417 : /// Compute the plan layout
418 73 : fn compute(&mut self) {
419 73 : let margin = self.sibling_margin();
420 73 : let mut packed_right = 0.0;
421 73 : let mut has_packed_root = false;
422 75 : for &root in self.root_operators {
423 75 : let root = root as usize;
424 : // First run over the tree
425 75 : self.first_walk(root, None);
426 : // Second run over the tree.
427 : // `prelim` stores the preliminary x-coordinate AFTER computing the subtree.
428 75 : self.second_walk(root, -1.0 * self.nodes[root].prelim, 0);
429 75 : self.resolve_level_overlaps(root);
430 :
431 : // Independent roots are laid out at the same origin. Pack their full subtree bounds left-to-right.
432 75 : let mut left = f64::MAX;
433 75 : let mut right = f64::MIN;
434 75 : let mut pending = vec![root];
435 608 : while let Some(node) = pending.pop() {
436 533 : let breadth = self.breadth(node);
437 533 : let n = &self.nodes[node];
438 533 : left = cpp_min(left, n.x - breadth / 2.0);
439 533 : right = cpp_max(right, n.x + breadth / 2.0);
440 533 : pending.extend(n.children());
441 533 : }
442 75 : if has_packed_root {
443 2 : let offset = packed_right + margin - left;
444 2 : pending.push(root);
445 5 : while let Some(node) = pending.pop() {
446 3 : self.nodes[node].x += offset;
447 3 : pending.extend(self.nodes[node].children());
448 3 : }
449 2 : right += offset;
450 73 : }
451 75 : has_packed_root = true;
452 75 : packed_right = right;
453 : }
454 73 : }
455 : }
456 :
457 : impl QueryProfile {
458 : /// Configure the layout
459 70 : pub fn configure(&mut self, config: &fb::ProfileLayoutConfig) {
460 70 : self.layout_config.set_input(config);
461 70 : self.layout_config.set_computed_node_width(config.node_min_width());
462 70 : }
463 :
464 : /// Compute the plan layout
465 73 : pub fn compute_layout(&mut self) {
466 73 : let input = *self.layout_config.input();
467 :
468 : // Retain the widest node pitch in the derived config for layout consumers.
469 73 : let mut cell_width = 0.0;
470 533 : for op in &self.operators {
471 533 : cell_width = cpp_max(cell_width, compute_node_width(op, &input) + input.node_margin_horizontal());
472 533 : }
473 73 : self.layout_config.set_computed_node_width(cell_width);
474 :
475 : // Compute the plan layout
476 73 : let mut layouter = ProfileLayouter::new(self, &self.layout_config);
477 73 : layouter.compute();
478 73 : let mut nodes = layouter.nodes;
479 :
480 : // A left-to-right plan turns the levels into columns. Walker placed the siblings along x, they move to y.
481 : // A column is as wide as its widest node, the columns are separated by the horizontal margin.
482 : // The nodes of a column are left-aligned, the edges of all inputs of an operator then turn at the same x.
483 73 : let left_to_right = input.orientation() == fb::ProfileLayoutOrientation::LEFT_TO_RIGHT;
484 73 : if left_to_right {
485 49 : let levels = nodes.iter().map(|node| node.level + 1).max().unwrap_or(0);
486 5 : let mut column_widths = vec![0.0; levels];
487 49 : for node in &nodes {
488 49 : column_widths[node.level] = cpp_max(column_widths[node.level], node.width);
489 49 : }
490 5 : let mut column_lefts = Vec::with_capacity(levels);
491 5 : let mut column_left = 0.0;
492 34 : for width in column_widths {
493 34 : column_lefts.push(column_left);
494 34 : column_left += width + input.node_margin_horizontal();
495 34 : }
496 49 : for node in &mut nodes {
497 49 : node.y = node.x;
498 49 : node.x = column_lefts[node.level] + node.width / 2.0;
499 49 : }
500 68 : }
501 :
502 : // Compute total width and x- and y-shifts to make each point positive
503 73 : let mut x_max = f64::MIN;
504 73 : let mut x_min = f64::MAX;
505 73 : let mut y_max = f64::MIN;
506 73 : let mut y_min = f64::MAX;
507 73 : let node_height = input.node_height();
508 : // The vertical room of a node: a level in a top-down plan, the node itself in a left-to-right plan
509 73 : let level_height = if left_to_right { node_height } else { input.level_height() };
510 533 : for node in &nodes {
511 533 : x_max = cpp_max(x_max, node.x + node.width / 2.0);
512 533 : x_min = cpp_min(x_min, node.x - node.width / 2.0);
513 533 : y_max = cpp_max(y_max, node.y);
514 533 : y_min = cpp_min(y_min, node.y);
515 533 : }
516 73 : let total_width = (x_max - x_min).abs();
517 73 : let total_height = (y_max - y_min).abs() + level_height;
518 73 : let shift_x = -x_min;
519 73 : let shift_y = (y_min - level_height / 2.0) * -1.0;
520 :
521 : // Set all nodes layouts
522 533 : for (out, node) in self.operators.iter_mut().zip(&nodes) {
523 533 : let rect = fb::ProfileLayoutRect::new(shift_x + node.x, shift_y + node.y, node.width, node_height);
524 533 : out.layout_rect = Some(rect);
525 533 : }
526 :
527 : // Update the plan layout info
528 73 : self.layout_rect = Some(if !self.operators.is_empty() {
529 73 : fb::ProfileLayoutRect::new(0.0, 0.0, total_width, total_height)
530 : } else {
531 0 : fb::ProfileLayoutRect::default()
532 : });
533 73 : }
534 : }
|
