package org.h2.table;
import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.Future;
import org.h2.command.dml.Query;
import org.h2.command.dml.Select;
import org.h2.command.dml.SelectUnion;
import org.h2.index.BaseIndex;
import org.h2.index.Cursor;
import org.h2.index.IndexCursor;
import org.h2.index.IndexLookupBatch;
import org.h2.index.ViewCursor;
import org.h2.index.ViewIndex;
import org.h2.message.DbException;
import org.h2.result.ResultInterface;
import org.h2.result.Row;
import org.h2.result.SearchRow;
import org.h2.util.DoneFuture;
import org.h2.util.LazyFuture;
import org.h2.util.Utils;
import org.h2.value.Value;
import org.h2.value.ValueLong;
public final class JoinBatch {
static final Cursor EMPTY_CURSOR = new Cursor() {
@Override
public boolean previous() {
return false;
}
@Override
public boolean next() {
return false;
}
@Override
public SearchRow getSearchRow() {
return null;
}
@Override
public Row get() {
return null;
}
@Override
public String toString() {
return "EMPTY_CURSOR";
}
};
static final Future<Cursor> EMPTY_FUTURE_CURSOR = new DoneFuture<>(EMPTY_CURSOR);
Future<Cursor> viewTopFutureCursor;
JoinFilter top;
final JoinFilter[] filters;
boolean batchedSubQuery;
private boolean started;
private JoinRow current;
private boolean found;
private final TableFilter additionalFilter;
public JoinBatch(int filtersCount, TableFilter additionalFilter) {
if (filtersCount > 32) {
throw DbException.getUnsupportedException(
"Too many tables in join (at most 32 supported).");
}
filters = new JoinFilter[filtersCount];
this.additionalFilter = additionalFilter;
}
public IndexLookupBatch getLookupBatch(int joinFilterId) {
return filters[joinFilterId].lookupBatch;
}
public void reset(boolean beforeQuery) {
current = null;
started = false;
found = false;
for (JoinFilter jf : filters) {
jf.reset(beforeQuery);
}
if (beforeQuery && additionalFilter != null) {
additionalFilter.reset();
}
}
public void register(TableFilter filter, IndexLookupBatch lookupBatch) {
assert filter != null;
top = new JoinFilter(lookupBatch, filter, top);
filters[top.id] = top;
}
public Value getValue(int filterId, Column column) {
if (current == null) {
return null;
}
Object x = current.row(filterId);
assert x != null;
Row row = current.isRow(filterId) ? (Row) x : ((Cursor) x).get();
int columnId = column.getColumnId();
if (columnId == -1) {
return ValueLong.get(row.getKey());
}
Value value = row.getValue(column.getColumnId());
if (value == null) {
throw DbException.throwInternalError("value is null: " + column + " " + row);
}
return value;
}
private void start() {
current = new JoinRow(new Object[filters.length]);
Cursor cursor;
if (batchedSubQuery) {
assert viewTopFutureCursor != null;
cursor = get(viewTopFutureCursor);
} else {
TableFilter f = top.filter;
IndexCursor indexCursor = f.getIndexCursor();
indexCursor.find(f.getSession(), f.getIndexConditions());
cursor = indexCursor;
}
current.updateRow(top.id, cursor, JoinRow.S_NULL, JoinRow.S_CURSOR);
JoinRow fake = new JoinRow(null);
fake.next = current;
current = fake;
}
public boolean next() {
if (!started) {
start();
started = true;
}
if (additionalFilter == null) {
if (batchedNext()) {
assert current.isComplete();
return true;
}
return false;
}
while (true) {
if (!found) {
if (!batchedNext()) {
return false;
}
assert current.isComplete();
found = true;
additionalFilter.reset();
}
if (additionalFilter.next()) {
return true;
}
found = false;
}
}
private static Cursor get(Future<Cursor> f) {
Cursor c;
try {
c = f.get();
} catch (Exception e) {
throw DbException.convert(e);
}
return c == null ? EMPTY_CURSOR : c;
}
private boolean batchedNext() {
if (current == null) {
return false;
}
current = current.next;
if (current == null) {
return false;
}
current.prev = null;
final int lastJfId = filters.length - 1;
int jfId = lastJfId;
while (current.row(jfId) == null) {
jfId--;
}
while (true) {
fetchCurrent(jfId);
if (!current.isDropped()) {
if (jfId == lastJfId) {
return true;
}
JoinFilter join = filters[jfId + 1];
if (join.isBatchFull()) {
current = join.find(current);
}
if (current.row(join.id) != null) {
jfId = join.id;
continue;
}
}
if (current.next == null) {
if (current.isDropped()) {
current = current.prev;
if (current == null) {
return false;
}
}
assert !current.isDropped();
assert jfId != lastJfId;
jfId = 0;
while (current.row(jfId) != null) {
jfId++;
}
current = filters[jfId].find(current);
} else {
current = current.next;
assert !current.isRow(jfId);
while (current.row(jfId) == null) {
assert jfId != top.id;
jfId--;
assert !current.isRow(jfId);
}
}
}
}
@SuppressWarnings("unchecked")
private void fetchCurrent(final int jfId) {
assert current.prev == null || current.prev.isRow(jfId) : "prev must be already fetched";
assert jfId == 0 || current.isRow(jfId - 1) : "left must be already fetched";
assert !current.isRow(jfId) : "double fetching";
Object x = current.row(jfId);
assert x != null : "x null";
boolean newCursor = x == EMPTY_CURSOR;
if (newCursor) {
if (jfId == 0) {
current.drop();
return;
}
} else if (current.isFuture(jfId)) {
x = get((Future<Cursor>) x);
current.updateRow(jfId, x, JoinRow.S_FUTURE, JoinRow.S_CURSOR);
newCursor = true;
}
final JoinFilter jf = filters[jfId];
Cursor c = (Cursor) x;
assert c != null;
JoinFilter join = jf.join;
while (true) {
if (c == null || !c.next()) {
if (newCursor && jf.isOuterJoin()) {
current.updateRow(jfId, jf.getNullRow(), JoinRow.S_CURSOR, JoinRow.S_ROW);
c = null;
newCursor = false;
} else {
current.drop();
return;
}
}
if (!jf.isOk(c == null)) {
continue;
}
boolean joinEmpty = false;
if (join != null && !join.collectSearchRows()) {
if (join.isOuterJoin()) {
joinEmpty = true;
} else {
continue;
}
}
if (c != null) {
current = current.copyBehind(jfId);
current.updateRow(jfId, c.get(), JoinRow.S_CURSOR, JoinRow.S_ROW);
}
if (joinEmpty) {
current.updateRow(join.id, EMPTY_CURSOR, JoinRow.S_NULL, JoinRow.S_CURSOR);
}
return;
}
}
private IndexLookupBatch viewIndexLookupBatch(ViewIndex viewIndex) {
return new ViewIndexLookupBatch(viewIndex);
}
public static IndexLookupBatch createViewIndexLookupBatch(ViewIndex viewIndex) {
Query query = viewIndex.getQuery();
if (query.isUnion()) {
ViewIndexLookupBatchUnion unionBatch = new ViewIndexLookupBatchUnion(viewIndex);
return unionBatch.initialize() ? unionBatch : null;
}
JoinBatch jb = ((Select) query).getJoinBatch();
if (jb == null || jb.getLookupBatch(0) == null) {
return null;
}
assert !jb.batchedSubQuery;
jb.batchedSubQuery = true;
return jb.viewIndexLookupBatch(viewIndex);
}
public static IndexLookupBatch createFakeIndexLookupBatch(TableFilter filter) {
return new FakeLookupBatch(filter);
}
@Override
public String toString() {
return "JoinBatch->\n" + "prev->" + (current == null ? null : current.prev) +
"\n" + "curr->" + current +
"\n" + "next->" + (current == null ? null : current.next);
}
private static final class JoinFilter {
final IndexLookupBatch lookupBatch;
final int id;
final JoinFilter join;
final TableFilter filter;
JoinFilter(IndexLookupBatch lookupBatch, TableFilter filter, JoinFilter join) {
this.filter = filter;
this.id = filter.getJoinFilterId();
this.join = join;
this.lookupBatch = lookupBatch;
assert lookupBatch != null || id == 0;
}
void reset(boolean beforeQuery) {
if (lookupBatch != null) {
lookupBatch.reset(beforeQuery);
}
}
Row getNullRow() {
return filter.getTable().getNullRow();
}
boolean isOuterJoin() {
return filter.isJoinOuter();
}
boolean isBatchFull() {
return lookupBatch.isBatchFull();
}
boolean isOk(boolean ignoreJoinCondition) {
boolean filterOk = filter.isOk(filter.getFilterCondition());
boolean joinOk = filter.isOk(filter.getJoinCondition());
return filterOk && (ignoreJoinCondition || joinOk);
}
boolean collectSearchRows() {
assert !isBatchFull();
IndexCursor c = filter.getIndexCursor();
c.prepare(filter.getSession(), filter.getIndexConditions());
if (c.isAlwaysFalse()) {
return false;
}
return lookupBatch.addSearchRows(c.getStart(), c.getEnd());
}
List<Future<Cursor>> find() {
return lookupBatch.find();
}
JoinRow find(JoinRow current) {
assert current != null;
List<Future<Cursor>> result = lookupBatch.find();
for (int i = result.size(); i > 0;) {
assert current.isRow(id - 1);
if (current.row(id) == EMPTY_CURSOR) {
current = current.prev;
continue;
}
assert current.row(id) == null;
Future<Cursor> future = result.get(--i);
if (future == null) {
current.updateRow(id, EMPTY_CURSOR, JoinRow.S_NULL, JoinRow.S_CURSOR);
} else {
current.updateRow(id, future, JoinRow.S_NULL, JoinRow.S_FUTURE);
}
if (current.prev == null || i == 0) {
break;
}
current = current.prev;
}
while (current.prev != null && current.prev.row(id) == EMPTY_CURSOR) {
current = current.prev;
}
assert current.prev == null || current.prev.isRow(id);
assert current.row(id) != null;
assert !current.isRow(id);
return current;
}
@Override
public String toString() {
return "JoinFilter->" + filter;
}
}
private static final class JoinRow {
private static final long S_NULL = 0;
private static final long S_FUTURE = 1;
private static final long S_CURSOR = 2;
private static final long S_ROW = 3;
private static final long S_MASK = 3;
JoinRow prev;
JoinRow next;
private Object[] row;
private long state;
JoinRow(Object[] row) {
this.row = row;
}
private long getState(int joinFilterId) {
return (state >>> (joinFilterId << 1)) & S_MASK;
}
private void incrementState(int joinFilterId, long i) {
assert i > 0 : i;
state += i << (joinFilterId << 1);
}
void updateRow(int joinFilterId, Object x, long oldState, long newState) {
assert getState(joinFilterId) == oldState : "old state: " + getState(joinFilterId);
row[joinFilterId] = x;
incrementState(joinFilterId, newState - oldState);
assert getState(joinFilterId) == newState : "new state: " + getState(joinFilterId);
}
Object row(int joinFilterId) {
return row[joinFilterId];
}
boolean isRow(int joinFilterId) {
return getState(joinFilterId) == S_ROW;
}
boolean isFuture(int joinFilterId) {
return getState(joinFilterId) == S_FUTURE;
}
private boolean isCursor(int joinFilterId) {
return getState(joinFilterId) == S_CURSOR;
}
boolean isComplete() {
return isRow(row.length - 1);
}
boolean isDropped() {
return row == null;
}
void drop() {
if (prev != null) {
prev.next = next;
}
if (next != null) {
next.prev = prev;
}
row = null;
}
JoinRow copyBehind(int jfId) {
assert isCursor(jfId);
assert jfId + 1 == row.length || row[jfId + 1] == null;
Object[] r = new Object[row.length];
if (jfId != 0) {
System.arraycopy(row, 0, r, 0, jfId);
}
JoinRow copy = new JoinRow(r);
copy.state = state;
if (prev != null) {
copy.prev = prev;
prev.next = copy;
}
prev = copy;
copy.next = this;
return copy;
}
@Override
public String toString() {
return "JoinRow->" + Arrays.toString(row);
}
}
private static final class FakeLookupBatch implements IndexLookupBatch {
private final TableFilter filter;
private SearchRow first;
private SearchRow last;
private boolean full;
private final List<Future<Cursor>> result = new SingletonList<>();
FakeLookupBatch(TableFilter filter) {
this.filter = filter;
}
@Override
public String getPlanSQL() {
return "fake";
}
@Override
public void reset(boolean beforeQuery) {
full = false;
first = last = null;
result.set(0, null);
}
@Override
public boolean addSearchRows(SearchRow first, SearchRow last) {
assert !full;
this.first = first;
this.last = last;
full = true;
return true;
}
@Override
public boolean isBatchFull() {
return full;
}
@Override
public List<Future<Cursor>> find() {
if (!full) {
return Collections.emptyList();
}
Cursor c = filter.getIndex().find(filter, first, last);
result.set(0, new DoneFuture<>(c));
full = false;
first = last = null;
return result;
}
}
static final class SingletonList<E> extends AbstractList<E> {
private E element;
@Override
public E get(int index) {
assert index == 0;
return element;
}
@Override
public E set(int index, E element) {
assert index == 0;
this.element = element;
return null;
}
@Override
public int size() {
return 1;
}
}
private abstract static class ViewIndexLookupBatchBase<R extends QueryRunnerBase>
implements IndexLookupBatch {
protected final ViewIndex viewIndex;
private final ArrayList<Future<Cursor>> result = Utils.newSmallArrayList();
private int resultSize;
private boolean findCalled;
protected ViewIndexLookupBatchBase(ViewIndex viewIndex) {
this.viewIndex = viewIndex;
}
@Override
public String getPlanSQL() {
return "view";
}
protected abstract boolean collectSearchRows(R r);
protected abstract R newQueryRunner();
protected abstract void startQueryRunners(int resultSize);
protected final boolean resetAfterFind() {
if (!findCalled) {
return false;
}
findCalled = false;
for (int i = 0; i < resultSize; i++) {
queryRunner(i).reset();
}
resultSize = 0;
return true;
}
@SuppressWarnings("unchecked")
protected R queryRunner(int i) {
return (R) result.get(i);
}
@Override
public final boolean addSearchRows(SearchRow first, SearchRow last) {
resetAfterFind();
viewIndex.setupQueryParameters(viewIndex.getSession(), first, last, null);
R r;
if (resultSize < result.size()) {
r = queryRunner(resultSize);
} else {
result.add(r = newQueryRunner());
}
r.first = first;
r.last = last;
if (!collectSearchRows(r)) {
r.clear();
return false;
}
resultSize++;
return true;
}
@Override
public void reset(boolean beforeQuery) {
if (resultSize != 0 && !resetAfterFind()) {
for (int i = 0; i < resultSize; i++) {
queryRunner(i).clear();
}
resultSize = 0;
}
}
@Override
public final List<Future<Cursor>> find() {
if (resultSize == 0) {
return Collections.emptyList();
}
findCalled = true;
startQueryRunners(resultSize);
return resultSize == result.size() ? result : result.subList(0, resultSize);
}
}
private abstract static class QueryRunnerBase extends LazyFuture<Cursor> {
protected final ViewIndex viewIndex;
protected SearchRow first;
protected SearchRow last;
private boolean isLazyResult;
QueryRunnerBase(ViewIndex viewIndex) {
this.viewIndex = viewIndex;
}
protected void clear() {
first = last = null;
}
@Override
public final boolean reset() {
if (isLazyResult) {
resetViewTopFutureCursorAfterQuery();
}
if (super.reset()) {
return true;
}
clear();
return false;
}
protected final ViewCursor newCursor(ResultInterface localResult) {
isLazyResult = localResult.isLazy();
ViewCursor cursor = new ViewCursor(viewIndex, localResult, first, last);
clear();
return cursor;
}
protected abstract void resetViewTopFutureCursorAfterQuery();
}
private final class ViewIndexLookupBatch extends ViewIndexLookupBatchBase<QueryRunner> {
ViewIndexLookupBatch(ViewIndex viewIndex) {
super(viewIndex);
}
@Override
protected QueryRunner newQueryRunner() {
return new QueryRunner(viewIndex);
}
@Override
protected boolean collectSearchRows(QueryRunner r) {
return top.collectSearchRows();
}
@Override
public boolean isBatchFull() {
return top.isBatchFull();
}
@Override
protected void startQueryRunners(int resultSize) {
List<Future<Cursor>> topFutureCursors = top.find();
if (topFutureCursors.size() != resultSize) {
throw DbException
.throwInternalError("Unexpected result size: " +
topFutureCursors.size() + ", expected :" +
resultSize);
}
for (int i = 0; i < resultSize; i++) {
QueryRunner r = queryRunner(i);
r.topFutureCursor = topFutureCursors.get(i);
}
}
}
private final class QueryRunner extends QueryRunnerBase {
Future<Cursor> topFutureCursor;
QueryRunner(ViewIndex viewIndex) {
super(viewIndex);
}
@Override
protected void clear() {
super.clear();
topFutureCursor = null;
}
@Override
protected Cursor run() throws Exception {
if (topFutureCursor == null) {
return EMPTY_CURSOR;
}
viewIndex.setupQueryParameters(viewIndex.getSession(), first, last, null);
JoinBatch.this.viewTopFutureCursor = topFutureCursor;
ResultInterface localResult;
boolean lazy = false;
try {
localResult = viewIndex.getQuery().query(0);
lazy = localResult.isLazy();
} finally {
if (!lazy) {
resetViewTopFutureCursorAfterQuery();
}
}
return newCursor(localResult);
}
@Override
protected void resetViewTopFutureCursorAfterQuery() {
JoinBatch.this.viewTopFutureCursor = null;
}
}
private static final class ViewIndexLookupBatchUnion
extends ViewIndexLookupBatchBase<QueryRunnerUnion> {
ArrayList<JoinFilter> filters;
ArrayList<JoinBatch> joinBatches;
private boolean onlyBatchedQueries = true;
protected ViewIndexLookupBatchUnion(ViewIndex viewIndex) {
super(viewIndex);
}
boolean initialize() {
return collectJoinBatches(viewIndex.getQuery()) && joinBatches != null;
}
private boolean collectJoinBatches(Query query) {
if (query.isUnion()) {
SelectUnion union = (SelectUnion) query;
return collectJoinBatches(union.getLeft()) &&
collectJoinBatches(union.getRight());
}
Select select = (Select) query;
JoinBatch jb = select.getJoinBatch();
if (jb == null) {
onlyBatchedQueries = false;
} else {
if (jb.getLookupBatch(0) == null) {
return false;
}
assert !jb.batchedSubQuery;
jb.batchedSubQuery = true;
if (joinBatches == null) {
joinBatches = Utils.newSmallArrayList();
filters = Utils.newSmallArrayList();
}
filters.add(jb.filters[0]);
joinBatches.add(jb);
}
return true;
}
@Override
public boolean isBatchFull() {
for (JoinFilter filter : filters) {
if (filter.isBatchFull()) {
return true;
}
}
return false;
}
@Override
protected boolean collectSearchRows(QueryRunnerUnion r) {
boolean collected = false;
for (int i = 0; i < filters.size(); i++) {
if (filters.get(i).collectSearchRows()) {
collected = true;
} else {
r.topFutureCursors[i] = EMPTY_FUTURE_CURSOR;
}
}
return collected || !onlyBatchedQueries;
}
@Override
protected QueryRunnerUnion newQueryRunner() {
return new QueryRunnerUnion(this);
}
@Override
protected void startQueryRunners(int resultSize) {
for (int f = 0; f < filters.size(); f++) {
List<Future<Cursor>> topFutureCursors = filters.get(f).find();
int r = 0, c = 0;
for (; r < resultSize; r++) {
Future<Cursor>[] cs = queryRunner(r).topFutureCursors;
if (cs[f] == null) {
cs[f] = topFutureCursors.get(c++);
}
}
assert r == resultSize;
assert c == topFutureCursors.size();
}
}
}
private static class QueryRunnerUnion extends QueryRunnerBase {
final Future<Cursor>[] topFutureCursors;
private final ViewIndexLookupBatchUnion batchUnion;
@SuppressWarnings("unchecked")
QueryRunnerUnion(ViewIndexLookupBatchUnion batchUnion) {
super(batchUnion.viewIndex);
this.batchUnion = batchUnion;
topFutureCursors = new Future[batchUnion.filters.size()];
}
@Override
protected void clear() {
super.clear();
for (int i = 0; i < topFutureCursors.length; i++) {
topFutureCursors[i] = null;
}
}
@Override
protected Cursor run() throws Exception {
viewIndex.setupQueryParameters(viewIndex.getSession(), first, last, null);
ArrayList<JoinBatch> joinBatches = batchUnion.joinBatches;
for (int i = 0, size = joinBatches.size(); i < size; i++) {
assert topFutureCursors[i] != null;
joinBatches.get(i).viewTopFutureCursor = topFutureCursors[i];
}
ResultInterface localResult;
boolean lazy = false;
try {
localResult = viewIndex.getQuery().query(0);
lazy = localResult.isLazy();
} finally {
if (!lazy) {
resetViewTopFutureCursorAfterQuery();
}
}
return newCursor(localResult);
}
@Override
protected void resetViewTopFutureCursorAfterQuery() {
ArrayList<JoinBatch> joinBatches = batchUnion.joinBatches;
if (joinBatches == null) {
return;
}
for (JoinBatch joinBatch : joinBatches) {
joinBatch.viewTopFutureCursor = null;
}
}
}
}