core/sql/qms/QmsMVMemo.h

// **********************************************************************
// @@@ 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:         MVMemo.h
 * Description:  Implementation of the MVMemo data structure for matching 
 *               a query JBB to JBBs of candidate MVs.
 *
 * Created:      12/04/07
 ***********************************************************************/

// _MEMSHAREDPTR;_MEMCHECK

#ifndef _MVMEMO_H_
#define _MVMEMO_H_


#include "NABasicObject.h"
#include "NAString.h"
#include "Collections.h"
#include "QRSharedPtr.h"
#include "QRDescriptor.h"

class MVMemo;
class MVMemoExpression;
class MVMemoLogicalExpression;
class MVMemoPhysicalExpression;
class MVMemoGroup;
class HubIterator;

#ifdef _MEMSHAREDPTR
typedef QRIntrusiveSharedPtr<MVMemo>			MVMemoPtr;
typedef QRIntrusiveSharedPtr<MVMemoLogicalExpression>	MVMemoLogicalExpressionPtr;
typedef QRIntrusiveSharedPtr<MVMemoPhysicalExpression>	MVMemoPhysicalExpressionPtr;
typedef QRIntrusiveSharedPtr<MVMemoGroup>		MVMemoGroupPtr;
typedef QRIntrusiveSharedPtr<HubIterator>		HubIteratorPtr;
#else
typedef MVMemo*			  MVMemoPtr;
typedef MVMemoLogicalExpression*  MVMemoLogicalExpressionPtr;
typedef MVMemoPhysicalExpression* MVMemoPhysicalExpressionPtr;
typedef MVMemoGroup*		  MVMemoGroupPtr;
typedef HubIterator*		  HubIteratorPtr;
#endif

// !!! These collection types do NOT inherit from NAIntrusiveSharedPtrObject themselves!!!
typedef NAPtrList<MVMemoGroupPtr>				             MVMemoGroupList;
typedef SharedPtrValueHash<const NAString, MVMemoLogicalExpression>          MVMemoExpressionHash;
typedef SharedPtrValueHashIterator<const NAString, MVMemoLogicalExpression>  MVMemoExpressionHashIterator;
typedef SharedPtrValueHash<const NAString, MVMemoPhysicalExpression>         GroupExpressionHash;
typedef SharedPtrValueHashIterator<const NAString, MVMemoPhysicalExpression> GroupExpressionHashIterator;

#include "QmsJoinGraph.h"
#include "QmsMVCandidate.h"
#include "QmsGroupLattice.h"
#include "QmsWorkloadAnalysis.h"


/**
 * Class MVMemoLogicalExpression
 * Implements an MVMemo logical expression
 * @see MVMemoPhysicalExpression
 * @see MVMemoGroup
 * @see MVMemo
 *****************************************************************************
 */
class MVMemoLogicalExpression : public NAIntrusiveSharedPtrObject
{
public:
  /**
   * Class constructor
   * @param key The hash key for the new expression.
   * @param groupNumber The group number this expression will belong to
   */
  MVMemoLogicalExpression(const NAString& key, Int32 groupNumber, ADD_MEMCHECK_ARGS_DECL(CollHeap* heap))
    : NAIntrusiveSharedPtrObject(ADD_MEMCHECK_ARGS_PASS(heap))
     ,hashKey_(key, heap)
     ,groupNumber_(groupNumber)
  {}

  virtual ~MVMemoLogicalExpression() {}

  NABoolean operator==(const MVMemoLogicalExpression& other)
  {
    return !hashKey_.compareTo(other.hashKey_); 
  }

  /**
   * Virtual method for checking if an MVMemo expression is physical.
   * @return FALSE
   */
  virtual NABoolean isPhysical() { return FALSE; }

  /**
   * @return the group number 
   */
  Int32 getGroupNumber() { return groupNumber_; }

  /**
   * @return the hash key
   */
  const NAString& getHashKey() { return hashKey_; }

private:
    // Copy construction/assignment not defined.
    MVMemoLogicalExpression(const MVMemoLogicalExpression&);
    MVMemoLogicalExpression& operator=(const MVMemoLogicalExpression&);

private:
  const NAString  hashKey_;
  const Int32	  groupNumber_;
};  // class MVMemoLogicalExpression


