Chen Luo created ASTERIXDB-2708:
-----------------------------------
Summary: 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
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)
