/* Copyright (c) 2001-2016, The HSQL Development Group
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* Redistributions of source code must retain the above copyright notice, this
* list of conditions and the following disclaimer.
*
* Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* Neither the name of the HSQL Development Group nor the names of its
* contributors may be used to endorse or promote products derived from this
* software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
* OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
package org.hsqldb;
import org.hsqldb.
ParserDQL.
CompileContext;
import org.hsqldb.
RangeVariable.
RangeVariableConditions;
import org.hsqldb.error.
Error;
import org.hsqldb.error.
ErrorCode;
import org.hsqldb.index.
Index;
import org.hsqldb.index.
Index.
IndexUse;
import org.hsqldb.lib.
ArrayUtil;
import org.hsqldb.lib.
HashMap;
import org.hsqldb.lib.
HsqlArrayList;
import org.hsqldb.lib.
HsqlList;
import org.hsqldb.lib.
IntKeyIntValueHashMap;
import org.hsqldb.lib.
Iterator;
import org.hsqldb.lib.
MultiValueHashMap;
import org.hsqldb.lib.
OrderedHashSet;
import org.hsqldb.lib.
OrderedIntHashSet;
import org.hsqldb.persist.
PersistentStore;
/**
* Determines how JOIN and WHERE expressions are used in query
* processing and which indexes are used for table access.
*
* @author Fred Toussi (fredt@users dot sourceforge.net)
* @version 2.3.3
* @since 1.9.0
*/
public class
RangeVariableResolver {
Session session;
QuerySpecification select;
RangeVariable[]
rangeVariables;
Expression conditions;
OrderedHashSet rangeVarSet = new
OrderedHashSet();
CompileContext compileContext;
SortAndSlice sortAndSlice =
SortAndSlice.
noSort;
boolean
reorder;
//
HsqlArrayList[]
tempJoinExpressions;
HsqlArrayList[]
joinExpressions;
HsqlArrayList[]
whereExpressions;
HsqlArrayList queryConditions = new
HsqlArrayList();
//
Expression[]
inExpressions;
boolean[]
inInJoin;
int
inExpressionCount = 0;
boolean
expandInExpression = true;
//
int
firstLeftJoinIndex;
int
firstRightJoinIndex;
int
lastRightJoinIndex;
int
firstLateralJoinIndex;
int
firstOuterJoinIndex;
int
lastOuterJoinIndex;
//
OrderedIntHashSet colIndexSetEqual = new
OrderedIntHashSet();
IntKeyIntValueHashMap colIndexSetOther = new
IntKeyIntValueHashMap();
OrderedHashSet tempSet = new
OrderedHashSet();
HashMap tempMap = new
HashMap();
MultiValueHashMap tempMultiMap = new
MultiValueHashMap();
RangeVariableResolver(
Session session,
QuerySpecification select) {
this.
session =
session;
this.
select =
select;
this.
rangeVariables =
select.
rangeVariables;
this.
conditions =
select.
queryCondition;
this.
compileContext =
select.
compileContext;
this.
sortAndSlice =
select.
sortAndSlice;
this.
reorder = true;
// this.expandInExpression = select.checkQueryCondition == null;
initialise();
}
RangeVariableResolver(
Session session,
RangeVariable[]
rangeVariables,
Expression conditions,
CompileContext compileContext, boolean
reorder) {
this.
session =
session;
this.
rangeVariables =
rangeVariables;
this.
conditions =
conditions;
this.
compileContext =
compileContext;
this.
reorder =
reorder;
initialise();
}
private void
initialise() {
firstLeftJoinIndex =
rangeVariables.length;
firstRightJoinIndex =
rangeVariables.length;
firstLateralJoinIndex =
rangeVariables.length;
firstOuterJoinIndex =
rangeVariables.length;
inExpressions = new
Expression[
rangeVariables.length];
inInJoin = new boolean[
rangeVariables.length];
tempJoinExpressions = new
HsqlArrayList[
rangeVariables.length];
for (int
i = 0;
i <
rangeVariables.length;
i++) {
tempJoinExpressions[
i] = new
HsqlArrayList();
}
joinExpressions = new
HsqlArrayList[
rangeVariables.length];
for (int
i = 0;
i <
rangeVariables.length;
i++) {
joinExpressions[
i] = new
HsqlArrayList();
}
whereExpressions = new
HsqlArrayList[
rangeVariables.length];
for (int
i = 0;
i <
rangeVariables.length;
i++) {
whereExpressions[
i] = new
HsqlArrayList();
}
queryConditions.
clear();
}
void
processConditions() {
if (
session.
sessionOptimization < 8) {
reorder = false;
}
decomposeAndConditions(
session,
conditions,
queryConditions);
for (int
i = 0;
i <
rangeVariables.length;
i++) {
rangeVarSet.
add(
rangeVariables[
i]);
if (
rangeVariables[
i].
joinCondition == null) {
continue;
}
decomposeAndConditions(
session,
rangeVariables[
i].
joinCondition,
tempJoinExpressions[
i]);
}
for (int
j = 0;
j <
queryConditions.
size();
j++) {
Expression e = (
Expression)
queryConditions.
get(
j);
if (
e.
isTrue()) {
continue;
}
if (
e.
isSingleColumnEqual ||
e.
isColumnCondition) {
RangeVariable range =
e.
getLeftNode().
getRangeVariable();
if (
e.
getLeftNode().
opType ==
OpTypes.
COLUMN
&&
range != null) {
int
index =
rangeVarSet.
getIndex(
range);
if (
index > 0) {
rangeVariables[
index].
isLeftJoin = false;
}
}
range =
e.
getRightNode().
getRangeVariable();
if (
e.
getRightNode().
opType ==
OpTypes.
COLUMN
&&
range != null) {
int
index =
rangeVarSet.
getIndex(
range);
if (
index > 0) {
rangeVariables[
index].
isLeftJoin = false;
}
}
}
}
for (int
i = 0;
i <
rangeVariables.length;
i++) {
RangeVariable range =
rangeVariables[
i];
boolean
isOuter = false;
if (
range.
isLeftJoin) {
if (
firstLeftJoinIndex ==
rangeVariables.length) {
firstLeftJoinIndex =
i;
}
isOuter = true;
}
if (
range.
isRightJoin) {
if (
firstRightJoinIndex ==
rangeVariables.length) {
firstRightJoinIndex =
i;
}
lastRightJoinIndex =
i;
isOuter = true;
}
if (
range.
isLateral) {
if (
firstLateralJoinIndex ==
rangeVariables.length) {
firstLateralJoinIndex =
i;
}
isOuter = true;
}
if (
isOuter) {
if (
firstOuterJoinIndex ==
rangeVariables.length) {
firstOuterJoinIndex =
i;
}
lastOuterJoinIndex =
i;
}
}
expandConditions();
conditions = null;
reorder();
assignToLists();
assignToRangeVariables();
// rangePositionInJoin and the two bounds are used only together, regardless of any IN ranges added
if (
select != null) {
select.
startInnerRange = 0;
select.
endInnerRange =
rangeVariables.length;
if (
firstRightJoinIndex <
rangeVariables.length) {
select.
startInnerRange =
firstRightJoinIndex;
}
if (
firstLeftJoinIndex <
rangeVariables.length) {
select.
endInnerRange =
firstLeftJoinIndex;
}
}
for (int
i = 0;
i <
rangeVariables.length;
i++) {
rangeVariables[
i].
rangePositionInJoin =
i;
}
if (
expandInExpression &&
inExpressionCount != 0) {
setInConditionsAsTables();
}
}
/**
* Divides AND and OR conditions and assigns
*/
static
Expression decomposeAndConditions(
Session session,
Expression e,
HsqlList conditions) {
if (
e == null) {
return
Expression.
EXPR_TRUE;
}
Expression arg1 =
e.
getLeftNode();
Expression arg2 =
e.
getRightNode();
int
type =
e.
getType();
if (
type ==
OpTypes.
AND) {
arg1 =
decomposeAndConditions(
session,
arg1,
conditions);
arg2 =
decomposeAndConditions(
session,
arg2,
conditions);
if (
arg1.
isTrue()) {
return
arg2;
}
if (
arg2.
isTrue()) {
return
arg1;
}
e.
setLeftNode(
arg1);
e.
setRightNode(
arg2);
return
e;
} else if (
type ==
OpTypes.
EQUAL) {
if (
arg1.
getType() ==
OpTypes.
ROW
&&
arg2.
getType() ==
OpTypes.
ROW) {
for (int
i = 0;
i <
arg1.
nodes.length;
i++) {
Expression part = new
ExpressionLogical(
arg1.
nodes[
i],
arg2.
nodes[
i]);
part.
resolveTypes(
session, null);
conditions.
add(
part);
}
return
Expression.
EXPR_TRUE;
}
}
if (!
e.
isTrue()) {
conditions.
add(
e);
}
return
Expression.
EXPR_TRUE;
}
/**
* Divides AND and OR conditions and assigns
*/
static
Expression decomposeOrConditions(
Expression e,
HsqlList conditions) {
if (
e == null) {
return
Expression.
EXPR_FALSE;
}
Expression arg1 =
e.
getLeftNode();
Expression arg2 =
e.
getRightNode();
int
type =
e.
getType();
if (
type ==
OpTypes.
OR) {
arg1 =
decomposeOrConditions(
arg1,
conditions);
arg2 =
decomposeOrConditions(
arg2,
conditions);
if (
arg1.
isFalse()) {
return
arg2;
}
if (
arg2.
isFalse()) {
return
arg1;
}
e = new
ExpressionLogical(
OpTypes.
OR,
arg1,
arg2);
return
e;
}
if (!
e.
isFalse()) {
conditions.
add(
e);
}
return
Expression.
EXPR_FALSE;
}
void
expandConditions() {
HsqlArrayList[]
array =
tempJoinExpressions;
if (
firstRightJoinIndex ==
rangeVariables.length) {
moveConditions(
tempJoinExpressions, 0,
firstOuterJoinIndex,
queryConditions, -1);
}
if (
firstOuterJoinIndex < 2) {
return;
}
for (int
i = 0;
i <
firstOuterJoinIndex;
i++) {
moveConditions(
tempJoinExpressions, 0,
firstOuterJoinIndex,
tempJoinExpressions[
i],
i);
}
if (
firstOuterJoinIndex < 3) {
return;
}
for (int
i = 0;
i <
firstOuterJoinIndex;
i++) {
HsqlArrayList list =
array[
i];
tempMultiMap.
clear();
tempSet.
clear();
tempMap.
clear();
boolean
hasValEqual = false;
boolean
hasColEqual = false;
boolean
hasChain = false;
for (int
j = 0;
j <
list.
size();
j++) {
Expression e = (
Expression)
list.
get(
j);
if (
e.
isTrue()) {
continue;
}
if (
e.
isSingleColumnEqual) {
hasValEqual = true;
if (
e.
getLeftNode().
opType ==
OpTypes.
COLUMN) {
tempMap.
put(
e.
getLeftNode().
getColumn(),
e.
getRightNode());
} else if (
e.
getRightNode().
opType ==
OpTypes.
COLUMN) {
tempMap.
put(
e.
getRightNode().
getColumn(),
e.
getLeftNode());
}
continue;
}
if (!
e.
isColumnEqual) {
continue;
}
if (
e.
getLeftNode().
getRangeVariable()
==
e.
getRightNode().
getRangeVariable()) {
continue;
}
if (
e.
getLeftNode().
getRangeVariable() == null
||
e.
getRightNode().
getRangeVariable() == null) {
continue;
}
int
idx =
rangeVarSet.
getIndex(
e.
getLeftNode().
getRangeVariable());
if (
idx < 0) {
e.
isSingleColumnEqual = true;
e.
isSingleColumnCondition = true;
tempMap.
put(
e.
getRightNode().
getColumn(),
e.
getLeftNode());
continue;
}
if (
idx >=
firstOuterJoinIndex) {
continue;
}
idx =
rangeVarSet.
getIndex(
e.
getRightNode().
getRangeVariable());
if (
idx < 0) {
e.
isSingleColumnEqual = true;
e.
isSingleColumnCondition = true;
tempMap.
put(
e.
getRightNode().
getColumn(),
e.
getLeftNode());
continue;
}
if (
idx >=
firstOuterJoinIndex) {
continue;
}
hasColEqual = true;
if (
e.
getLeftNode().
getRangeVariable() ==
rangeVariables[
i]) {
ColumnSchema column =
e.
getLeftNode().
getColumn();
tempMultiMap.
put(
column,
e.
getRightNode());
if (
tempMultiMap.
valueCount(
column) > 1) {
hasChain = true;
}
} else if (
e.
getRightNode().
getRangeVariable()
==
rangeVariables[
i]) {
ColumnSchema column =
e.
getRightNode().
getColumn();
tempMultiMap.
put(
column,
e.
getLeftNode());
if (
tempMultiMap.
valueCount(
column) > 1) {
hasChain = true;
}
}
}
if (
hasChain) {
Iterator keyIt =
tempMultiMap.
keySet().
iterator();
while (
keyIt.
hasNext()) {
Object key =
keyIt.
next();
Iterator it =
tempMultiMap.
get(
key);
tempSet.
clear();
while (
it.
hasNext()) {
tempSet.
add(
it.
next());
}
while (
tempSet.
size() > 1) {
Expression e1 =
(
Expression)
tempSet.
remove(
tempSet.
size() - 1);
for (int
j = 0;
j <
tempSet.
size();
j++) {
Expression e2 = (
Expression)
tempSet.
get(
j);
closeJoinChain(
array,
e1,
e2);
}
}
}
}
if (
hasColEqual &&
hasValEqual) {
Iterator keyIt =
tempMultiMap.
keySet().
iterator();
while (
keyIt.
hasNext()) {
Object key =
keyIt.
next();
Expression e1 = (
Expression)
tempMap.
get(
key);
if (
e1 != null) {
Iterator it =
tempMultiMap.
get(
key);
while (
it.
hasNext()) {
Expression e2 = (
Expression)
it.
next();
Expression e = new
ExpressionLogical(
e1,
e2);
int
index =
rangeVarSet.
getIndex(
e2.
getRangeVariable());
array[
index].
add(
e);
}
}
}
}
}
}
void
moveConditions(
HsqlList[]
lists, int
rangeStart, int
rangeLimit,
HsqlList list, int
listIndex) {
for (int
j = 0;
j <
list.
size();
j++) {
Expression e = (
Expression)
list.
get(
j);
tempSet.
clear();
e.
collectRangeVariables(
rangeVariables,
tempSet);
int
index =
rangeVarSet.
getSmallestIndex(
tempSet);
if (
index <
rangeStart) {
continue;
}
index =
rangeVarSet.
getLargestIndex(
tempSet);
if (
index >=
rangeLimit) {
continue;
}
if (
index !=
listIndex) {
list.
remove(
j);
lists[
index].
add(
e);
j--;
}
}
}
void
closeJoinChain(
HsqlList[]
array,
Expression e1,
Expression e2) {
int
idx1 =
rangeVarSet.
getIndex(
e1.
getRangeVariable());
int
idx2 =
rangeVarSet.
getIndex(
e2.
getRangeVariable());
int
index =
idx1 >
idx2 ?
idx1
:
idx2;
if (
idx1 == -1 ||
idx2 == -1) {
return;
}
Expression e = new
ExpressionLogical(
e1,
e2);
for (int
i = 0;
i <
array[
index].
size();
i++) {
if (
e.
equals(
array[
index].
get(
i))) {
return;
}
}
array[
index].
add(
e);
}
void
reorder() {
if (!
reorder) {
return;
}
if (
rangeVariables.length == 1
||
firstRightJoinIndex !=
rangeVariables.length) {
return;
}
if (
firstLeftJoinIndex == 1) {
return;
}
if (
firstLateralJoinIndex !=
rangeVariables.length) {
return;
}
if (
sortAndSlice.
usingIndex
&&
sortAndSlice.
primaryTableIndex != null) {
return;
}
HsqlArrayList joins = new
HsqlArrayList();
HsqlArrayList starts = new
HsqlArrayList();
for (int
i = 0;
i <
firstLeftJoinIndex;
i++) {
HsqlArrayList tempJoins =
tempJoinExpressions[
i];
for (int
j = 0;
j <
tempJoins.
size();
j++) {
Expression e = (
Expression)
tempJoins.
get(
j);
if (
e.
isColumnEqual) {
joins.
add(
e);
} else if (
e.
isSingleColumnCondition) {
starts.
add(
e);
}
}
}
reorderRanges(
starts,
joins);
}
void
reorderRanges(
HsqlArrayList starts,
HsqlArrayList joins) {
if (
starts.
size() == 0) {
return;
}
int
position = -1;
RangeVariable range = null;
double
cost = 1024;
for (int
i = 0;
i <
firstLeftJoinIndex;
i++) {
Table table =
rangeVariables[
i].
rangeTable;
if (
table instanceof
TableDerived) {
continue;
}
collectIndexableColumns(
rangeVariables[
i],
starts);
IndexUse[]
indexes =
table.
getIndexForColumns(
session,
colIndexSetEqual,
OpTypes.
EQUAL, false);
Index index = null;
for (int
j = 0;
j <
indexes.length;
j++) {
index =
indexes[
j].
index;
double
currentCost =
searchCost(
session,
table,
index,
indexes[
j].
columnCount,
OpTypes.
EQUAL);
if (
currentCost <
cost) {
cost =
currentCost;
position =
i;
}
}
if (
index == null) {
Iterator it =
colIndexSetOther.
keySet().
iterator();
while (
it.
hasNext()) {
int
colIndex =
it.
nextInt();
index =
table.
getIndexForColumn(
session,
colIndex);
if (
index != null) {
cost =
table.
getRowStore(
session).
elementCount() / 2.0;
if (
colIndexSetOther.
get(
colIndex, 0) > 1) {
cost /= 2;
}
break;
}
}
}
if (
index == null) {
continue;
}
if (
i == 0) {
position = 0;
break;
}
}
if (
position < 0) {
return;
}
if (
position == 0 &&
firstLeftJoinIndex == 2) {
return;
}
RangeVariable[]
newRanges = new
RangeVariable[
rangeVariables.length];
ArrayUtil.
copyArray(
rangeVariables,
newRanges,
rangeVariables.length);
range =
newRanges[
position];
newRanges[
position] =
newRanges[0];
newRanges[0] =
range;
position = 1;
for (;
position <
firstLeftJoinIndex;
position++) {
boolean
found = false;
for (int
i = 0;
i <
joins.
size();
i++) {
Expression e = (
Expression)
joins.
get(
i);
if (
e == null) {
continue;
}
int
newPosition =
getJoinedRangePosition(
e,
position,
newRanges);
if (
newPosition >=
position) {
range =
newRanges[
position];
newRanges[
position] =
newRanges[
newPosition];
newRanges[
newPosition] =
range;
joins.
set(
i, null);
found = true;
break;
}
}
if (
found) {
continue;
}
for (int
i = 0;
i <
starts.
size();
i++) {
Table table =
newRanges[
i].
rangeTable;
collectIndexableColumns(
newRanges[
i],
starts);
IndexUse[]
indexes =
table.
getIndexForColumns(
session,
colIndexSetEqual,
OpTypes.
EQUAL, false);
if (
indexes.length > 0) {
found = true;
break;
}
}
if (!
found) {
break;
}
}
if (
position !=
firstLeftJoinIndex) {
return;
}
ArrayUtil.
copyArray(
newRanges,
rangeVariables,
rangeVariables.length);
joins.
clear();
for (int
i = 0;
i <
firstLeftJoinIndex;
i++) {
HsqlArrayList tempJoins =
tempJoinExpressions[
i];
joins.
addAll(
tempJoins);
tempJoins.
clear();
}
tempJoinExpressions[
firstLeftJoinIndex - 1].
addAll(
joins);
rangeVarSet.
clear();
for (int
i = 0;
i <
rangeVariables.length;
i++) {
rangeVarSet.
add(
rangeVariables[
i]);
}
}
int
getJoinedRangePosition(
Expression e, int
position,
RangeVariable[]
currentRanges) {
int
found = -1;
tempSet.
clear();
e.
getJoinRangeVariables(
currentRanges,
tempSet);
for (int
i = 0;
i <
tempSet.
size();
i++) {
for (int
j = 0;
j <
currentRanges.length;
j++) {
if (
tempSet.
get(
i) ==
currentRanges[
j]) {
if (
j >=
position) {
if (
found > 0) {
return -1;
} else {
found =
j;
}
}
}
}
}
return
found;
}
/**
* Assigns the conditions to separate lists
*/
void
assignToLists() {
int
lastOuterIndex = -1;
for (int
i = 0;
i <
rangeVariables.length;
i++) {
if (
rangeVariables[
i].
isLeftJoin) {
lastOuterIndex =
i;
}
if (
rangeVariables[
i].
isRightJoin) {
lastOuterIndex =
i;
}
if (
lastOuterIndex ==
i) {
joinExpressions[
i].
addAll(
tempJoinExpressions[
i]);
} else {
int
start =
lastOuterIndex + 1;
for (int
j = 0;
j <
tempJoinExpressions[
i].
size();
j++) {
Expression e = (
Expression)
tempJoinExpressions[
i].
get(
j);
assignToJoinLists(
e,
joinExpressions,
start);
}
}
}
for (int
i = 0;
i <
queryConditions.
size();
i++) {
assignToJoinLists((
Expression)
queryConditions.
get(
i),
whereExpressions,
lastRightJoinIndex);
}
}
/**
* Assigns a single condition to the relevant list of conditions
*
* Parameter first indicates the first range variable to which condition
* can be assigned
*/
void
assignToJoinLists(
Expression e,
HsqlList[]
expressionLists,
int
first) {
if (
e == null) {
return;
}
tempSet.
clear();
e.
collectRangeVariables(
rangeVariables,
tempSet);
int
index =
rangeVarSet.
getLargestIndex(
tempSet);
if (
index == -1) {
index = 0;
}
if (
index <
first) {
index =
first;
}
if (
e instanceof
ExpressionLogical) {
if (((
ExpressionLogical)
e).
isTerminal) {
index =
expressionLists.length - 1;
}
}
expressionLists[
index].
add(
e);
}
/**
* Assigns conditions to range variables and converts suitable IN conditions
* to table lookup.
*/
void
assignToRangeVariables() {
for (int
i = 0;
i <
rangeVariables.length;
i++) {
boolean
hasIndex = false;
RangeVariableConditions conditions;
if (
i <
firstLeftJoinIndex
&&
firstRightJoinIndex ==
rangeVariables.length) {
conditions =
rangeVariables[
i].
joinConditions[0];
joinExpressions[
i].
addAll(
whereExpressions[
i]);
assignToRangeVariable(
rangeVariables[
i],
conditions,
i,
joinExpressions[
i]);
assignToRangeVariable(
conditions,
joinExpressions[
i]);
} else {
conditions =
rangeVariables[
i].
joinConditions[0];
assignToRangeVariable(
rangeVariables[
i],
conditions,
i,
joinExpressions[
i]);
conditions =
rangeVariables[
i].
joinConditions[0];
if (
conditions.
hasIndex()) {
hasIndex = true;
}
assignToRangeVariable(
conditions,
joinExpressions[
i]);
conditions =
rangeVariables[
i].
whereConditions[0];
for (int
j =
i + 1;
j <
rangeVariables.length;
j++) {
if (
rangeVariables[
j].
isRightJoin) {
assignToRangeVariable(
rangeVariables[
j].
whereConditions[0],
whereExpressions[
i]);
}
}
if (!
hasIndex) {
assignToRangeVariable(
rangeVariables[
i],
conditions,
i,
whereExpressions[
i]);
}
assignToRangeVariable(
conditions,
whereExpressions[
i]);
}
}
}
void
assignToRangeVariable(
RangeVariableConditions conditions,
HsqlList exprList) {
for (int
j = 0,
size =
exprList.
size();
j <
size;
j++) {
Expression e = (
Expression)
exprList.
get(
j);
conditions.
addCondition(
e);
}
}
private void
collectIndexableColumns(
RangeVariable range,
HsqlList exprList) {
colIndexSetEqual.
clear();
colIndexSetOther.
clear();
for (int
j = 0,
size =
exprList.
size();
j <
size;
j++) {
Expression e = (
Expression)
exprList.
get(
j);
if (!
e.
isSingleColumnCondition) {
continue;
}
int
idx;
if (
e.
getLeftNode().
getRangeVariable() ==
range) {
idx =
e.
getLeftNode().
getColumnIndex();
} else if (
e.
getRightNode().
getRangeVariable() ==
range) {
idx =
e.
getRightNode().
getColumnIndex();
} else {
continue;
}
if (
e.
isSingleColumnEqual) {
colIndexSetEqual.
add(
idx);
} else {
int
count =
colIndexSetOther.
get(
idx, 0);
colIndexSetOther.
put(
idx,
count + 1);
}
}
}
/**
* Assigns a set of conditions to a range variable.
*/
void
assignToRangeVariable(
RangeVariable rangeVar,
RangeVariableConditions conditions,
int
rangeVarIndex,
HsqlList exprList) {
if (
exprList.
isEmpty()) {
return;
}
setIndexConditions(
conditions,
exprList,
rangeVarIndex, true);
}
private void
setIndexConditions(
RangeVariableConditions conditions,
HsqlList exprList, int
rangeVarIndex,
boolean
includeOr) {
boolean
hasIndex;
colIndexSetEqual.
clear();
colIndexSetOther.
clear();
for (int
j = 0,
size =
exprList.
size();
j <
size;
j++) {
Expression e = (
Expression)
exprList.
get(
j);
if (
e == null) {
continue;
}
if (!
e.
isIndexable(
conditions.
rangeVar)) {
continue;
}
int
type =
e.
getType();
switch (
type) {
case
OpTypes.
OR : {
continue;
}
case
OpTypes.
COLUMN : {
continue;
}
case
OpTypes.
EQUAL : {
if (
e.
getSubType() ==
OpTypes.
ANY_QUANTIFIED
||
e.
getSubType() ==
OpTypes.
ALL_QUANTIFIED) {
continue;
}
if (
e.
getLeftNode().
getRangeVariable()
!=
conditions.
rangeVar) {
continue;
}
int
colIndex =
e.
getLeftNode().
getColumnIndex();
colIndexSetEqual.
add(
colIndex);
break;
}
case
OpTypes.
IS_NULL : {
if (
e.
getLeftNode().
getRangeVariable()
!=
conditions.
rangeVar) {
continue;
}
if (
conditions.
rangeVar.
isLeftJoin) {
continue;
}
int
colIndex =
e.
getLeftNode().
getColumnIndex();
colIndexSetEqual.
add(
colIndex);
break;
}
case
OpTypes.
NOT : {
if (
e.
getLeftNode().
getLeftNode().
getRangeVariable()
!=
conditions.
rangeVar) {
continue;
}
if (
conditions.
rangeVar.
isLeftJoin) {
continue;
}
int
colIndex =
e.
getLeftNode().
getLeftNode().
getColumnIndex();
int
count =
colIndexSetOther.
get(
colIndex, 0);
colIndexSetOther.
put(
colIndex,
count + 1);
break;
}
case
OpTypes.
SMALLER :
case
OpTypes.
SMALLER_EQUAL :
case
OpTypes.
GREATER :
case
OpTypes.
GREATER_EQUAL :
case
OpTypes.
GREATER_EQUAL_PRE : {
if (
e.
getLeftNode().
getRangeVariable()
!=
conditions.
rangeVar) {
continue;
}
int
colIndex =
e.
getLeftNode().
getColumnIndex();
int
count =
colIndexSetOther.
get(
colIndex, 0);
colIndexSetOther.
put(
colIndex,
count + 1);
break;
}
default : {
throw
Error.
runtimeError(
ErrorCode.
U_S0500,
"RangeVariableResolver");
}
}
}
setEqualityConditions(
conditions,
exprList,
rangeVarIndex);
hasIndex =
conditions.
hasIndex();
if (!
hasIndex) {
setNonEqualityConditions(
conditions,
exprList,
rangeVarIndex);
hasIndex =
conditions.
hasIndex();
}
if (
rangeVarIndex == 0 &&
sortAndSlice.
usingIndex) {
hasIndex = true;
}
boolean
isOR = false;
if (!
hasIndex &&
includeOr) {
for (int
j = 0,
size =
exprList.
size();
j <
size;
j++) {
Expression e = (
Expression)
exprList.
get(
j);
if (
e == null) {
continue;
}
if (
e.
getType() ==
OpTypes.
OR) {
hasIndex =
setOrConditions(
conditions,
(
ExpressionLogical)
e,
rangeVarIndex);
if (
hasIndex) {
exprList.
set(
j, null);
isOR = true;
break;
}
} else if (
e.
getType() ==
OpTypes.
EQUAL
&&
e.
exprSubType ==
OpTypes.
ANY_QUANTIFIED) {
if (
rangeVarIndex >=
firstLeftJoinIndex
||
firstRightJoinIndex !=
rangeVariables.length) {
continue;
}
if (
e.
getRightNode().
isCorrelated()) {
continue;
}
OrderedIntHashSet set = new
OrderedIntHashSet();
((
ExpressionLogical)
e).
addLeftColumnsForAllAny(
conditions.
rangeVar,
set);
IndexUse[]
indexes =
conditions.
rangeVar.
rangeTable.
getIndexForColumns(
session,
set,
OpTypes.
EQUAL, false);
// code to disable IN optimisation
// index = null;
if (
indexes.length != 0
&&
inExpressions[
rangeVarIndex] == null) {
inExpressions[
rangeVarIndex] =
e;
inInJoin[
rangeVarIndex] =
conditions.
isJoin;
inExpressionCount++;
exprList.
set(
j, null);
break;
}
}
}
}
for (int
i = 0,
size =
exprList.
size();
i <
size;
i++) {
Expression e = (
Expression)
exprList.
get(
i);
if (
e == null) {
continue;
}
if (
isOR) {
for (int
j = 0;
j <
conditions.
rangeVar.
joinConditions.length;
j++) {
if (
conditions.
isJoin) {
conditions.
rangeVar.
joinConditions[
j]
.
nonIndexCondition =
ExpressionLogical
.
andExpressions(
e,
conditions.
rangeVar
.
joinConditions[
j].
nonIndexCondition);
} else {
conditions.
rangeVar.
whereConditions[
j]
.
nonIndexCondition =
ExpressionLogical
.
andExpressions(
e,
conditions.
rangeVar
.
whereConditions[
j].
nonIndexCondition);
}
}
} else {
conditions.
addCondition(
e);
}
}
}
private boolean
setOrConditions(
RangeVariableConditions conditions,
ExpressionLogical orExpression,
int
rangeVarIndex) {
HsqlArrayList orExprList = new
HsqlArrayList();
decomposeOrConditions(
orExpression,
orExprList);
RangeVariableConditions[]
conditionsArray =
new
RangeVariableConditions[
orExprList.
size()];
for (int
i = 0;
i <
orExprList.
size();
i++) {
HsqlArrayList exprList = new
HsqlArrayList();
Expression e = (
Expression)
orExprList.
get(
i);
decomposeAndConditions(
session,
e,
exprList);
RangeVariableConditions c =
new
RangeVariableConditions(
conditions);
setIndexConditions(
c,
exprList,
rangeVarIndex, false);
conditionsArray[
i] =
c;
if (!
c.
hasIndex()) {
// deep OR
return false;
}
}
Expression exclude = null;
for (int
i = 0;
i <
conditionsArray.length;
i++) {
RangeVariableConditions c =
conditionsArray[
i];
conditionsArray[
i].
excludeConditions =
exclude;
if (
i ==
conditionsArray.length - 1) {
break;
}
Expression e = null;
if (
c.
indexCond != null) {
for (int
k = 0;
k <
c.
indexedColumnCount;
k++) {
e =
ExpressionLogical.
andExpressions(
e,
c.
indexCond[
k]);
}
}
e =
ExpressionLogical.
andExpressions(
e,
c.
indexEndCondition);
e =
ExpressionLogical.
andExpressions(
e,
c.
nonIndexCondition);
exclude =
ExpressionLogical.
orExpressions(
e,
exclude);
}
if (
exclude != null) {
// return false;
}
if (
conditions.
isJoin) {
conditions.
rangeVar.
joinConditions =
conditionsArray;
conditionsArray = new
RangeVariableConditions[
orExprList.
size()];
ArrayUtil.
fillArray(
conditionsArray,
conditions.
rangeVar.
whereConditions[0]);
conditions.
rangeVar.
whereConditions =
conditionsArray;
} else {
conditions.
rangeVar.
whereConditions =
conditionsArray;
conditionsArray = new
RangeVariableConditions[
orExprList.
size()];
ArrayUtil.
fillArray(
conditionsArray,
conditions.
rangeVar.
joinConditions[0]);
conditions.
rangeVar.
joinConditions =
conditionsArray;
}
return true;
}
private void
setEqualityConditions(
RangeVariableConditions conditions,
HsqlList exprList, int
rangeVarIndex) {
Index index = null;
if (
rangeVarIndex == 0 &&
sortAndSlice.
usingIndex) {
index =
sortAndSlice.
primaryTableIndex;
if (
index != null) {
conditions.
rangeIndex =
index;
}
}
if (
index == null) {
IndexUse[]
indexes =
conditions.
rangeVar.
rangeTable.
getIndexForColumns(
session,
colIndexSetEqual,
OpTypes.
EQUAL, false);
if (
indexes.length == 0) {
return;
}
index =
indexes[0].
index;
double
cost =
Double.
MAX_VALUE;
if (
indexes.length > 1) {
for (int
i = 0;
i <
indexes.length;
i++) {
PersistentStore store =
conditions.
rangeVar.
rangeTable.
getRowStore(
session);
double
currentCost =
store.
searchCost(
session,
indexes[
i].
index,
indexes[
i].
columnCount,
OpTypes.
EQUAL);
if (
currentCost <
cost) {
cost =
currentCost;
index =
indexes[
i].
index;
}
}
}
}
int[]
cols =
index.
getColumns();
int
colCount =
cols.length;
Expression[]
firstRowExpressions = new
Expression[
cols.length];
for (int
j = 0;
j <
exprList.
size();
j++) {
Expression e = (
Expression)
exprList.
get(
j);
if (
e == null) {
continue;
}
int
type =
e.
getType();
if (
type ==
OpTypes.
EQUAL ||
type ==
OpTypes.
IS_NULL) {
if (
e.
getLeftNode().
getRangeVariable()
!=
conditions.
rangeVar) {
continue;
}
if (!
e.
isIndexable(
conditions.
rangeVar)) {
continue;
}
int
offset =
ArrayUtil.
find(
cols,
e.
getLeftNode().
getColumnIndex());
if (
offset != -1 &&
firstRowExpressions[
offset] == null) {
firstRowExpressions[
offset] =
e;
exprList.
set(
j, null);
continue;
}
}
}
boolean
hasNull = false;
for (int
i = 0;
i <
firstRowExpressions.length;
i++) {
Expression e =
firstRowExpressions[
i];
if (
e == null) {
if (
colCount ==
cols.length) {
colCount =
i;
}
hasNull = true;
continue;
}
if (
hasNull) {
exprList.
add(
e);
firstRowExpressions[
i] = null;
}
}
if (
colCount > 0) {
conditions.
addIndexCondition(
firstRowExpressions,
index,
colCount);
}
}
private void
setNonEqualityConditions(
RangeVariableConditions conditions,
HsqlList exprList,
int
rangeVarIndex) {
if (
colIndexSetOther.
isEmpty()) {
return;
}
int
currentCount = 0;
Index index = null;
Iterator it;
if (
rangeVarIndex == 0 &&
sortAndSlice.
usingIndex) {
index =
sortAndSlice.
primaryTableIndex;
}
if (
index == null) {
it =
colIndexSetOther.
keySet().
iterator();
while (
it.
hasNext()) {
int
colIndex =
it.
nextInt();
int
colCount =
colIndexSetOther.
get(
colIndex, 0);
if (
colCount >
currentCount) {
Index currentIndex =
conditions.
rangeVar.
rangeTable.
getIndexForColumn(
session,
colIndex);
if (
currentIndex != null) {
index =
currentIndex;
currentCount =
colCount;
}
}
}
}
if (
index == null) {
return;
}
int[]
cols =
index.
getColumns();
for (int
j = 0;
j <
exprList.
size();
j++) {
Expression e = (
Expression)
exprList.
get(
j);
if (
e == null) {
continue;
}
boolean
isIndexed = false;
switch (
e.
getType()) {
case
OpTypes.
NOT : {
if (
e.
getLeftNode().
getType() ==
OpTypes.
IS_NULL
&&
cols[0]
==
e.
getLeftNode().
getLeftNode()
.
getColumnIndex()) {
isIndexed = true;
}
break;
}
case
OpTypes.
SMALLER :
case
OpTypes.
SMALLER_EQUAL :
case
OpTypes.
GREATER :
case
OpTypes.
GREATER_EQUAL :
case
OpTypes.
GREATER_EQUAL_PRE : {
if (
cols[0] ==
e.
getLeftNode().
getColumnIndex()) {
if (
e.
getRightNode() != null
&& !
e.
getRightNode().
isCorrelated()) {
isIndexed = true;
}
}
break;
}
}
if (
isIndexed) {
Expression[]
firstRowExpressions =
new
Expression[
index.
getColumnCount()];
firstRowExpressions[0] =
e;
conditions.
addIndexCondition(
firstRowExpressions,
index, 1);
exprList.
set(
j, null);
break;
}
}
}
/**
* Converts an IN conditions into a JOIN
*/
void
setInConditionsAsTables() {
for (int
i =
rangeVariables.length - 1;
i >= 0;
i--) {
RangeVariable rangeVar =
rangeVariables[
i];
ExpressionLogical in = (
ExpressionLogical)
inExpressions[
i];
if (
in != null) {
OrderedIntHashSet set = new
OrderedIntHashSet();
in.
addLeftColumnsForAllAny(
rangeVar,
set);
IndexUse[]
indexes =
rangeVar.
rangeTable.
getIndexForColumns(
session,
set,
OpTypes.
EQUAL, false);
Index index =
indexes[0].
index;
int
indexedColCount = 0;
for (int
j = 0;
j <
index.
getColumnCount();
j++) {
if (
set.
contains(
index.
getColumns()[
j])) {
indexedColCount++;
} else {
break;
}
}
RangeVariable newRangeVar =
new
RangeVariable(
in.
getRightNode().
getTable(), null,
null, null,
compileContext);
newRangeVar.
isGenerated = true;
RangeVariable[]
newList =
new
RangeVariable[
rangeVariables.length + 1];
ArrayUtil.
copyAdjustArray(
rangeVariables,
newList,
newRangeVar,
i, 1);
rangeVariables =
newList;
// make two columns as arg
Expression[]
firstRowExpressions =
new
Expression[
index.
getColumnCount()];
for (int
j = 0;
j <
indexedColCount;
j++) {
int
leftIndex =
index.
getColumns()[
j];
int
rightIndex =
set.
getIndex(
leftIndex);
Expression e = new
ExpressionLogical(
rangeVar,
leftIndex,
newRangeVar,
rightIndex);
firstRowExpressions[
j] =
e;
}
boolean
isOuter =
rangeVariables[
i].
isLeftJoin
||
rangeVariables[
i].
isRightJoin;
RangeVariableConditions conditions =
!
inInJoin[
i] &&
isOuter ?
rangeVar.
whereConditions[0]
:
rangeVar.
joinConditions[0];
conditions.
addIndexCondition(
firstRowExpressions,
index,
indexedColCount);
for (int
j = 0;
j <
set.
size();
j++) {
int
leftIndex =
set.
get(
j);
int
rightIndex =
j;
Expression e = new
ExpressionLogical(
rangeVar,
leftIndex,
newRangeVar,
rightIndex);
conditions.
addCondition(
e);
}
}
}
}
private double
searchCost(
Session session,
Table table,
Index index,
int
count, int
opType) {
if (
table instanceof
TableDerived) {
return 1000;
} else {
return
table.
getRowStore(
session).
searchCost(
session,
index,
count,
opType);
}
}
}