aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorkungasc <kungasc@yandex-team.com>2023-11-08 17:20:58 +0300
committerkungasc <kungasc@yandex-team.com>2023-11-08 18:30:59 +0300
commit4c94e44e7808c0b62370bee78c216fd131216d8c (patch)
tree7357152d8c6b0c4073901943e3640a15f7fdad55
parentbc031f602959d21285e3695a6cd25ebbfaab70d5 (diff)
downloadydb-4c94e44e7808c0b62370bee78c216fd131216d8c.tar.gz
KIKIMR-19521 BTreeIndex Fixed format
-rw-r--r--ydb/core/tablet_flat/flat_page_btree_index.h171
-rw-r--r--ydb/core/tablet_flat/flat_page_btree_index_writer.h89
-rw-r--r--ydb/core/tablet_flat/ut/ut_btree_index.cpp183
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());
}
}