Column-oriented GPU-accelerated Database Management System
CoGaDB
|
00001 #pragma once 00002 00003 //#include <core/scheduling_decision.hpp> 00004 00005 //#include <boost/shared_ptr.hpp> 00006 00007 #include <stack> 00008 #include <query_processing/node.hpp> 00009 #include <query_processing/physical_query_plan.hpp> 00010 #include <util/get_name.hpp> 00011 00012 #include <boost/thread.hpp> 00013 #include <boost/bind.hpp> 00014 00015 namespace hype { 00016 namespace queryprocessing { 00017 00018 struct print_NodePtr_functor { 00019 00020 void operator()(NodePtr ptr) const { 00021 for (unsigned int i = 0; i < ptr->getLevel(); i++) 00022 std::cout << "\t"; 00023 //std::cout << "Operation: " << ptr->getOperationName(); 00024 std::cout << ptr->toString(true); 00025 if (ptr->getDeviceConstraint().getDeviceTypeConstraint() != hype::ANY_DEVICE) { 00026 std::cout << "\t[" << hype::util::getName(ptr->getDeviceConstraint().getDeviceTypeConstraint()) << "]"; 00027 } 00028 std::cout << std::endl; 00029 } 00030 }; 00031 00032 struct assign_treelevel_NodePtr_functor { 00033 00034 void operator()(NodePtr ptr) { 00035 if (ptr.get() != NULL) { 00036 NodePtr left = ptr->getLeft(); 00037 NodePtr right = ptr->getRight(); 00038 if (left.get() != NULL) { 00039 left->setLevel(ptr->getLevel() + 1); 00040 } 00041 if (right.get() != NULL) { 00042 right->setLevel(ptr->getLevel() + 1); 00043 } 00044 00045 00046 } 00047 } 00048 }; 00049 00050 struct init_parent_NodePtr_functor { 00051 00052 void operator()(NodePtr ptr) { 00053 if (ptr) { 00054 NodePtr left = ptr->getLeft(); 00055 NodePtr right = ptr->getRight(); 00056 if (left) { 00057 left->setParent(ptr); 00058 } 00059 if (right) { 00060 right->setParent(ptr); 00061 } 00062 00063 00064 } 00065 } 00066 }; 00067 00068 template <typename Type> 00069 struct Construct_Physical_Query_Plan_functor { 00070 typedef typename OperatorMapper_Helper_Template<Type>::TypedOperatorPtr TypedOperatorPtr; 00071 typedef typename OperatorMapper_Helper_Template<Type>::TypedNodePtr TypedNodePtr; 00072 00073 typedef std::map<TypedNodePtr, TypedOperatorPtr> Map; 00074 00075 Construct_Physical_Query_Plan_functor() : root_(), map_log_op_to_phy_op_() { 00076 00077 } 00078 00079 TypedOperatorPtr getRootOperator() { 00080 return root_; 00081 } 00082 00083 void operator()(TypedNodePtr ptr, bool chopped = false) { 00084 if (!hype::core::quiet && hype::core::verbose && hype::core::debug) std::cout << typeid (ptr).name(); 00085 00086 if (ptr) { 00087 00088 TypedOperatorPtr left_op; 00089 TypedOperatorPtr right_op; 00090 00091 TypedNodePtr left = boost::static_pointer_cast<typename TypedNodePtr::element_type > (ptr->getLeft()); 00092 TypedNodePtr right = boost::static_pointer_cast<typename TypedNodePtr::element_type > (ptr->getRight()); 00093 if (left != NULL) { 00094 typename Map::iterator it = map_log_op_to_phy_op_.find(left); 00095 if (it != map_log_op_to_phy_op_.end()) 00096 left_op = it->second; 00097 } 00098 if (right != NULL) { 00099 assert(left != 0); //check whether convention is obeyed 00100 typename Map::iterator it = map_log_op_to_phy_op_.find(right); 00101 if (it != map_log_op_to_phy_op_.end()) 00102 right_op = it->second; 00103 } 00104 00105 TypedOperatorPtr phy_op_ptr = ptr->getOptimalOperator(left_op, right_op, ptr->getDeviceConstraint()); 00106 map_log_op_to_phy_op_[ptr] = phy_op_ptr; 00107 root_ = phy_op_ptr; //update root (only important thing that the correct root node is stored in here at the end, when get funcion is called) 00108 if (chopped) { 00109 phy_op_ptr->run(); 00110 } 00111 } 00112 00113 } 00114 00115 TypedOperatorPtr root_; 00116 //maps logical to physical operator 00117 Map map_log_op_to_phy_op_; 00118 }; 00119 00120 template <typename Type> 00121 class LogicalQueryPlan { 00122 public: 00123 typedef Type NodeElementType; 00124 typedef typename OperatorMapper_Helper_Template<Type>::Physical_Operator_Map Physical_Operator_Map; 00125 typedef typename OperatorMapper_Helper_Template<Type>::TypedOperatorPtr TypedOperatorPtr; 00126 typedef typename OperatorMapper_Helper_Template<Type>::TypedNodePtr TypedNodePtr; 00127 typedef typename OperatorMapper_Helper_Template<Type>::PhysicalQueryPlanPtr PhysicalQueryPlanPtr; 00128 00129 LogicalQueryPlan(TypedNodePtr root) : root_(root) { 00130 root_->setLevel(0); 00131 //set the tree level of each node appropriately 00132 traverse(assign_treelevel_NodePtr_functor()); 00133 //set the parent pointer of eachnode appropriately 00134 traverse(init_parent_NodePtr_functor()); 00135 } 00136 00137 const PhysicalQueryPlanPtr convertToPhysicalQueryPlan() { 00138 Construct_Physical_Query_Plan_functor<Type> functor = reverse_traverse(Construct_Physical_Query_Plan_functor<Type>()); 00139 TypedOperatorPtr root = functor.getRootOperator(); 00140 PhysicalQueryPlanPtr ptr(new PhysicalQueryPlan<Type>(root)); 00141 return ptr; 00142 } 00143 00144 const PhysicalQueryPlanPtr runChoppedPlan() { 00145 double begin = double(hype::core::getTimestamp()); 00146 Construct_Physical_Query_Plan_functor<Type> functor = query_chopping_traversal(Construct_Physical_Query_Plan_functor<Type>()); 00147 TypedOperatorPtr root = functor.getRootOperator(); 00148 PhysicalQueryPlanPtr ptr(new PhysicalQueryPlan<Type>(root)); 00149 ptr->setTimeNeeded(double( hype::core::getTimestamp()) - begin); 00150 return ptr; 00151 } 00152 00153 template<class UnaryFunction> 00154 UnaryFunction traverse(UnaryFunction f) { 00155 00156 std::list<TypedNodePtr> queue; 00157 00158 if (root_.get() == NULL) return f; 00159 00160 queue.push_back(root_); 00161 00162 while (!queue.empty()) { 00163 TypedNodePtr currentNode = queue.front(); 00164 queue.pop_front(); //delete first element 00165 00166 if (currentNode.get() != NULL) { 00167 TypedNodePtr left = boost::static_pointer_cast<typename TypedNodePtr::element_type > (currentNode->getLeft()); 00168 TypedNodePtr right = boost::static_pointer_cast<typename TypedNodePtr::element_type > (currentNode->getRight()); 00169 00170 f(currentNode); 00171 00172 if (left.get() != NULL) { 00173 queue.push_back(left); 00174 } 00175 if (right.get() != NULL) { 00176 queue.push_back(right); 00177 } 00178 00179 } 00180 00181 } 00182 00183 return f; 00184 } 00185 00186 template<class UnaryFunction> 00187 UnaryFunction query_chopping_traversal(UnaryFunction f) { 00188 chop(&f, root_); 00189 return f; 00190 } 00191 00192 template<class UnaryFunction> 00193 static void chop(UnaryFunction *f, TypedNodePtr nodePtr) { 00194 TypedNodePtr left = boost::static_pointer_cast<typename TypedNodePtr::element_type > (nodePtr->getLeft()); 00195 TypedNodePtr right = boost::static_pointer_cast<typename TypedNodePtr::element_type > (nodePtr->getRight()); 00196 if (left != NULL && right != NULL) { 00197 boost::thread t1(boost::bind(&LogicalQueryPlan<Type>::chop<UnaryFunction>, f, left)); 00198 boost::thread t2(boost::bind(&LogicalQueryPlan<Type>::chop<UnaryFunction>, f, right)); 00199 t1.join(); 00200 t2.join(); 00201 } else if (left != NULL) { 00202 chop(f, left); 00203 } 00204 (*f)(nodePtr, true); 00205 } 00206 00207 template<class UnaryFunction> 00208 UnaryFunction reverse_traverse(UnaryFunction f) { 00209 00210 std::list<TypedNodePtr> queue = this->getLevelOrder(); 00211 queue.reverse(); 00212 //process in reverse level order 00213 typename std::list<TypedNodePtr>::iterator it; 00214 for (it = queue.begin(); it != queue.end(); ++it) { 00215 f(*it); 00216 } 00217 00218 return f; 00219 } 00220 00221 template<class UnaryFunction> 00222 UnaryFunction traverse_inorder(UnaryFunction f, TypedNodePtr node) { 00223 if (!node) return f; 00224 00225 traverse_inorder(f, boost::dynamic_pointer_cast<typename TypedNodePtr::element_type > (node->getLeft())); 00226 f(node); 00227 traverse_inorder(f, boost::dynamic_pointer_cast<typename TypedNodePtr::element_type > (node->getRight())); 00228 return f; 00229 } 00230 00231 template<class UnaryFunction> 00232 UnaryFunction traverse_inorder(UnaryFunction f) { 00233 return traverse_inorder(f, root_); 00234 } 00235 00236 std::list<TypedNodePtr> getLevelOrder() { 00237 std::list<TypedNodePtr> queue; 00238 std::list<TypedNodePtr> result_queue; 00239 00240 if (root_.get() == NULL) return result_queue; 00241 00242 queue.push_back(root_); 00243 result_queue.push_back(root_); 00244 00245 while (!queue.empty()) { 00246 TypedNodePtr currentNode = queue.front(); 00247 queue.pop_front(); //delete first element 00248 00249 if (currentNode.get() != NULL) { 00250 TypedNodePtr left = boost::static_pointer_cast<typename TypedNodePtr::element_type > (currentNode->getLeft()); 00251 TypedNodePtr right = boost::static_pointer_cast<typename TypedNodePtr::element_type > (currentNode->getRight()); 00252 //f(currentNode); 00253 00254 if (left.get() != NULL) { 00255 queue.push_back(left); 00256 result_queue.push_back(left); 00257 } 00258 if (right.get() != NULL) { 00259 queue.push_back(right); 00260 result_queue.push_back(right); 00261 } 00262 00263 } 00264 00265 } 00266 return result_queue; 00267 } 00268 00269 template<class UnaryFunction> 00270 UnaryFunction traverse_preorder(UnaryFunction f) { 00271 std::stack<TypedNodePtr> nodeStack; 00272 TypedNodePtr curr = root_; 00273 while (true) { 00274 if (curr.get() != NULL) { 00275 00276 f(curr); 00277 00278 nodeStack.push(curr); 00279 curr = boost::static_pointer_cast<typename TypedNodePtr::element_type > (curr->getLeft()); 00280 continue; 00281 } 00282 if (!nodeStack.size()) { 00283 return f; 00284 } 00285 curr = nodeStack.top(); 00286 nodeStack.pop(); 00287 curr = boost::static_pointer_cast<typename TypedNodePtr::element_type > (curr->getRight()); 00288 } 00289 return f; 00290 } 00291 00292 void print() { 00293 00294 traverse_preorder(print_NodePtr_functor()); 00295 00296 } 00297 00298 private: 00299 TypedNodePtr root_; 00300 00301 }; 00302 00303 }; //end namespace queryprocessing 00304 }; //end namespace hype