1#include "duckdb/optimizer/join_order/join_relation.hpp"
2#include "duckdb/common/string_util.hpp"
3#include "duckdb/common/to_string.hpp"
4
5#include <algorithm>
6
7namespace duckdb {
8
9using JoinRelationTreeNode = JoinRelationSetManager::JoinRelationTreeNode;
10
11// LCOV_EXCL_START
12string JoinRelationSet::ToString() const {
13 string result = "[";
14 result += StringUtil::Join(input: relations, count, separator: ", ", f: [](const idx_t &relation) { return to_string(val: relation); });
15 result += "]";
16 return result;
17}
18// LCOV_EXCL_STOP
19
20//! Returns true if sub is a subset of super
21bool JoinRelationSet::IsSubset(JoinRelationSet &super, JoinRelationSet &sub) {
22 D_ASSERT(sub.count > 0);
23 if (sub.count > super.count) {
24 return false;
25 }
26 idx_t j = 0;
27 for (idx_t i = 0; i < super.count; i++) {
28 if (sub.relations[j] == super.relations[i]) {
29 j++;
30 if (j == sub.count) {
31 return true;
32 }
33 }
34 }
35 return false;
36}
37
38JoinRelationSet &JoinRelationSetManager::GetJoinRelation(unsafe_unique_array<idx_t> relations, idx_t count) {
39 // now look it up in the tree
40 reference<JoinRelationTreeNode> info(root);
41 for (idx_t i = 0; i < count; i++) {
42 auto entry = info.get().children.find(x: relations[i]);
43 if (entry == info.get().children.end()) {
44 // node not found, create it
45 auto insert_it = info.get().children.insert(x: make_pair(x&: relations[i], y: make_uniq<JoinRelationTreeNode>()));
46 entry = insert_it.first;
47 }
48 // move to the next node
49 info = *entry->second;
50 }
51 // now check if the JoinRelationSet has already been created
52 if (!info.get().relation) {
53 // if it hasn't we need to create it
54 info.get().relation = make_uniq<JoinRelationSet>(args: std::move(relations), args&: count);
55 }
56 return *info.get().relation;
57}
58
59//! Create or get a JoinRelationSet from a single node with the given index
60JoinRelationSet &JoinRelationSetManager::GetJoinRelation(idx_t index) {
61 // create a sorted vector of the relations
62 auto relations = make_unsafe_uniq_array<idx_t>(n: 1);
63 relations[0] = index;
64 idx_t count = 1;
65 return GetJoinRelation(relations: std::move(relations), count);
66}
67
68JoinRelationSet &JoinRelationSetManager::GetJoinRelation(unordered_set<idx_t> &bindings) {
69 // create a sorted vector of the relations
70 unsafe_unique_array<idx_t> relations = bindings.empty() ? nullptr : make_unsafe_uniq_array<idx_t>(n: bindings.size());
71 idx_t count = 0;
72 for (auto &entry : bindings) {
73 relations[count++] = entry;
74 }
75 std::sort(first: relations.get(), last: relations.get() + count);
76 return GetJoinRelation(relations: std::move(relations), count);
77}
78
79JoinRelationSet &JoinRelationSetManager::Union(JoinRelationSet &left, JoinRelationSet &right) {
80 auto relations = make_unsafe_uniq_array<idx_t>(n: left.count + right.count);
81 idx_t count = 0;
82 // move through the left and right relations, eliminating duplicates
83 idx_t i = 0, j = 0;
84 while (true) {
85 if (i == left.count) {
86 // exhausted left relation, add remaining of right relation
87 for (; j < right.count; j++) {
88 relations[count++] = right.relations[j];
89 }
90 break;
91 } else if (j == right.count) {
92 // exhausted right relation, add remaining of left
93 for (; i < left.count; i++) {
94 relations[count++] = left.relations[i];
95 }
96 break;
97 } else if (left.relations[i] == right.relations[j]) {
98 // equivalent, add only one of the two pairs
99 relations[count++] = left.relations[i];
100 i++;
101 j++;
102 } else if (left.relations[i] < right.relations[j]) {
103 // left is smaller, progress left and add it to the set
104 relations[count++] = left.relations[i];
105 i++;
106 } else {
107 // right is smaller, progress right and add it to the set
108 relations[count++] = right.relations[j];
109 j++;
110 }
111 }
112 return GetJoinRelation(relations: std::move(relations), count);
113}
114
115// JoinRelationSet *JoinRelationSetManager::Difference(JoinRelationSet *left, JoinRelationSet *right) {
116// auto relations = unsafe_unique_array<idx_t>(new idx_t[left->count]);
117// idx_t count = 0;
118// // move through the left and right relations
119// idx_t i = 0, j = 0;
120// while (true) {
121// if (i == left->count) {
122// // exhausted left relation, we are done
123// break;
124// } else if (j == right->count) {
125// // exhausted right relation, add remaining of left
126// for (; i < left->count; i++) {
127// relations[count++] = left->relations[i];
128// }
129// break;
130// } else if (left->relations[i] == right->relations[j]) {
131// // equivalent, add nothing
132// i++;
133// j++;
134// } else if (left->relations[i] < right->relations[j]) {
135// // left is smaller, progress left and add it to the set
136// relations[count++] = left->relations[i];
137// i++;
138// } else {
139// // right is smaller, progress right
140// j++;
141// }
142// }
143// return GetJoinRelation(std::move(relations), count);
144// }
145
146} // namespace duckdb
147