Column-oriented GPU-accelerated Database Management System
CoGaDB
/home/sebastian/gpudbms/trunk/hype-library/include/query_processing/logical_query_plan.hpp
Go to the documentation of this file.
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines