[IGNITE-17231] Optimization of DeltaFilePageStore: improve mapping of pageIdx to file offset

• Type: Improvement
• Status: Open
• Priority: Major
• Resolution: Unresolved
• Fix Version/s: 3.0
• Labels: ignite-3
• Epic Link: New PageMemory Persistent Store
• Assignee: Unassigned
• Reporter: Kirill Tkalenko
• Created: 27/Jun/22 07:04
• Updated: 04/Sep/24 16:19

Description

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.

Issue Links

• is a child of: IGNITE-17230 Support split-file page store