core/sql/optimizer/mdamkey.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 @@@
**********************************************************************/
#ifndef _MDAMKEY_H
#define _MDAMKEY_H
/* -*-C++-*-
 *****************************************************************************
 *
 * File:         mdamkey.h
 * Description:  Handling of disjuncts and costing for mdam
 * Code location: mdam.C
 *
 * Created:      //96
 * Language:     C++
 *
 *
 *
 *
 *****************************************************************************
 */

// -----------------------------------------------------------------------

#include "mdam.h"
#include "disjuncts.h"
#include "keycolumns.h"
#include "NABasicObject.h"
#include "IndexDesc.h"

// -----------------------------------------------------------------------
// Class ScanKey
// A ScanKey is an abstract class that represents a set of
// of subsets to be read from an index file.
// A ScanKey is logically an array of "key disjuncts",
// each key disjunct containing a set of key predicates.
// These key predicates may be accessed through a data structure
// called OrderColumnList (see method getKeyPredicatesByColumn).
//
// The predicates of the key disjuncts, when applied to the index
// table may give raise to several subsets. It is the responsability
// of the derived class to enforce the semantics of the key disjunct
// generation (for example, the key disjunct generation for
// the SearchKey guarantees that the key disjunct represents a single
// subset)
//
// Classes SearchKey (a single subset) and MdamKey (multiple subsets)
// inherit from ScanKey.
// -----------------------------------------------------------------------

// class Key contains common procedures and declarations
// for MdamKey and SearchKey
class ScanKey : public NABasicObject
{
public:
  // -----------------------------------------------------------------------
  // the nonKeyColumnSet is used by the SearchKey when it is
  // computing the key for an index desc and it is trying to decide
  // whether to replicate the keys in the executor predicates.
  // It should be an empty set for the case when search key is used
  // to compute the partitioning key.
  // -----------------------------------------------------------------------
  
  ScanKey(
       const ValueIdList& keyColumnIdList
       ,const ValueIdSet& operatorInputs
       ,const Disjuncts& associatedDisjuncts
       ,const ValueIdSet& nonKeyColumnSet
       ,const IndexDesc * indexDesc
       ,const IndexDesc * UDindexDesc = NULL
       ) :
       keyColumnIdList_(keyColumnIdList)
    ,associatedDisjuncts_(associatedDisjuncts)
    ,operatorInputs_(operatorInputs)
    ,nonKeyColumnSet_(nonKeyColumnSet)
    ,iDesc_(indexDesc)
    ,udiDesc_(UDindexDesc)
  {}


  // -----------------------------------------------------------------------
  // Accessors:
  // -----------------------------------------------------------------------

  const IndexDesc * getIndexDesc() const
  { return iDesc_; }

  const IndexDesc * getUDIndexDesc() const
  { return udiDesc_; }

  const ValueIdSet& getExecutorPredicates() const
  { return executorPredicates_; }

  void setExecutorPredicates(const ValueIdSet& executorPredicates)
          { executorPredicates_ = executorPredicates; }                                                       

  // get the number of key disjuncts for this key (the key must
  // have at least one disjunct)
  virtual CollIndex getKeyDisjunctEntries() const = 0;

  // Obtain the key predicates (hashed by column order)
  // in the key disjunct:
  virtual void getKeyPredicatesByColumn(
       ColumnOrderList& keyPredsByCol, /*out*/
       CollIndex disjunctNumber = 0) const = 0;

  // Obtain the set of key predicates in the disjunct:
  virtual void getKeyPredicates(ValueIdSet &keyPredicates, /* out */
			NABoolean * allKeyPredicates = NULL,/*out*/
                        CollIndex disjunctNumber = 0 /*in*/) const;


  const ValueIdSet& getNonKeyColumnSet() const
  { return nonKeyColumnSet_; }

  const ValueIdSet getAllColumnsReferenced() const;

  // -----------------------------------------------------------------------
  // isAKeyPredicate()
  // 
  // A predicate is eligible to be used for searching an index when it
  // satisfies the following requirements:
  // 1) It should be a unary, binary, or ternary comparison predicate.
  // 2) One of the key columns must be a child of the root of the
  //    predicate tree.
  // 3) If the predicate performs binary or ternary comparison, the operand
  //    that is compared with the key column must be a value 
  //    belonging to the external inputs.
  // 4) If the predicate performs a ternary comparison, in addition to
  //    3), the extra inclusion indicator must also be an external input.
  //  
  // Parameters:
  //
  // const ValueId &  predId
  //    IN : A read-only reference to the ValueId of the predicate
  //         to be analyzed.
  //
  //
  // ValueId & referencedInput
  //    OUT: The ValueId of the expression that belongs to externalInputs
  //         and is compared with the keyColumn in the predicate.
  //         It may be set to the NULL_VALUE_ID for an IS NULL predicate.
  //
  // ValueId & intervalExclusionExpr
  //    OUT: The value id of a boolean expression that indicates that
  //         the decision whether the predicate is an exclusive or inclusive
  //         key predicate is made at run time. It is set to NULL_VALUE_ID
  //         if this decision can be made at compile time.
  //
  // Return value
  //    OUT: TRUE  If the given predicate can be used as a key on
  //               a key column
  //         FALSE Otherwise
  //
  // -----------------------------------------------------------------------

