[
https://issues.apache.org/jira/browse/ASTERIXDB-2708?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Chen Luo resolved ASTERIXDB-2708.
---------------------------------
Resolution: Implemented
> Optimize Primary Point Searches Via Batching and Stateful Cursors
> -----------------------------------------------------------------
>
> Key: ASTERIXDB-2708
> URL: https://issues.apache.org/jira/browse/ASTERIXDB-2708
> Project: Apache AsterixDB
> Issue Type: Improvement
> Components: RT - Runtime, STO - Storage
> Reporter: Chen Luo
> Assignee: Chen Luo
> Priority: Major
>
> Currently, the primary index point searches can be expensive, especially when
> a query is not selecitivity, for a few reasons:
> * Enter and exit LSM components for each search key
> * Always traverse from root to leaf when searching a key
> To optimize primary point searches, we introduce a number of optimizations
> here:
> * Introduce a batched point search cursor that enters an LSM index for a
> batch of keys to amortize the cost
> * Introduce a stateful BTree search algorithm that reuses the previous search
> history to speedup subsequently searches. Specifically, we keep track of the
> last leaf page ID and the last key index. For the next search key, if it
> still exists in the last leaf page, we do not have to traverse from root to
> leaf again. Moreover, instead of using binary search, we use exponential
> search to reduce the search cost in case there are a lot of keys.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
