in phoenix-core-client/src/main/java/org/apache/phoenix/compile/WhereOptimizer.java [1002:1231]
private KeySlots andKeySlots(AndExpression andExpression, List<KeySlots> childSlots) {
if(childSlots.isEmpty()) {
return null;
}
// Exit early if it's already been determined that one of the child slots cannot
// possibly be true.
boolean partialExtraction = andExpression.getChildren().size() != childSlots.size();
int nChildSlots = childSlots.size();
for (int i = 0; i < nChildSlots; i++) {
KeySlots childSlot = childSlots.get(i);
if (childSlot == EMPTY_KEY_SLOTS) {
return EMPTY_KEY_SLOTS;
}
// If any child slots represent partially extracted expressions, then carry
// that forward. An example of a partially extracted expression would be a
// RVC of (K1, K2, NonK3) in which only leading PK columns are extracted
// from the RVC.
partialExtraction |= childSlot.isPartialExtraction();
}
boolean mayExtractNodes = true;
ImmutableBytesWritable ptr = context.getTempPtr();
RowKeySchema rowKeySchema = table.getRowKeySchema();
int nPkColumns = table.getPKColumns().size();
KeySlot[] keySlotArray = new KeySlot[nPkColumns];
int initPkPos = (table.getBucketNum() ==null ? 0 : 1) + (this.context.getConnection().getTenantId() != null && table.isMultiTenant() ? 1 : 0) + (table.getViewIndexId() == null ? 0 : 1);
List<List<List<KeyRange[]>>> slotsTrailingRanges = Lists.newArrayListWithExpectedSize(nPkColumns);
// Process all columns being ANDed in position order to guarantee
// we have all information for leading PK columns before we attempt
// to intersect them. For example:
// (A, B, C) >= (1, 2, 3) AND (B, C) < (4, 5) AND A = 1
// will processing slot 0 (i.e PK column A) across all children first,
// followed by slot 1 (PK column B), and finally slot 2 (C). This is
// done because we carry forward any constraints from preceding PK
// columns which may impact following PK columns. In the above example
// we'd carry forward that (B,C) >= (2,3) since we know that A is 1.
for (int pkPos = initPkPos; pkPos < nPkColumns; pkPos++) {
SlotsIterator iterator = new SlotsIterator(childSlots, pkPos);
OrderPreserving orderPreserving = null;
Set<KeyPart> visitedKeyParts = Sets.newHashSet();
Set<Expression> extractNodes = new LinkedHashSet<>();
List<KeyRange> keyRanges = Lists.newArrayList();
// This is the information carried forward as we process in PK order.
// It's parallel with the list of keyRanges.
List<KeyRange[]> trailingRangesList = Lists.<KeyRange[]>newArrayList();
KeyRange result = null;
TrailingRangeIterator trailingRangeIterator = new TrailingRangeIterator(initPkPos, pkPos, slotsTrailingRanges);
// Iterate through all combinations (i.e. constraints) for the PK slot being processed.
// For example, with (A = 1 OR A = 2) AND (A,B) > (1,2) AND C = 3, we'd process the
// following two combinations:
// A=1,(A,B) > (1,2)
// A=2,(A,B) > (1,2)
// If we have no constraints for a PK, then we still must iterate through the information
// that may have been rolled up based on the processing of previous PK slots. For example,
// in the above ANDed expressions, we have no constraint on B, but we would end up with
// rolled up information based on the B part of the (A,B) constraint.
while (iterator.next() || (trailingRangeIterator.hasNext() && result != KeyRange.EMPTY_RANGE)) {
result = null;
KeyRange[] trailingRanges = newTrailingRange();
for (int i = 0; i < nChildSlots && result != KeyRange.EMPTY_RANGE; i++) {
KeySlot slot = iterator.getSlot(i);
// Rollup the order preserving and concatenate the extracted expressions.
// Extracted expressions end up being removed from the AND expression at
// the top level call (pushKeyExpressionsToScan) with anything remaining
// ending up as a Filter (rather than contributing to the start/stop row
// of the scan.
if (slot != null) {
KeyRange otherRange = iterator.getRange(i);
KeyRange range = result;
if (slot.getOrderPreserving() != null) {
orderPreserving = slot.getOrderPreserving().combine(orderPreserving);
}
// Extract once per iteration, when there are large number
// of OR clauses (for e.g N > 100k).
// The extractNodes.addAll method can get called N times.
if (visitedKeyParts.add(slot.getKeyPart()) && slot.getKeyPart().getExtractNodes() != null) {
extractNodes.addAll(slot.getKeyPart().getExtractNodes());
}
// Keep a running intersection of the ranges we see. Note that the
// ranges are derived from constants appearing on the RHS of a comparison
// expression. For example, the expression A > 5 would produce a keyRange
// of (5, *) for slot 0 (assuming A is the leading PK column) If the result
// ends up as an empty key, that combination is ruled out. This is essentially
// doing constant reduction.
result = intersectRanges(pkPos, range, otherRange, trailingRanges);
}
}
if (result != KeyRange.EMPTY_RANGE) {
Map<KeyRange,List<KeyRange[]>> results = Maps.newHashMap();
trailingRangeIterator.init();
// Process all constraints that have been rolled up from previous
// processing of PK slots. This occurs for RVCs which span PK slots
// in which the leading part of the RVC is determined to be equal
// to a constant on the RHS.
while (trailingRangeIterator.hasNext()) {
// Loop through all combinations of values for all previously
// calculated slots.
do {
// Loop through all combinations of range constraints for the
// current combinations of values. If no valid combinations
// are found, we can rule out the result. We can also end up
// modifying the result if it has an intersection with the
// range constraints.
do {
KeyRange priorTrailingRange = trailingRangeIterator.getRange();
if (priorTrailingRange != KeyRange.EVERYTHING_RANGE) {
KeyRange[] intTrailingRanges = Arrays.copyOf(trailingRanges, trailingRanges.length);
// Intersect the current result with each range constraint. We essentially
// rule out the result when we find a constraint that has no intersection
KeyRange intResult = intersectRanges(pkPos, result, priorTrailingRange, intTrailingRanges);
if (intResult != KeyRange.EMPTY_RANGE) {
addResult(intResult, intTrailingRanges, results);
}
}
} while (trailingRangeIterator.nextTrailingRange());
} while (trailingRangeIterator.nextRange());
}
if (results.isEmpty() && result != null) { // No trailing range constraints
keyRanges.add(result);
trailingRangesList.add(trailingRanges);
} else {
mayExtractNodes &= results.size() <= 1;
for (Map.Entry<KeyRange,List<KeyRange[]>> entry : results.entrySet()) {
// Add same KeyRange with each KeyRange[] since the two lists are parallel
for (KeyRange[] trailingRange : entry.getValue()) {
keyRanges.add(entry.getKey());
trailingRangesList.add(trailingRange);
}
}
}
}
}
if (result == null && keyRanges.isEmpty()) {
slotsTrailingRanges.add(Collections.<List<KeyRange[]>>emptyList());
} else {
// If we encountered a result for this slot and
// there are no ranges, this is the degenerate case.
if (keyRanges.isEmpty()) {
return EMPTY_KEY_SLOTS;
}
// Similar to KeyRange.coalesce(), except we must combine together
// any rolled up constraints (as a list of KeyRanges) for a
// particular value (as they're coalesced together). We maintain
// these KeyRange constraints as a parallel list between keyRanges
// and trailingRangesList.
keyRanges = coalesceKeyRangesAndTrailingRanges(keyRanges, trailingRangesList, slotsTrailingRanges);
int maxSpan = 1;
for (KeyRange aRange : keyRanges) {
int span = rowKeySchema.computeMaxSpan(pkPos, aRange, context.getTempPtr());
if (span > maxSpan) {
maxSpan = span;
}
}
keySlotArray[pkPos] = new KeySlot(
new BaseKeyPart(table, table.getPKColumns().get(pkPos), mayExtractNodes ? extractNodes : Collections.<Expression>emptySet()),
pkPos,
maxSpan,
keyRanges,
orderPreserving);
}
}
// Filters trailing part of RVC based on ranges from PK columns after the one we're
// currently processing that may overlap with this range. For example, with a PK
// columns A,B,C and a range of A from [(1,2,3) - (4,5,6)] and B from (6-*), we
// can filter the trailing part of the RVC for A, because the trailing part of
// the RVC (2,3)-(5,6) does not intersect with (6-*). By removing the trailing
// part of the RVC, we end up with a range of A from [1-4] and B from (6-*) which
// enables us to use a skip scan.
for (int i = 0; i < keySlotArray.length; i++) {
KeySlot keySlot = keySlotArray[i];
if (keySlot == null) continue;
int pkSpan = keySlot.getPKSpan();
int pkPos = keySlot.getPKPosition();
boolean slotWasIntersected = false;
List<KeyRange> keyRanges = keySlot.getKeyRanges();
List<KeyRange> slotTrimmedResults = Lists.newArrayListWithExpectedSize(keyRanges.size());
for (KeyRange result : keyRanges) {
boolean resultWasIntersected = false;
Set<KeyRange> trimmedResults = Sets.newHashSetWithExpectedSize(keyRanges.size());
for (int trailingPkPos = pkPos+1; trailingPkPos < pkPos+pkSpan && trailingPkPos < nPkColumns; trailingPkPos++) {
KeySlot nextKeySlot = keySlotArray[trailingPkPos];
if (nextKeySlot == null) continue;
for (KeyRange trailingRange : nextKeySlot.getKeyRanges()) {
resultWasIntersected = true;
KeyRange intResult = intersectTrailing(result, pkPos, trailingRange, trailingPkPos);
if (intResult != KeyRange.EMPTY_RANGE) {
trimmedResults.add(intResult);
}
}
}
if (resultWasIntersected) {
slotWasIntersected = true;
slotTrimmedResults.addAll(trimmedResults);
mayExtractNodes &= trimmedResults.size() <= 1;
} else {
slotTrimmedResults.add(result);
}
}
if (slotTrimmedResults.isEmpty()) {
return EMPTY_KEY_SLOTS;
}
if (slotWasIntersected) {
// Re-coalesce the ranges and recalc the max span since the ranges may have changed
slotTrimmedResults = KeyRange.coalesce(slotTrimmedResults);
pkSpan = 1;
for (KeyRange trimmedResult : slotTrimmedResults) {
pkSpan = Math.max(pkSpan, rowKeySchema.computeMaxSpan(pkPos, trimmedResult, ptr));
}
}
Set<Expression> extractNodes = mayExtractNodes ?
keySlotArray[pkPos].getKeyPart().getExtractNodes() : new LinkedHashSet<>();
keySlotArray[pkPos] = new KeySlot(
new BaseKeyPart(table, table.getPKColumns().get(pkPos), extractNodes),
pkPos,
pkSpan,
slotTrimmedResults,
keySlotArray[pkPos].getOrderPreserving());
}
List<KeySlot> keySlots = Arrays.asList(keySlotArray);
// If we have a salt column, skip that slot because
// they'll never be an expression that uses it directly.
keySlots = keySlots.subList(initPkPos, keySlots.size());
return new MultiKeySlot(keySlots, partialExtraction);
}