Source code: org/apache/derby/impl/sql/compile/FromBaseTable.java

   /*
   
      Derby - Class org.apache.derby.impl.sql.compile.FromBaseTable
   
      Copyright 1997, 2004 The Apache Software Foundation or its licensors, as applicable.
   
      Licensed 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.
  
   */
  
  package  org.apache.derby.impl.sql.compile;
  
  import org.apache.derby.catalog.IndexDescriptor;
  import org.apache.derby.iapi.util.StringUtil;
  
  import org.apache.derby.iapi.reference.ClassName;
  import org.apache.derby.iapi.reference.SQLState;
  
  import org.apache.derby.iapi.services.io.FormatableBitSet;
  import org.apache.derby.iapi.services.io.FormatableArrayHolder;
  import org.apache.derby.iapi.services.io.FormatableIntHolder;
  import org.apache.derby.iapi.util.JBitSet;
  import org.apache.derby.iapi.util.ReuseFactory;
  import org.apache.derby.iapi.services.classfile.VMOpcode;
  
  import org.apache.derby.iapi.services.loader.GeneratedMethod;
  import org.apache.derby.iapi.services.context.ContextManager;
  import org.apache.derby.iapi.services.compiler.MethodBuilder;
  import org.apache.derby.iapi.services.monitor.Monitor;
  import org.apache.derby.iapi.services.property.PropertyUtil;
  import org.apache.derby.iapi.services.sanity.SanityManager;
  
  import org.apache.derby.iapi.error.StandardException;
  
  import org.apache.derby.iapi.sql.conn.LanguageConnectionContext;
  
  import org.apache.derby.iapi.sql.compile.CompilerContext;
  import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
  import org.apache.derby.iapi.sql.compile.Optimizer;
  import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
  import org.apache.derby.iapi.sql.compile.Optimizable;
  import org.apache.derby.iapi.sql.compile.CostEstimate;
  import org.apache.derby.iapi.sql.compile.AccessPath;
  import org.apache.derby.iapi.sql.compile.JoinStrategy;
  import org.apache.derby.iapi.sql.compile.RowOrdering;
  import org.apache.derby.iapi.sql.compile.C_NodeTypes;
  
  import org.apache.derby.iapi.sql.dictionary.DataDictionary;
  import org.apache.derby.iapi.sql.dictionary.ColumnDescriptor;
  import org.apache.derby.iapi.sql.dictionary.ColumnDescriptorList;
  import org.apache.derby.iapi.sql.dictionary.ConstraintDescriptor;
  import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
  import org.apache.derby.iapi.sql.dictionary.IndexRowGenerator;
  import org.apache.derby.iapi.sql.dictionary.SchemaDescriptor;
  import org.apache.derby.iapi.sql.dictionary.TableDescriptor;
  import org.apache.derby.iapi.sql.dictionary.ViewDescriptor;
  
  import org.apache.derby.iapi.sql.execute.CursorResultSet;
  import org.apache.derby.iapi.sql.execute.ExecRow;
  import org.apache.derby.iapi.sql.execute.ExecutionContext;
  
  
  import org.apache.derby.iapi.sql.ResultSet;
  import org.apache.derby.iapi.sql.Activation;
  import org.apache.derby.iapi.sql.LanguageProperties;
  
  import org.apache.derby.iapi.types.TypeId;
  
  import org.apache.derby.iapi.store.access.Qualifier;
  import org.apache.derby.iapi.store.access.StaticCompiledOpenConglomInfo;
  import org.apache.derby.iapi.store.access.StoreCostController;
  import org.apache.derby.iapi.store.access.ScanController;
  import org.apache.derby.iapi.store.access.TransactionController;
  
  import org.apache.derby.iapi.types.DataValueDescriptor;
  
  import org.apache.derby.impl.sql.compile.ExpressionClassBuilder;
  import org.apache.derby.impl.sql.compile.ActivationClassBuilder;
  
  import org.apache.derby.impl.sql.execute.HashScanResultSet;
  
  
  
  import java.sql.Connection;
  
  import java.util.Enumeration;
  import java.util.Properties;
  import java.util.Vector;
  
 /**
  * A FromBaseTable represents a table in the FROM list of a DML statement,
  * as distinguished from a FromSubquery, which represents a subquery in the
  * FROM list. A FromBaseTable may actually represent a view.  During parsing,
  * we can't distinguish views from base tables. During binding, when we
  * find FromBaseTables that represent views, we replace them with FromSubqueries.
  * By the time we get to code generation, all FromSubqueries have been eliminated,
  * and all FromBaseTables will represent only true base tables.
  * <p>
  * <B>Positioned Update</B>: Currently, all columns of an updatable cursor
  * are selected to deal with a positioned update.  This is because we don't
  * know what columns will ultimately be needed from the UpdateNode above
  * us.  For example, consider:<pre><i>
  *
  *   get c as 'select cint from t for update of ctinyint'
  *  update t set ctinyint = csmallint
  *
  * </pre></i> Ideally, the cursor only selects cint.  Then,
  * something akin to an IndexRowToBaseRow is generated to
  * take the CursorResultSet and get the appropriate columns
  * out of the base table from the RowLocation retunrned by the
  * cursor.  Then the update node can generate the appropriate
  * NormalizeResultSet (or whatever else it might need) to
  * get things into the correct format for the UpdateResultSet.
  * See CurrentOfNode for more information.
  *
 * @author Jeff Lichtman
  */
 
 public class FromBaseTable extends FromTable
 {
   static final int UNSET = -1;
 
   TableName    tableName;
   TableDescriptor  tableDescriptor;
 
   ConglomerateDescriptor    baseConglomerateDescriptor;
   ConglomerateDescriptor[]  conglomDescs;
 
   int        updateOrDelete;
   
   /*
   ** The number of rows to bulkFetch.
   ** Initially it is unset.  If the user
   ** uses the bulkFetch table property,  
   ** it is set to that.  Otherwise, it
   ** may be turned on if it isn't an updatable
   ** cursor and it is the right type of
   ** result set (more than 1 row expected to
   ** be returned, and not hash, which does its
   ** own bulk fetch, and subquery).
   */
   int       bulkFetch = UNSET;
 
   /* We may turn off bulk fetch for a variety of reasons,
    * including because of the min optimization.  
    * bulkFetchTurnedOff is set to true in those cases.
    */
   boolean      bulkFetchTurnedOff;
   
   private double  singleScanRowCount;
 
   private FormatableBitSet referencedCols;
   private ResultColumnList templateColumns;
 
   /* A 0-based array of column names for this table used
    * for optimizer trace.
    */
   private String[] columnNames;
 
   // true if we are to do a special scan to retrieve the last value
   // in the index
   private boolean specialMaxScan;
 
   // true if we are to do a distinct scan
   private boolean distinctScan;
 
   /**
    *Information for dependent table scan for Referential Actions
    */
   private boolean raDependentScan;
   private String raParentResultSetId;
   private long fkIndexConglomId;  
   private int[] fkColArray;
 
   /**
    * Restriction as a PredicateList
    */
   PredicateList baseTableRestrictionList;
   PredicateList nonBaseTableRestrictionList;
   PredicateList restrictionList;
   PredicateList storeRestrictionList;
   PredicateList nonStoreRestrictionList;
   PredicateList requalificationRestrictionList;
 
   public static final int UPDATE = 1;
   public static final int DELETE = 2;
 
   /* Variables for EXISTS FBTs */
   private boolean  existsBaseTable;
   private boolean  isNotExists;  //is a NOT EXISTS base table
   private JBitSet dependencyMap;
 
   private boolean getUpdateLocks;
 
   /**
    * Initializer for a table in a FROM list.
    *
    * @param tableName      The name of the table
    * @param correlationName  The correlation name
    * @param derivedRCL    The derived column list
    * @param tableProperties  The Properties list associated with the table.
    *
    *  - OR -
    *
    * @param tableName      The name of the table
    * @param correlationName  The correlation name
    * @param updateOrDelete  Table is being updated/deleted from. 
    * @param derivedRCL    The derived column list
    */
   public void init(
               Object arg1,
               Object arg2,
                 Object arg3,
               Object arg4)
   {
     if (arg3 instanceof Integer)
     {
       init(arg2, null);
       this.tableName = (TableName) arg1;
       this.updateOrDelete = ((Integer) arg3).intValue();
       resultColumns = (ResultColumnList) arg4;
     }
     else
     {
       init(arg2, arg4);
       this.tableName = (TableName) arg1;
       resultColumns = (ResultColumnList) arg3;
     }
 
     templateColumns = resultColumns;
   }
 
   /**
    * no LOJ reordering for base table.
    */
   public boolean LOJ_reorderable(int numTables)
         throws StandardException
   {
     return false;
   }
 
   public JBitSet LOJgetReferencedTables(int numTables)
         throws StandardException
   {
     JBitSet map = new JBitSet(numTables);
     fillInReferencedTableMap(map);
     return map;
   }
 
   /*
    * Optimizable interface.
    */
 
   /**
    * @see Optimizable#nextAccessPath
    *
    * @exception StandardException    Thrown on error
    */
   public boolean nextAccessPath(Optimizer optimizer,
                   OptimizablePredicateList predList,
                   RowOrdering rowOrdering)
           throws StandardException
   {
     String userSpecifiedIndexName = getUserSpecifiedIndexName();
     AccessPath ap = getCurrentAccessPath();
     ConglomerateDescriptor currentConglomerateDescriptor =
                         ap.getConglomerateDescriptor();
 
     optimizer.trace(Optimizer.CALLING_NEXT_ACCESS_PATH,
              ((predList == null) ? 0 : predList.size()),
              0, 0.0, getExposedName());
 
     /*
     ** Remove the ordering of the current conglomerate descriptor,
     ** if any.
     */
     rowOrdering.removeOptimizable(getTableNumber());
 
     // RESOLVE: This will have to be modified to step through the
     // join strategies as well as the conglomerates.
 
     if (userSpecifiedIndexName != null)
     {
       /*
       ** User specified an index name, so we should look at only one
       ** index.  If there is a current conglomerate descriptor, and there
       ** are no more join strategies, we've already looked at the index,
       ** so go back to null.
       */
       if (currentConglomerateDescriptor != null)
       {
         if ( ! super.nextAccessPath(optimizer,
                       predList,
                       rowOrdering) )
         {
           currentConglomerateDescriptor = null;
         }
       }
       else
       {
         optimizer.trace(Optimizer.LOOKING_FOR_SPECIFIED_INDEX,
                 tableNumber, 0, 0.0, userSpecifiedIndexName);
 
         if (StringUtil.SQLToUpperCase(userSpecifiedIndexName).equals("NULL"))
         {
           /* Special case - user-specified table scan */
           currentConglomerateDescriptor =
             tableDescriptor.getConglomerateDescriptor(
                     tableDescriptor.getHeapConglomerateId()
                   );
         }
         else
         {
           /* User-specified index name */
           getConglomDescs();
         
           for (int index = 0; index < conglomDescs.length; index++)
           {
             currentConglomerateDescriptor = conglomDescs[index];
             String conglomerateName =
               currentConglomerateDescriptor.getConglomerateName();
             if (conglomerateName != null)
             {
               /* Have we found the desired index? */
               if (conglomerateName.equals(userSpecifiedIndexName))
               {
                 break;
               }
             }
           }
 
           /* We should always find a match */
           if (SanityManager.DEBUG)
           {
             if (currentConglomerateDescriptor == null)
             {
               SanityManager.THROWASSERT(
                 "Expected to find match for forced index " +
                 userSpecifiedIndexName);
             }
           }
         }
 
         if ( ! super.nextAccessPath(optimizer,
                       predList,
                       rowOrdering))
         {
           if (SanityManager.DEBUG)
           {
             SanityManager.THROWASSERT("No join strategy found");
           }
         }
       }
     }
     else
     {
       if (currentConglomerateDescriptor != null)
       {
         /* 
         ** Once we have a conglomerate descriptor, cycle through
         ** the join strategies (done in parent).
         */
         if ( ! super.nextAccessPath(optimizer,
                       predList,
                       rowOrdering))
         {
           /*
           ** When we're out of join strategies, go to the next
           ** conglomerate descriptor.
           */
           currentConglomerateDescriptor = getNextConglom(currentConglomerateDescriptor);
 
           /*
           ** New conglomerate, so step through join strategies
           ** again.
           */
           resetJoinStrategies(optimizer);
 
           if ( ! super.nextAccessPath(optimizer,
                         predList,
                         rowOrdering))
           {
             if (SanityManager.DEBUG)
             {
               SanityManager.THROWASSERT("No join strategy found");
             }
           }
         }
       }
       else
       {
         /* Get the first conglomerate descriptor */
         currentConglomerateDescriptor = getFirstConglom();
 
         if ( ! super.nextAccessPath(optimizer,
                       predList,
                       rowOrdering))
         {
           if (SanityManager.DEBUG)
           {
             SanityManager.THROWASSERT("No join strategy found");
           }
         }
       }
     }
 
     if (currentConglomerateDescriptor == null)
     {
       optimizer.trace(Optimizer.NO_MORE_CONGLOMERATES, tableNumber, 0, 0.0, null);
     }
     else
     {
       currentConglomerateDescriptor.setColumnNames(columnNames);
       optimizer.trace(Optimizer.CONSIDERING_CONGLOMERATE, tableNumber, 0, 0.0, 
               currentConglomerateDescriptor);
     }
 
     /*
     ** Tell the rowOrdering that what the ordering of this conglomerate is
     */
     if (currentConglomerateDescriptor != null)
     {
       if ( ! currentConglomerateDescriptor.isIndex())
       {
         /* If we are scanning the heap, but there
          * is a full match on a unique key, then
          * we can say that the table IS NOT unordered.
          * (We can't currently say what the ordering is
          * though.)
          */
         if (! isOneRowResultSet(predList))
         {
           optimizer.trace(Optimizer.ADDING_UNORDERED_OPTIMIZABLE,
                    ((predList == null) ? 0 : predList.size()), 
                    0, 0.0, null);
 
           rowOrdering.addUnorderedOptimizable(this);
         }
         else
         {
           optimizer.trace(Optimizer.SCANNING_HEAP_FULL_MATCH_ON_UNIQUE_KEY,
                    0, 0, 0.0, null);
         }
       }
       else
       {
         IndexRowGenerator irg =
               currentConglomerateDescriptor.getIndexDescriptor();
 
         int[] baseColumnPositions = irg.baseColumnPositions();
         boolean[] isAscending = irg.isAscending();
 
         for (int i = 0; i < baseColumnPositions.length; i++)
         {
           /*
           ** Don't add the column to the ordering if it's already
           ** an ordered column.  This can happen in the following
           ** case:
           **
           **    create index ti on t(x, y);
           **    select * from t where x = 1 order by y;
           **
           ** Column x is always ordered, so we want to avoid the
           ** sort when using index ti.  This is accomplished by
           ** making column y appear as the first ordered column
           ** in the list.
           */
           if ( ! rowOrdering.orderedOnColumn(isAscending[i] ?
                           RowOrdering.ASCENDING :
                           RowOrdering.DESCENDING,
                           getTableNumber(),
                           baseColumnPositions[i]))
           {
             rowOrdering.nextOrderPosition(isAscending[i] ?
                           RowOrdering.ASCENDING :
                           RowOrdering.DESCENDING);
 
             rowOrdering.addOrderedColumn(isAscending[i] ?
                           RowOrdering.ASCENDING :
                           RowOrdering.DESCENDING,
                           getTableNumber(),
                           baseColumnPositions[i]);
           }
         }
       }  
     }
 
     ap.setConglomerateDescriptor(currentConglomerateDescriptor);
 
     return currentConglomerateDescriptor != null;
   }
 
   /** Tell super-class that this Optimizable can be ordered */
   protected boolean canBeOrdered()
   {
     return true;
   }
 
   /**
    * @see org.apache.derby.iapi.sql.compile.Optimizable#optimizeIt
    *
    * @exception StandardException    Thrown on error
    */
   public CostEstimate optimizeIt(
         Optimizer optimizer,
         OptimizablePredicateList predList,
         CostEstimate outerCost,
         RowOrdering rowOrdering)
       throws StandardException
   {
     optimizer.costOptimizable(
               this,
               tableDescriptor,
               getCurrentAccessPath().getConglomerateDescriptor(),
               predList,
               outerCost);
 
     return costEstimate;
   }
 
   /** @see Optimizable#getTableDescriptor */
   public TableDescriptor getTableDescriptor()
   {
     return tableDescriptor;
   }
 
 
   /** @see Optimizable#isMaterializable 
    *
    * @exception StandardException    Thrown on error
    */
   public boolean isMaterializable()
     throws StandardException
   {
     /* base tables are always materializable */
     return true;
   }
 
 
   /**
    * @see Optimizable#pushOptPredicate
    *
    * @exception StandardException    Thrown on error
    */
 
   public boolean pushOptPredicate(OptimizablePredicate optimizablePredicate)
     throws StandardException
   {
     if (SanityManager.DEBUG)
     {
       SanityManager.ASSERT(optimizablePredicate instanceof Predicate,
         "optimizablePredicate expected to be instanceof Predicate");
     }
 
     /* Add the matching predicate to the restrictionList */
     restrictionList.addPredicate((Predicate) optimizablePredicate);
 
     return true;
   }
 
   /**
    * @see Optimizable#pullOptPredicates
    *
    * @exception StandardException    Thrown on error
    */
   public void pullOptPredicates(
                 OptimizablePredicateList optimizablePredicates)
           throws StandardException
   {
     for (int i = restrictionList.size() - 1; i >= 0; i--) {
       optimizablePredicates.addOptPredicate(
                   restrictionList.getOptPredicate(i));
       restrictionList.removeOptPredicate(i);
     }
   }
 
   /** 
    * @see Optimizable#isCoveringIndex
    * @exception StandardException    Thrown on error
    */
   public boolean isCoveringIndex(ConglomerateDescriptor cd) throws StandardException
   {
     boolean coveringIndex = true;
     IndexRowGenerator  irg;
     int[]        baseCols;
     int          colPos;
 
     /* You can only be a covering index if you're an index */
     if ( ! cd.isIndex())
       return false;
 
     irg = cd.getIndexDescriptor();
     baseCols = irg.baseColumnPositions();
 
     /* First we check to see if this is a covering index */
     int rclSize = resultColumns.size();
     for (int index = 0; index < rclSize; index++)
     {
       ResultColumn rc = (ResultColumn) resultColumns.elementAt(index);
 
       /* Ignore unreferenced columns */
       if (! rc.isReferenced())
       {
         continue;
       }
 
       /* Ignore constants - this can happen if all of the columns
        * were projected out and we ended up just generating
        * a "1" in RCL.doProject().
        */
       if (rc.getExpression() instanceof ConstantNode)
       {
         continue;
       }
 
       coveringIndex = false;
 
       colPos = rc.getColumnPosition();
 
       /* Is this column in the index? */
       for (int i = 0; i < baseCols.length; i++)
       {
         if (colPos == baseCols[i])
         {
           coveringIndex = true;
           break;
         }
       }
 
       /* No need to continue if the column was not in the index */
       if (! coveringIndex)
       {
         break;
       }
     }
     return coveringIndex;
   }
 
   /** @see Optimizable#verifyProperties 
    * @exception StandardException    Thrown on error
    */
   public void verifyProperties(DataDictionary dDictionary)
     throws StandardException
   {
     if (tableProperties == null)
     {
       return;
     }
     /* Check here for:
      *    invalid properties key
      *    index and constraint properties
      *    non-existent index
      *    non-existent constraint
      *    invalid joinStrategy
      *    invalid value for hashInitialCapacity
      *    invalid value for hashLoadFactor
      *    invalid value for hashMaxCapacity
      */
     boolean indexSpecified = false;
     boolean constraintSpecified = false;
     ConstraintDescriptor consDesc = null;
     Enumeration e = tableProperties.keys();
 
       StringUtil.SQLEqualsIgnoreCase(tableDescriptor.getSchemaName(), 
                        "SYS");
     while (e.hasMoreElements())
     {
       String key = (String) e.nextElement();
       String value = (String) tableProperties.get(key);
 
       if (key.equals("index"))
       {
         // User only allowed to specify 1 of index and constraint, not both
         if (constraintSpecified)
         {
           throw StandardException.newException(SQLState.LANG_BOTH_FORCE_INDEX_AND_CONSTRAINT_SPECIFIED, 
                 getBaseTableName());
         }
         indexSpecified = true;
 
         /* Validate index name - NULL means table scan */
         if (! StringUtil.SQLToUpperCase(value).equals("NULL"))
         {
           ConglomerateDescriptor cd = null;
           ConglomerateDescriptor[] cds = tableDescriptor.getConglomerateDescriptors();
 
           for (int index = 0; index < cds.length; index++)
           {
             cd = cds[index];
             String conglomerateName = cd.getConglomerateName();
             if (conglomerateName != null)
             {
               if (conglomerateName.equals(value))
               {
                 break;
               }
             }
             // Not a match, clear cd
             cd = null;
           }
 
           // Throw exception if user specified index not found
           if (cd == null)
           {
             throw StandardException.newException(SQLState.LANG_INVALID_FORCED_INDEX1, 
                     value, getBaseTableName());
           }
           /* Query is dependent on the ConglomerateDescriptor */
           getCompilerContext().createDependency(cd);
         }
       }
       else if (key.equals("constraint"))
       {
         // User only allowed to specify 1 of index and constraint, not both
         if (indexSpecified)
         {
           throw StandardException.newException(SQLState.LANG_BOTH_FORCE_INDEX_AND_CONSTRAINT_SPECIFIED, 
                 getBaseTableName());
         }
         constraintSpecified = true;
 
         /* Validate constraint name - NULL means table scan */
         if (! StringUtil.SQLToUpperCase(value).equals("NULL"))
         {
           consDesc = 
             dDictionary.getConstraintDescriptorByName(
                   tableDescriptor, (SchemaDescriptor)null, value,
                   false);
 
           /* Throw exception if user specified constraint not found
            * or if it does not have a backing index.
            */
           if ((consDesc == null) || ! consDesc.hasBackingIndex())
           {
             throw StandardException.newException(SQLState.LANG_INVALID_FORCED_INDEX2, 
                     value, getBaseTableName());
           }
 
           /* Query is dependent on the ConstraintDescriptor */
           getCompilerContext().createDependency(consDesc);
         }
       }
       else if (key.equals("joinStrategy"))
       {
         userSpecifiedJoinStrategy = StringUtil.SQLToUpperCase(value);
       }
       else if (key.equals("hashInitialCapacity"))
       {
         initialCapacity = getIntProperty(value, key);
 
         // verify that the specified value is valid
         if (initialCapacity <= 0)
         {
           throw StandardException.newException(SQLState.LANG_INVALID_HASH_INITIAL_CAPACITY, 
               String.valueOf(initialCapacity));
         }
       }
       else if (key.equals("hashLoadFactor"))
       {
         try
         {
           loadFactor = Float.valueOf(value).floatValue();
         }
         catch (NumberFormatException nfe)
         {
           throw StandardException.newException(SQLState.LANG_INVALID_NUMBER_FORMAT_FOR_OVERRIDE, 
               value, key);
         }
 
         // verify that the specified value is valid
         if (loadFactor <= 0.0 || loadFactor > 1.0)
         {
           throw StandardException.newException(SQLState.LANG_INVALID_HASH_LOAD_FACTOR, 
               value);
         }
       }
       else if (key.equals("hashMaxCapacity"))
       {
         maxCapacity = getIntProperty(value, key);
 
         // verify that the specified value is valid
         if (maxCapacity <= 0)
         {
           throw StandardException.newException(SQLState.LANG_INVALID_HASH_MAX_CAPACITY, 
               String.valueOf(maxCapacity));
         }
       }
       else if (key.equals("bulkFetch"))
       {
         bulkFetch = getIntProperty(value, key);
 
         // verify that the specified value is valid
         if (bulkFetch <= 0)
         {
           throw StandardException.newException(SQLState.LANG_INVALID_BULK_FETCH_VALUE, 
               String.valueOf(bulkFetch));
         }
       
         // no bulk fetch on updatable scans
         if (forUpdate())
         {
           throw StandardException.newException(SQLState.LANG_INVALID_BULK_FETCH_UPDATEABLE);
         }
       }
       else
       {
         // No other "legal" values at this time
         throw StandardException.newException(SQLState.LANG_INVALID_FROM_TABLE_PROPERTY, key,
           "index, constraint, joinStrategy");
       }
     }
 
     /* If user specified a constraint name, then replace it in the 
      * properties list with the underlying index name to simplify
      * the code in the optimizer.
      * NOTE: The code to get from the constraint name, for a constraint
      * with a backing index, to the index name is convoluted.  Given
      * the constraint name, we can get the conglomerate id from the
      * ConstraintDescriptor.  We then use the conglomerate id to get
      * the ConglomerateDescriptor from the DataDictionary and, finally,
      * we get the index name (conglomerate name) from the ConglomerateDescriptor.
      */
     if (constraintSpecified)
     {
       ConglomerateDescriptor cd = 
         dDictionary.getConglomerateDescriptor(
           consDesc.getConglomerateId());
       String indexName = cd.getConglomerateName();
 
       tableProperties.remove("constraint");
       tableProperties.put("index", indexName);
     }
   }
 
   /** @see Optimizable#getBaseTableName */
   public String getBaseTableName()
   {
     return tableName.getTableName();
   }
 
   /** @see Optimizable#startOptimizing */
   public void startOptimizing(Optimizer optimizer, RowOrdering rowOrdering)
   {
     AccessPath ap = getCurrentAccessPath();
     AccessPath bestAp = getBestAccessPath();
     AccessPath bestSortAp = getBestSortAvoidancePath();
 
     ap.setConglomerateDescriptor((ConglomerateDescriptor) null);
     bestAp.setConglomerateDescriptor((ConglomerateDescriptor) null);
     bestSortAp.setConglomerateDescriptor((ConglomerateDescriptor) null);
     ap.setCoveringIndexScan(false);
     bestAp.setCoveringIndexScan(false);
     bestSortAp.setCoveringIndexScan(false);
     ap.setLockMode(0);
     bestAp.setLockMode(0);
     bestSortAp.setLockMode(0);
 
     /*
     ** Only need to do this for current access path, because the
     ** costEstimate will be copied to the best access paths as
     ** necessary.
     */
     CostEstimate costEstimate = getCostEstimate(optimizer);
     ap.setCostEstimate(costEstimate);
 
     /*
     ** This is the initial cost of this optimizable.  Initialize it
     ** to the maximum cost so that the optimizer will think that
     ** any access path is better than none.
     */
     costEstimate.setCost(Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE);
 
     super.startOptimizing(optimizer, rowOrdering);
   }
 
   /** @see Optimizable#convertAbsoluteToRelativeColumnPosition */
   public int convertAbsoluteToRelativeColumnPosition(int absolutePosition)
   {
     return mapAbsoluteToRelativeColumnPosition(absolutePosition);
   }
 
   /**
    * @see Optimizable#estimateCost
    *
    * @exception StandardException    Thrown on error
    */
   public CostEstimate estimateCost(OptimizablePredicateList predList,
                   ConglomerateDescriptor cd,
                   CostEstimate outerCost,
                   Optimizer optimizer,
                   RowOrdering rowOrdering)
       throws StandardException
   {
     double cost;
     boolean statisticsForTable = false;
     boolean statisticsForConglomerate = false;
     /* unknownPredicateList contains all predicates whose effect on
      * cost/selectivity can't be calculated by the store.
      */
     PredicateList unknownPredicateList = null;
 
     if (optimizer.useStatistics() && predList != null)
     {
       /* if user has specified that we don't use statistics,
          pretend that statistics don't exist.
       */
       statisticsForConglomerate = tableDescriptor.statisticsExist(cd);
       statisticsForTable = tableDescriptor.statisticsExist(null);
       unknownPredicateList = new PredicateList();
       predList.copyPredicatesToOtherList(unknownPredicateList);
 
     }
 
     AccessPath currentAccessPath = getCurrentAccessPath();
     JoinStrategy currentJoinStrategy = 
       currentAccessPath.getJoinStrategy();
 
     optimizer.trace(Optimizer.ESTIMATING_COST_OF_CONGLOMERATE,
             tableNumber, 0, 0.0, cd);
 
     /* Get the uniqueness factory for later use (see below) */
     double tableUniquenessFactor =
         optimizer.uniqueJoinWithOuterTable(predList);
 
     boolean oneRowResultSetForSomeConglom = isOneRowResultSet(predList);
 
     /* Get the predicates that can be used for scanning the base table */
     baseTableRestrictionList.removeAllElements();
 
     currentJoinStrategy.getBasePredicates(predList,  
                      baseTableRestrictionList,
                      this);
                   
     /* RESOLVE: Need to figure out how to cache the StoreCostController */
     StoreCostController scc = getStoreCostController(cd);
 
     CostEstimate costEstimate = getScratchCostEstimate(optimizer);
 
     /* First, get the cost for one scan */
 
     /* Does the conglomerate match at most one row? */
     if (isOneRowResultSet(cd, baseTableRestrictionList))
     {
       /*
       ** Tell the RowOrdering that this optimizable is always ordered.
       ** It will figure out whether it is really always ordered in the
       ** context of the outer tables and their orderings.
       */
       rowOrdering.optimizableAlwaysOrdered(this);
 
       singleScanRowCount = 1.0;
 
       /* Yes, the cost is to fetch exactly one row */
       // RESOLVE: NEED TO FIGURE OUT HOW TO GET REFERENCED COLUMN LIST,
       // FIELD STATES, AND ACCESS TYPE
       cost = scc.getFetchFromFullKeyCost(
                     (FormatableBitSet) null,
                     0);
 
       optimizer.trace(Optimizer.MATCH_SINGLE_ROW_COST,
               tableNumber, 0, cost, null);
 
       costEstimate.setCost(cost, 1.0d, 1.0d);
 
       /*
       ** Let the join strategy decide whether the cost of the base
       ** scan is a single scan, or a scan per outer row.
       ** NOTE: The multiplication should only be done against the
       ** total row count, not the singleScanRowCount.
       */
       double newCost = costEstimate.getEstimatedCost();
 
       if (currentJoinStrategy.multiplyBaseCostByOuterRows())
       {
         newCost *= outerCost.rowCount();
       }
 
       costEstimate.setCost(
         newCost,
         costEstimate.rowCount() * outerCost.rowCount(),
         costEstimate.singleScanRowCount());
 
       /*
       ** Choose the lock mode.  If the start/stop conditions are
       ** constant, choose row locking, because we will always match
       ** the same row.  If they are not constant (i.e. they include
       ** a join), we decide whether to do row locking based on
       ** the total number of rows for the life of the query.
       */
      boolean constantStartStop = true;
      for (int i = 0; i < predList.size(); i++)
      {
        OptimizablePredicate pred = predList.getOptPredicate(i);

        /*
        ** The predicates are in index order, so the start and
        ** stop keys should be first.
        */
        if ( ! (pred.isStartKey() || pred.isStopKey()))
        {
          break;
        }

        /* Stop when we've found a join */
        if ( ! pred.getReferencedMap().hasSingleBitSet())
        {
          constantStartStop = false;
          break;
        }
      }

      if (constantStartStop)
      {
        currentAccessPath.setLockMode(
                      TransactionController.MODE_RECORD);

        optimizer.trace(Optimizer.ROW_LOCK_ALL_CONSTANT_START_STOP,
                0, 0, 0.0, null);
      }
      else
      {
        setLockingBasedOnThreshold(optimizer, costEstimate.rowCount());
      }

      optimizer.trace(Optimizer.COST_OF_N_SCANS, 
              tableNumber, 0, outerCost.rowCount(), costEstimate);

      /* Add in cost of fetching base row for non-covering index */
      if (cd.isIndex() && ( ! isCoveringIndex(cd) ) )
      {
        double singleFetchCost =
            getBaseCostController().getFetchFromRowLocationCost(
                                (FormatableBitSet) null,
                                0);
        cost = singleFetchCost * costEstimate.rowCount();

        costEstimate.setEstimatedCost(
                costEstimate.getEstimatedCost() + cost);

        optimizer.trace(Optimizer.NON_COVERING_INDEX_COST,
                tableNumber, 0, cost, null);
      }
    }
    else
    {
      /* Conglomerate might match more than one row */

      /*
      ** Some predicates are good for start/stop, but we don't know
      ** the values they are being compared to at this time, so we
      ** estimate their selectivity in language rather than ask the
      ** store about them .  The predicates on the first column of
      ** the conglomerate reduce the number of pages and rows scanned.
      ** The predicates on columns after the first reduce the number
      ** of rows scanned, but have a much smaller effect on the number
      ** of pages scanned, so we keep track of these selectivities in
      ** two separate variables: extraFirstColumnSelectivity and
      ** extraStartStopSelectivity. (Theoretically, we could try to
      ** figure out the effect of predicates after the first column
      ** on the number of pages scanned, but it's too hard, so we
      ** use these predicates only to reduce the estimated number of
      ** rows.  For comparisons with known values, though, the store
      ** can figure out exactly how many rows and pages are scanned.)
      **
      ** Other predicates are not good for start/stop.  We keep track
      ** of their selectvities separately, because these limit the
      ** number of rows, but not the number of pages, and so need to
      ** be factored into the row count but not into the cost.
      ** These selectivities are factored into extraQualifierSelectivity.
      **
      ** statStartStopSelectivity (using statistics) represents the 
      ** selectivity of start/stop predicates that can be used to scan 
      ** the index. If no statistics exist for the conglomerate then 
      ** the value of this variable remains at 1.0
      ** 
      ** statCompositeSelectivity (using statistics) represents the 
      ** selectivity of all the predicates (including NonBaseTable 
      ** predicates). This represents the most educated guess [among 
      ** all the wild surmises in this routine] as to the number
      ** of rows that will be returned from this joinNode.
      ** If no statistics exist on the table or no statistics at all
      ** can be found to satisfy the predicates at this join opertor,
      ** then statCompositeSelectivity is left initialized at 1.0
      */
      double extraFirstColumnSelectivity = 1.0d;
      double extraStartStopSelectivity = 1.0d;
      double extraQualifierSelectivity = 1.0d;
      double extraNonQualifierSelectivity = 1.0d;
      double statStartStopSelectivity = 1.0d;
      double statCompositeSelectivity = 1.0d;

      int     numExtraFirstColumnPreds = 0;
      int     numExtraStartStopPreds = 0;
      int     numExtraQualifiers = 0;
      int     numExtraNonQualifiers = 0;

      /*
      ** It is possible for something to be a start or stop predicate
      ** without it being possible to use it as a key for cost estimation.
      ** For example, with an index on (c1, c2), and the predicate
      ** c1 = othertable.c3 and c2 = 1, the comparison on c1 is with
      ** an unknown value, so we can't pass it to the store.  This means
      ** we can't pass the comparison on c2 to the store, either.
      **
      ** The following booleans keep track of whether we have seen
      ** gaps in the keys we can pass to the store.
      */
      boolean startGap = false;
      boolean stopGap = false;
      boolean seenFirstColumn = false;

      /*
      ** We need to figure out the number of rows touched to decide
      ** whether to use row locking or table locking.  If the start/stop
      ** conditions are constant (i.e. no joins), the number of rows
      ** touched is the number of rows per scan.  But if the start/stop
      ** conditions contain a join, the number of rows touched must
      ** take the number of outer rows into account.
      */
      boolean constantStartStop = true;
      boolean startStopFound = false;

      /* Count the number of start and stop keys */
      int startKeyNum = 0;
      int stopKeyNum = 0;
      OptimizablePredicate pred;
      int predListSize;

      if (predList != null)
        predListSize = baseTableRestrictionList.size();
      else
        predListSize = 0;

      int startStopPredCount = 0;
      ColumnReference firstColumn = null;
      for (int i = 0; i < predListSize; i++)
      {
        pred = baseTableRestrictionList.getOptPredicate(i);
        boolean startKey = pred.isStartKey();
        boolean stopKey = pred.isStopKey();
        if (startKey || stopKey)
        {
          startStopFound = true;

          if ( ! pred.getReferencedMap().hasSingleBitSet())
          {
            constantStartStop = false;
          }

          boolean knownConstant =
            pred.compareWithKnownConstant(this, true);
          if (startKey)
          {
            if (knownConstant && ( ! startGap ) )
            {
              startKeyNum++;
                if (unknownPredicateList != null)
                  unknownPredicateList.removeOptPredicate(pred);
            }
            else
            {
              startGap = true;
            }
          }

          if (stopKey)
          {
            if (knownConstant && ( ! stopGap ) )
            {
              stopKeyNum++;
                if (unknownPredicateList != null)
                  unknownPredicateList.removeOptPredicate(pred);
            }
            else
            {
              stopGap = true;
            }
          }

          /* If either we are seeing startGap or stopGap because start/stop key is
           * comparison with non-constant, we should multiply the selectivity to
           * extraFirstColumnSelectivity.  Beetle 4787.
           */
          if (startGap || stopGap)
          {
            // Don't include redundant join predicates in selectivity calculations
            if (baseTableRestrictionList.isRedundantPredicate(i))
              continue;

            if (startKey && stopKey)
              startStopPredCount++;

            if (pred.getIndexPosition() == 0)
            {
              extraFirstColumnSelectivity *=
                            pred.selectivity(this);
              if (! seenFirstColumn)
              {
                ValueNode relNode = ((Predicate) pred).getAndNode().getLeftOperand();
                if (relNode instanceof BinaryRelationalOperatorNode)
                  firstColumn = ((BinaryRelationalOperatorNode) relNode).getColumnOperand(this);
                seenFirstColumn = true;
              }
            }
            else
            {
              extraStartStopSelectivity *= pred.selectivity(this);
              numExtraStartStopPreds++;
            }
          }
        }
        else
        {
          // Don't include redundant join predicates in selectivity calculations
          if (baseTableRestrictionList.isRedundantPredicate(i))
          {
            continue;
          }

          /* If we have "like" predicate on the first index column, it is more likely
           * to have a smaller range than "between", so we apply extra selectivity 0.2
           * here.  beetle 4387, 4787.
           */
          if (pred instanceof Predicate)
          {
            ValueNode leftOpnd = ((Predicate) pred).getAndNode().getLeftOperand();
            if (firstColumn != null && leftOpnd instanceof LikeEscapeOperatorNode)
            {
              LikeEscapeOperatorNode likeNode = (LikeEscapeOperatorNode) leftOpnd;
              if (likeNode.getLeftOperand().isParameterNode())
              {
                ValueNode receiver = ((TernaryOperatorNode) likeNode).getReceiver();
                if (receiver instanceof ColumnReference)
                {
                  ColumnReference cr = (ColumnReference) receiver;
                  if (cr.getTableNumber() == firstColumn.getTableNumber() &&
                    cr.getColumnNumber() == firstColumn.getColumnNumber())
                    extraFirstColumnSelectivity *= 0.2;
                }
              }
            }
          }

          if (pred.isQualifier())
          {
            extraQualifierSelectivity *= pred.selectivity(this);
            numExtraQualifiers++;
          }
          else
          {
            extraNonQualifierSelectivity *= pred.selectivity(this);
            numExtraNonQualifiers++;
          }

          /*
          ** Strictly speaking, it shouldn't be necessary to
          ** indicate a gap here, since there should be no more
          ** start/stop predicates, but let's do it, anyway.
          */
          startGap = true;
          stopGap = true;
        }
      }

      if (unknownPredicateList != null)
      {
        statCompositeSelectivity = unknownPredicateList.selectivity(this);
        if (statCompositeSelectivity == -1.0d)
          statCompositeSelectivity = 1.0d;
      }

      if (seenFirstColumn && statisticsForConglomerate &&
        (startStopPredCount > 0))
      {
        statStartStopSelectivity = 
          tableDescriptor.selectivityForConglomerate(cd, startStopPredCount);
      }

      /*
      ** Factor the non-base-table predicates into the extra
      ** non-qualifier selectivity, since these will restrict the
      ** number of rows, but not the cost.
      */
      extraNonQualifierSelectivity *=
        currentJoinStrategy.nonBasePredicateSelectivity(this, predList);

      /* Create the start and stop key arrays, and fill them in */
      DataValueDescriptor[] startKeys;
      DataValueDescriptor[] stopKeys;

      if (startKeyNum > 0)
        startKeys = new DataValueDescriptor[startKeyNum];
      else
        startKeys = null;

      if (stopKeyNum > 0)
        stopKeys = new DataValueDescriptor[stopKeyNum];
      else
        stopKeys = null;

      startKeyNum = 0;
      stopKeyNum = 0;
      startGap = false;
      stopGap = false;

      for (int i = 0; i < predListSize; i++)
      {
        pred = baseTableRestrictionList.getOptPredicate(i);
        boolean startKey = pred.isStartKey();
        boolean stopKey = pred.isStopKey();

        if (startKey || stopKey)
        {
          boolean knownConstant = pred.compareWithKnownConstant(this, true);

          if (startKey)
          {
            if (knownConstant && ( ! startGap ) )
            {
              startKeys[startKeyNum] = pred.getCompareValue(this);
              startKeyNum++;
            }
            else
            {
              startGap = true;
            }
          }

          if (stopKey)
          {
            if (knownConstant && ( ! stopGap ) )
            {
              stopKeys[stopKeyNum] = pred.getCompareValue(this);
              stopKeyNum++;
            }
            else
            {
              stopGap = true;
            }
          }
        }
        else
        {
          startGap = true;
          stopGap = true;
        }
      }

      int startOperator;
      int stopOperator;

      if (baseTableRestrictionList != null)
      {
        startOperator = baseTableRestrictionList.startOperator(this);
        stopOperator = baseTableRestrictionList.stopOperator(this);
      }
      else
      {
        /*
        ** If we're doing a full scan, it doesn't matter what the
        ** start and stop operators are.
        */
        startOperator = ScanController.NA;
        stopOperator = ScanController.NA;
      }

      /*
      ** Get a row template for this conglomerate.  For now, just tell
      ** it we are using all the columns in the row.
      */
      DataValueDescriptor[] rowTemplate = 
                getRowTemplate(cd, getBaseCostController());

      /* we prefer index than table scan for concurrency reason, by a small
       * adjustment on estimated row count.  This affects optimizer's decision
       * especially when few rows are in table. beetle 5006. This makes sense
       * since the plan may stay long before we actually check and invalidate it.
       * And new rows may be inserted before we check and invalidate the plan.
       * Here we only prefer index that has start/stop key from predicates. Non-
       * constant start/stop key case is taken care of by selectivity later.
       */
      long baseRC = (startKeys != null || stopKeys != null) ? baseRowCount() : baseRowCount() + 5;

      scc.getScanCost(
          currentJoinStrategy.scanCostType(),
          baseRC,
                    1,
          forUpdate(),
          (FormatableBitSet) null,
          rowTemplate,
          startKeys,
          startOperator,
          stopKeys,
          stopOperator,
          false,
          0,
          costEstimate);

      /* initialPositionCost is the first part of the index scan cost we get above.
       * It's the cost of initial positioning/fetch of key.  So it's unrelated to
       * row count of how many rows we fetch from index.  We extract it here so that
       * we only multiply selectivity to the other part of index scan cost, which is
       * nearly linear, to make cost calculation more accurate and fair, especially
       * compared to the plan of "one row result set" (unique index). beetle 4787.
       */
      double initialPositionCost = 0.0;
      if (cd.isIndex())
      {
        initialPositionCost = scc.getFetchFromFullKeyCost((FormatableBitSet) null, 0);
        /* oneRowResultSetForSomeConglom means there's a unique index, but certainly
         * not this one since we are here.  If store knows this non-unique index
         * won't return any row or just returns one row (eg., the predicate is a
         * comparison with constant or almost empty table), we do minor adjustment
         * on cost (affecting decision for covering index) and rc (decision for
         * non-covering). The purpose is favoring unique index. beetle 5006.
         */
        if (oneRowResultSetForSomeConglom && costEstimate.rowCount() <= 1)
        {
          costEstimate.setCost(costEstimate.getEstimatedCost() * 2,
                     costEstimate.rowCount() + 2,
                     costEstimate.singleScanRowCount() + 2);
        }
      }

      optimizer.trace(Optimizer.COST_OF_CONGLOMERATE_SCAN1,
              tableNumber, 0, 0.0, cd);
      optimizer.trace(Optimizer.COST_OF_CONGLOMERATE_SCAN2,
              tableNumber, 0, 0.0, costEstimate);
      optimizer.trace(Optimizer.COST_OF_CONGLOMERATE_SCAN3,
              numExtraFirstColumnPreds, 0, 
              extraFirstColumnSelectivity, null);
      optimizer.trace(Optimizer.COST_OF_CONGLOMERATE_SCAN4,
              numExtraStartStopPreds, 0, 
              extraStartStopSelectivity, null);
      optimizer.trace(Optimizer.COST_OF_CONGLOMERATE_SCAN7,