[jira] [Created] (IGNITE-17231) Optimization of DeltaFilePageStore: improve mapping of pageIdx to file offset

["Kirill Tkalenko (Jira)" <ji...@apache.org>]

Kirill Tkalenko created IGNITE-17231:
----------------------------------------

             Summary: Optimization of DeltaFilePageStore: improve mapping of pageIdx to file offset
                 Key: IGNITE-17231
                 URL: https://issues.apache.org/jira/browse/IGNITE-17231
             Project: Ignite
          Issue Type: Improvement
            Reporter: Kirill Tkalenko
             Fix For: 3.0.0-alpha6


For ease of implementation, a sorted list of *pageIdx* has been added to the *DeltaFilePageStore*, thereby allowing a binary search to find a *pageId -> pageIdx*.

Perhaps this is not quite optimal, and it can be optimized.

It is important that we need to find a balance between memory usage and *pageId* lookup speed, since the *DeltaFilePageStore* class can be many (very many) due to the fact that it depends on the checkpoint, compacter, number of partitions and number of groups.

Before implementation, we need to study the options in more depth and perhaps try a few of them.

What can we consider:
* roaring map - this needs to be carefully studied;
* list of containers (idea) - there are 3 types of container, the first is a bitmask, the second is value intervals (provided that the values are greater than 64 (two integers)), the third is a sorted list (or hash map); then by binary search we find the container (by the first *pageIdx* in this container) and then we query the container.



--
This message was sent by Atlassian Jira
(v8.20.7#820007)