1#include "duckdb/optimizer/join_order/query_graph.hpp"
2
3#include "duckdb/common/printer.hpp"
4#include "duckdb/common/string_util.hpp"
5#include "duckdb/common/assert.hpp"
6#include "duckdb/common/to_string.hpp"
7
8namespace duckdb {
9
10using QueryEdge = QueryGraph::QueryEdge;
11
12// LCOV_EXCL_START
13static string QueryEdgeToString(const QueryEdge *info, vector<idx_t> prefix) {
14 string result = "";
15 string source = "[";
16 for (idx_t i = 0; i < prefix.size(); i++) {
17 source += to_string(val: prefix[i]) + (i < prefix.size() - 1 ? ", " : "");
18 }
19 source += "]";
20 for (auto &entry : info->neighbors) {
21 result += StringUtil::Format(fmt_str: "%s -> %s\n", params: source.c_str(), params: entry->neighbor.ToString().c_str());
22 }
23 for (auto &entry : info->children) {
24 vector<idx_t> new_prefix = prefix;
25 new_prefix.push_back(x: entry.first);
26 result += QueryEdgeToString(info: entry.second.get(), prefix: new_prefix);
27 }
28 return result;
29}
30
31string QueryGraph::ToString() const {
32 return QueryEdgeToString(info: &root, prefix: {});
33}
34
35void QueryGraph::Print() {
36 Printer::Print(str: ToString());
37}
38// LCOV_EXCL_STOP
39
40QueryEdge &QueryGraph::GetQueryEdge(JoinRelationSet &left) {
41 D_ASSERT(left.count > 0);
42 // find the EdgeInfo corresponding to the left set
43 reference<QueryEdge> info(root);
44 for (idx_t i = 0; i < left.count; i++) {
45 auto entry = info.get().children.find(x: left.relations[i]);
46 if (entry == info.get().children.end()) {
47 // node not found, create it
48 auto insert_it = info.get().children.insert(x: make_pair(x&: left.relations[i], y: make_uniq<QueryEdge>()));
49 entry = insert_it.first;
50 }
51 // move to the next node
52 info = *entry->second;
53 }
54 return info;
55}
56
57void QueryGraph::CreateEdge(JoinRelationSet &left, JoinRelationSet &right, optional_ptr<FilterInfo> filter_info) {
58 D_ASSERT(left.count > 0 && right.count > 0);
59 // find the EdgeInfo corresponding to the left set
60 auto &info = GetQueryEdge(left);
61 // now insert the edge to the right relation, if it does not exist
62 for (idx_t i = 0; i < info.neighbors.size(); i++) {
63 if (&info.neighbors[i]->neighbor == &right) {
64 if (filter_info) {
65 // neighbor already exists just add the filter, if we have any
66 info.neighbors[i]->filters.push_back(x: *filter_info);
67 }
68 return;
69 }
70 }
71 // neighbor does not exist, create it
72 auto n = make_uniq<NeighborInfo>(args&: right);
73 if (filter_info) {
74 n->filters.push_back(x: *filter_info);
75 }
76 info.neighbors.push_back(x: std::move(n));
77}
78
79void QueryGraph::EnumerateNeighbors(JoinRelationSet &node, const std::function<bool(NeighborInfo &)> &callback) {
80 for (idx_t j = 0; j < node.count; j++) {
81 reference<QueryEdge> info = root;
82 for (idx_t i = j; i < node.count; i++) {
83 auto entry = info.get().children.find(x: node.relations[i]);
84 if (entry == info.get().children.end()) {
85 // node not found
86 break;
87 }
88 // check if any subset of the other set is in this sets neighbors
89 info = *entry->second;
90 for (auto &neighbor : info.get().neighbors) {
91 if (callback(*neighbor)) {
92 return;
93 }
94 }
95 }
96 }
97}
98
99//! Returns true if a JoinRelationSet is banned by the list of exclusion_set, false otherwise
100static bool JoinRelationSetIsExcluded(JoinRelationSet &node, unordered_set<idx_t> &exclusion_set) {
101 return exclusion_set.find(x: node.relations[0]) != exclusion_set.end();
102}
103
104vector<idx_t> QueryGraph::GetNeighbors(JoinRelationSet &node, unordered_set<idx_t> &exclusion_set) {
105 unordered_set<idx_t> result;
106 EnumerateNeighbors(node, callback: [&](NeighborInfo &info) -> bool {
107 if (!JoinRelationSetIsExcluded(node&: info.neighbor, exclusion_set)) {
108 // add the smallest node of the neighbor to the set
109 result.insert(x: info.neighbor.relations[0]);
110 }
111 return false;
112 });
113 vector<idx_t> neighbors;
114 neighbors.insert(position: neighbors.end(), first: result.begin(), last: result.end());
115 return neighbors;
116}
117
118vector<reference<NeighborInfo>> QueryGraph::GetConnections(JoinRelationSet &node, JoinRelationSet &other) {
119 vector<reference<NeighborInfo>> connections;
120 EnumerateNeighbors(node, callback: [&](NeighborInfo &info) -> bool {
121 if (JoinRelationSet::IsSubset(super&: other, sub&: info.neighbor)) {
122 connections.push_back(x: info);
123 }
124 return false;
125 });
126 return connections;
127}
128
129} // namespace duckdb
130