KIKIMR-19521 BTreeIndex Fixed format

3 files changed, 306 insertions, 137 deletions

diff --git a/ydb/core/tablet_flat/flat_page_btree_index.h b/ydb/core/tablet_flat/flat_page_btree_index.h
index a708c88632..c0b1beb006 100644
--- a/ydb/core/tablet_flat/flat_page_btree_index.h
+++ b/ydb/core/tablet_flat/flat_page_btree_index.h
@@ -9,24 +9,39 @@ namespace NKikimr::NTable::NPage {
     
     /*
         TKey binary layout
-        .---------.---------------.
+        .-------------------------.
         | Non-null cell bitmap    | for all schema key columns
-        .---------.---------------.      -.
+        .-------------------------.      -.
         | value OR offs           | col_1 |
-        .---------.---------------.       |
+        .-------------------------.       |
         |       .    .    .       |       | for each non-null column
-        .---------.---------------.       |
+        .-------------------------.       |
         | value OR offs           | col_K |
         .-.------.--.-------.-----.      -'
         | |      |  |       |     | var-size values
         '-'------'--'-------'-----'
 
+        TKey fixed binary layout
+        .-------------------------.      -.
+        | value                   | col_1 |
+        .-------------------------.       |
+        |       .    .    .       |       | for each schema column, non-null
+        .-------------------------.       |
+        | value                   | col_K |
+        '-------------------------'      -'
+
         TBtreeIndexNode page binary layout
         - TLabel - page label
         - THeader - page header
         - TPgSize[N] - keys offsets
         - TKey[N] - keys data                <-- var-size
         - TChild[N+1] - children
+
+        TBtreeIndexNode fixed page binary layout
+        - TLabel - page label
+        - THeader - page header
+        - TKey[N] - keys data                <-- fixed-size
+        - TChild[N+1] - children
     */
 
     class TBtreeIndexNode {
@@ -38,56 +53,13 @@ namespace NKikimr::NTable::NPage {
         struct THeader {
             TRecIdx KeysCount;
             TPgSize KeysSize;
+            ui8 FixedKeySize;
         } Y_PACKED;
 
-        static_assert(sizeof(THeader) == 8, "Invalid TBtreeIndexNode THeader size");
-
-        struct TKey {
-            struct TCellsIter {
-                TCellsIter(const TKey* key, TColumns columns)
-                    : Key(key)
-                    , Columns(columns)
-                    , Pos(0)
-                {
-                    Ptr = (char*)Key + key->NullBitmapLength(columns.size());
-                }
-
-                TPos Count()
-                {
-                    return Columns.size();
-                }
-
-                TCell Next()
-                {
-                    Y_ABORT_UNLESS(Pos < Columns.size());
-
-                    if (Key->IsNull(Pos)) {
-                        Pos++;
-                        return { };
-                    }
+        static_assert(sizeof(THeader) == 9, "Invalid TBtreeIndexNode THeader size");
 
-                    TCell result;
-
-                    if (Columns[Pos].IsFixed) {
-                        result = TCell(Ptr, Columns[Pos].FixedSize);
-                    } else {
-                        auto *ref = TDeref<TDataRef>::At(Ptr);
-                        result = TCell(TDeref<const char>::At(Ptr, ref->Offset), ref->Size);
-                    }
-                    Ptr += Columns[Pos].FixedSize; // fixed data or data ref size
-                    Pos++;
-
-                    return result;
-                }
-
-            private:
-                const TKey* const Key;
-                const TColumns Columns;
-                TPos Pos;
-                const char* Ptr;
-            };
-
-            static TPos NullBitmapLength(TPos capacity) {
+        struct TIsNullBitmap {
+            static TPos Length(TPos capacity) {
                 // round up (capacity / 8)
                 return (capacity + 7) >> 3;
             }
@@ -106,7 +78,7 @@ namespace NKikimr::NTable::NPage {
             ui8 IsNullBitmap_;
         } Y_PACKED;
 
-        static_assert(sizeof(TKey) == 1, "Invalid TBtreeIndexNode TKey size");
+        static_assert(sizeof(TIsNullBitmap) == 1, "Invalid TBtreeIndexNode TIsNullBitmap size");
 
         struct TChild {
             TPageId PageId;
@@ -127,6 +99,57 @@ namespace NKikimr::NTable::NPage {
 
 #pragma pack(pop)
 
+        struct TCellsIter {
+            TCellsIter(const char* ptr, TColumns columns)
+                : IsNullBitmap(nullptr)
+                , Columns(columns)
+                , Ptr(ptr)
+            {
+            }
+
+            TCellsIter(const TIsNullBitmap* isNullBitmap, TColumns columns)
+                : IsNullBitmap(isNullBitmap)
+                , Columns(columns)
+                , Ptr(reinterpret_cast<const char*>(IsNullBitmap) + IsNullBitmap->Length(columns.size()))
+            {
+            }
+
+            TPos Count()
+            {
+                return Columns.size();
+            }
+
+            TCell Next()
+            {
+                Y_ABORT_UNLESS(Pos < Columns.size());
+
+                if (IsNullBitmap && IsNullBitmap->IsNull(Pos)) {
+                    Pos++;
+                    return { };
+                }
+
+                TCell result;
+
+                if (Columns[Pos].IsFixed) {
+                    result = TCell(Ptr, Columns[Pos].FixedSize);
+                } else {
+                    Y_ABORT_UNLESS(IsNullBitmap, "Can't have references in fixed format");
+                    auto *ref = TDeref<TDataRef>::At(Ptr);
+                    result = TCell(TDeref<const char>::At(Ptr, ref->Offset), ref->Size);
+                }
+                Ptr += Columns[Pos].FixedSize; // fixed data or data ref size
+                Pos++;
+
+                return result;
+            }
+
+        private:
+            const TIsNullBitmap* const IsNullBitmap;
+            const TColumns Columns;
+            const char* Ptr;
+            TPos Pos = 0;
+        };
+
     public:
         TBtreeIndexNode(TSharedData raw)
             : Raw(std::move(raw))
@@ -134,18 +157,21 @@ namespace NKikimr::NTable::NPage {
             const auto data = NPage::TLabelWrapper().Read(Raw, EPage::BTreeIndex);
             Y_ABORT_UNLESS(data == ECodec::Plain && data.Version == 0);
 
-            auto *header = TDeref<const THeader>::At(data.Page.data());
-            Keys.Count = header->KeysCount;
+            Header = TDeref<const THeader>::At(data.Page.data());
             size_t offset = sizeof(THeader);
 
-            Keys.Offsets = TDeref<const TRecordsEntry>::At(header, offset);
-            offset += Keys.Count * sizeof(TRecordsEntry);
-
-            Keys.Base = Raw.data();
-            offset += header->KeysSize;
+            if (IsFixedFormat()) {
+                Y_ABORT_UNLESS(Header->KeysSize == static_cast<TPgSize>(Header->KeysCount) * Header->FixedKeySize);
+                Keys = TDeref<const TRecordsEntry>::At(Header, offset);
+            } else {
+                Keys = Raw.data();
+                Offsets = TDeref<const TRecordsEntry>::At(Header, offset);
+                offset += Header->KeysCount * sizeof(TRecordsEntry);
+            }
+            offset += Header->KeysSize;
 
-            Children = TDeref<const TChild>::At(header, offset);
-            offset += (1 + Keys.Count) * sizeof(TChild);
+            Children = TDeref<const TChild>::At(Header, offset);
+            offset += (1 + Header->KeysCount) * sizeof(TChild);
 
             Y_ABORT_UNLESS(offset == data.Page.size());
         }
@@ -155,14 +181,25 @@ namespace NKikimr::NTable::NPage {
             return ReadUnaligned<NPage::TLabel>(Raw.data());
         }
 
+        bool IsFixedFormat() const noexcept
+        {
+            return Header->FixedKeySize != Max<ui8>();
+        }
+
         TRecIdx GetKeysCount() const noexcept
         {
-            return Keys.Count;
+            return Header->KeysCount;
         }
 
-        TKey::TCellsIter GetKeyCells(TRecIdx pos, TColumns columns) const noexcept
+        TCellsIter GetKeyCells(TRecIdx pos, TColumns columns) const noexcept
         {
-            return TKey::TCellsIter(Keys.Record(pos), columns);
+            if (IsFixedFormat()) {
+                const char* ptr = TDeref<const char>::At(Keys, pos * Header->FixedKeySize);
+                return TCellsIter(ptr, columns);
+            } else {
+                const TIsNullBitmap* isNullBitmap = TDeref<const TIsNullBitmap>::At(Keys, Offsets[pos].Offset);
+                return TCellsIter(isNullBitmap, columns);
+            }
         }
 
         const TChild& GetChild(TPos pos) const noexcept
@@ -174,8 +211,10 @@ namespace NKikimr::NTable::NPage {
 
     private:
         TSharedData Raw;
-        TBlockWithRecords<TKey> Keys;
-        const TChild* Children;
+        const THeader* Header = nullptr;
+        const void* Keys = nullptr;
+        const TRecordsEntry* Offsets = nullptr;
+        const TChild* Children = nullptr;
     };
 
     struct TBtreeIndexMeta : public TBtreeIndexNode::TChild {
diff --git a/ydb/core/tablet_flat/flat_page_btree_index_writer.h b/ydb/core/tablet_flat/flat_page_btree_index_writer.h
index caafb0e76a..fd855f18f9 100644
--- a/ydb/core/tablet_flat/flat_page_btree_index_writer.h
+++ b/ydb/core/tablet_flat/flat_page_btree_index_writer.h
@@ -7,7 +7,7 @@ namespace NKikimr::NTable::NPage {
 
     class TBtreeIndexNodeWriter {
         using THeader = TBtreeIndexNode::THeader;
-        using TKey = TBtreeIndexNode::TKey;
+        using TIsNullBitmap = TBtreeIndexNode::TIsNullBitmap;
         using TChild = TBtreeIndexNode::TChild;
 
     public:
@@ -16,6 +16,21 @@ namespace NKikimr::NTable::NPage {
             , GroupId(groupId)
             , GroupInfo(Scheme->GetLayout(groupId))
         {
+            if (GroupId.IsMain()) {
+                FixedKeySize = Max<ui8>();
+            } else {
+                FixedKeySize = 0;
+                for (TPos pos : xrange(GroupInfo.KeyTypes.size())) {
+                    Y_ABORT_UNLESS(GroupInfo.ColsKeyIdx[pos].IsFixed);
+                    FixedKeySize += GroupInfo.ColsKeyIdx[pos].FixedSize;
+                }
+                Y_ABORT_UNLESS(FixedKeySize < Max<ui8>(), "KeysSize is out of bounds");
+            }
+        }
+
+        bool IsFixedFormat() const noexcept
+        {
+            return FixedKeySize != Max<ui8>();
         }
 
         void AddKey(TCellsRef cells) {
@@ -80,20 +95,26 @@ namespace NKikimr::NTable::NPage {
             header.KeysCount = Keys.size();
             Y_ABORT_UNLESS(KeysSize < Max<TPgSize>(), "KeysSize is out of bounds");
             header.KeysSize = KeysSize;
-
-            size_t keyOffset = Ptr - buf.mutable_begin() + sizeof(TRecordsEntry) * Keys.size();
-            for (const auto &key : Keys) {
-                auto &meta = Place<TRecordsEntry>();
-                Y_ABORT_UNLESS(keyOffset < Max<TPgSize>(), "Key offset is out of bounds");
-                meta.Offset = keyOffset;
-                keyOffset += key.size();
+            header.FixedKeySize = FixedKeySize;
+
+            if (!IsFixedFormat()) {
+                size_t keyOffset = Ptr - buf.mutable_begin() + sizeof(TRecordsEntry) * Keys.size();
+                for (const auto &key : Keys) {
+                    auto &meta = Place<TRecordsEntry>();
+                    Y_ABORT_UNLESS(keyOffset < Max<TPgSize>(), "Key offset is out of bounds");
+                    meta.Offset = keyOffset;
+                    keyOffset += key.size();
+                }
+                Y_ABORT_UNLESS(Ptr == buf.mutable_begin() + sizeof(TLabel) + sizeof(THeader) + sizeof(TRecordsEntry) * Keys.size());
             }
-            Y_ABORT_UNLESS(Ptr == buf.mutable_begin() + sizeof(TLabel) + sizeof(THeader) + sizeof(TRecordsEntry) * Keys.size());
 
             for (auto &key : Keys) {
                 PlaceBytes(std::move(key));
             }
-            Y_ABORT_UNLESS(Ptr == buf.mutable_begin() + sizeof(TLabel) + sizeof(THeader) + sizeof(TRecordsEntry) * Keys.size() + KeysSize);
+            Y_ABORT_UNLESS(Ptr == buf.mutable_begin() + 
+                sizeof(TLabel) + sizeof(THeader) + 
+                (IsFixedFormat() ? 0 : sizeof(TRecordsEntry) * Keys.size()) + 
+                KeysSize);
             Keys.clear();
             KeysSize = 0;
 
@@ -111,10 +132,10 @@ namespace NKikimr::NTable::NPage {
             return CalcPageSize(KeysSize, Keys.size());
         }
 
-        static size_t CalcPageSize(size_t keysSize, size_t keysCount) {
+        size_t CalcPageSize(size_t keysSize, size_t keysCount) const {
             return
                 sizeof(TLabel) + sizeof(THeader) +
-                sizeof(TRecordsEntry) * keysCount +
+                (IsFixedFormat() ? 0 : sizeof(TRecordsEntry) * keysCount) +
                 keysSize +
                 sizeof(TChild) * (keysCount + 1);
         }
@@ -130,7 +151,11 @@ namespace NKikimr::NTable::NPage {
     private:
         TPgSize CalcKeySize(TCellsRef cells) const noexcept
         {
-            TPgSize size = TKey::NullBitmapLength(GroupInfo.ColsKeyIdx.size());
+            if (IsFixedFormat()) {
+                return FixedKeySize;
+            }
+
+            TPgSize size = TIsNullBitmap::Length(GroupInfo.ColsKeyIdx.size());
 
             for (TPos pos : xrange(cells.size())) {
                 if (const auto &val = cells[pos]) {
@@ -146,10 +171,21 @@ namespace NKikimr::NTable::NPage {
 
         void PlaceKey(TCellsRef cells) 
         {
-            auto *key = TDeref<TKey>::At(Ptr);
+            if (IsFixedFormat()) {
+                for (TPos pos : xrange(cells.size())) {
+                    Y_ABORT_UNLESS(cells[pos], "Can't have null cells in fixed format");
+                    const auto &info = GroupInfo.ColsKeyIdx[pos];
+                    Y_ABORT_UNLESS(info.IsFixed, "Can't have non-fixed cells in fixed format");
+                    Y_ABORT_UNLESS(cells[pos].Size() == info.FixedSize, "invalid fixed cell size)");
+                    memcpy(Advance(cells[pos].Size()), cells[pos].Data(), cells[pos].Size());
+                }
+                return;
+            }
+
+            auto *isNullBitmap = TDeref<TIsNullBitmap>::At(Ptr);
 
             // mark all cells as non-null
-            Zero(key->NullBitmapLength(GroupInfo.ColsKeyIdx.size()));
+            Zero(isNullBitmap->Length(GroupInfo.ColsKeyIdx.size()));
 
             auto* keyCellsPtr = Ptr;
 
@@ -158,21 +194,21 @@ namespace NKikimr::NTable::NPage {
                     const auto &info = GroupInfo.ColsKeyIdx[pos];
                     Zero(info.FixedSize);
                 } else {
-                    key->SetNull(pos);
+                    isNullBitmap->SetNull(pos);
                 }
             }
             for (TPos pos : xrange(cells.size(), GroupInfo.ColsKeyIdx.size())) {
-                key->SetNull(pos);
+                isNullBitmap->SetNull(pos);
             }
 
             for (TPos pos : xrange(cells.size())) {
                 if (const auto &cell = cells[pos]) {
-                    Y_DEBUG_ABORT_UNLESS(!key->IsNull(pos));
+                    Y_DEBUG_ABORT_UNLESS(!isNullBitmap->IsNull(pos));
                     const auto &info = GroupInfo.ColsKeyIdx[pos];
                     PlaceCell(info, cell, keyCellsPtr);
                     keyCellsPtr += info.FixedSize;
                 } else {
-                    Y_DEBUG_ABORT_UNLESS(key->IsNull(pos));
+                    Y_DEBUG_ABORT_UNLESS(isNullBitmap->IsNull(pos));
                 }
             }
         }
@@ -224,11 +260,12 @@ namespace NKikimr::NTable::NPage {
 
     public:
         const TIntrusiveConstPtr<TPartScheme> Scheme;
-
-    private:
         const TGroupId GroupId;
         const TPartScheme::TGroupInfo& GroupInfo;
 
+    private:
+        size_t FixedKeySize;
+
         TVector<TString> Keys;
         size_t KeysSize = 0;
 
@@ -289,7 +326,10 @@ namespace NKikimr::NTable::NPage {
     public:
         TBtreeIndexBuilder(TIntrusiveConstPtr<TPartScheme> scheme, TGroupId groupId,
                 ui32 nodeTargetSize, ui32 nodeKeysMin, ui32 nodeKeysMax)
-            : Writer(std::move(scheme), groupId)
+            : Scheme(std::move(scheme))
+            , GroupId(groupId)
+            , GroupInfo(Scheme->GetLayout(groupId))
+            , Writer(Scheme, groupId)
             , Levels(1)
             , NodeTargetSize(nodeTargetSize)
             , NodeKeysMin(nodeKeysMin)
@@ -421,6 +461,11 @@ namespace NKikimr::NTable::NPage {
             return Writer.CalcPageSize(level.GetKeysSize(), level.GetKeysCount());
         }
 
+    public:
+        const TIntrusiveConstPtr<TPartScheme> Scheme;
+        const TGroupId GroupId;
+        const TPartScheme::TGroupInfo& GroupInfo;
+
     private:
         ui64 IndexSize = 0;
 
diff --git a/ydb/core/tablet_flat/ut/ut_btree_index.cpp b/ydb/core/tablet_flat/ut/ut_btree_index.cpp
index 74bc51e2df..641fd945bc 100644
--- a/ydb/core/tablet_flat/ut/ut_btree_index.cpp
+++ b/ydb/core/tablet_flat/ut/ut_btree_index.cpp
@@ -57,7 +57,7 @@ namespace {
         return TChild{index + 10000, index + 100, index + 30, index + 1000};
     }
 
-    void Dump(TChild meta, const TPartScheme& scheme, const TStore& store, ui32 level = 0) noexcept
+    void Dump(TChild meta, const TPartScheme::TGroupInfo& groupInfo, const TStore& store, ui32 level = 0) noexcept
     {
         TString intend;
         for (size_t i = 0; i < level; i++) {
@@ -66,7 +66,7 @@ namespace {
 
         auto dumpChild = [&] (TChild child) {
             if (child.PageId < 1000) {
-                Dump(child, scheme, store, level + 1);
+                Dump(child, groupInfo, store, level + 1);
             } else {
                 Cerr << intend << " | " << child.ToString() << Endl;
             }
@@ -89,10 +89,10 @@ namespace {
         for (TRecIdx i : xrange(node.GetKeysCount())) {
             Cerr << intend << " | > ";
 
-            auto cells = node.GetKeyCells(i, scheme.Groups[0].ColsKeyIdx);
+            auto cells = node.GetKeyCells(i, groupInfo.ColsKeyIdx);
             for (TPos pos : xrange(cells.Count())) {
                 TString str;
-                DbgPrintValue(str, cells.Next(), scheme.Groups[0].KeyTypes[pos]);
+                DbgPrintValue(str, cells.Next(), groupInfo.KeyTypes[pos]);
                 if (str.size() > 10) {
                     str = str.substr(0, 10) + "..";
                 }
@@ -106,19 +106,19 @@ namespace {
         Cerr << Endl;
     }
 
-    void Dump(TSharedData node, const TPartScheme& scheme) {
+    void Dump(TSharedData node, const TPartScheme::TGroupInfo& groupInfo) {
         TWriterBundle pager(1, TLogoBlobID());
         auto pageId = ((IPageWriter*)&pager)->Write(node, EPage::BTreeIndex, 0);
         TChild page{pageId, 0, 0, 0};
-        Dump(page, scheme, pager.Back());
+        Dump(page, groupInfo, pager.Back());
     }
 
-    void CheckKeys(const NPage::TBtreeIndexNode& node, const TVector<TString>& keys, const TPartScheme& scheme) {
+    void CheckKeys(const NPage::TBtreeIndexNode& node, const TVector<TString>& keys, const TPartScheme::TGroupInfo& groupInfo) {
         UNIT_ASSERT_VALUES_EQUAL(node.GetKeysCount(), keys.size());
         for (TRecIdx i : xrange(node.GetKeysCount())) {
             TVector<TCell> actualCells;
-            auto cells = node.GetKeyCells(i, scheme.Groups[0].ColsKeyIdx);
-            UNIT_ASSERT_VALUES_EQUAL(cells.Count(), scheme.Groups[0].ColsKeyIdx.size());
+            auto cells = node.GetKeyCells(i, groupInfo.ColsKeyIdx);
+            UNIT_ASSERT_VALUES_EQUAL(cells.Count(), groupInfo.ColsKeyIdx.size());
             
             for (TPos pos : xrange(cells.Count())) {
                 Y_UNUSED(pos);
@@ -130,10 +130,10 @@ namespace {
         }
     }
 
-    void CheckKeys(TPageId pageId, const TVector<TString>& keys, const TPartScheme& scheme, const TStore& store) {
+    void CheckKeys(TPageId pageId, const TVector<TString>& keys, const TPartScheme::TGroupInfo& groupInfo, const TStore& store) {
         auto page = store.GetPage(0, pageId);
         auto node = TBtreeIndexNode(*page);
-        CheckKeys(node, keys, scheme);
+        CheckKeys(node, keys, groupInfo);
     }
 
     void CheckChildren(const NPage::TBtreeIndexNode& node, const TVector<TChild>& children) {
@@ -148,23 +148,23 @@ Y_UNIT_TEST_SUITE(TBtreeIndexNode) {
     using namespace NTest;
     using TChild = TBtreeIndexNode::TChild;
 
-    Y_UNIT_TEST(TKeyBitmap) {
+    Y_UNIT_TEST(TIsNullBitmap) {
         TString buffer(754, 0);
-        auto* key = (TBtreeIndexNode::TKey*)(buffer.data());
+        auto* bitmap = (TBtreeIndexNode::TIsNullBitmap*)(buffer.data());
 
-        UNIT_ASSERT_VALUES_EQUAL(key->NullBitmapLength(0), 0);
-        UNIT_ASSERT_VALUES_EQUAL(key->NullBitmapLength(1), 1);
-        UNIT_ASSERT_VALUES_EQUAL(key->NullBitmapLength(4), 1);
-        UNIT_ASSERT_VALUES_EQUAL(key->NullBitmapLength(7), 1);
-        UNIT_ASSERT_VALUES_EQUAL(key->NullBitmapLength(8), 1);
-        UNIT_ASSERT_VALUES_EQUAL(key->NullBitmapLength(9), 2);
-        UNIT_ASSERT_VALUES_EQUAL(key->NullBitmapLength(256), 32);
-        UNIT_ASSERT_VALUES_EQUAL(key->NullBitmapLength(257), 33);
+        UNIT_ASSERT_VALUES_EQUAL(bitmap->Length(0), 0);
+        UNIT_ASSERT_VALUES_EQUAL(bitmap->Length(1), 1);
+        UNIT_ASSERT_VALUES_EQUAL(bitmap->Length(4), 1);
+        UNIT_ASSERT_VALUES_EQUAL(bitmap->Length(7), 1);
+        UNIT_ASSERT_VALUES_EQUAL(bitmap->Length(8), 1);
+        UNIT_ASSERT_VALUES_EQUAL(bitmap->Length(9), 2);
+        UNIT_ASSERT_VALUES_EQUAL(bitmap->Length(256), 32);
+        UNIT_ASSERT_VALUES_EQUAL(bitmap->Length(257), 33);
 
         for (TPos pos : xrange(buffer.size() * 8)) {
-            UNIT_ASSERT(!key->IsNull(pos));
-            key->SetNull(pos);
-            UNIT_ASSERT(key->IsNull(pos));
+            UNIT_ASSERT(!bitmap->IsNull(pos));
+            bitmap->SetNull(pos);
+            UNIT_ASSERT(bitmap->IsNull(pos));
         }
     }
 
@@ -206,8 +206,93 @@ Y_UNIT_TEST_SUITE(TBtreeIndexNode) {
 
         auto node = TBtreeIndexNode(serialized);
 
-        Dump(serialized, *writer.Scheme);
-        CheckKeys(node, keys, *writer.Scheme);
+        Dump(serialized, writer.GroupInfo);
+        CheckKeys(node, keys, writer.GroupInfo);
+        CheckChildren(node, children);
+    }
+
+    Y_UNIT_TEST(Group) {
+        TLayoutCook lay;
+        
+        lay
+            .Col(0, 0,  NScheme::NTypeIds::Uint32)
+            .Col(0, 1,  NScheme::NTypeIds::String)
+            .Col(1, 2,  NScheme::NTypeIds::Bool)
+            .Col(1, 3,  NScheme::NTypeIds::Uint64)
+            .Key({0, 1});
+
+        TBtreeIndexNodeWriter writer(new TPartScheme(lay.RowScheme()->Cols), TGroupId{ 1 });
+
+        TVector<TString> keys;
+        for (ui32 i : xrange(13)) {
+            Y_UNUSED(i);
+            TVector<TCell> cells;
+            keys.push_back(TSerializedCellVec::Serialize(cells));
+        }
+
+        TVector<TChild> children;
+        for (ui32 i : xrange(keys.size() + 1)) {
+            children.push_back(MakeChild(i));
+        }
+
+        for (auto k : keys) {
+            TSerializedCellVec deserialized(k);
+            writer.AddKey(deserialized.GetCells());
+        }
+        for (auto c : children) {
+            writer.AddChild(c);
+        }
+
+        auto serialized = writer.Finish();
+
+        auto node = TBtreeIndexNode(serialized);
+
+        Dump(serialized, writer.GroupInfo);
+        CheckKeys(node, keys, writer.GroupInfo);
+        CheckChildren(node, children);
+    }
+
+    Y_UNIT_TEST(History) {
+        TLayoutCook lay;
+        
+        lay
+            .Col(0, 0,  NScheme::NTypeIds::Uint32)
+            .Col(0, 1,  NScheme::NTypeIds::String)
+            .Col(1, 2,  NScheme::NTypeIds::Bool)
+            .Col(1, 3,  NScheme::NTypeIds::Uint64)
+            .Key({0, 1});
+
+        TBtreeIndexNodeWriter writer(new TPartScheme(lay.RowScheme()->Cols), TGroupId{ 0, 1 });
+
+        TVector<TString> keys;
+        for (ui32 i : xrange(13)) {
+            Y_UNUSED(i);
+            TVector<TCell> cells;
+            cells.push_back(TCell::Make(TRowId(i)));
+            cells.push_back(TCell::Make(ui64(10 * i)));
+            cells.push_back(TCell::Make(ui64(100 * i)));
+            keys.push_back(TSerializedCellVec::Serialize(cells));
+        }
+
+        TVector<TChild> children;
+        for (ui32 i : xrange(keys.size() + 1)) {
+            children.push_back(MakeChild(i));
+        }
+
+        for (auto k : keys) {
+            TSerializedCellVec deserialized(k);
+            writer.AddKey(deserialized.GetCells());
+        }
+        for (auto c : children) {
+            writer.AddChild(c);
+        }
+
+        auto serialized = writer.Finish();
+
+        auto node = TBtreeIndexNode(serialized);
+
+        Dump(serialized, writer.GroupInfo);
+        CheckKeys(node, keys, writer.GroupInfo);
         CheckChildren(node, children);
     }
 
@@ -237,8 +322,8 @@ Y_UNIT_TEST_SUITE(TBtreeIndexNode) {
 
             auto node = TBtreeIndexNode(serialized);
 
-            Dump(serialized, *writer.Scheme);
-            CheckKeys(node, keys, *writer.Scheme);
+            Dump(serialized, writer.GroupInfo);
+            CheckKeys(node, keys, writer.GroupInfo);
             CheckChildren(node, children);
         };
 
@@ -291,8 +376,8 @@ Y_UNIT_TEST_SUITE(TBtreeIndexNode) {
 
         auto node = TBtreeIndexNode(serialized);
 
-        Dump(serialized, *writer.Scheme);
-        CheckKeys(node, keys, *writer.Scheme);
+        Dump(serialized, writer.GroupInfo);
+        CheckKeys(node, keys, writer.GroupInfo);
         CheckChildren(node, children);
     }
 
@@ -336,8 +421,8 @@ Y_UNIT_TEST_SUITE(TBtreeIndexNode) {
 
         auto node = TBtreeIndexNode(serialized);
 
-        Dump(serialized, *writer.Scheme);
-        CheckKeys(node, fullKeys, *writer.Scheme);
+        Dump(serialized, writer.GroupInfo);
+        CheckKeys(node, fullKeys, writer.GroupInfo);
         CheckChildren(node, children);
     }
 
@@ -391,12 +476,12 @@ Y_UNIT_TEST_SUITE(TBtreeIndexBuilder) {
         auto result = builder.Flush(pager, true);
         UNIT_ASSERT(result);
 
-        Dump(*result, *scheme, pager.Back());
+        Dump(*result, builder.GroupInfo, pager.Back());
 
-        TBtreeIndexMeta expected{{0, 1155, 385, 11055}, 1, 594};
+        TBtreeIndexMeta expected{{0, 1155, 385, 11055}, 1, 595};
         UNIT_ASSERT_EQUAL_C(*result, expected, "Got " + result->ToString());
 
-        CheckKeys(result->PageId, keys, *scheme, pager.Back());
+        CheckKeys(result->PageId, keys, builder.GroupInfo, pager.Back());
     }
 
     Y_UNIT_TEST(FewNodes) {
@@ -427,12 +512,12 @@ Y_UNIT_TEST_SUITE(TBtreeIndexBuilder) {
         auto result = builder.Flush(pager, true);
         UNIT_ASSERT(result);
 
-        Dump(*result, *scheme, pager.Back());
+        Dump(*result, builder.GroupInfo, pager.Back());
         
         UNIT_ASSERT_VALUES_EQUAL(result->LevelsCount, 3);
         
         auto checkKeys = [&](TPageId pageId, const TVector<TString>& keys) {
-            CheckKeys(pageId, keys, *scheme, pager.Back());
+            CheckKeys(pageId, keys, builder.GroupInfo, pager.Back());
         };
 
         // Level 0:
@@ -477,7 +562,7 @@ Y_UNIT_TEST_SUITE(TBtreeIndexBuilder) {
             keys[8]
         });
 
-        TBtreeIndexMeta expected{{9, 0, 0, 0}, 3, 1540};
+        TBtreeIndexMeta expected{{9, 0, 0, 0}, 3, 1550};
         for (auto c : children) {
             expected.Count += c.Count;
             expected.ErasedCount += c.ErasedCount;
@@ -514,9 +599,9 @@ Y_UNIT_TEST_SUITE(TBtreeIndexBuilder) {
         auto result = builder.Flush(pager, true);
         UNIT_ASSERT(result);
 
-        Dump(*result, *scheme, pager.Back());
+        Dump(*result, builder.GroupInfo, pager.Back());
         
-        TBtreeIndexMeta expected{{15, 15150, 8080, 106050}, 3, 10254};
+        TBtreeIndexMeta expected{{15, 15150, 8080, 106050}, 3, 10270};
         UNIT_ASSERT_EQUAL_C(*result, expected, "Got " + result->ToString());
     }
 
@@ -580,7 +665,7 @@ Y_UNIT_TEST_SUITE(TBtreeIndexTPart) {
         auto pages = IndexTools::CountMainPages(*part);
         UNIT_ASSERT_VALUES_EQUAL(pages, 2);
 
-        TBtreeIndexMeta expected{{3, 10, 0, 10480}, 1, 1114};
+        TBtreeIndexMeta expected{{3, 10, 0, 10480}, 1, 1115};
         UNIT_ASSERT_EQUAL_C(part->IndexPages.BTreeGroups[0], expected, "Got " + part->IndexPages.BTreeGroups[0].ToString());
     }
 
@@ -613,7 +698,7 @@ Y_UNIT_TEST_SUITE(TBtreeIndexTPart) {
         auto pages = IndexTools::CountMainPages(*part);
         UNIT_ASSERT_VALUES_EQUAL(pages, 117);
 
-        TBtreeIndexMeta expected{{143, 700, 0, 733140}, 3, 86010};
+        TBtreeIndexMeta expected{{143, 700, 0, 733140}, 3, 86036};
         UNIT_ASSERT_EQUAL_C(part->IndexPages.BTreeGroups[0], expected, "Got " + part->IndexPages.BTreeGroups[0].ToString());
     }
 
@@ -647,7 +732,7 @@ Y_UNIT_TEST_SUITE(TBtreeIndexTPart) {
         auto pages = IndexTools::CountMainPages(*part);
         UNIT_ASSERT_VALUES_EQUAL(pages, 31);
 
-        TBtreeIndexMeta expected{{37, 1000, 143, 22098}, 2, 1374};
+        TBtreeIndexMeta expected{{37, 1000, 143, 22098}, 2, 1380};
         UNIT_ASSERT_EQUAL_C(part->IndexPages.BTreeGroups[0], expected, "Got " + part->IndexPages.BTreeGroups[0].ToString());
     }
 
@@ -681,10 +766,10 @@ Y_UNIT_TEST_SUITE(TBtreeIndexTPart) {
         auto pages = IndexTools::CountMainPages(*part);
         UNIT_ASSERT_VALUES_EQUAL(pages, 334);
 
-        TBtreeIndexMeta expected0{{438, 1000, 0, 16680}, 3, 15181};
+        TBtreeIndexMeta expected0{{438, 1000, 0, 16680}, 3, 15246};
         UNIT_ASSERT_EQUAL_C(part->IndexPages.BTreeGroups[0], expected0, "Got " + part->IndexPages.BTreeGroups[0].ToString());
 
-        TBtreeIndexMeta expected1{{441, 1000, 0, 21890}, 3, 9772};
+        TBtreeIndexMeta expected1{{441, 1000, 0, 21890}, 3, 8817};
         UNIT_ASSERT_EQUAL_C(part->IndexPages.BTreeGroups[1], expected1, "Got " + part->IndexPages.BTreeGroups[1].ToString());
     }
 
@@ -720,16 +805,16 @@ Y_UNIT_TEST_SUITE(TBtreeIndexTPart) {
         auto pages = IndexTools::CountMainPages(*part);
         UNIT_ASSERT_VALUES_EQUAL(pages, 334);
 
-        TBtreeIndexMeta expected0{{1315, 1000, 0, 32680}, 3, 15181};
+        TBtreeIndexMeta expected0{{1315, 1000, 0, 32680}, 3, 15246};
         UNIT_ASSERT_EQUAL_C(part->IndexPages.BTreeGroups[0], expected0, "Got " + part->IndexPages.BTreeGroups[0].ToString());
 
-        TBtreeIndexMeta expected1{{1318, 1000, 0, 22889}, 3, 9772};
+        TBtreeIndexMeta expected1{{1318, 1000, 0, 22889}, 3, 8817};
         UNIT_ASSERT_EQUAL_C(part->IndexPages.BTreeGroups[1], expected1, "Got " + part->IndexPages.BTreeGroups[1].ToString());
 
-        TBtreeIndexMeta expectedHist0{{1322, 2000, 0, 77340}, 4, 43814};
+        TBtreeIndexMeta expectedHist0{{1322, 2000, 0, 77340}, 4, 40617};
         UNIT_ASSERT_EQUAL_C(part->IndexPages.BTreeHistoric[0], expectedHist0, "Got " + part->IndexPages.BTreeHistoric[0].ToString());
 
-        TBtreeIndexMeta expectedHist1{{1325, 2000, 0, 45780}, 3, 19576};
+        TBtreeIndexMeta expectedHist1{{1325, 2000, 0, 45780}, 3, 17662};
         UNIT_ASSERT_EQUAL_C(part->IndexPages.BTreeHistoric[1], expectedHist1, "Got " + part->IndexPages.BTreeHistoric[1].ToString());
     }
 }