  NABoolean isAKeyPredicate(const ValueId & predId,
                            ValueId & referencedInput,
                            ValueId & intervalExclusionExpr) const;
  
  // same semantics as above, but the caller does not need the
  // referenced input nor the interval exclusion ptr
  NABoolean isAKeyPredicate(const ValueId& predId) const;

  // same semantics as above for detecting key predicates
  // but we need to make sure that the predicate is a key pred
  // for the column
  // for instance, for key columns A,B and the pred:
  // VegRef{A,2} = VegRef{C}
  // the pred is a key pred. However, it is not a key pred for A.
  NABoolean
  isAKeyPredicateForColumn(
       const ValueId & predId
       ,ValueId & referencedInput
       ,ValueId & intervalExclusionExpr
       ,const ValueId& keyColumn
       ) const;

  static NABoolean
  isAKeyPredicateForColumn(
       const ValueId & predId
       ,ValueId & referencedInput
       ,ValueId & intervalExclusionExpr
       ,const ValueId& keyColum
       ,const ValueIdSet& inputValues);

  NABoolean
  isAKeyPredicateForColumn(
       const ValueId& predId
       ,const ValueId& keyColumn) const;

  static void createComputedColumnPredicates(
       ValueIdSet &predicates,           /* in/out */
       const ValueIdSet &keyColumns,     /* in */
       const ValueIdSet &operatorInputs, /* in */
       ValueIdSet &generatedPredicates   /* out */);
  
  // -----------------------------------------------------------------------
  // Put those key predicates in keyPredicates that need to be
  // replicated in replicatedKeyPredicates:
  // -----------------------------------------------------------------------
  void
  replicateNonKeyVEGPredicates(
     const ValueIdSet& keyPredicates,
     ValueIdSet& replicatedKeyPredicates /* out */
     ) const;

  // -----------------------------------------------------------------------
  // Mutators:
  // -----------------------------------------------------------------------
  
  // Generate the data structures needed by the generator and
  // rewrite VEG preds and predicates:
  virtual void preCodeGen(ValueIdSet& executorPredicates,
			  const ValueIdSet& selectionPredicates,
			  const ValueIdSet & availableValues,
			  const ValueIdSet & inputValues,
			  VEGRewritePairs * vegPairsPtr,
			  NABoolean replicateExpression = FALSE,
                          NABoolean partKeyPredsAdded = FALSE) = 0;

  

  const ValueIdList& getKeyColumns() const
  { return keyColumnIdList_; }

  const Disjuncts& getDisjuncts() const
  { return associatedDisjuncts_ ; } 


  const ValueIdSet& getOperatorInputs() const
  { return operatorInputs_; }

protected:

  // -----------------------------------------------------------------------
  // Accessors:
  // -----------------------------------------------------------------------

  // get the selection predicates in MDNF for this key:

  // construct a key column order from the given set:
  void getKeyColumnOrderList(ColumnOrderList& keyPredsByCol, /* out*/
			     const ValueIdSet& predSet) const;


  static NABoolean expressionContainsColumn(
       const ItemExpr& iePtr
       ,const ValueId& keyColumn
       );

  // This is a quick fix:
  void splitRangeSpecRef(ColumnOrderList& keyPredsByCol,
			 const ValueId& predId,
			 const ValueIdList& columns,
			 NABoolean firstElemInRangeSpec,
			 const ValueId& predIdRange) const;    

  const ValueIdSet& getOperatorInputs() { return operatorInputs_;}


  // -----------------------------------------------------------------------
  // Mutators:
  // -----------------------------------------------------------------------

  
private:
  const IndexDesc  *iDesc_;
  const IndexDesc  *udiDesc_;
  const ValueIdList keyColumnIdList_;
  const ValueIdSet nonKeyColumnSet_;
  const ValueIdSet operatorInputs_;
  const Disjuncts& associatedDisjuncts_;
  ValueIdSet executorPredicates_;

}; // class ScanKey

