001: /*
002:
003: Derby - Class org.apache.derby.impl.sql.compile.NestedLoopJoinStrategy
004:
005: Licensed to the Apache Software Foundation (ASF) under one or more
006: contributor license agreements. See the NOTICE file distributed with
007: this work for additional information regarding copyright ownership.
008: The ASF licenses this file to you under the Apache License, Version 2.0
009: (the "License"); you may not use this file except in compliance with
010: the License. You may obtain a copy of the License at
011:
012: http://www.apache.org/licenses/LICENSE-2.0
013:
014: Unless required by applicable law or agreed to in writing, software
015: distributed under the License is distributed on an "AS IS" BASIS,
016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017: See the License for the specific language governing permissions and
018: limitations under the License.
019:
020: */
021:
022: package org.apache.derby.impl.sql.compile;
023:
024: import org.apache.derby.iapi.sql.compile.CostEstimate;
025: import org.apache.derby.iapi.sql.compile.ExpressionClassBuilderInterface;
026: import org.apache.derby.iapi.sql.compile.JoinStrategy;
027: import org.apache.derby.iapi.sql.compile.Optimizable;
028: import org.apache.derby.iapi.sql.compile.Optimizer;
029: import org.apache.derby.iapi.sql.compile.OptimizablePredicateList;
030: import org.apache.derby.iapi.sql.compile.OptimizablePredicate;
031:
032: import org.apache.derby.iapi.sql.dictionary.DataDictionary;
033: import org.apache.derby.iapi.sql.dictionary.ConglomerateDescriptor;
034:
035: import org.apache.derby.iapi.store.access.StoreCostController;
036: import org.apache.derby.iapi.store.access.TransactionController;
037:
038: import org.apache.derby.iapi.services.compiler.MethodBuilder;
039:
040: import org.apache.derby.impl.sql.compile.ExpressionClassBuilder;
041:
042: import org.apache.derby.iapi.error.StandardException;
043:
044: import org.apache.derby.iapi.services.sanity.SanityManager;
045:
046: public class NestedLoopJoinStrategy extends BaseJoinStrategy {
047: public NestedLoopJoinStrategy() {
048: }
049:
050: /**
051: * @see JoinStrategy#feasible
052: *
053: * @exception StandardException Thrown on error
054: */
055: public boolean feasible(Optimizable innerTable,
056: OptimizablePredicateList predList, Optimizer optimizer)
057: throws StandardException {
058: /* Nested loop is feasible, except in the corner case
059: * where innerTable is a VTI that cannot be materialized
060: * (because it has a join column as a parameter) and
061: * it cannot be instantiated multiple times.
062: * RESOLVE - Actually, the above would work if all of
063: * the tables outer to innerTable were 1 row tables, but
064: * we don't have that info yet, and it should probably
065: * be hidden in inner table somewhere.
066: * NOTE: A derived table that is correlated with an outer
067: * query block is not materializable, but it can be
068: * "instantiated" multiple times because that only has
069: * meaning for VTIs.
070: */
071: if (innerTable.isMaterializable()) {
072: return true;
073: }
074: if (innerTable.supportsMultipleInstantiations()) {
075: return true;
076: }
077: return false;
078: }
079:
080: /** @see JoinStrategy#multiplyBaseCostByOuterRows */
081: public boolean multiplyBaseCostByOuterRows() {
082: return true;
083: }
084:
085: /**
086: * @see JoinStrategy#getBasePredicates
087: *
088: * @exception StandardException Thrown on error
089: */
090: public OptimizablePredicateList getBasePredicates(
091: OptimizablePredicateList predList,
092: OptimizablePredicateList basePredicates,
093: Optimizable innerTable) throws StandardException {
094: if (SanityManager.DEBUG) {
095: SanityManager.ASSERT(basePredicates == null
096: || basePredicates.size() == 0,
097: "The base predicate list should be empty.");
098: }
099:
100: if (predList != null) {
101: predList.transferAllPredicates(basePredicates);
102: basePredicates
103: .classify(innerTable, innerTable
104: .getCurrentAccessPath()
105: .getConglomerateDescriptor());
106: }
107:
108: return basePredicates;
109: }
110:
111: /** @see JoinStrategy#nonBasePredicateSelectivity */
112: public double nonBasePredicateSelectivity(Optimizable innerTable,
113: OptimizablePredicateList predList) {
114: /*
115: ** For nested loop, all predicates are base predicates, so there
116: ** is no extra selectivity.
117: */
118: return 1.0;
119: }
120:
121: /**
122: * @see JoinStrategy#putBasePredicates
123: *
124: * @exception StandardException Thrown on error
125: */
126: public void putBasePredicates(OptimizablePredicateList predList,
127: OptimizablePredicateList basePredicates)
128: throws StandardException {
129: for (int i = basePredicates.size() - 1; i >= 0; i--) {
130: OptimizablePredicate pred = basePredicates
131: .getOptPredicate(i);
132:
133: predList.addOptPredicate(pred);
134: basePredicates.removeOptPredicate(i);
135: }
136: }
137:
138: /* @see JoinStrategy#estimateCost */
139: public void estimateCost(Optimizable innerTable,
140: OptimizablePredicateList predList,
141: ConglomerateDescriptor cd, CostEstimate outerCost,
142: Optimizer optimizer, CostEstimate costEstimate) {
143: costEstimate.multiply(outerCost.rowCount(), costEstimate);
144:
145: optimizer.trace(Optimizer.COST_OF_N_SCANS, innerTable
146: .getTableNumber(), 0, outerCost.rowCount(),
147: costEstimate);
148: }
149:
150: /** @see JoinStrategy#maxCapacity */
151: public int maxCapacity(int userSpecifiedCapacity,
152: int maxMemoryPerTable, double perRowUsage) {
153: return Integer.MAX_VALUE;
154: }
155:
156: /** @see JoinStrategy#getName */
157: public String getName() {
158: return "NESTEDLOOP";
159: }
160:
161: /** @see JoinStrategy#scanCostType */
162: public int scanCostType() {
163: return StoreCostController.STORECOST_SCAN_NORMAL;
164: }
165:
166: /** @see JoinStrategy#resultSetMethodName */
167: public String resultSetMethodName(boolean bulkFetch) {
168: if (bulkFetch)
169: return "getBulkTableScanResultSet";
170: else
171: return "getTableScanResultSet";
172: }
173:
174: /** @see JoinStrategy#joinResultSetMethodName */
175: public String joinResultSetMethodName() {
176: return "getNestedLoopJoinResultSet";
177: }
178:
179: /** @see JoinStrategy#halfOuterJoinResultSetMethodName */
180: public String halfOuterJoinResultSetMethodName() {
181: return "getNestedLoopLeftOuterJoinResultSet";
182: }
183:
184: /**
185: * @see JoinStrategy#getScanArgs
186: *
187: * @exception StandardException Thrown on error
188: */
189: public int getScanArgs(TransactionController tc, MethodBuilder mb,
190: Optimizable innerTable,
191: OptimizablePredicateList storeRestrictionList,
192: OptimizablePredicateList nonStoreRestrictionList,
193: ExpressionClassBuilderInterface acbi, int bulkFetch,
194: MethodBuilder resultRowAllocator, int colRefItem,
195: int indexColItem, int lockMode, boolean tableLocked,
196: int isolationLevel, int maxMemoryPerTable)
197: throws StandardException {
198: ExpressionClassBuilder acb = (ExpressionClassBuilder) acbi;
199: int numArgs;
200:
201: if (SanityManager.DEBUG) {
202: if (nonStoreRestrictionList.size() != 0) {
203: SanityManager
204: .THROWASSERT("nonStoreRestrictionList should be empty for "
205: + "nested loop join strategy, but it contains "
206: + nonStoreRestrictionList.size()
207: + " elements");
208: }
209: }
210:
211: if (bulkFetch > 1) {
212: numArgs = 25;
213: } else {
214: numArgs = 24;
215: }
216:
217: fillInScanArgs1(tc, mb, innerTable, storeRestrictionList, acb,
218: resultRowAllocator);
219:
220: fillInScanArgs2(mb, innerTable, bulkFetch, colRefItem,
221: indexColItem, lockMode, tableLocked, isolationLevel);
222:
223: return numArgs;
224: }
225:
226: /**
227: * @see JoinStrategy#divideUpPredicateLists
228: *
229: * @exception StandardException Thrown on error
230: */
231: public void divideUpPredicateLists(Optimizable innerTable,
232: OptimizablePredicateList originalRestrictionList,
233: OptimizablePredicateList storeRestrictionList,
234: OptimizablePredicateList nonStoreRestrictionList,
235: OptimizablePredicateList requalificationRestrictionList,
236: DataDictionary dd) throws StandardException {
237: /*
238: ** All predicates are store predicates. No requalification is
239: ** necessary for non-covering index scans.
240: */
241: originalRestrictionList
242: .setPredicatesAndProperties(storeRestrictionList);
243: }
244:
245: /**
246: * @see JoinStrategy#doesMaterialization
247: */
248: public boolean doesMaterialization() {
249: return false;
250: }
251:
252: public String toString() {
253: return getName();
254: }
255:
256: /**
257: * Can this join strategy be used on the
258: * outermost table of a join.
259: *
260: * @return Whether or not this join strategy
261: * can be used on the outermose table of a join.
262: */
263: protected boolean validForOutermostTable() {
264: return true;
265: }
266: }
|