1#include "duckdb/common/tree_renderer.hpp"
2#include "duckdb/planner/logical_operator.hpp"
3#include "duckdb/execution/physical_operator.hpp"
4#include "duckdb/common/string_util.hpp"
5#include "duckdb/common/pair.hpp"
6#include "duckdb/execution/operator/join/physical_delim_join.hpp"
7#include "duckdb/execution/operator/aggregate/physical_hash_aggregate.hpp"
8#include "duckdb/execution/operator/scan/physical_positional_scan.hpp"
9#include "duckdb/parallel/pipeline.hpp"
10#include "utf8proc_wrapper.hpp"
11
12#include <sstream>
13
14namespace duckdb {
15
16RenderTree::RenderTree(idx_t width_p, idx_t height_p) : width(width_p), height(height_p) {
17 nodes = unique_ptr<unique_ptr<RenderTreeNode>[]>(new unique_ptr<RenderTreeNode>[(width + 1) * (height + 1)]);
18}
19
20RenderTreeNode *RenderTree::GetNode(idx_t x, idx_t y) {
21 if (x >= width || y >= height) {
22 return nullptr;
23 }
24 return nodes[GetPosition(x, y)].get();
25}
26
27bool RenderTree::HasNode(idx_t x, idx_t y) {
28 if (x >= width || y >= height) {
29 return false;
30 }
31 return nodes[GetPosition(x, y)].get() != nullptr;
32}
33
34idx_t RenderTree::GetPosition(idx_t x, idx_t y) {
35 return y * width + x;
36}
37
38void RenderTree::SetNode(idx_t x, idx_t y, unique_ptr<RenderTreeNode> node) {
39 nodes[GetPosition(x, y)] = std::move(node);
40}
41
42void TreeRenderer::RenderTopLayer(RenderTree &root, std::ostream &ss, idx_t y) {
43 for (idx_t x = 0; x < root.width; x++) {
44 if (x * config.NODE_RENDER_WIDTH >= config.MAXIMUM_RENDER_WIDTH) {
45 break;
46 }
47 if (root.HasNode(x, y)) {
48 ss << config.LTCORNER;
49 ss << StringUtil::Repeat(str: config.HORIZONTAL, n: config.NODE_RENDER_WIDTH / 2 - 1);
50 if (y == 0) {
51 // top level node: no node above this one
52 ss << config.HORIZONTAL;
53 } else {
54 // render connection to node above this one
55 ss << config.DMIDDLE;
56 }
57 ss << StringUtil::Repeat(str: config.HORIZONTAL, n: config.NODE_RENDER_WIDTH / 2 - 1);
58 ss << config.RTCORNER;
59 } else {
60 ss << StringUtil::Repeat(str: " ", n: config.NODE_RENDER_WIDTH);
61 }
62 }
63 ss << std::endl;
64}
65
66void TreeRenderer::RenderBottomLayer(RenderTree &root, std::ostream &ss, idx_t y) {
67 for (idx_t x = 0; x <= root.width; x++) {
68 if (x * config.NODE_RENDER_WIDTH >= config.MAXIMUM_RENDER_WIDTH) {
69 break;
70 }
71 if (root.HasNode(x, y)) {
72 ss << config.LDCORNER;
73 ss << StringUtil::Repeat(str: config.HORIZONTAL, n: config.NODE_RENDER_WIDTH / 2 - 1);
74 if (root.HasNode(x, y: y + 1)) {
75 // node below this one: connect to that one
76 ss << config.TMIDDLE;
77 } else {
78 // no node below this one: end the box
79 ss << config.HORIZONTAL;
80 }
81 ss << StringUtil::Repeat(str: config.HORIZONTAL, n: config.NODE_RENDER_WIDTH / 2 - 1);
82 ss << config.RDCORNER;
83 } else if (root.HasNode(x, y: y + 1)) {
84 ss << StringUtil::Repeat(str: " ", n: config.NODE_RENDER_WIDTH / 2);
85 ss << config.VERTICAL;
86 ss << StringUtil::Repeat(str: " ", n: config.NODE_RENDER_WIDTH / 2);
87 } else {
88 ss << StringUtil::Repeat(str: " ", n: config.NODE_RENDER_WIDTH);
89 }
90 }
91 ss << std::endl;
92}
93
94string AdjustTextForRendering(string source, idx_t max_render_width) {
95 idx_t cpos = 0;
96 idx_t render_width = 0;
97 vector<pair<idx_t, idx_t>> render_widths;
98 while (cpos < source.size()) {
99 idx_t char_render_width = Utf8Proc::RenderWidth(s: source.c_str(), len: source.size(), pos: cpos);
100 cpos = Utf8Proc::NextGraphemeCluster(s: source.c_str(), len: source.size(), pos: cpos);
101 render_width += char_render_width;
102 render_widths.emplace_back(args&: cpos, args&: render_width);
103 if (render_width > max_render_width) {
104 break;
105 }
106 }
107 if (render_width > max_render_width) {
108 // need to find a position to truncate
109 for (idx_t pos = render_widths.size(); pos > 0; pos--) {
110 if (render_widths[pos - 1].second < max_render_width - 4) {
111 return source.substr(pos: 0, n: render_widths[pos - 1].first) + "..." +
112 string(max_render_width - render_widths[pos - 1].second - 3, ' ');
113 }
114 }
115 source = "...";
116 }
117 // need to pad with spaces
118 idx_t total_spaces = max_render_width - render_width;
119 idx_t half_spaces = total_spaces / 2;
120 idx_t extra_left_space = total_spaces % 2 == 0 ? 0 : 1;
121 return string(half_spaces + extra_left_space, ' ') + source + string(half_spaces, ' ');
122}
123
124static bool NodeHasMultipleChildren(RenderTree &root, idx_t x, idx_t y) {
125 for (; x < root.width && !root.HasNode(x: x + 1, y); x++) {
126 if (root.HasNode(x: x + 1, y: y + 1)) {
127 return true;
128 }
129 }
130 return false;
131}
132
133void TreeRenderer::RenderBoxContent(RenderTree &root, std::ostream &ss, idx_t y) {
134 // we first need to figure out how high our boxes are going to be
135 vector<vector<string>> extra_info;
136 idx_t extra_height = 0;
137 extra_info.resize(new_size: root.width);
138 for (idx_t x = 0; x < root.width; x++) {
139 auto node = root.GetNode(x, y);
140 if (node) {
141 SplitUpExtraInfo(extra_info: node->extra_text, result&: extra_info[x]);
142 if (extra_info[x].size() > extra_height) {
143 extra_height = extra_info[x].size();
144 }
145 }
146 }
147 extra_height = MinValue<idx_t>(a: extra_height, b: config.MAX_EXTRA_LINES);
148 idx_t halfway_point = (extra_height + 1) / 2;
149 // now we render the actual node
150 for (idx_t render_y = 0; render_y <= extra_height; render_y++) {
151 for (idx_t x = 0; x < root.width; x++) {
152 if (x * config.NODE_RENDER_WIDTH >= config.MAXIMUM_RENDER_WIDTH) {
153 break;
154 }
155 auto node = root.GetNode(x, y);
156 if (!node) {
157 if (render_y == halfway_point) {
158 bool has_child_to_the_right = NodeHasMultipleChildren(root, x, y);
159 if (root.HasNode(x, y: y + 1)) {
160 // node right below this one
161 ss << StringUtil::Repeat(str: config.HORIZONTAL, n: config.NODE_RENDER_WIDTH / 2);
162 ss << config.RTCORNER;
163 if (has_child_to_the_right) {
164 // but we have another child to the right! keep rendering the line
165 ss << StringUtil::Repeat(str: config.HORIZONTAL, n: config.NODE_RENDER_WIDTH / 2);
166 } else {
167 // only a child below this one: fill the rest with spaces
168 ss << StringUtil::Repeat(str: " ", n: config.NODE_RENDER_WIDTH / 2);
169 }
170 } else if (has_child_to_the_right) {
171 // child to the right, but no child right below this one: render a full line
172 ss << StringUtil::Repeat(str: config.HORIZONTAL, n: config.NODE_RENDER_WIDTH);
173 } else {
174 // empty spot: render spaces
175 ss << StringUtil::Repeat(str: " ", n: config.NODE_RENDER_WIDTH);
176 }
177 } else if (render_y >= halfway_point) {
178 if (root.HasNode(x, y: y + 1)) {
179 // we have a node below this empty spot: render a vertical line
180 ss << StringUtil::Repeat(str: " ", n: config.NODE_RENDER_WIDTH / 2);
181 ss << config.VERTICAL;
182 ss << StringUtil::Repeat(str: " ", n: config.NODE_RENDER_WIDTH / 2);
183 } else {
184 // empty spot: render spaces
185 ss << StringUtil::Repeat(str: " ", n: config.NODE_RENDER_WIDTH);
186 }
187 } else {
188 // empty spot: render spaces
189 ss << StringUtil::Repeat(str: " ", n: config.NODE_RENDER_WIDTH);
190 }
191 } else {
192 ss << config.VERTICAL;
193 // figure out what to render
194 string render_text;
195 if (render_y == 0) {
196 render_text = node->name;
197 } else {
198 if (render_y <= extra_info[x].size()) {
199 render_text = extra_info[x][render_y - 1];
200 }
201 }
202 render_text = AdjustTextForRendering(source: render_text, max_render_width: config.NODE_RENDER_WIDTH - 2);
203 ss << render_text;
204
205 if (render_y == halfway_point && NodeHasMultipleChildren(root, x, y)) {
206 ss << config.LMIDDLE;
207 } else {
208 ss << config.VERTICAL;
209 }
210 }
211 }
212 ss << std::endl;
213 }
214}
215
216string TreeRenderer::ToString(const LogicalOperator &op) {
217 std::stringstream ss;
218 Render(op, ss);
219 return ss.str();
220}
221
222string TreeRenderer::ToString(const PhysicalOperator &op) {
223 std::stringstream ss;
224 Render(op, ss);
225 return ss.str();
226}
227
228string TreeRenderer::ToString(const QueryProfiler::TreeNode &op) {
229 std::stringstream ss;
230 Render(op, ss);
231 return ss.str();
232}
233
234string TreeRenderer::ToString(const Pipeline &op) {
235 std::stringstream ss;
236 Render(op, ss);
237 return ss.str();
238}
239
240void TreeRenderer::Render(const LogicalOperator &op, std::ostream &ss) {
241 auto tree = CreateTree(op);
242 ToStream(root&: *tree, ss);
243}
244
245void TreeRenderer::Render(const PhysicalOperator &op, std::ostream &ss) {
246 auto tree = CreateTree(op);
247 ToStream(root&: *tree, ss);
248}
249
250void TreeRenderer::Render(const QueryProfiler::TreeNode &op, std::ostream &ss) {
251 auto tree = CreateTree(op);
252 ToStream(root&: *tree, ss);
253}
254
255void TreeRenderer::Render(const Pipeline &op, std::ostream &ss) {
256 auto tree = CreateTree(op);
257 ToStream(root&: *tree, ss);
258}
259
260void TreeRenderer::ToStream(RenderTree &root, std::ostream &ss) {
261 while (root.width * config.NODE_RENDER_WIDTH > config.MAXIMUM_RENDER_WIDTH) {
262 if (config.NODE_RENDER_WIDTH - 2 < config.MINIMUM_RENDER_WIDTH) {
263 break;
264 }
265 config.NODE_RENDER_WIDTH -= 2;
266 }
267
268 for (idx_t y = 0; y < root.height; y++) {
269 // start by rendering the top layer
270 RenderTopLayer(root, ss, y);
271 // now we render the content of the boxes
272 RenderBoxContent(root, ss, y);
273 // render the bottom layer of each of the boxes
274 RenderBottomLayer(root, ss, y);
275 }
276}
277
278bool TreeRenderer::CanSplitOnThisChar(char l) {
279 return (l < '0' || (l > '9' && l < 'A') || (l > 'Z' && l < 'a')) && l != '_';
280}
281
282bool TreeRenderer::IsPadding(char l) {
283 return l == ' ' || l == '\t' || l == '\n' || l == '\r';
284}
285
286string TreeRenderer::RemovePadding(string l) {
287 idx_t start = 0, end = l.size();
288 while (start < l.size() && IsPadding(l: l[start])) {
289 start++;
290 }
291 while (end > 0 && IsPadding(l: l[end - 1])) {
292 end--;
293 }
294 return l.substr(pos: start, n: end - start);
295}
296
297void TreeRenderer::SplitStringBuffer(const string &source, vector<string> &result) {
298 D_ASSERT(Utf8Proc::IsValid(source.c_str(), source.size()));
299 idx_t max_line_render_size = config.NODE_RENDER_WIDTH - 2;
300 // utf8 in prompt, get render width
301 idx_t cpos = 0;
302 idx_t start_pos = 0;
303 idx_t render_width = 0;
304 idx_t last_possible_split = 0;
305 while (cpos < source.size()) {
306 // check if we can split on this character
307 if (CanSplitOnThisChar(l: source[cpos])) {
308 last_possible_split = cpos;
309 }
310 size_t char_render_width = Utf8Proc::RenderWidth(s: source.c_str(), len: source.size(), pos: cpos);
311 idx_t next_cpos = Utf8Proc::NextGraphemeCluster(s: source.c_str(), len: source.size(), pos: cpos);
312 if (render_width + char_render_width > max_line_render_size) {
313 if (last_possible_split <= start_pos + 8) {
314 last_possible_split = cpos;
315 }
316 result.push_back(x: source.substr(pos: start_pos, n: last_possible_split - start_pos));
317 start_pos = last_possible_split;
318 cpos = last_possible_split;
319 render_width = 0;
320 }
321 cpos = next_cpos;
322 render_width += char_render_width;
323 }
324 if (source.size() > start_pos) {
325 result.push_back(x: source.substr(pos: start_pos, n: source.size() - start_pos));
326 }
327}
328
329void TreeRenderer::SplitUpExtraInfo(const string &extra_info, vector<string> &result) {
330 if (extra_info.empty()) {
331 return;
332 }
333 if (!Utf8Proc::IsValid(s: extra_info.c_str(), len: extra_info.size())) {
334 return;
335 }
336 auto splits = StringUtil::Split(input: extra_info, split: "\n");
337 if (!splits.empty() && splits[0] != "[INFOSEPARATOR]") {
338 result.push_back(x: ExtraInfoSeparator());
339 }
340 for (auto &split : splits) {
341 if (split == "[INFOSEPARATOR]") {
342 result.push_back(x: ExtraInfoSeparator());
343 continue;
344 }
345 string str = RemovePadding(l: split);
346 if (str.empty()) {
347 continue;
348 }
349 SplitStringBuffer(source: str, result);
350 }
351}
352
353string TreeRenderer::ExtraInfoSeparator() {
354 return StringUtil::Repeat(str: string(config.HORIZONTAL) + " ", n: (config.NODE_RENDER_WIDTH - 7) / 2);
355}
356
357unique_ptr<RenderTreeNode> TreeRenderer::CreateRenderNode(string name, string extra_info) {
358 auto result = make_uniq<RenderTreeNode>();
359 result->name = std::move(name);
360 result->extra_text = std::move(extra_info);
361 return result;
362}
363
364class TreeChildrenIterator {
365public:
366 template <class T>
367 static bool HasChildren(const T &op) {
368 return !op.children.empty();
369 }
370 template <class T>
371 static void Iterate(const T &op, const std::function<void(const T &child)> &callback) {
372 for (auto &child : op.children) {
373 callback(*child);
374 }
375 }
376};
377
378template <>
379bool TreeChildrenIterator::HasChildren(const PhysicalOperator &op) {
380 switch (op.type) {
381 case PhysicalOperatorType::DELIM_JOIN:
382 case PhysicalOperatorType::POSITIONAL_SCAN:
383 return true;
384 default:
385 return !op.children.empty();
386 }
387}
388template <>
389void TreeChildrenIterator::Iterate(const PhysicalOperator &op,
390 const std::function<void(const PhysicalOperator &child)> &callback) {
391 for (auto &child : op.children) {
392 callback(*child);
393 }
394 if (op.type == PhysicalOperatorType::DELIM_JOIN) {
395 auto &delim = op.Cast<PhysicalDelimJoin>();
396 callback(*delim.join);
397 } else if ((op.type == PhysicalOperatorType::POSITIONAL_SCAN)) {
398 auto &pscan = op.Cast<PhysicalPositionalScan>();
399 for (auto &table : pscan.child_tables) {
400 callback(*table);
401 }
402 }
403}
404
405struct PipelineRenderNode {
406 explicit PipelineRenderNode(const PhysicalOperator &op) : op(op) {
407 }
408
409 const PhysicalOperator &op;
410 unique_ptr<PipelineRenderNode> child;
411};
412
413template <>
414bool TreeChildrenIterator::HasChildren(const PipelineRenderNode &op) {
415 return op.child.get();
416}
417
418template <>
419void TreeChildrenIterator::Iterate(const PipelineRenderNode &op,
420 const std::function<void(const PipelineRenderNode &child)> &callback) {
421 if (op.child) {
422 callback(*op.child);
423 }
424}
425
426template <class T>
427static void GetTreeWidthHeight(const T &op, idx_t &width, idx_t &height) {
428 if (!TreeChildrenIterator::HasChildren(op)) {
429 width = 1;
430 height = 1;
431 return;
432 }
433 width = 0;
434 height = 0;
435
436 TreeChildrenIterator::Iterate<T>(op, [&](const T &child) {
437 idx_t child_width, child_height;
438 GetTreeWidthHeight<T>(child, child_width, child_height);
439 width += child_width;
440 height = MaxValue<idx_t>(a: height, b: child_height);
441 });
442 height++;
443}
444
445template <class T>
446idx_t TreeRenderer::CreateRenderTreeRecursive(RenderTree &result, const T &op, idx_t x, idx_t y) {
447 auto node = TreeRenderer::CreateNode(op);
448 result.SetNode(x, y, node: std::move(node));
449
450 if (!TreeChildrenIterator::HasChildren(op)) {
451 return 1;
452 }
453 idx_t width = 0;
454 // render the children of this node
455 TreeChildrenIterator::Iterate<T>(
456 op, [&](const T &child) { width += CreateRenderTreeRecursive<T>(result, child, x + width, y + 1); });
457 return width;
458}
459
460template <class T>
461unique_ptr<RenderTree> TreeRenderer::CreateRenderTree(const T &op) {
462 idx_t width, height;
463 GetTreeWidthHeight<T>(op, width, height);
464
465 auto result = make_uniq<RenderTree>(args&: width, args&: height);
466
467 // now fill in the tree
468 CreateRenderTreeRecursive<T>(*result, op, 0, 0);
469 return result;
470}
471
472unique_ptr<RenderTreeNode> TreeRenderer::CreateNode(const LogicalOperator &op) {
473 return CreateRenderNode(name: op.GetName(), extra_info: op.ParamsToString());
474}
475
476unique_ptr<RenderTreeNode> TreeRenderer::CreateNode(const PhysicalOperator &op) {
477 return CreateRenderNode(name: op.GetName(), extra_info: op.ParamsToString());
478}
479
480unique_ptr<RenderTreeNode> TreeRenderer::CreateNode(const PipelineRenderNode &op) {
481 return CreateNode(op: op.op);
482}
483
484string TreeRenderer::ExtractExpressionsRecursive(ExpressionInfo &state) {
485 string result = "\n[INFOSEPARATOR]";
486 result += "\n" + state.function_name;
487 result += "\n" + StringUtil::Format(fmt_str: "%.9f", params: double(state.function_time));
488 if (state.children.empty()) {
489 return result;
490 }
491 // render the children of this node
492 for (auto &child : state.children) {
493 result += ExtractExpressionsRecursive(state&: *child);
494 }
495 return result;
496}
497
498unique_ptr<RenderTreeNode> TreeRenderer::CreateNode(const QueryProfiler::TreeNode &op) {
499 auto result = TreeRenderer::CreateRenderNode(name: op.name, extra_info: op.extra_info);
500 result->extra_text += "\n[INFOSEPARATOR]";
501 result->extra_text += "\n" + to_string(val: op.info.elements);
502 string timing = StringUtil::Format(fmt_str: "%.2f", params: op.info.time);
503 result->extra_text += "\n(" + timing + "s)";
504 if (config.detailed) {
505 for (auto &info : op.info.executors_info) {
506 if (!info) {
507 continue;
508 }
509 for (auto &executor_info : info->roots) {
510 string sample_count = to_string(val: executor_info->sample_count);
511 result->extra_text += "\n[INFOSEPARATOR]";
512 result->extra_text += "\nsample_count: " + sample_count;
513 string sample_tuples_count = to_string(val: executor_info->sample_tuples_count);
514 result->extra_text += "\n[INFOSEPARATOR]";
515 result->extra_text += "\nsample_tuples_count: " + sample_tuples_count;
516 string total_count = to_string(val: executor_info->total_count);
517 result->extra_text += "\n[INFOSEPARATOR]";
518 result->extra_text += "\ntotal_count: " + total_count;
519 for (auto &state : executor_info->root->children) {
520 result->extra_text += ExtractExpressionsRecursive(state&: *state);
521 }
522 }
523 }
524 }
525 return result;
526}
527
528unique_ptr<RenderTree> TreeRenderer::CreateTree(const LogicalOperator &op) {
529 return CreateRenderTree<LogicalOperator>(op);
530}
531
532unique_ptr<RenderTree> TreeRenderer::CreateTree(const PhysicalOperator &op) {
533 return CreateRenderTree<PhysicalOperator>(op);
534}
535
536unique_ptr<RenderTree> TreeRenderer::CreateTree(const QueryProfiler::TreeNode &op) {
537 return CreateRenderTree<QueryProfiler::TreeNode>(op);
538}
539
540unique_ptr<RenderTree> TreeRenderer::CreateTree(const Pipeline &op) {
541 auto operators = op.GetOperators();
542 D_ASSERT(!operators.empty());
543 unique_ptr<PipelineRenderNode> node;
544 for (auto &op : operators) {
545 auto new_node = make_uniq<PipelineRenderNode>(args: op.get());
546 new_node->child = std::move(node);
547 node = std::move(new_node);
548 }
549 return CreateRenderTree<PipelineRenderNode>(op: *node);
550}
551
552} // namespace duckdb
553