| // ********************************************************************** |
| // @@@ START COPYRIGHT @@@ |
| // |
| // Licensed to the Apache Software Foundation (ASF) under one |
| // or more contributor license agreements. See the NOTICE file |
| // distributed with this work for additional information |
| // regarding copyright ownership. The ASF licenses this file |
| // to you under the Apache License, Version 2.0 (the |
| // "License"); you may not use this file except in compliance |
| // with the License. You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, |
| // software distributed under the License is distributed on an |
| // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| // KIND, either express or implied. See the License for the |
| // specific language governing permissions and limitations |
| // under the License. |
| // |
| // @@@ END COPYRIGHT @@@ |
| // ********************************************************************** |
| |
| // *********************************************************************** |
| // |
| // File: QRJoinGraph.h |
| // Description: |
| // |
| // |
| // |
| // |
| // Created: 12/11/07 |
| // *********************************************************************** |
| |
| // _MEMSHAREDPTR;_MEMCHECK |
| |
| |
| |
| #include "NABasicObject.h" |
| #include "NAString.h" |
| #include "Collections.h" |
| #include "Int64.h" |
| #include "QRSharedPtr.h" |
| #include "QRDescriptor.h" |
| |
| class JoinGraphTable; |
| class JoinGraphHalfPredicate; |
| class JoinGraphEqualitySet; |
| class QRJoinGraph; |
| class QRJoinSubGraph; |
| class QRJoinSubGraphMap; |
| |
| #ifdef _MEMSHAREDPTR |
| typedef QRIntrusiveSharedPtr<JoinGraphTable> JoinGraphTablePtr; |
| typedef QRIntrusiveSharedPtr<JoinGraphHalfPredicate> JoinGraphHalfPredicatePtr; |
| typedef QRIntrusiveSharedPtr<JoinGraphEqualitySet> JoinGraphEqualitySetPtr; |
| typedef QRIntrusiveSharedPtr<QRJoinGraph> QRJoinGraphPtr; |
| typedef QRIntrusiveSharedPtr<QRJoinSubGraph> QRJoinSubGraphPtr; |
| typedef QRIntrusiveSharedPtr<QRJoinSubGraphMap> QRJoinSubGraphMapPtr; |
| #else |
| typedef JoinGraphTable* JoinGraphTablePtr; |
| typedef JoinGraphHalfPredicate* JoinGraphHalfPredicatePtr; |
| typedef JoinGraphEqualitySet* JoinGraphEqualitySetPtr; |
| typedef QRJoinGraph* QRJoinGraphPtr; |
| typedef QRJoinSubGraph* QRJoinSubGraphPtr; |
| typedef QRJoinSubGraphMap* QRJoinSubGraphMapPtr; |
| #endif |
| |
| typedef NAPtrList<JoinGraphHalfPredicatePtr> HalfPredicateList; |
| typedef NAPtrList<JoinGraphEqualitySetPtr> EqualitySetList; |
| typedef NAPtrList<JoinGraphTablePtr> JoinGraphTableList; |
| typedef NAPtrArray<JoinGraphTablePtr> JoinGraphTableArray; |
| typedef NASubArray<JoinGraphTablePtr> JoinGraphTableSubArray; |
| typedef NAPtrList<QRJoinSubGraphPtr> SubGraphList; |
| typedef NAPtrList<QRJoinSubGraphMapPtr> SubGraphMapList; |
| |
| typedef SharedPtrValueHash<const NAString, JoinGraphTable> JoinGraphTableHash; |
| typedef SharedPtrValueHashIterator<const NAString, JoinGraphTable> JoinGraphTableHashIterator; |
| typedef SharedPtrValueHash<const NAString, QRJoinSubGraph> SubGraphHash; |
| typedef SharedPtrValueHashIterator<const NAString, QRJoinSubGraph> SubGraphHashIterator; |
| |
| #ifndef _QRJOINGRAPH_H_ |
| #define _QRJOINGRAPH_H_ |
| |
| enum OperationType { OP_INSERT = 0, OP_SEARCH, OP_INSERT_TOP }; |
| |
| #include "QmsMVDetails.h" |
| #include "QmsMVCandidate.h" |
| #include "QmsSelfJoinHandler.h" |
| |
| |
| /** |
| * A JoinGraphTable is a node in the join graph. |
| * It holds the table name, its descriptor ID, and pointers to predicates. |
| * The ordinal number of a table is its index into the QRJoinGraph table array. |
| * The temp number is used when building the MVMemo hash key. |
| * |
| * @see QRJoinGraph |
| * @see JoinGraphHalfPredicate |
| * @see JoinGraphEqualitySet |
| * @see QRJoinSubGraph |
| ***************************************************************************** |
| */ |
| class JoinGraphTable : public NAIntrusiveSharedPtrObject |
| { |
| public: |
| |
| /** |
| * Public constructor. |
| * @param num The ordinal number - the index of this table into the QRJoinGraph table array. |
| * @param tableElement Table element from the descriptor. |
| * @param heap Heap from which to allocate internal data members. |
| */ |
| JoinGraphTable(CollIndex num, |
| const QRTablePtr tableElement, |
| NABoolean isHub, |
| const BaseTableDetailsPtr baseTable, |
| ADD_MEMCHECK_ARGS_DECL(CollHeap* heap)) |
| : NAIntrusiveSharedPtrObject(ADD_MEMCHECK_ARGS_PASS(heap)) |
| ,ordinalNumber_(num) |
| ,tempNumber_(-1) |
| ,keyColumns_(0) |
| ,reducedConnections_(0) |
| ,tableElement_(tableElement) |
| ,isHub_(isHub) |
| ,baseTable_(baseTable) |
| ,predList_(heap) |
| ,name_(tableElement->getTableName()) |
| ,isSelfJoinTable_(FALSE) |
| {} |
| |
| virtual ~JoinGraphTable() {} |
| |
| NABoolean operator==(const JoinGraphTable& other) |
| { |
| return ordinalNumber_ == other.ordinalNumber_; |
| } |
| |
| /** Get the ordinal number - the index into the QRJoinGraph table array. */ |
| CollIndex getOrdinalNumber() const { return ordinalNumber_; } |
| /** Get the temp number - used when building the MVMemo hash key. */ |
| Int32 getTempNumber() const { return tempNumber_; } |
| /** Get the table name. */ |
| const NAString& getName() const { return tableElement_->getTableName(); } |
| /** Get the table element ID from the MV/query descriptor. */ |
| const NAString& getID() const { return tableElement_->getID(); } |
| /** Get the table element from the descriptor. */ |
| const QRTablePtr getTableElement() const { return tableElement_; } |
| |
| const BaseTableDetailsPtr getBaseTable() const { return baseTable_; } |
| |
| NABoolean isHub() const { return isHub_; }; |
| |
| /** Get the list of equality sets involving this table. */ |
| const EqualitySetList& getEqualitySets() { return predList_; } |
| |
| /** Set the table's ordinal number. Used after the QRJoinGraph table array is re-ordered. */ |
| void setOrdinalNumber(CollIndex ix) { ordinalNumber_ = ix; } |
| /** Set the table's temp number. Used when marking the table during generation of a sub-graph.*/ |
| void setTempNumber(Int32 ix) { tempNumber_ = ix; } |
| |
| /** Add an equality set. */ |
| void addEqualitySet(JoinGraphEqualitySetPtr pred) |
| { |
| predList_.insert(pred); |
| } |
| |
| /** Remove an equality set. */ |
| void removeEqualitySet(JoinGraphEqualitySetPtr pred) |
| { |
| predList_.remove(pred); |
| } |
| |
| /** Clear the table's equality sets list. */ |
| void clearEqualitySets() { predList_.clear(); } |
| |
| /** Add a line with this table's information to the graphical join graph in the output parameter string. */ |
| void dumpGraph(NAString& to); |
| |
| /** Is this table directly connected to the sub-graph? */ |
| NABoolean isConnectedTo(const QRJoinSubGraphPtr subGraph) const; |
| |
| /** Find an equality set from the ones this table is connected to, that match otherHalfPred, which is from a different join graph. */ |
| JoinGraphEqualitySetPtr getEqSetUsing(JoinGraphHalfPredicatePtr otherHalfPred); |
| |
| /** Check if predicates on this table are on its key columns. */ |
| NABoolean checkPredsOnKey(CollHeap* heap); |
| |
| void reduceConnection() |
| { |
| reducedConnections_++; |
| } |
| |
| NABoolean isOnTheEdge(); |
| |
| void setSelfJoinTable() |
| { |
| isSelfJoinTable_ = TRUE; |
| } |
| |
| NABoolean isSelfJoinTable() |
| { |
| return isSelfJoinTable_; |
| } |
| |
| void getAndReducePredicateColumnsPointingToMe(ElementPtrList& pointingCols); |
| |
| Int32 getDegree(); |
| |
| private: |
| // Copy construction/assignment not defined. |
| JoinGraphTable(const JoinGraphTable&); |
| JoinGraphTable& operator=(const JoinGraphTable&); |
| |
| private: |
| /** Index into the QRJoinGraph table array. */ |
| CollIndex ordinalNumber_; |
| /** Used when building the MVMemo hash key. */ |
| Int32 tempNumber_; |
| /** Used for indirect GroupBy detection */ |
| CollIndex keyColumns_; |
| CollIndex reducedConnections_; |
| /** 3-part name of the table. */ |
| const NAString& name_; |
| /** Pointer to table element from the descriptor. */ |
| const QRTablePtr tableElement_; |
| /** Is this a hub table? */ |
| NABoolean isHub_; |
| /** List of equi-join predicates involving this table. */ |
| EqualitySetList predList_; |
| /** A pointer to this table's BaseTableDetails object. */ |
| const BaseTableDetailsPtr baseTable_; |
| /** Does the join graph contain more than one instance of this table? */ |
| NABoolean isSelfJoinTable_; |
| }; // class JoinGraphTable |
| |
| /** |
| * A "Half Predicate" is an expression that can be found in either side |
| * of the equal sign in an equi-join predicate. It holds an expression |
| * text and a pointer to a table that includes all the columns used by |
| * the expression. The expression is typically a name of a single column, |
| * but if it is more complex, all the columns it uses must be of the same |
| * table. |
| * |
| * @see QRJoinGraph |
| * @see JoinGraphTable |
| * @see JoinGraphEqualitySet |
| * @see QRJoinSubGraph |
| ***************************************************************************** |
| */ |
| class JoinGraphHalfPredicate : public NAIntrusiveSharedPtrObject |
| { |
| public: |
| /** |
| * Public constructor. |
| * @param tablePtr The table this half-pred is pointing to. |
| * @param expr The half-pred expression (or column name). |
| * @param id The element ID from the MV/query descriptor. |
| * @param heap Heap from which to allocate internal data members. |
| */ |
| JoinGraphHalfPredicate(const JoinGraphTablePtr tablePtr, |
| const QRElementPtr elementPtr, |
| const NAString& expr, |
| ADD_MEMCHECK_ARGS_DECL(CollHeap* heap)) |
| : NAIntrusiveSharedPtrObject(ADD_MEMCHECK_ARGS_PASS(heap)) |
| ,tablePtr_(tablePtr) |
| ,elementPtr_(elementPtr) |
| ,expr_(expr, heap) |
| {} |
| |
| /** Get the table this half-pred is pointing to. */ |
| const JoinGraphTablePtr getTable() const { return tablePtr_; } |
| /** Get the half-pred expression. */ |
| const NAString& getExpr() const { return expr_; } |
| /** Get the descriptor ID. */ |
| const NAString& getID() const { return elementPtr_->getID(); } |
| /** Get the descriptor element */ |
| const QRElementPtr getElementPtr() const { return elementPtr_; } |
| |
| /** |
| * Match this halfPred to other, which is from a different join graph. |
| * Match only the expression text, not the destination table. |
| * @param other The halfPred from the other join graph. |
| * @return TRUE if matching, FALSE otherwise. |
| */ |
| NABoolean match(JoinGraphHalfPredicatePtr other) const |
| { |
| return getExpr() == other->getExpr(); |
| } |
| |
| private: |
| // Copy construction/assignment not defined. |
| JoinGraphHalfPredicate(const JoinGraphHalfPredicate&); |
| JoinGraphHalfPredicate& operator=(const JoinGraphHalfPredicate&); |
| |
| private: |
| const JoinGraphTablePtr tablePtr_; |
| const NAString expr_; |
| const QRElementPtr elementPtr_; |
| }; // class JoinGraphHalfPredicate |
| |
| /** |
| * An equality set is a list of "half predicates", that are all declared |
| * as equal by the query's equi-join predicates. |
| * |
| * @see QRJoinGraph |
| * @see JoinGraphTable |
| * @see JoinGraphHalfPredicate |
| * @see QRJoinSubGraph |
| ***************************************************************************** |
| */ |
| class JoinGraphEqualitySet : public NAIntrusiveSharedPtrObject |
| { |
| public: |
| /** |
| * Public constructor. |
| * @param id The equi-join predicate element ID from the MV/query descriptor. |
| * @param heap Heap from which to allocate internal data members. |
| */ |
| JoinGraphEqualitySet(const NAString& id, |
| ADD_MEMCHECK_ARGS_DECL(CollHeap* heap)) |
| : NAIntrusiveSharedPtrObject(ADD_MEMCHECK_ARGS_PASS(heap)) |
| ,halfPreds_(heap) |
| ,descriptorID_(id, heap) |
| ,maxExprSize_(0) |
| // ,tempNumber_(-1) |
| ,isOnKey_(FALSE) |
| ,keyDirection_(0) |
| {} |
| |
| virtual ~JoinGraphEqualitySet() |
| { |
| // Delete all the half preds. |
| JoinGraphHalfPredicatePtr pred; |
| while (halfPreds_.entries() > 0) |
| { |
| CollIndex last = halfPreds_.entries()-1; |
| pred = halfPreds_[last]; |
| halfPreds_.removeAt(last); |
| deletePtr(pred); |
| pred = NULL; |
| } |
| } |
| |
| /** Get the descriptor ID. */ |
| const NAString& getID() { return descriptorID_; } |
| /** Get the list of half-preds in this equality set. */ |
| HalfPredicateList& getHalfPredicates() { return halfPreds_; } |
| |
| // Temp numbers are not used for now, because equality set lines |
| // in the MVMemo hash key are not numbered. This may change... |
| // int getTempNumber() { return tempNumber_; } |
| // void setTempNumber(int ix) { tempNumber_ = ix; } |
| |
| /** Add a half-pred to the equality set. */ |
| void addHalfPredicate(JoinGraphHalfPredicatePtr pred) |
| { |
| halfPreds_.insert(pred); |
| |
| // Maintain the size of the longest column/expression. |
| if (pred->getExpr().length() > maxExprSize_) |
| maxExprSize_ = pred->getExpr().length(); |
| } |
| |
| /** |
| * Union this and other equality sets by adding all the half preds |
| * from other into this, and remove them from other. |
| */ |
| void addHalfPredicatesFrom(JoinGraphEqualitySetPtr other); |
| |
| /** |
| * Is this equality set part of the current subgraph? |
| * @return TRUE if this subgraph has at least two half-predicates |
| * that are part of the subgraph, that is, have a tempNumber other |
| * than -1. |
| */ |
| NABoolean isInCurrentSubGraph(); |
| |
| /** |
| * Generate the MVMemo hash key line for this equality set: |
| * \par |
| * 1. Collect the list of half predicates on participating tables.\par |
| * 2. Format them as <table-temp-number>.<column-name/expression> \par |
| * 3. Sort them. \par |
| * 4. Generate a single line in the format: <tt>{1.CUSTOMER_ID,2.ORDERED_BY}</tt> \par |
| * The result is returned in an NAString object allocated off the heap. |
| * @return the formatted hash key line. |
| */ |
| NAString* getHashKeyLine(CollHeap* heap); |
| |
| /** |
| * Is this equality set directly connected to the sub-graph. |
| */ |
| NABoolean isConnectedTo(const QRJoinSubGraphPtr subGraph) const; |
| |
| /** |
| * Find the halfPred pointing to sourceTable (must be from the same join graph). |
| */ |
| const JoinGraphHalfPredicatePtr findHalfPredTo(const JoinGraphTablePtr sourceTable) const; |
| |
| /** |
| * Sets this equality set as a join predicate on a key column of the target table. |
| * @param targetTable |
| */ |
| void setOnKeyTo(const JoinGraphTablePtr targetTable); |
| |
| /** |
| * Is this equality set a joinpredicate on the target table's key column? |
| * @param targetTable |
| * @return |
| */ |
| NABoolean isOnKeyTo(const JoinGraphTablePtr targetTable); |
| |
| /** |
| * Get the other table involved in this equality set, that is not the one |
| * involved in the given half-pred. |
| * @param target |
| * @return |
| */ |
| JoinGraphTablePtr getOtherTable(JoinGraphHalfPredicatePtr target); |
| |
| /** |
| * Get the half pred that is on the other side - not on key. |
| * @return |
| */ |
| JoinGraphHalfPredicatePtr getForeignKeySide(); |
| |
| /** |
| * The degree of the equality set is the number of join preds it covers. |
| * Since a join pred is from one table to all other tables in the equality set, |
| * the degree is equal to the number of halfPreds minus one. |
| * @return |
| */ |
| Int32 getDegree() |
| { |
| return halfPreds_.entries() - 1; |
| } |
| |
| Int32 getKeySource() |
| { |
| if (keyDirection_ == 0) |
| return 1; |
| else |
| return 0; |
| } |
| |
| /** |
| * Prepare the input text for the Dotty graphical graph viewer for this |
| * equality set. |
| * @param[out] to Output string. |
| */ |
| void dumpGraph(NAString& to); |
| |
| private: |
| // Copy construction/assignment not defined. |
| JoinGraphEqualitySet(const JoinGraphEqualitySet&); |
| JoinGraphEqualitySet& operator=(const JoinGraphEqualitySet&); |
| |
| private: |
| HalfPredicateList halfPreds_; |
| const NAString descriptorID_; |
| UInt32 maxExprSize_; |
| // int tempNumber_; |
| NABoolean isOnKey_; |
| Int32 keyDirection_; |
| }; // class JoinGraphEqualitySet |
| |
| /** |
| * A join graph is a graph of tables and equi-join predicates, corresponding |
| * to a JBB of an MV or query. |
| * The nodes of the graph are the tables and the equality sets, while the |
| * edges are the half predicates. |
| * The QRJoinGraph class encapsulates the methods for building the graph |
| * from the descriptor classes, while the traversal of the graph is the |
| * responsibility of the HubIterator class. |
| * |
| * @see JoinGraphTable |
| * @see JoinGraphHalfPredicate |
| * @see JoinGraphEqualitySet |
| * @see QRJoinSubGraph |
| * @see HubIterator |
| ***************************************************************************** |
| */ |
| class QRJoinGraph : public NAIntrusiveSharedPtrObject |
| { |
| friend class QRJoinSubGraph; |
| |
| public: |
| /** |
| * Public constructor. |
| * @param heap Heap from which to allocate internal data members. |
| */ |
| QRJoinGraph(ADD_MEMCHECK_ARGS_DECL(CollHeap* heap)) |
| : NAIntrusiveSharedPtrObject(ADD_MEMCHECK_ARGS_PASS(heap)) |
| ,heap_(heap) |
| ,nextTable_(0) |
| ,isSelfJoin_(FALSE) |
| ,tableHashByID_(hashKey, INIT_HASH_SIZE_SMALL, TRUE, heap) |
| ,equalitySets_(heap) |
| ,tableArray_(heap, 10) |
| ,name_(heap) |
| ,hasGroupBy_(FALSE) |
| ,hubSize_(0) |
| ,tablesToReduce_(heap_) |
| ,minimizedSubGraph_(NULL) |
| ,sortedTables_(NULL) |
| ,pos_(0) |
| {} |
| |
| virtual ~QRJoinGraph(); |
| |
| // Accessors |
| //////////////////// |
| |
| /** Does this join graph include more than one instance of any table? */ |
| NABoolean isSelfJoin() { return isSelfJoin_; } |
| /** Get the heap pointer. */ |
| CollHeap* getHeap() { return heap_; } |
| /** How many tables are included in this join graph? (For self-joins, individual instances are counted) */ |
| CollIndex entries() { return tableArray_.entries(); } |
| /** Mark that this join graph includes a GROUP BY node. */ |
| void setGroupBy() { hasGroupBy_ = TRUE; } |
| /** Does this join graph include a GROUP BY node at the top? */ |
| NABoolean hasGroupBy() { return hasGroupBy_; } |
| /** How many tables are in the hub? */ |
| Int32 getHubSize() const { return hubSize_; } |
| |
| /** |
| * Find the JoinGraphTable object from the table ID. |
| * @param id The descriptor ID of the table. |
| * @return Pointer to JoinGraphTablePtr object. |
| */ |
| JoinGraphTablePtr getTableByID(const NAString& id) |
| { |
| return tableHashByID_.getFirstValue(&id); |
| } |
| |
| /** Find an equality set using its descriptor ID. */ |
| JoinGraphEqualitySetPtr FindEqualitySetByID(const NAString& id); |
| |
| /** |
| * Find the JoinGraphTable object from the table's ordinal number. |
| * @param ix The table's ordinal number - its index into the QRJoinGraph table array. |
| * @return Pointer to JoinGraphTablePtr object. |
| */ |
| JoinGraphTablePtr getTableByOrdinal(CollIndex ix) |
| { |
| return tableArray_[ix]; |
| } |
| |
| /** |
| * Get the list of equality sets in this join graph. |
| */ |
| EqualitySetList& getEqualitySets() { return equalitySets_; } |
| |
| /** |
| * Get the number of tables in this join graph. |
| * @return |
| */ |
| CollIndex getNumberOfTables() |
| { |
| return nextTable_; |
| } |
| |
| JoinGraphTableList& getTablesToReduce() |
| { |
| return tablesToReduce_; |
| } |
| |
| QRJoinSubGraphPtr getMinimizedSubGraph() |
| { |
| return minimizedSubGraph_; |
| } |
| |
| // Graph construction methods |
| ///////////////////////////////// |
| |
| /** |
| * Add a table to the join graph. |
| * @param tableElement A table element from the descriptor. |
| */ |
| void addTable(const QRTablePtr tableElement, |
| NABoolean isHub, |
| const BaseTableDetailsPtr baseTable); |
| |
| /** |
| * Add a half-pred to the join graph. |
| * @param equalitySet Pointer to the equality set object. |
| * @param tablePtr Pointer to the table object. |
| * @param expr The half-pred expression. |
| * @param id The descriptor ID of the new half-pred. |
| */ |
| void addHalfPredicate(JoinGraphEqualitySetPtr equalitySet, |
| JoinGraphTablePtr tablePtr, |
| const QRElementPtr elementPtr, |
| const NAString& expr); |
| |
| /** |
| * Add an equality set to the join graph from the descriptor data. |
| * @param predElement The descriptor element for the new equality set. |
| */ |
| void addEqualitySet(const QRJoinPredPtr predElement); |
| |
| /** |
| * Analyze a JBB element from the descriptor, and build the entire join graph from it. |
| * @param jbb |
| */ |
| void initFromJBB(const QRJBBPtr jbb, MVDetailsPtr mv); |
| |
| /** |
| * Reset the temp numbers of all tables to -1 before starting a new traversal of the join graph. |
| */ |
| void resetTempNumbers(); |
| |
| /** A heuristic method for finding a good table to start a connected graph walk. */ |
| JoinGraphTablePtr getFirstTable(); |
| /** Find a table that is connected to the subgraph, but not yet part of it. */ |
| JoinGraphTablePtr getNextTable(QRJoinSubGraphPtr subGraph); |
| |
| // Debugging stuff |
| //////////////////// |
| |
| /** Set a name to the join graph for the graphical representation. */ |
| void setName(const NAString& name) { name_ = name; } |
| /** Get the name of the join graph. */ |
| const NAString& getName() { return name_; } |
| /** Create a graphical representation of the join graph by using the DOT language. */ |
| void dumpGraph(MVDetailsPtr mv); |
| |
| private: |
| void shiftTable(CollIndex insertPos); |
| CollIndex shiftArray(const NAString name); |
| |
| private: |
| // Copy construction/assignment not defined. |
| QRJoinGraph(const QRJoinGraph&); |
| QRJoinGraph& operator=(const QRJoinGraph&); |
| |
| private: |
| CollHeap* heap_; |
| Int32 nextTable_; |
| NABoolean isSelfJoin_; |
| JoinGraphTableHash tableHashByID_; |
| EqualitySetList equalitySets_; |
| JoinGraphTableArray tableArray_; |
| NAString name_; // For debugging |
| NABoolean hasGroupBy_; |
| Int32 hubSize_; |
| JoinGraphTableList tablesToReduce_; |
| QRJoinSubGraphPtr minimizedSubGraph_; |
| JoinGraphTableList* sortedTables_; // Used for WA SQL generation |
| UInt32 pos_; |
| }; // class QRJoinGraph |
| |
| /** |
| * A QRJoinSubGraph includes a subset of the tables of its parent join graph |
| * and all the equality sets that include at least two half-predicates on |
| * these tables. |
| * for loop sample use: |
| * QRJoinSubGraph sg; |
| * for(sg.reset(); sg.hasNext(); sg.advance()) ... getCurrent()... |
| * |
| * @see QRJoinGraph |
| * @see JoinGraphTable |
| * @see JoinGraphHalfPredicate |
| * @see JoinGraphEqualitySet |
| * @see HubIterator |
| ***************************************************************************** |
| */ |
| class QRJoinSubGraph : public NAIntrusiveSharedPtrObject |
| { |
| public: |
| /** |
| * Public constructor. |
| * @param parent A pointer to the join graph this subgraph is a part of. |
| * @param heap Heap from which to allocate internal data members. |
| */ |
| QRJoinSubGraph(QRJoinGraphPtr parent, ADD_MEMCHECK_ARGS_DECL(CollHeap* heap)) |
| : NAIntrusiveSharedPtrObject(ADD_MEMCHECK_ARGS_PASS(heap)) |
| ,parentGraph_(parent) |
| ,subArray_(&parent->tableArray_, heap) |
| ,graphHashKey_(heap) |
| ,pos_(0) |
| ,isSelfJoin_(FALSE) |
| ,hasGroupBy_(FALSE) |
| ,stillUsed_(FALSE) |
| ,fastKey_(heap) |
| ,selfJoinHandler_(NULL) |
| {} |
| |
| /** |
| * Copy construction IS defined for this class. |
| */ |
| QRJoinSubGraph(const QRJoinSubGraph& other, ADD_MEMCHECK_ARGS_DECL(CollHeap* heap)) |
| : NAIntrusiveSharedPtrObject(ADD_MEMCHECK_ARGS_PASS(heap)) |
| ,parentGraph_(other.parentGraph_) |
| ,subArray_(other.subArray_) |
| ,graphHashKey_(heap) |
| ,pos_(0) |
| ,isSelfJoin_(other.isSelfJoin_) |
| ,hasGroupBy_(other.hasGroupBy_) |
| ,stillUsed_(FALSE) |
| ,fastKey_(heap) |
| ,selfJoinHandler_(NULL) |
| {} |
| |
| virtual ~QRJoinSubGraph() |
| {} |
| |
| // Mutators |
| |
| /** Add a table to the join subgraph. */ |
| void addTable(JoinGraphTablePtr table); |
| |
| /** Remove a table from this join subgraph. */ |
| void removeTable(JoinGraphTablePtr table); |
| |
| /** Add all the tables in the join graph to this subgraph. */ |
| void addAllTables(); |
| |
| /** Does this subgraph contain that table? */ |
| NABoolean contains(JoinGraphTablePtr table) |
| { |
| return subArray_.contains(table->getOrdinalNumber()); |
| } |
| |
| /** Return the pointer to the parent JoinGraph. */ |
| QRJoinGraphPtr getParentGraph() |
| { |
| return parentGraph_; |
| } |
| |
| /** equals operator. */ |
| NABoolean operator==(const QRJoinSubGraph& other) |
| { |
| return subArray_ == other.subArray_ && |
| hasGroupBy_ == other.hasGroupBy_; |
| } |
| |
| void updateTables(const QRJoinSubGraphPtr other) |
| { |
| subArray_ = other->subArray_; |
| } |
| |
| /** Mark that this subgraph includes a GROUP BY node. */ |
| void setGroupBy() |
| { |
| hasGroupBy_ = TRUE; |
| graphHashKey_ = ""; // Invalidate hash key. |
| fastKey_ = ""; // Invalidate hash key. |
| } |
| |
| /** Does this subgraph include a GROUP BY node? */ |
| NABoolean hasGroupBy() { return hasGroupBy_; } |
| |
| // Mark that this subGraph is being used for the rewrite instructions |
| void setStillUsed(NABoolean used) |
| { stillUsed_ = used; } |
| NABoolean stillUsed() |
| { return stillUsed_; } |
| |
| /** |
| * Compute the MVMemo hash key for the contained sub-graph. |
| * @return the hash key text. |
| */ |
| const QRJoinSubGraphMapPtr getSubGraphMap(OperationType op); |
| |
| // Methods for iterating over the contained tables |
| /////////////////////////////////////////////////////// |
| void reset() { pos_ = 0; } |
| NABoolean hasNext() { return subArray_.nextUsedFast(pos_); } |
| void advance() { pos_++; } |
| JoinGraphTablePtr getCurrent() { return subArray_.element(pos_); } |
| CollIndex entries() { return subArray_.entries(); } |
| |
| /** |
| * Calculate the "fastKey" - a quick internal hash key based on the used tables |
| * and groupby flag. Internal means that it uses the table IDs, so can only |
| * be used for comparisons on the same descriptor. |
| */ |
| void calcFastKey(); |
| |
| /** |
| * Get the FastKey hash string. |
| * @return |
| */ |
| const NAString* getFastKey() |
| { |
| // If we have not already calculated the fastKey, do it now. |
| if (fastKey_ == "") |
| calcFastKey(); |
| |
| return &fastKey_; |
| } |
| |
| /** |
| * Is the subGraph using all the hub tables in the full join graph? |
| * @return |
| */ |
| NABoolean isFull() const |
| { |
| return subArray_.entries() == parentGraph_->getHubSize() && |
| hasGroupBy_ == parentGraph_->hasGroupBy(); |
| } |
| |
| /** |
| * Does this subgraph contain a self-join? |
| * @return |
| */ |
| NABoolean isSelfJoin() |
| { |
| return isSelfJoin_; |
| } |
| |
| void setSelfJoin() |
| { |
| isSelfJoin_ = TRUE; |
| } |
| |
| /** |
| * |
| * @return |
| */ |
| SelfJoinHandlerPtr getSelfJoinHandler() |
| { |
| return selfJoinHandler_; |
| } |
| |
| void doEqualitySetsPart(NAString& hashKey) const; |
| |
| protected: |
| void doTablesPart(NAString& hashKey, QRJoinSubGraphMapPtr map); |
| |
| // Assignment NOT defined for this class. |
| QRJoinSubGraph& operator=(const QRJoinSubGraph&); |
| |
| private: |
| QRJoinGraphPtr parentGraph_; |
| JoinGraphTableSubArray subArray_; |
| NAString graphHashKey_; |
| CollIndex pos_; |
| NABoolean isSelfJoin_; |
| NABoolean hasGroupBy_; |
| NABoolean stillUsed_; |
| NAString fastKey_; |
| SelfJoinHandlerPtr selfJoinHandler_; |
| }; // class QRJoinSubGraph |
| |
| /** |
| * |
| * |
| * |
| * |
| * |
| */ |
| class QRJoinSubGraphMap : public NAIntrusiveSharedPtrObject |
| { |
| public: |
| /** |
| * Public constructor. |
| * @param parent A pointer to the join graph this subgraph is a part of. |
| * @param heap Heap from which to allocate internal data members. |
| */ |
| QRJoinSubGraphMap(QRJoinSubGraphPtr subGraph, NABoolean isMV, CollIndex size, |
| ADD_MEMCHECK_ARGS_DECL(CollHeap* heap)) |
| : NAIntrusiveSharedPtrObject(ADD_MEMCHECK_ARGS_PASS(heap)) |
| ,subGraph_(subGraph) |
| ,hashKey_(heap) |
| ,tableMapping_(heap, size) |
| ,indexHashByID_(hashKey, INIT_HASH_SIZE_SMALL, TRUE, heap) // Pass NAString::hashKey |
| ,isMV_(isMV) |
| ,mvDetails_(NULL) |
| ,isACopy_(FALSE) |
| ,shiftVector_(heap) |
| { |
| subGraph->setStillUsed(TRUE); |
| } |
| |
| // Copy Ctor. |
| QRJoinSubGraphMap(const QRJoinSubGraphMap& other, ADD_MEMCHECK_ARGS_DECL(CollHeap* heap)); |
| |
| virtual ~QRJoinSubGraphMap(); |
| |
| void addTable(CollIndex ix, const JoinGraphTablePtr table); |
| |
| /** |
| * The query side translation: find the hash key index for a particular table. |
| * @param id The query descriptor ID of the table. |
| * @return The query hash key index, -1 if not found. |
| */ |
| Int32 getIndexForTable(const NAString& id) const; |
| |
| /** |
| * The MV side translation: find the table information for its index. |
| * @param ix The table index in the MV hash key. |
| * @return Pointer to the table information. |
| */ |
| const JoinGraphTablePtr getTableForIndex(CollIndex ix) const; |
| |
| /** |
| * Is the subGraph using all the tables in the full joinn graph? |
| * @return |
| */ |
| NABoolean isFull() const |
| { |
| return subGraph_->isFull(); |
| } |
| |
| void setHashKey(const NAString& key) |
| { |
| hashKey_ = key; |
| } |
| |
| const NAString& getHashKey() |
| { |
| return hashKey_; |
| } |
| |
| QRJoinSubGraphPtr getSubGraph() |
| { |
| return subGraph_; |
| } |
| |
| NABoolean contains(const NAString& id) |
| { |
| return indexHashByID_.contains(&id); |
| } |
| |
| void setMVDetails(MVDetailsPtr mv) |
| { |
| mvDetails_ = mv; |
| } |
| |
| MVDetailsPtr getMVDetails() const |
| { |
| return mvDetails_; |
| } |
| |
| /** Does this subgraph include a GROUP BY node? */ |
| NABoolean hasGroupBy() { return subGraph_->hasGroupBy(); } |
| |
| // Self-Joins |
| /////////////////// |
| |
| /** |
| * Does the join subgraph this map is based on include more than |
| * a single instance of any of its tables? |
| */ |
| NABoolean isSelfJoin() |
| { |
| return subGraph_->isSelfJoin(); |
| // Return FALSE here in order to disable SelfJoin handling. |
| //return FALSE; |
| } |
| |
| void prepareForSelfJoinWork(); |
| |
| /** |
| * Does the last subgraph have an equivalent MVMemo hash key for its self-join? |
| */ |
| NABoolean hasNextEquivalentMap() const; |
| |
| /** |
| * Get the next equivalent MVMemo hash key for the current self-join subgraph. |
| */ |
| QRJoinSubGraphMapPtr nextEquivalentMap() const; |
| |
| const NAString& getShiftVector() |
| { |
| return shiftVector_; |
| } |
| |
| void restoreTempNumbers() const; |
| |
| private: |
| class UnsignedInteger : public NABasicObject |
| { |
| public: |
| // Default constructor |
| UnsignedInteger() |
| : data_(0) |
| {} |
| |
| UnsignedInteger(CollIndex data) |
| : data_(data) |
| {} |
| |
| virtual ~UnsignedInteger() |
| {} |
| |
| // Copy construction |
| UnsignedInteger(const UnsignedInteger& other) |
| : data_(other.data_) |
| {} |
| |
| // Assignment operator |
| UnsignedInteger& operator=(const UnsignedInteger& other) |
| { data_ = other.data_; return *this; } |
| |
| NABoolean operator==(const UnsignedInteger& other) |
| { return data_ == other.data_; } |
| |
| CollIndex getInt() |
| { return data_; } |
| |
| private: |
| CollIndex data_; |
| }; // Internal class UnsignedInteger |
| |
| typedef NAHashDictionary<const NAString, UnsignedInteger> IndexHash; |
| typedef NAHashDictionaryIterator<const NAString, UnsignedInteger> IndexHashIterator; |
| |
| QRJoinSubGraphPtr subGraph_; |
| NAString hashKey_; |
| JoinGraphTableArray tableMapping_; |
| IndexHash indexHashByID_; |
| NABoolean isMV_; |
| MVDetailsPtr mvDetails_; |
| NABoolean isACopy_; // Was this object created using the copy constructor? |
| NAString shiftVector_; // For debugging only. |
| }; // class QRJoinSubGraphMap |
| |
| /** |
| * Takes a join graph, generates a stream of unique subgraphs of it, and |
| * produces the hash keys of those subgraphs. |
| * For now, Produces only connected subgraphs - graphs with cross products |
| * are not handled yet. |
| * Has two modes of operation: for insert and search operations in MVMemo. |
| * |
| * @see QRJoinGraph |
| * @see QRJoinSubGraph |
| * @see MVMemo |
| * \todo Produce equivalent expressions for self-joins. |
| * \todo Produce more expressions for join graphs with circular join predicates. |
| ***************************************************************************** |
| */ |
| class HubIterator : public NAIntrusiveSharedPtrObject |
| { |
| public: |
| /** |
| * Public constructor. |
| * @param joinGraph The join graph to iterate on. |
| * @param isForInsert Operation mode: insert or search? |
| * @param heap Heap from which to allocate internal data members. |
| */ |
| HubIterator(QRJoinGraphPtr joinGraph, |
| OperationType isForInsert, |
| ADD_MEMCHECK_ARGS_DECL(CollHeap* heap)) |
| : NAIntrusiveSharedPtrObject(ADD_MEMCHECK_ARGS_PASS(heap)) |
| ,joinGraph_(joinGraph) |
| ,opType_(isForInsert) |
| ,subGraphsVisited_(hashKey, INIT_HASH_SIZE_LARGE, FALSE, heap) |
| ,subGraphsReady_(heap, 100) |
| ,subGraphsToAvoid_(hashKey, INIT_HASH_SIZE_LARGE, FALSE, heap) |
| ,currentSubgraph_(NULL) |
| ,usedGroupBy_(FALSE) |
| {} |
| |
| virtual ~HubIterator(); |
| |
| /** |
| * There are probably more results if there are still more subgraphs in |
| * the ready list. Its only probably true because the remaining subgraphs |
| * may be duplicates. However, if this method returns FALSE, then its final. |
| */ |
| NABoolean hasNext() |
| { |
| assertLogAndThrow(CAT_MVMEMO_JOINGRAPH, LL_MVQR_FAIL, |
| subGraphsVisited_.entries() > 0, QRLogicException, |
| "This method should not be called before trying any subgraphs."); |
| |
| // Check if we have subgraphs to work on. |
| if (subGraphsReady_.entries() > 0) |
| return TRUE; |
| |
| // Did we check the top subgraph with the GroupBy flag yet? |
| if (joinGraph_->hasGroupBy() && !usedGroupBy_) |
| return TRUE; |
| |
| return FALSE; |
| } |
| |
| /** |
| * Initialize the iterator: populate the ready list with all the single-table |
| * subgraphs of the join graph. |
| */ |
| void init(); |
| |
| /** |
| * Return the next subgraph to search/insert. |
| */ |
| const QRJoinSubGraphPtr nextSubGraph(); |
| |
| const QRJoinSubGraphPtr getMinimizedSubGraph(); |
| |
| /** |
| * Computes the supersets of subGraph that include a single additional table |
| * that is conneted to it, and add them to the ready list. \par |
| * 1. For each table included in the subgraph, find all the connected tables |
| * that are not yet part of the subgraph, and add them to a set of |
| * unique entries. \par |
| * 2. For each of the tables in the resulting set, create a new subgraph from |
| * the current subgraph plus that table, and add it to the ready list. \par |
| * @param subGraph The current subgraph. |
| */ |
| void getNextLevelSupersets(QRJoinSubGraphPtr subGraph); |
| |
| /** |
| * The current join graph uses an MV as one of its tables. |
| * Rewrite the join graph to use the MVs query instead. |
| */ |
| void rewriteJoinGraph(const MVDetailsPtr mvDetails) {} |
| |
| /** |
| * During a search operation, report that the current subgraph was not found |
| * in MVMemo, and so it and its supersets should be avoided. |
| */ |
| void reportAsMissing(); |
| |
| /** |
| * Does this join graph have too many self-joins? |
| * @return |
| */ |
| NABoolean isSelfJoinTooBig(); |
| |
| /** |
| * Create a subGraph for the full join graph. |
| * @return |
| */ |
| const QRJoinSubGraphPtr getFullSubGraph(); |
| |
| private: |
| // Copy construction/assignment not defined. |
| HubIterator(const HubIterator&); |
| HubIterator& operator=(const HubIterator&); |
| |
| private: |
| // Max threshold for self-join permutation work. |
| // If the join graph is more complex than this, MVMemo will skip self-join work. |
| // and only same order queries will be matched. |
| // Biggest Yotta query I've seen is 4x4x2 = 1,152 |
| // At 8x2 > 80,000 we run out of memory and crash. |
| // 6000 allows for a 5x4x2 self-join (5760). |
| enum { MAX_SELFJOIN_PERMUTATIONS = 6000 }; |
| |
| QRJoinGraphPtr joinGraph_; |
| OperationType opType_; |
| |
| /** This hash table remembers every subgraph we tried. Used to detect duplicates. */ |
| SubGraphHash subGraphsVisited_; |
| |
| /** The ready list contains subgraphs that are ready to be tested. */ |
| SubGraphList subGraphsReady_; |
| |
| /** Subgraphs that were not found in MVMemo during search, and so they and their supersets should be skipped. */ |
| SubGraphHash subGraphsToAvoid_; |
| |
| /** The last subgraph that was returned. */ |
| QRJoinSubGraphPtr currentSubgraph_; |
| |
| // Did the iterator already produce the subgraph with the GROUP BY node? |
| NABoolean usedGroupBy_; |
| }; // class HubIterator |
| |
| |
| #endif |