Uploaded image for project: 'Ignite'
  1. Ignite
  2. IGNITE-17536

Implement BinaryTuple inlining in a hash index B+Tree

    XMLWordPrintableJSON

Details

    • Task
    • Status: Resolved
    • Major
    • Resolution: Fixed
    • None
    • 3.0.0-beta1
    • None

    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.

      Attachments

        Issue Links

          Activity

            People

              ktkalenko@gridgain.com Kirill Tkalenko
              ktkalenko@gridgain.com Kirill Tkalenko
              Ivan Bessonov Ivan Bessonov
              Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved:

                Time Tracking

                  Estimated:
                  Original Estimate - Not Specified
                  Not Specified
                  Remaining:
                  Remaining Estimate - 0h
                  0h
                  Logged:
                  Time Spent - 4h
                  4h