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