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

Implement B+Tree based sorted index storage

    XMLWordPrintableJSON

Details

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

    Description

      Like in IGNITE-17318, binary tuple format is a main goal here, because that's what we're gonna pass into API.

      Implementing a tree for indexes isn't hard by itself. I expect it to be stored in same partition files as raw storage, everything should be colocated in a single file.

      What's complicated is the inlining of data into trees pages. I see it as the following:

      • If tuple has no offset table, we can always store the entire payload in the tree. This is the best case scenario, because the size is fixed and known a priori, we don't even need to store it before the payload.
      • If tuple has an offset table, the inline size will immediately get bigger. In my view, we will have to:
        • store the size of inlined payload, that's 4 bytes
        • store null table if it's there, that's a known amount of bytes
        • store header and offset table:
          • if there are non-fixed-length columns, then a single entry in offset table can be up to 4 bytes
          • if there are only fixed-length columns, like ints, floats or even bitsets, the amount of bytes per single entry can be accurately estimated with the upper bound
        • then store a good amount of the actual columns data. How much? I'd be generous, but then we would probably have too much space, so all of this is debatable:
          • for columns with fixed size, allocate room for entire value
          • for strings and numbers (is there something else?) we have to pre-allocate a reasonable amount of bytes. Like, 8, for example. I don't know, there are defaults somewhere in the code of Ignite 2.x, we can use them.

      So, my point is, there's no new data format for inlined section of the tuple, we should reuse it and thus avoid many possible errors. And, if record fits into a tree page, there's no need in inserting it into a free list. Good!

      And yes, of course, there has to be a room for row id in inlined section as well.

      Last, meta tree is still a thing. But, we shouldn't identify indexes by their names, cause there's UUID id or even integer id (see IGNITE-17318).

      Other ideas

      I don't like how durable background tasks work in Ignite 2.x, there are always some issues. I would prefer having a general-purposed "recycle bin" in partition and a background cleaner process that would clean it. Maybe this queue should contain other entities in the future.

      Attachments

        Issue Links

          Activity

            People

              ktkalenko@gridgain.com Kirill Tkalenko
              ibessonov Ivan Bessonov
              Semyon Danilov Semyon Danilov
              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 - 1h 20m
                  1h 20m