Uploaded image for project: 'Apache AsterixDB'
  1. Apache AsterixDB
  2. ASTERIXDB-2708

Optimize Primary Point Searches Via Batching and Stateful Cursors

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Open
    • Priority: Major
    • Resolution: Unresolved
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: RT - Runtime, STO - Storage
    • Labels:
      None

      Description

      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.

        Attachments

          Activity

            People

            • Assignee:
              luochen01 Chen Luo
              Reporter:
              luochen01 Chen Luo
            • Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated: