IGNITE-6663: SQL: optimized PK index lookup (use findOne instead of find(lower, upper)). This closes #3086.
Project: http://git-wip-us.apache.org/repos/asf/ignite/repo Commit: http://git-wip-us.apache.org/repos/asf/ignite/commit/850863e1 Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/850863e1 Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/850863e1 Branch: refs/heads/ignite-zk-ce Commit: 850863e1c4ad794bd1147149a522cc126897d96d Parents: 2e65a78 Author: gg-shq <[email protected]> Authored: Tue Dec 12 15:47:50 2017 +0300 Committer: devozerov <[email protected]> Committed: Tue Dec 12 15:47:50 2017 +0300 ---------------------------------------------------------------------- .../internal/util/OffheapReadWriteLock.java | 8 +- .../processors/query/h2/database/H2Tree.java | 6 +- .../query/h2/database/H2TreeIndex.java | 162 ++++++++++++------- .../IgniteCacheAbstractFieldsQuerySelfTest.java | 43 ++++- 4 files changed, 151 insertions(+), 68 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/ignite/blob/850863e1/modules/core/src/main/java/org/apache/ignite/internal/util/OffheapReadWriteLock.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/util/OffheapReadWriteLock.java b/modules/core/src/main/java/org/apache/ignite/internal/util/OffheapReadWriteLock.java index ee6a04d..b119960 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/util/OffheapReadWriteLock.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/util/OffheapReadWriteLock.java @@ -171,6 +171,8 @@ public class OffheapReadWriteLock { lockObj.lock(); try { + // Note that we signal all waiters for this stripe. Since not all waiters in this + // stripe/index belong to this particular lock, we can't wake up just one of them. writeConditions[idx].signalAll(); } finally { @@ -296,6 +298,8 @@ public class OffheapReadWriteLock { * @param idx Lock index. */ private void signalNextWaiter(int writeWaitCnt, int readWaitCnt, int idx) { + // Note that we signal all waiters for this stripe. Since not all waiters in this stripe/index belong + // to this particular lock, we can't wake up just one of them. if (writeWaitCnt == 0) { Condition readCondition = readConditions[idx]; @@ -496,8 +500,10 @@ public class OffheapReadWriteLock { } /** + * Returns index of lock object corresponding to the stripe of this lock address. + * * @param lock Lock address. - * @return Lock monitor object. + * @return Lock monitor object that corresponds to the stripe for this lock address. */ private int lockIndex(long lock) { return U.safeAbs(U.hash(lock)) & monitorsMask; http://git-wip-us.apache.org/repos/asf/ignite/blob/850863e1/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/H2Tree.java ---------------------------------------------------------------------- diff --git a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/H2Tree.java b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/H2Tree.java index 4aecab7..67bde69 100644 --- a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/H2Tree.java +++ b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/H2Tree.java @@ -238,13 +238,13 @@ public abstract class H2Tree extends BPlusTree<SearchRow, GridH2Row> { } /** - * Compare two rows. + * Compares two H2 rows. * * @param r1 Row 1. * @param r2 Row 2. - * @return Compare result. + * @return Compare result: see {@link Comparator#compare(Object, Object)} for values. */ - private int compareRows(GridH2Row r1, SearchRow r2) { + public int compareRows(SearchRow r1, SearchRow r2) { if (r1 == r2) return 0; http://git-wip-us.apache.org/repos/asf/ignite/blob/850863e1/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/H2TreeIndex.java ---------------------------------------------------------------------- diff --git a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/H2TreeIndex.java b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/H2TreeIndex.java index 5a336c5..edfaecf 100644 --- a/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/H2TreeIndex.java +++ b/modules/indexing/src/main/java/org/apache/ignite/internal/processors/query/h2/database/H2TreeIndex.java @@ -20,6 +20,8 @@ package org.apache.ignite.internal.processors.query.h2.database; import java.util.ArrayList; import java.util.HashSet; import java.util.List; +import java.util.NoSuchElementException; + import org.apache.ignite.IgniteCheckedException; import org.apache.ignite.IgniteException; import org.apache.ignite.IgniteSystemProperties; @@ -30,8 +32,8 @@ import org.apache.ignite.internal.processors.cache.persistence.tree.BPlusTree; import org.apache.ignite.internal.processors.cache.persistence.tree.io.BPlusIO; import org.apache.ignite.internal.processors.cache.persistence.tree.io.PageIO; import org.apache.ignite.internal.processors.query.h2.H2Cursor; -import org.apache.ignite.internal.processors.query.h2.database.io.H2RowLinkIO; import org.apache.ignite.internal.processors.query.h2.opt.GridH2IndexBase; +import org.apache.ignite.internal.processors.query.h2.database.io.H2RowLinkIO; import org.apache.ignite.internal.processors.query.h2.opt.GridH2Row; import org.apache.ignite.internal.processors.query.h2.opt.GridH2Table; import org.apache.ignite.internal.util.IgniteTree; @@ -44,6 +46,7 @@ import org.h2.index.Cursor; import org.h2.index.IndexType; import org.h2.index.SingleRowCursor; import org.h2.message.DbException; +import org.h2.result.Row; import org.h2.result.SearchRow; import org.h2.result.SortOrder; import org.h2.table.Column; @@ -174,7 +177,16 @@ public class H2TreeIndex extends GridH2IndexBase { H2Tree tree = treeForRead(seg); - return new H2Cursor(tree.find(lower, upper, filter)); + if (indexType.isPrimaryKey() && lower != null && upper != null && tree.compareRows(lower, upper) == 0) { + GridH2Row row = tree.findOne(lower, filter); + + return (row == null) ? EMPTY_CURSOR : new SingleRowCursor(row); + } + else { + GridCursor<GridH2Row> cursor = tree.find(lower, upper, filter); + + return new H2Cursor(cursor); + } } catch (IgniteCheckedException e) { throw DbException.convert(e); @@ -275,7 +287,7 @@ public class H2TreeIndex extends GridH2IndexBase { H2Tree tree = treeForRead(seg); - BPlusTree.TreeRowClosure<SearchRow, GridH2Row> filter = filter(); + BPlusTree.TreeRowClosure<SearchRow, GridH2Row> filter = filterClosure(); return tree.size(filter); } @@ -284,47 +296,6 @@ public class H2TreeIndex extends GridH2IndexBase { } } - /** - * An adapter from {@link IndexingQueryCacheFilter} to {@link BPlusTree.TreeRowClosure} to - * filter entries that belong to the current partition. - */ - private static class PartitionFilterTreeRowClosure implements BPlusTree.TreeRowClosure<SearchRow, GridH2Row> { - private final IndexingQueryCacheFilter filter; - - /** - * Creates a {@link BPlusTree.TreeRowClosure} adapter based on the given partition filter. - * - * @param filter The partition filter. - */ - public PartitionFilterTreeRowClosure(IndexingQueryCacheFilter filter) { - this.filter = filter; - } - - /** {@inheritDoc} */ - @Override public boolean apply(BPlusTree<SearchRow, GridH2Row> tree, - BPlusIO<SearchRow> io, long pageAddr, int idx) throws IgniteCheckedException { - - H2RowLinkIO h2io = (H2RowLinkIO)io; - - return filter.applyPartition( - PageIdUtils.partId( - PageIdUtils.pageId( - h2io.getLink(pageAddr, idx)))); - } - } - - /** - * Returns a filter to apply to rows in the current index to obtain only the - * ones owned by the this cache. - * - * @return The filter, which returns true for rows owned by this cache. - */ - @Nullable private BPlusTree.TreeRowClosure<SearchRow, GridH2Row> filter() { - final IndexingQueryCacheFilter filter = partitionFilter(threadLocalFilter()); - - return filter != null ? new PartitionFilterTreeRowClosure(filter) : null; - } - /** {@inheritDoc} */ @Override public long getRowCountApproximation() { return 10_000; // TODO @@ -385,12 +356,12 @@ public class H2TreeIndex extends GridH2IndexBase { @Nullable SearchRow last, IndexingQueryFilter filter) { try { - IndexingQueryCacheFilter p = partitionFilter(filter); + IndexingQueryCacheFilter pf = partitionFilter(filter); - GridCursor<GridH2Row> range = t.find(first, last, p); + GridCursor<GridH2Row> range = t.find(first, last, pf); if (range == null) - range = EMPTY_CURSOR; + range = GridH2IndexBase.EMPTY_CURSOR; return new H2Cursor(range); } @@ -400,21 +371,6 @@ public class H2TreeIndex extends GridH2IndexBase { } /** - * Filter which returns true for entries belonging to a particular partition. - * - * @param qryFilter Factory that creates a predicate for filtering entries for a particular cache. - * @return The filter or null if the filter is not needed (e.g., if the cache is not partitioned). - */ - @Nullable private IndexingQueryCacheFilter partitionFilter(@Nullable IndexingQueryFilter qryFilter) { - if (qryFilter == null) - return null; - - String cacheName = getTable().cacheName(); - - return qryFilter.forCache(cacheName); - } - - /** * @param inlineIdxs Inline index helpers. * @param cfgInlineSize Inline size from cache config. * @return Inline size. @@ -470,4 +426,86 @@ public class H2TreeIndex extends GridH2IndexBase { private void dropMetaPage(String name, int segIdx) throws IgniteCheckedException { cctx.offheap().dropRootPageForIndex(cctx.cacheId(), name + "%" + segIdx); } + + /** + * Returns a filter which returns true for entries belonging to a particular partition. + * + * @param qryFilter Factory that creates a predicate for filtering entries for a particular cache. + * @return The filter or null if the filter is not needed (e.g., if the cache is not partitioned). + */ + @Nullable private IndexingQueryCacheFilter partitionFilter(@Nullable IndexingQueryFilter qryFilter) { + if (qryFilter == null) + return null; + + String cacheName = getTable().cacheName(); + + return qryFilter.forCache(cacheName); + } + + /** + * An adapter from {@link IndexingQueryCacheFilter} to {@link BPlusTree.TreeRowClosure} which + * filters entries that belong to the current partition. + */ + private static class PartitionFilterTreeRowClosure implements BPlusTree.TreeRowClosure<SearchRow, GridH2Row> { + /** Filter. */ + private final IndexingQueryCacheFilter filter; + + /** + * Creates a {@link BPlusTree.TreeRowClosure} adapter based on the given partition filter. + * + * @param filter The partition filter. + */ + public PartitionFilterTreeRowClosure(IndexingQueryCacheFilter filter) { + this.filter = filter; + } + + /** {@inheritDoc} */ + @Override public boolean apply(BPlusTree<SearchRow, GridH2Row> tree, + BPlusIO<SearchRow> io, long pageAddr, int idx) throws IgniteCheckedException { + + H2RowLinkIO h2io = (H2RowLinkIO)io; + + return filter.applyPartition( + PageIdUtils.partId( + PageIdUtils.pageId( + h2io.getLink(pageAddr, idx)))); + } + } + + /** + * Returns a filter to apply to rows in the current index to obtain only the + * ones owned by the this cache. + * + * @return The filter, which returns true for rows owned by this cache. + */ + @Nullable private BPlusTree.TreeRowClosure<SearchRow, GridH2Row> filterClosure() { + final IndexingQueryCacheFilter filter = partitionFilter(threadLocalFilter()); + + return filter != null ? new PartitionFilterTreeRowClosure(filter) : null; + } + + /** + * Empty cursor. + */ + public static final Cursor EMPTY_CURSOR = new Cursor() { + /** {@inheritDoc} */ + @Override public Row get() { + throw DbException.convert(new NoSuchElementException("Empty cursor")); + } + + /** {@inheritDoc} */ + @Override public SearchRow getSearchRow() { + throw DbException.convert(new NoSuchElementException("Empty cursor")); + } + + /** {@inheritDoc} */ + @Override public boolean next() { + return false; + } + + /** {@inheritDoc} */ + @Override public boolean previous() { + return false; + } + }; } http://git-wip-us.apache.org/repos/asf/ignite/blob/850863e1/modules/indexing/src/test/java/org/apache/ignite/internal/processors/cache/IgniteCacheAbstractFieldsQuerySelfTest.java ---------------------------------------------------------------------- diff --git a/modules/indexing/src/test/java/org/apache/ignite/internal/processors/cache/IgniteCacheAbstractFieldsQuerySelfTest.java b/modules/indexing/src/test/java/org/apache/ignite/internal/processors/cache/IgniteCacheAbstractFieldsQuerySelfTest.java index 322598a..a285a8b 100644 --- a/modules/indexing/src/test/java/org/apache/ignite/internal/processors/cache/IgniteCacheAbstractFieldsQuerySelfTest.java +++ b/modules/indexing/src/test/java/org/apache/ignite/internal/processors/cache/IgniteCacheAbstractFieldsQuerySelfTest.java @@ -36,6 +36,7 @@ import org.apache.ignite.cache.CacheMode; import org.apache.ignite.cache.CacheRebalanceMode; import org.apache.ignite.cache.CacheWriteSynchronizationMode; import org.apache.ignite.cache.affinity.AffinityKey; +import org.apache.ignite.cache.query.FieldsQueryCursor; import org.apache.ignite.cache.query.QueryCursor; import org.apache.ignite.cache.query.SqlFieldsQuery; import org.apache.ignite.cache.query.annotations.QuerySqlField; @@ -43,8 +44,11 @@ import org.apache.ignite.configuration.CacheConfiguration; import org.apache.ignite.configuration.IgniteConfiguration; import org.apache.ignite.internal.IgniteKernal; import org.apache.ignite.internal.binary.BinaryMarshaller; +import org.apache.ignite.internal.processors.cache.index.AbstractSchemaSelfTest; import org.apache.ignite.internal.processors.cache.query.GridCacheSqlIndexMetadata; import org.apache.ignite.internal.processors.cache.query.GridCacheSqlMetadata; +import org.apache.ignite.internal.processors.cache.persistence.tree.BPlusTree; +import org.apache.ignite.internal.processors.cache.query.SqlFieldsQueryEx; import org.apache.ignite.internal.processors.datastructures.GridCacheAtomicLongValue; import org.apache.ignite.internal.processors.datastructures.GridCacheInternalKeyImpl; import org.apache.ignite.internal.processors.query.GridQueryFieldMetadata; @@ -663,8 +667,43 @@ public abstract class IgniteCacheAbstractFieldsQuerySelfTest extends GridCommonA Collection<List<?>> res = qry.getAll(); - assert res != null; - assert res.isEmpty(); + assertNotNull(res); + assertTrue(res.isEmpty()); + } + + /** + * Verifies that exactly one record is found when we have equality comparison in where clause (which is supposed + * to use {@link BPlusTree#findOne(Object, Object)} instead of {@link BPlusTree#find(Object, Object, Object)}. + * + * @throws Exception If failed. + */ + public void testSingleResultUsesFindOne() throws Exception { + QueryCursor<List<?>> qry = + intCache.query(sqlFieldsQuery("select _val from Integer where _key = 25")); + + List<List<?>> res = qry.getAll(); + + assertNotNull(res); + assertEquals(1, res.size()); + assertEquals(1, res.get(0).size()); + assertEquals(25, res.get(0).get(0)); + } + + /** + * Verifies that zero records are found when we have equality comparison in where clause (which is supposed + * to use {@link BPlusTree#findOne(Object, Object)} instead of {@link BPlusTree#find(Object, Object, Object)} + * and the key is not in the cache. + * + * @throws Exception If failed. + */ + public void testEmptyResultUsesFindOne() throws Exception { + QueryCursor<List<?>> qry = + intCache.query(sqlFieldsQuery("select _val from Integer where _key = -10")); + + List<List<?>> res = qry.getAll(); + + assertNotNull(res); + assertEquals(0, res.size()); } /** @throws Exception If failed. */
