diff options
author | kungasc <kungasc@yandex-team.com> | 2023-11-08 17:20:58 +0300 |
---|---|---|
committer | kungasc <kungasc@yandex-team.com> | 2023-11-08 18:30:59 +0300 |
commit | 4c94e44e7808c0b62370bee78c216fd131216d8c (patch) | |
tree | 7357152d8c6b0c4073901943e3640a15f7fdad55 | |
parent | bc031f602959d21285e3695a6cd25ebbfaab70d5 (diff) | |
download | ydb-4c94e44e7808c0b62370bee78c216fd131216d8c.tar.gz |
KIKIMR-19521 BTreeIndex Fixed format
-rw-r--r-- | ydb/core/tablet_flat/flat_page_btree_index.h | 171 | ||||
-rw-r--r-- | ydb/core/tablet_flat/flat_page_btree_index_writer.h | 89 | ||||
-rw-r--r-- | ydb/core/tablet_flat/ut/ut_btree_index.cpp | 183 |
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()); } } |