/**
 * Class MVMemoPhysicalExpression
 * Implements an MVMemo physical expression.
 * Stores an MVDetails object of a matching candidate MV.
 * @see MVMemoLogicalExpression
 * @see MVMemoGroup
 * @see MVMemo
 *****************************************************************************
 */
class MVMemoPhysicalExpression : public MVMemoLogicalExpression
{
public:

  /**
   * Class constructor
   * @param key The hash key for the new expression.
   * @param groupNumber The group number this expression will belong to
   * @param mv The name of the MV.
   */
  MVMemoPhysicalExpression(const QRJoinSubGraphMapPtr map, 
			   Int32 groupNumber, 
			   const MVDetailsPtr mv, 
			   ADD_MEMCHECK_ARGS_DECL(CollHeap* heap));

  virtual ~MVMemoPhysicalExpression();

  /**
   * Virtual method for checking if an MVMemo expression is physical.
   * @return TRUE - override superclass implementation.
   */
  virtual NABoolean isPhysical() { return TRUE; }

  /**
   * 
   * @return the details of the MV
   */
  const MVDetailsPtr getMVDetails() { return mv_; }

  /**
   * 
   * @return the name of the MV
   */
  const NAString& getMVName();

  /**
   * 
   * @return 
   */
  const QRJoinSubGraphMapPtr getMvSubGraphMap()
  {
    return map_;
  }

private:
  // Copy construction/assignment not defined.
  MVMemoPhysicalExpression(const MVMemoPhysicalExpression&);
  MVMemoPhysicalExpression& operator=(const MVMemoPhysicalExpression&);

private:
  const MVDetailsPtr	      mv_;
  const QRJoinSubGraphMapPtr  map_;
}; // class MVMemoPhysicalExpression

/**
 * Class MVMemoGroup
 * Includes a list of logical expressions and a list of physical expressions.
 * Every group has a unique group number.
 * @see MVMemoLogicalExpression
 * @see MVMemoPhysicalExpression
 * @see MVMemo
 *****************************************************************************
 */
class MVMemoGroup : public NAIntrusiveSharedPtrObject
{
public:
 /**
  * Class constructor
  * @param number The MVMemo group number
  * @param heap A heap pointer for internal allocations.
  */
  MVMemoGroup(Int32 number, ADD_MEMCHECK_ARGS_DECL(CollHeap* heap))
    : NAIntrusiveSharedPtrObject(ADD_MEMCHECK_ARGS_PASS(heap))
     ,groupNumber_(number)
     ,logicalExprs_(heap)
     ,physicalExprsHash_(hashKey, INIT_HASH_SIZE_SMALL, TRUE, heap) // Pass NAString::hashKey
     ,groupLattice_(NULL)
     ,tempExpr_(NULL)
  {}

  /**
   * Class destructor
   */
  virtual ~MVMemoGroup() 
  {
    if (groupLattice_)
      deletePtr(groupLattice_);
  }

  /**
   * @return The group number.
   */
  Int32 getGroupNumber()
  {
    return groupNumber_;
  }

  /**
   * Does this group have any physical expressions in it?
   */
  NABoolean hasPhysicalExpressions()
  {
    return (physicalExprsHash_.entries() > 0);
  }

 /**
  * Add the MVs in this group to the list of candidates so far.
  */
  void getPhysicalExpressions(MVCandidatesForJBBPtr   candidateList, 
			      QRJoinSubGraphMapPtr    querySubGraphMap,
			      QRJBBPtr		      jbb,
			      CollHeap*		      heap, 
			      NABoolean		      isPreferredMatch,
                              ElementPtrList*         minimizedGroupingList);

 /**
  * Add a logical expression to the group's list of logical expressions.
  * @param expr The logical expression to add.
  */
  MVMemoLogicalExpressionPtr addLogicalExpression(const NAString& key, 
						  ADD_MEMCHECK_ARGS_DECL(CollHeap* heap));

 /**
  * Add a physical expression to the group's list of physical expressions.
  */
  NABoolean addPhysicalExpression(const QRJoinSubGraphMapPtr     map, 
			          const MVDetailsPtr		 mv, 
			          const QRJBBPtr		 jbb,
			          NABoolean			 hasGroupby,
			          ADD_MEMCHECK_ARGS_DECL(CollHeap* heap));

