[IGNITE-17536] Implement BinaryTuple inlining in a hash index B+Tree

• Type: Task
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 3.0.0-beta1
• Labels: ignite-3
• Epic Link: Indexes optimizations
• Assignee: Kirill Tkalenko
• Reporter: Kirill Tkalenko
• Reviewer: Ivan Bessonov
• Created: 16/Aug/22 08:43
• Updated: 14/Oct/22 08:01
• Resolved: 14/Oct/22 08:01

Description

In a simple implementation, instead of a BinaryTuple, we store its link from the FreeList in the key, this is not optimal and we need to inline the BinaryTuple in the key, for starters, you can see how to do this in 2.0.

What should be done:

• Calculate approximate inline size:
  • It is set by the user through the configuration or calculated automatically, but should not be more than 2 KB (similar to PageIO#MAX_PAYLOAD_SIZE from 2.0);
  • For automatic calculation, the BinaryTuple format must be taken into account: header + null map + offset table;
    • To cover most cases, we will consider the size class to be 2 bytes (BinaryTupleFormat-Header);
    • For columns of variable length (for example, a string), we will assume that 10 bytes should be enough;
• Write BinaryTuple as is up to inline size;
  • If the user BinaryTuple is larger than the inline size, then without its transformations (as it is) we will write it according to the inline size (cut it off);
  • If the user BinaryTuple is less than or equal to the inline size, then we will write it as is without writing it to the FreeList;
    • At the same time, we need to make a note somewhere that the BinaryTuple is written in full, this will help us when comparing BinaryTuple's inside the B+tree;
• Comparing BinaryTuple's at B+tree nodes:
  • If the BinaryTuple in the tree node is completely written, then compare them without loading the BinaryTuple by link (since we will not write it to the FreeList);
  • Otherwise, compare BinaryTuple's with loading it by link (we need to do it optimally right away).

The configuration will most likely be done later, since the user experience for this is not yet clear.

Issue Links

• is a child of: IGNITE-17339 Implement B+Tree based hash index storage
• is a parent of: IGNITE-17855 Implement inline size calculation for B+tree
• relates to: IGNITE-17843 Use partitionless pageId in BplusInnerIo
• links to: GitHub Pull Request #1161