//-------------------------------------------------------------
// An MdamKey contains different states at different
// times in the optimizer.
//
// Before optimization it contains data to generate
// state for a mdam key with all columns sparse and
// all stop columns set to the maximum order.
//
// After optimization, if the MdamKey survives (i.e.
// if a SingleSubset key was not chosen) the
// MdamKey may contain a mix. of sparse/dense
// columns and not all of the stop columns will be
// set to the max (this is chosen by costing)
//
// After pre-code generation, a data structure
// called OrderListPtrArray is created. It contains
// An array of key predicates ordered by key column.
// There is one entry of this array for each disjunct
// present if the MdamKey was generated from the associated
// disjuncts. There will be a single array entry, corresponding
// to the common predicates of the associated disjuncts, if the
// MdamKey was generated from the common predicates.
// Also in this phase VEG predicates and references are
// rewritten and executor predicates are generated.
//
// After code generation an Mdam Network is generated from
// the OrderListPtrArray.
//
//--------------------------------------------------------------


class MdamKey : public ScanKey
{
public:
  MdamKey(
       const ValueIdList& keyColumnIdList
       ,const ValueIdSet& operatorInputs
       ,const Disjuncts& associatedDisjuncts
       ,const ValueIdSet& nonKeyColumnSet
       ,const IndexDesc * indexDesc
       );
  ~MdamKey();



  // Return the number of disjuncts that were created
  // out of the selection predicates:
  virtual CollIndex getKeyDisjunctEntries() const;

  // returns the key predicates in those disjuncts
  virtual void getKeyPredicatesByColumn(
       ColumnOrderList& keyPredsByCol, /*out*/
       CollIndex disjunctNumber = 0) const;

  
  void setNoExePred(NABoolean v = TRUE){ noExePred_= v; }

  NABoolean getNoExePred(){ return noExePred_;}
    
  
  CollIndex getStopColumn(CollIndex disjunctNumber) const;

  // TRUE means that column is sparse, else it is dense
  NABoolean getSparseFlag(CollIndex columnOrder) const;

  NABoolean isColumnSparse(CollIndex columnOrder) const
  { return getSparseFlag(columnOrder); }
  NABoolean isColumnDense(CollIndex columnOrder) const
  { return NOT isColumnSparse(columnOrder); }
  

  void setAllStopColumnsToMax(); // all stop columns are the highest
  void setAllColumnsToSparse(); // all columns are sparse
  
  void setStopColumn(CollIndex disjunctNumber,
		     CollIndex columnOrder);
  void setSparseFlag(CollIndex columnOrder, NABoolean isSparse);

  void setColumnToDense(CollIndex columnOrder)
  { setSparseFlag(columnOrder,FALSE); }

  void setColumnToSparse(CollIndex columnOrder)
  { setSparseFlag(columnOrder,TRUE); }
  
  // This function copies information from 'other' MDAM key
  // to the current MDAM key: stop columns, starse keys and
  // noExePred. It is used to share this information when
  // saving and reusing BasicCost for MDAM key.
  void reuseMdamKeyInfo(MdamKey * other);

  // ---------------------------------
  // ---- Pre-code generation interface:
  // ---------------------------------
  // Pre-code gen materializes the columnorderlist
  // and rewrites the predicates.
  // It also computes the executor predicates:
  void preCodeGen(ValueIdSet& executorPredicates,
		  const ValueIdSet& selectionPredicates,
		  const ValueIdSet & availableValues,
		  const ValueIdSet & inputValues,
		  VEGRewritePairs * vegPairsPtr,
		  NABoolean replicateExpression = FALSE,
                  NABoolean partKeyPredsAdded = FALSE);
  

  // ---------------------------------
  // ---- Generator interface:
  // ---------------------------------
  const ColumnOrderListPtrArray& getColumnOrderListPtrArray() const; 

  
  // -----------------------------------------------------------------------
  // Utility functions:
  // -----------------------------------------------------------------------
  void display() { print(); }
  void print( FILE* ofd = stdout,
		    const char* indent = DEFAULT_INDENT,
		    const char* title = "") const;


private:

  // extract key predicates from predicates and append them to
  // keyPredicates (side-effects keyPredicates):
  void appendKeyPredicates(ValueIdSet& keyPredicates,
			   const ValueIdSet& predicates,
                           const ValueIdSet& inputValues) const;

  NABoolean isAPartKeyPredicateForMdam(const ValueId& predId,
                                       const ValueIdSet& inputValues) const;



  // -----------------------------------------------------------------------
  // This members are created by the costing. They contain the data
  // needed to generate the ColumnOrderListArray in preCodeGen.
  // Also, ScanKey::associatedDisjuncts is used in this generation.
  // -----------------------------------------------------------------------
  NABoolean *sparseFlagArray_;
  CollIndex *stopColumnArray_;
  //Boolean that tells us if executor predicates can be empty or not.
  //It can be empty if all predicates are applied at the dp2.
  NABoolean noExePred_;

  // -----------------------------------------------------------------------
  //  The ColumnOrderListArray contains the data from which the generator
  // builds the mdam network.
  // This array is NULL in the optimizer and it is generated by preCodeGen
  // -----------------------------------------------------------------------
  ColumnOrderListPtrArray *columnOrderListPtrArrayPtr_;
}; // class MdamKey
       




#endif
// eof