  /**
   * Remove a physical expression for an MV that has been dropped.
   * @param key The hash key for the MV to remove.
   */
  void removePhysicalExpression(MVMemoPhysicalExpressionPtr expr);

  /**
   * 
   * @param name 
   * @return 
   */
  QRJoinSubGraphMapPtr getSubGraphMapForMV(const NAString& name)
  {
    MVMemoPhysicalExpressionPtr expr = physicalExprsHash_.getFirstValue(&name);
    assertLogAndThrow(CAT_MVMEMO_JOINGRAPH, LL_MVQR_FAIL,
                  expr != NULL, QRLogicException, 
		  "An MV found by GroupLattice must be in physical expression list.");
    return expr->getMvSubGraphMap();
  }

  /**
   * 
   * @param name 
   * @return 
   */
  void dropMV(const NAString& name);

  /**
   * Start renaming an MV being pointed to by this Group.
   * @param oldName 
   * @return 
   */
  void startRenameMV(const NAString& oldName);

  /**
   * Finish renaming an MV being pointed to by this Group.
   * @return 
   */
  void FinishRenameMV();

  /**
   * Set the pointer to the next step of matching algorithm, to further
   * reduce the number of candidate MVs.
   * @param next Pointer to next matching data structure.
   */
  void setGroupLattice(QRGroupLatticePtr lattice) 
  { 
    groupLattice_ = lattice; 
  }

  /**
   * Get the pointer to the next step of matching algorithm, to further
   * reduce the number of candidate MVs.
   * @return Pointer to next matching data structure.
   */
  QRGroupLatticePtr getGroupLattice() 
  { 
    return groupLattice_; 
  }

  Int32 getNumOfMVs();

  void reportStats(NAString& text);

  /**
   * Collect data on query (MV) groups with shared join+GroupBy.
   */
  void collectMVGroups(WorkloadAnalysisPtr workload, Int32 minQueriesPerMV, CollHeap* heap);

private:
    // Copy construction/assignment not defined.
    MVMemoGroup(const MVMemoGroup&);
    MVMemoGroup& operator=(const MVMemoGroup&);

private:
  const Int32				  groupNumber_;
  NAPtrList<MVMemoLogicalExpressionPtr>   logicalExprs_;
  GroupExpressionHash			  physicalExprsHash_;
  QRGroupLatticePtr			  groupLattice_;
  MVMemoPhysicalExpressionPtr             tempExpr_;
};  // class MVMemoGroup

/**
 * Main class of the MVMemo data structure.
 * Implements the insert and search methods.
 * @see MVMemoLogicalExpression
 * @see MVMemoPhysicalExpression
 * @see MVMemoGroup
 * @see HubIterator
 *****************************************************************************
 */
class MVMemo : public NAIntrusiveSharedPtrObject
{
public:
  /**
   * Class constructor
   * @param heap Heap from which to allocate internal objects.
   * @return 
   */
  MVMemo(ADD_MEMCHECK_ARGS_DECL(CollHeap* heap))
    : NAIntrusiveSharedPtrObject(ADD_MEMCHECK_ARGS_PASS(heap))
      ,heap_(heap)
      ,expressionHash_(hashKey, INIT_HASH_SIZE_LARGE, TRUE, heap) // Pass NAString::hashKey
      ,groupsArray_(heap, 100)
      ,nextGroup_(0)
  {}

  /**
   * Class destructor
   * \todo - Delete the lists.
   */
  virtual ~MVMemo();

  void insert(QRJBBPtr jbb, MVDetailsPtr mv);

  void search(QRJBBPtr jbb, MVCandidatesForJBBPtr candidateList, CollHeap* heap);

  HubIteratorPtr createHubIteratorForJBB(const QRJBBPtr jbb, MVDetailsPtr mv, OperationType op, CollHeap* heap);

  /**
   * Get the group with the specified number.
   */
  MVMemoGroupPtr getGroup(Int32 number)
  {
    assertLogAndThrow(CAT_MVMEMO_JOINGRAPH, LL_MVQR_FAIL,
                      number < nextGroup_, QRLogicException, 
		      "Invalid MVMemo group number.");
    return groupsArray_[number];
  }

  /**
   * Allocate a new MVMemo group, and insert it into the MVMemo group array.
   * @return A pointer to the new group.
   */
  MVMemoGroupPtr allocateNewGroup()
  {
    MVMemoGroupPtr newGroup = new(heap_) 
      MVMemoGroup(nextGroup_++, ADD_MEMCHECK_ARGS(heap_));
    groupsArray_.insertAt(newGroup->getGroupNumber(), newGroup);
    return newGroup;
  }

  /**
   * Does MVMemo already contain a group with the specified hash key?
   * @param  key Hash key of group.
   * @return TRUE if found, FALSE otherwise.
   */
  NABoolean contains(const NAString& key) 
  { 
    return expressionHash_.contains(&key); 
  }

  /**
   * Get the logical or physical expression with the specified hash key.
   * @param key Hash key of expression
   * @return Pointer to found expression.
   */
  MVMemoLogicalExpressionPtr getExpression(const NAString& key)
  {
    return expressionHash_.getFirstValue(&key);
  }

  /**
   * Insert the specified expression into the expression hash table.
   * @param expr 
   */
  void insertExpression(MVMemoLogicalExpressionPtr expr)
  {
    expressionHash_.insert(&expr->getHashKey(), expr);
  }

  NABoolean handleInsertedSubgraph(QRJoinSubGraphMapPtr map, 
                                   QRJBBPtr jbb, 
                                   MVDetailsPtr mv,
                                   NABoolean& isDuplicate);

  MVMemoGroupPtr probeForSubGraph(HubIteratorPtr hubIterator, 
                                  const QRJoinSubGraphMapPtr map);

  /**
   * Report usage statistics to the log file.
   */
  void reportStats(Int32 numOfMVs);

  /**
   * Collect data on query (MV) groups with shared join+GroupBy.
   */
  void collectMVGroups(WorkloadAnalysisPtr workload, Int32 minQueriesPerMV, CollHeap* heap);

private:
    // Copy construction/assignment not defined.
    MVMemo(const MVMemo&);
    MVMemo& operator=(const MVMemo&);

private:
  CollHeap*		      heap_;             // Heap pointer from which to allocate internal objects.
  MVMemoExpressionHash	      expressionHash_;   // Hash table of logical and physical expressions.
  NAPtrArray<MVMemoGroupPtr>  groupsArray_;      // Array of groups in MVMemo.
  Int32			      nextGroup_;        // Index of the next group to be inserted.
};  // class MVMemo

/**
 * A helper class for performing the Indirect GroupBy minimization algorithm.
 * The algorithm is trying to push the GroupBy node down through the join, by
 * reducing tables to which the join is done on a unique key. 
 * Grouping columns from this table are transformed to the foreign key columns
 * of the joining table.
 * Reduced tables must have no aggregate functions on them.
 *****************************************************************************
 */
class GroupingListMinimizer : public NAIntrusiveSharedPtrObject
{
public:
  /**
   * Class constructor
   * @param heap Heap from which to allocate internal objects.
   * @return 
   */
  GroupingListMinimizer(const QRJBBPtr jbb, 
                        const QRJoinSubGraphMapPtr map,
                        ADD_MEMCHECK_ARGS_DECL(CollHeap* heap));
 
  /**
   * Class destructor
   */
  virtual ~GroupingListMinimizer()
  {}

  ElementPtrList* calcIndirectGroupingList();

protected:
  typedef NAHashDictionary<const NAString, ElementPtrList>         PartitionedGroupingList;
  typedef NAHashDictionaryIterator<const NAString, ElementPtrList> PartitionedGroupingListIterator;

  NABoolean verifyAggregateFunctions();
  void addGroupingCol(QRElementPtr groupingCol);
  void partitionGroupingList();
  void reduceTable(JoinGraphTablePtr table);
  NABoolean verifyTablesWereReduced();
  ElementPtrList* prepareResult();
  NABoolean isReducedTable(const NAString& tableID);
  void dumpResult(ElementPtrList* result);

private:
  const ElementPtrList&    fullGroupingList_;
  PartitionedGroupingList  partitionedGroupingList_;
  JoinGraphTableList       tablesToReduce_;
  QROutputListPtr          outputs_;
  CollHeap*		   heap_;
};  // class GroupingListMinimizer

#endif // _MVMEMO_H_