summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--ydb/core/tablet_flat/flat_page_btree_index.h39
-rw-r--r--ydb/core/tablet_flat/flat_part_btree_index_iter.h18
-rw-r--r--ydb/core/tablet_flat/flat_part_charge.h61
-rw-r--r--ydb/core/tablet_flat/flat_part_charge_btree_index.h242
-rw-r--r--ydb/core/tablet_flat/ut/ut_btree_index_iter_charge.cpp191
-rw-r--r--ydb/core/tablet_flat/ut/ut_btree_index_nodes.cpp44
-rw-r--r--ydb/core/tablet_flat/ut/ut_charge.cpp10
7 files changed, 369 insertions, 236 deletions
diff --git a/ydb/core/tablet_flat/flat_page_btree_index.h b/ydb/core/tablet_flat/flat_page_btree_index.h
index 0fc722dcce9..70f2681a3aa 100644
--- a/ydb/core/tablet_flat/flat_page_btree_index.h
+++ b/ydb/core/tablet_flat/flat_page_btree_index.h
@@ -101,8 +101,11 @@ namespace NKikimr::NTable::NPage {
auto operator<=>(const TChild&) const = default;
- TString ToString() const noexcept
- {
+ TRowId GetNonErasedRowCount() const noexcept {
+ return RowCount - ErasedRowCount;
+ }
+
+ TString ToString() const noexcept {
return TStringBuilder() << "PageId: " << PageId << " RowCount: " << RowCount << " DataSize: " << DataSize << " ErasedRowCount: " << ErasedRowCount;
}
} Y_PACKED;
@@ -268,6 +271,11 @@ namespace NKikimr::NTable::NPage {
return ReadUnaligned<NPage::TLabel>(Raw.data());
}
+ bool IsShortChildFormat() const noexcept
+ {
+ return Header->IsShortChildFormat;
+ }
+
bool IsFixedFormat() const noexcept
{
return Header->FixedKeySize != Header->MaxFixedKeySize;
@@ -293,23 +301,26 @@ namespace NKikimr::NTable::NPage {
return GetCells<TCellsIter>(pos, columns);
}
+ const TShortChild* GetShortChildRef(TRecIdx pos) const noexcept
+ {
+ return TDeref<const TShortChild>::At(Children,
+ pos * (Header->IsShortChildFormat ? sizeof(TShortChild) : sizeof(TChild)));
+ }
+
const TShortChild& GetShortChild(TRecIdx pos) const noexcept
{
- if (Header->IsShortChildFormat) {
- return *TDeref<const TShortChild>::At(Children, pos * sizeof(TShortChild));
- } else {
- return *TDeref<const TShortChild>::At(Children, pos * sizeof(TChild));
- }
+ return *GetShortChildRef(pos);
}
- TChild GetChild(TRecIdx pos) const noexcept
+ const TChild* GetChildRef(TRecIdx pos) const noexcept
{
- if (Header->IsShortChildFormat) {
- const TShortChild* const shortChild = TDeref<const TShortChild>::At(Children, pos * sizeof(TShortChild));
- return { shortChild->PageId, shortChild->RowCount, shortChild->DataSize, 0 };
- } else {
- return *TDeref<const TChild>::At(Children, pos * sizeof(TChild));
- }
+ Y_DEBUG_ABORT_UNLESS(!Header->IsShortChildFormat, "GetShortChildRef should be used instead");
+ return TDeref<const TChild>::At(Children, pos * sizeof(TChild));
+ }
+
+ const TChild& GetChild(TRecIdx pos) const noexcept
+ {
+ return *GetChildRef(pos);
}
static bool Has(TRowId rowId, TRowId beginRowId, TRowId endRowId) noexcept {
diff --git a/ydb/core/tablet_flat/flat_part_btree_index_iter.h b/ydb/core/tablet_flat/flat_part_btree_index_iter.h
index d924e670de4..53517fe7669 100644
--- a/ydb/core/tablet_flat/flat_part_btree_index_iter.h
+++ b/ydb/core/tablet_flat/flat_part_btree_index_iter.h
@@ -18,7 +18,7 @@ class TPartBtreeIndexIt : public IIndexIter {
using TBtreeIndexMeta = NPage::TBtreeIndexMeta;
struct TNodeState {
- TChild Meta;
+ TPageId PageId;
TRowId BeginRowId;
TRowId EndRowId;
TCellsIterable BeginKey;
@@ -26,8 +26,8 @@ class TPartBtreeIndexIt : public IIndexIter {
std::optional<TBtreeIndexNode> Node;
std::optional<TRecIdx> Pos;
- TNodeState(TChild meta, TRowId beginRowId, TRowId endRowId, TCellsIterable beginKey, TCellsIterable endKey)
- : Meta(meta)
+ TNodeState(TPageId pageId, TRowId beginRowId, TRowId endRowId, TCellsIterable beginKey, TCellsIterable endKey)
+ : PageId(pageId)
, BeginRowId(beginRowId)
, EndRowId(endRowId)
, BeginKey(beginKey)
@@ -118,7 +118,7 @@ public:
, State(Reserve(Meta.LevelCount + 1))
{
const static TCellsIterable EmptyKey(static_cast<const char*>(nullptr), TColumns());
- State.emplace_back(Meta, 0, GetEndRowId(), EmptyKey, EmptyKey);
+ State.emplace_back(Meta.PageId, 0, GetEndRowId(), EmptyKey, EmptyKey);
}
EReady Seek(TRowId rowId) override {
@@ -251,7 +251,7 @@ public:
TPageId GetPageId() const override {
Y_ABORT_UNLESS(IsLeaf());
- return State.back().Meta.PageId;
+ return State.back().PageId;
}
TRowId GetRowId() const override {
@@ -332,15 +332,15 @@ private:
Y_ABORT_UNLESS(pos < current.Node->GetChildrenCount(), "Should point to some child");
current.Pos.emplace(pos);
- auto child = current.Node->GetChild(pos);
+ auto& child = current.Node->GetShortChild(pos);
- TRowId beginRowId = pos ? current.Node->GetChild(pos - 1).RowCount : current.BeginRowId;
+ TRowId beginRowId = pos ? current.Node->GetShortChild(pos - 1).RowCount : current.BeginRowId;
TRowId endRowId = child.RowCount;
TCellsIterable beginKey = pos ? current.Node->GetKeyCellsIterable(pos - 1, GroupInfo.ColsKeyIdx) : current.BeginKey;
TCellsIterable endKey = pos < current.Node->GetKeysCount() ? current.Node->GetKeyCellsIterable(pos, GroupInfo.ColsKeyIdx) : current.EndKey;
- State.emplace_back(child, beginRowId, endRowId, beginKey, endKey);
+ State.emplace_back(child.PageId, beginRowId, endRowId, beginKey, endKey);
}
bool TryLoad(TNodeState& state) {
@@ -348,7 +348,7 @@ private:
return true;
}
- auto page = Env->TryGetPage(Part, state.Meta.PageId);
+ auto page = Env->TryGetPage(Part, state.PageId);
if (page) {
state.Node.emplace(*page);
return true;
diff --git a/ydb/core/tablet_flat/flat_part_charge.h b/ydb/core/tablet_flat/flat_part_charge.h
index 4c990357ad5..9553e802ea4 100644
--- a/ydb/core/tablet_flat/flat_part_charge.h
+++ b/ydb/core/tablet_flat/flat_part_charge.h
@@ -208,7 +208,7 @@ namespace NTable {
ui64 items = 0;
ui64 bytes = 0;
- TRowId prechargedFirstRowId, prechargedLastRowId;
+ std::optional<std::pair<TRowId, TRowId>> prechargedRowsRange;
bool needExactBounds = Groups || HistoryIndex;
for (auto current = first;
@@ -235,6 +235,15 @@ namespace NTable {
prechargeCurrentFirstRowId = Max<TRowId>(); // no precharge
}
}
+ if (itemsLimit && prechargeCurrentFirstRowId <= prechargeCurrentLastRowId) {
+ ui64 left = itemsLimit - items; // we count only foolproof taken rows, so here we may precharge some extra rows
+ if (prechargeCurrentLastRowId - prechargeCurrentFirstRowId > left) {
+ prechargeCurrentLastRowId = prechargeCurrentFirstRowId + left;
+ }
+ }
+ if (prechargeCurrentFirstRowId <= prechargeCurrentLastRowId) {
+ items += prechargeCurrentLastRowId - prechargeCurrentFirstRowId + 1;
+ }
if (key2Page && key2Page <= current) {
if (key2Page == current) {
if (needExactBounds && page) {
@@ -251,29 +260,22 @@ namespace NTable {
prechargeCurrentFirstRowId = Max<TRowId>(); // no precharge
}
}
- if (itemsLimit && prechargeCurrentFirstRowId <= prechargeCurrentLastRowId) {
- ui64 left = itemsLimit - items; // we count only foolproof taken rows, so here we may precharge some extra rows
- if (prechargeCurrentLastRowId - prechargeCurrentFirstRowId > left) {
- prechargeCurrentLastRowId = prechargeCurrentFirstRowId + left;
- }
- }
-
if (prechargeCurrentFirstRowId <= prechargeCurrentLastRowId) {
- if (!items) {
- prechargedFirstRowId = prechargeCurrentFirstRowId;
+ if (prechargedRowsRange) {
+ prechargedRowsRange->second = prechargeCurrentLastRowId;
+ } else {
+ prechargedRowsRange.emplace(prechargeCurrentFirstRowId, prechargeCurrentLastRowId);
}
- prechargedLastRowId = prechargeCurrentLastRowId;
if (Groups) {
for (auto& g : Groups) {
ready &= DoPrechargeGroup(g, prechargeCurrentFirstRowId, prechargeCurrentLastRowId, bytes);
}
}
- items += prechargeCurrentLastRowId - prechargeCurrentFirstRowId + 1;
}
}
- if (items && HistoryIndex) {
- ready &= DoPrechargeHistory(prechargedFirstRowId, prechargedLastRowId);
+ if (prechargedRowsRange && HistoryIndex) {
+ ready &= DoPrechargeHistory(prechargedRowsRange->first, prechargedRowsRange->second);
}
}
@@ -304,7 +306,7 @@ namespace NTable {
ui64 items = 0;
ui64 bytes = 0;
- TRowId prechargedFirstRowId, prechargedLastRowId;
+ std::optional<std::pair<TRowId, TRowId>> prechargedRowsRange;
bool needExactBounds = Groups || HistoryIndex;
for (auto current = first;
@@ -335,6 +337,15 @@ namespace NTable {
prechargeCurrentLastRowId = Max<TRowId>(); // no precharge
}
}
+ if (itemsLimit && prechargeCurrentFirstRowId >= prechargeCurrentLastRowId) {
+ ui64 left = itemsLimit - items; // we count only foolproof taken rows, so here we may precharge some extra rows
+ if (prechargeCurrentFirstRowId - prechargeCurrentLastRowId > left) {
+ prechargeCurrentLastRowId = prechargeCurrentFirstRowId - left;
+ }
+ }
+ if (prechargeCurrentFirstRowId >= prechargeCurrentLastRowId) {
+ items += prechargeCurrentFirstRowId - prechargeCurrentLastRowId + 1;
+ }
if (key2Page && key2Page >= current) {
if (key2Page == current) {
if (needExactBounds && page) {
@@ -349,25 +360,17 @@ namespace NTable {
prechargeCurrentLastRowId = Max<TRowId>(); // no precharge
}
}
-
- if (itemsLimit && prechargeCurrentFirstRowId >= prechargeCurrentLastRowId) {
- ui64 left = itemsLimit - items; // we count only foolproof taken rows, so here we may precharge some extra rows
- if (prechargeCurrentFirstRowId - prechargeCurrentLastRowId > left) {
- prechargeCurrentLastRowId = prechargeCurrentFirstRowId - left;
- }
- }
-
if (prechargeCurrentFirstRowId >= prechargeCurrentLastRowId) {
- if (!items) {
- prechargedFirstRowId = prechargeCurrentFirstRowId;
+ if (prechargedRowsRange) {
+ prechargedRowsRange->second = prechargeCurrentLastRowId;
+ } else {
+ prechargedRowsRange.emplace(prechargeCurrentFirstRowId, prechargeCurrentLastRowId);
}
- prechargedLastRowId = prechargeCurrentLastRowId;
if (Groups) {
for (auto& g : Groups) {
ready &= DoPrechargeGroupReverse(g, prechargeCurrentFirstRowId, prechargeCurrentLastRowId, bytes);
}
}
- items += prechargeCurrentFirstRowId - prechargeCurrentLastRowId + 1;
}
if (current.Off() == 0) {
@@ -375,8 +378,8 @@ namespace NTable {
}
}
- if (items && HistoryIndex) {
- ready &= DoPrechargeHistory(prechargedFirstRowId, prechargedLastRowId);
+ if (prechargedRowsRange && HistoryIndex) {
+ ready &= DoPrechargeHistory(prechargedRowsRange->first, prechargedRowsRange->second);
}
}
diff --git a/ydb/core/tablet_flat/flat_part_charge_btree_index.h b/ydb/core/tablet_flat/flat_part_charge_btree_index.h
index 2c87bd4d926..b404c7450e2 100644
--- a/ydb/core/tablet_flat/flat_part_charge_btree_index.h
+++ b/ydb/core/tablet_flat/flat_part_charge_btree_index.h
@@ -13,13 +13,13 @@ class TChargeBTreeIndex : public ICharge {
using TGroupId = NPage::TGroupId;
using TChild = TBtreeIndexNode::TChild;
- // TODO: store PageId only instead of TChild?
- struct TChildState : TChild {
+ struct TChildState {
+ TPageId PageId;
TRowId BeginRowId;
TRowId EndRowId;
- TChildState(TChild meta, TRowId beginRowId, TRowId endRowId)
- : TChild(meta)
+ TChildState(TPageId pageId, TRowId beginRowId, TRowId endRowId)
+ : PageId(pageId)
, BeginRowId(beginRowId)
, EndRowId(endRowId)
{
@@ -27,8 +27,8 @@ class TChargeBTreeIndex : public ICharge {
};
struct TNodeState : TChildState, TBtreeIndexNode {
- TNodeState(TSharedData data, TChild meta, TRowId beginRowId, TRowId endRowId)
- : TChildState(meta, beginRowId, endRowId)
+ TNodeState(TSharedData data, TPageId pageId, TRowId beginRowId, TRowId endRowId)
+ : TChildState(pageId, beginRowId, endRowId)
, TBtreeIndexNode(data)
{
}
@@ -66,11 +66,9 @@ public:
endRowId++; // current interface accepts inclusive row2 bound
Y_ABORT_UNLESS(beginRowId < endRowId);
- bool ready = true;
+ bool ready = true, overshot = true;
bool chargeGroups = bool(Groups); // false value means that beginRowId, endRowId are invalid and shouldn't be used
-
- Y_UNUSED(itemsLimit);
- Y_UNUSED(bytesLimit);
+ ui64 chargeGroupsItemsLimit = itemsLimit; // pessimistic items limit for groups
const auto& meta = Part->IndexPages.BTreeGroups[0];
Y_ABORT_UNLESS(endRowId <= meta.RowCount);
@@ -89,6 +87,8 @@ public:
// tryHandleChild may update them, copy for simplicity
// always load beginRowId regardless of keys
const TRowId levelBeginRowId = beginRowId, levelEndRowId = Max(endRowId, beginRowId + 1);
+
+ const TChild* firstChild = nullptr;
for (const auto &node : level) {
if (node.EndRowId <= levelBeginRowId || node.BeginRowId >= levelEndRowId) {
continue;
@@ -102,17 +102,50 @@ public:
to = node.Seek(levelEndRowId - 1) + 1;
}
for (TRecIdx pos : xrange(from, to)) {
- auto child = node.GetChild(pos);
- TRowId beginRowId = pos ? node.GetChild(pos - 1).RowCount : node.BeginRowId;
- TRowId endRowId = child.RowCount;
- ready &= tryHandleChild(TChildState(child, beginRowId, endRowId));
+ auto child = node.GetChildRef(pos);
+ auto prevChild = pos ? node.GetChildRef(pos - 1) : nullptr;
+ TRowId beginRowId = prevChild ? prevChild->RowCount : node.BeginRowId;
+ TRowId endRowId = child->RowCount;
+ ready &= tryHandleChild(TChildState(child->PageId, beginRowId, endRowId));
+ if (itemsLimit || bytesLimit) {
+ if (!firstChild) {
+ // do not apply limit on the first child because beginRowId/key1 position is uncertain
+ firstChild = child;
+ } else {
+ if (itemsLimit) {
+ ui64 items = child->GetNonErasedRowCount() - firstChild->GetNonErasedRowCount();
+ if (LimitExceeded(items, itemsLimit)) {
+ overshot = false;
+ return;
+ }
+ }
+ }
+ }
}
}
};
+ const auto skipUnloadedRows = [&](const TChildState& child) {
+ if (child.PageId == key1PageId) {
+ if (chargeGroups && chargeGroupsItemsLimit) {
+ // TODO: use erased count
+ ui64 unloadedItems = child.EndRowId - child.BeginRowId;
+ if (unloadedItems < chargeGroupsItemsLimit) {
+ chargeGroupsItemsLimit -= unloadedItems;
+ } else {
+ chargeGroups = false;
+ }
+ }
+ beginRowId = Max(beginRowId, child.EndRowId);
+ }
+ if (child.PageId == key2PageId) {
+ endRowId = Min(endRowId, child.BeginRowId);
+ }
+ };
+
const auto tryHandleNode = [&](TChildState child) -> bool {
if (child.PageId == key1PageId || child.PageId == key2PageId) {
- if (TryLoadNode(child, nextLevel)) { // update beginRowId, endRowId
+ if (TryLoadNode(child, nextLevel)) {
const auto& node = nextLevel.back();
if (child.PageId == key1PageId) {
TRecIdx pos = node.Seek(ESeek::Lower, key1, Scheme.Groups[0].ColsKeyIdx, &keyDefaults);
@@ -123,20 +156,16 @@ public:
}
if (child.PageId == key2PageId) {
TRecIdx pos = node.Seek(ESeek::Lower, key2, Scheme.Groups[0].ColsKeyIdx, &keyDefaults);
- key2PageId = node.GetShortChild(pos).PageId;
- endRowId = Min(endRowId, node.GetShortChild(pos).RowCount + 1); // move endRowId - 1 to the first key > key2
- if (node.GetShortChild(pos).RowCount <= beginRowId) {
+ auto& key2Child = node.GetShortChild(pos);
+ key2PageId = key2Child.PageId;
+ endRowId = Min(endRowId, key2Child.RowCount + 1); // move endRowId - 1 to the first key > key2
+ if (key2Child.RowCount <= beginRowId) {
chargeGroups = false; // key2 is before current slice
}
}
return true;
- } else { // skip unloaded page rows
- if (child.PageId == key1PageId) {
- beginRowId = Max(beginRowId, child.EndRowId);
- }
- if (child.PageId == key2PageId) {
- endRowId = Min(endRowId, child.BeginRowId);
- }
+ } else {
+ skipUnloadedRows(child);
return false;
}
} else {
@@ -147,7 +176,7 @@ public:
const auto tryHandleDataPage = [&](TChildState child) -> bool {
if (chargeGroups && (child.PageId == key1PageId || child.PageId == key2PageId)) {
const auto page = TryGetDataPage(child.PageId, { });
- if (page) { // update beginRowId, endRowId
+ if (page) {
auto data = NPage::TDataPage(page);
if (child.PageId == key1PageId) {
TRowId key1RowId = data.BaseRow() + data.LookupKey(key1, Scheme.Groups[0], ESeek::Lower, &keyDefaults).Off();
@@ -158,13 +187,8 @@ public:
endRowId = Min(endRowId, key2RowId);
}
return true;
- } else { // skip unloaded page rows
- if (child.PageId == key1PageId) {
- beginRowId = Max(beginRowId, child.EndRowId);
- }
- if (child.PageId == key2PageId) {
- endRowId = Min(endRowId, child.BeginRowId);
- }
+ } else {
+ skipUnloadedRows(child);
return false;
}
} else {
@@ -174,7 +198,7 @@ public:
for (ui32 height = 0; height < meta.LevelCount && ready; height++) {
if (height == 0) {
- ready &= tryHandleNode(TChildState(meta, 0, meta.RowCount));
+ ready &= tryHandleNode(TChildState(meta.PageId, 0, meta.RowCount));
} else {
iterateLevel(tryHandleNode);
}
@@ -183,21 +207,21 @@ public:
}
if (!ready) { // some index pages are missing, do not continue
- ready &= DoPrechargeGroups(chargeGroups, beginRowId, endRowId); // precharge groups using the latest row bounds
+ ready &= DoPrechargeGroups(chargeGroups, beginRowId, endRowId, chargeGroupsItemsLimit, bytesLimit); // precharge groups using the latest row bounds
return {ready, false};
}
// flat index doesn't treat key placement within data page, so let's do the same
// TODO: remove it later
- bool overshot = endRowId == sliceEndRowId;
+ overshot &= endRowId == sliceEndRowId;
if (meta.LevelCount == 0) {
- ready &= tryHandleDataPage(TChildState(meta, 0, meta.RowCount));
+ ready &= tryHandleDataPage(TChildState(meta.PageId, 0, meta.RowCount));
} else {
iterateLevel(tryHandleDataPage);
}
- ready &= DoPrechargeGroups(chargeGroups, beginRowId, endRowId); // precharge groups using the latest row bounds
+ ready &= DoPrechargeGroups(chargeGroups, beginRowId, endRowId, chargeGroupsItemsLimit, bytesLimit); // precharge groups using the latest row bounds
return {ready, overshot};
}
@@ -207,11 +231,9 @@ public:
endRowId++; // current interface accepts inclusive row1 bound
Y_ABORT_UNLESS(beginRowId < endRowId);
- bool ready = true;
+ bool ready = true, overshot = true;
bool chargeGroups = bool(Groups); // false value means that beginRowId, endRowId are invalid and shouldn't be used
-
- Y_UNUSED(itemsLimit);
- Y_UNUSED(bytesLimit);
+ ui64 chargeGroupsItemsLimit = itemsLimit; // pessimistic items limit for groups
const auto& meta = Part->IndexPages.BTreeGroups[0];
Y_ABORT_UNLESS(endRowId <= meta.RowCount);
@@ -222,6 +244,7 @@ public:
chargeGroups = false;
}
+ // level's nodes is in reverse order
TVector<TNodeState> level, nextLevel(::Reserve(3));
TPageId key1PageId = key1 ? meta.PageId : Max<TPageId>();
TPageId key2PageId = key2 ? meta.PageId : Max<TPageId>();
@@ -230,6 +253,9 @@ public:
// tryHandleChild may update them, copy for simplicity
// always load endRowId - 1 regardless of keys
const TRowId levelBeginRowId = Min(beginRowId, endRowId - 1), levelEndRowId = endRowId;
+
+ const TChild* lastChild = nullptr;
+ const TChild* prevLastChild = nullptr;
for (const auto &node : level) {
if (node.EndRowId <= levelBeginRowId || node.BeginRowId >= levelEndRowId) {
continue;
@@ -242,42 +268,75 @@ public:
if (node.EndRowId > levelEndRowId) {
to = node.Seek(levelEndRowId - 1) + 1;
}
- for (TRecIdx pos : xrange(from, to)) {
- auto child = node.GetChild(pos);
- TRowId beginRowId = pos ? node.GetChild(pos - 1).RowCount : node.BeginRowId;
- TRowId endRowId = child.RowCount;
- ready &= tryHandleChild(TChildState(child, beginRowId, endRowId));
+ for (TRecIdx posExt = to; posExt > from; posExt--) {
+ auto child = node.GetChildRef(posExt - 1);
+ auto prevChild = posExt - 1 ? node.GetChildRef(posExt - 2) : nullptr;
+ TRowId beginRowId = prevChild ? prevChild->RowCount : node.BeginRowId;
+ TRowId endRowId = child->RowCount;
+ if (itemsLimit || bytesLimit) {
+ if (!lastChild) {
+ // do not apply limit on the last child because endRowId/key1 position is uncertain
+ lastChild = child;
+ } else {
+ if (!prevLastChild) {
+ prevLastChild = child;
+ }
+ if (itemsLimit) {
+ ui64 items = prevLastChild->GetNonErasedRowCount() - child->GetNonErasedRowCount();
+ if (LimitExceeded(items, itemsLimit)) {
+ overshot = false;
+ return;
+ }
+ }
+ }
+ }
+ ready &= tryHandleChild(TChildState(child->PageId, beginRowId, endRowId));
}
}
};
+ const auto skipUnloadedRows = [&](const TChildState& child) {
+ if (child.PageId == key1PageId) {
+ if (chargeGroups && chargeGroupsItemsLimit) {
+ // TODO: use erased count
+ ui64 unloadedItems = child.EndRowId - child.BeginRowId;
+ if (unloadedItems < chargeGroupsItemsLimit) {
+ chargeGroupsItemsLimit -= unloadedItems;
+ } else {
+ chargeGroups = false;
+ }
+ }
+ endRowId = Min(endRowId, child.BeginRowId);
+ }
+ if (child.PageId == key2PageId) {
+ beginRowId = Max(beginRowId, child.EndRowId);
+ }
+ };
+
const auto tryHandleNode = [&](TChildState child) -> bool {
if (child.PageId == key1PageId || child.PageId == key2PageId) {
- if (TryLoadNode(child, nextLevel)) { // update beginRowId, endRowId
+ if (TryLoadNode(child, nextLevel)) {
const auto& node = nextLevel.back();
if (child.PageId == key1PageId) {
TRecIdx pos = node.SeekReverse(ESeek::Lower, key1, Scheme.Groups[0].ColsKeyIdx, &keyDefaults);
- key1PageId = node.GetShortChild(pos).PageId;
- endRowId = Min(endRowId, node.GetShortChild(pos).RowCount); // move endRowId - 1 to the last key <= key1
+ auto& key1Child = node.GetShortChild(pos);
+ key1PageId = key1Child.PageId;
+ endRowId = Min(endRowId, key1Child.RowCount); // move endRowId - 1 to the last key <= key1
}
if (child.PageId == key2PageId) {
TRecIdx pos = node.Seek(ESeek::Lower, key2, Scheme.Groups[0].ColsKeyIdx, &keyDefaults);
key2PageId = node.GetShortChild(pos).PageId;
if (pos) {
- beginRowId = Max(beginRowId, node.GetShortChild(pos - 1).RowCount - 1); // move beginRowId to the last key < key2
- if (node.GetShortChild(pos - 1).RowCount >= endRowId) {
+ auto& prevKey2Child = node.GetShortChild(pos - 1);
+ beginRowId = Max(beginRowId, prevKey2Child.RowCount - 1); // move beginRowId to the last key < key2
+ if (prevKey2Child.RowCount >= endRowId) {
chargeGroups = false; // key2 is after current slice
}
}
}
return true;
- } else { // skip unloaded page rows
- if (child.PageId == key1PageId) {
- endRowId = Min(endRowId, child.BeginRowId);
- }
- if (child.PageId == key2PageId) {
- beginRowId = Max(beginRowId, child.EndRowId);
- }
+ } else {
+ skipUnloadedRows(child);
return false;
}
} else {
@@ -288,7 +347,7 @@ public:
const auto tryHandleDataPage = [&](TChildState child) -> bool {
if (chargeGroups && (child.PageId == key1PageId || child.PageId == key2PageId)) {
const auto page = TryGetDataPage(child.PageId, { });
- if (page) { // update beginRowId, endRowId
+ if (page) {
auto data = NPage::TDataPage(page);
if (child.PageId == key1PageId) {
auto iter = data.LookupKeyReverse(key1, Scheme.Groups[0], ESeek::Lower, &keyDefaults);
@@ -309,13 +368,8 @@ public:
}
}
return true;
- } else { // skip unloaded page rows
- if (child.PageId == key1PageId) {
- endRowId = Min(endRowId, child.BeginRowId);
- }
- if (child.PageId == key2PageId) {
- beginRowId = Max(beginRowId, child.EndRowId);
- }
+ } else {
+ skipUnloadedRows(child);
return false;
}
} else {
@@ -325,7 +379,7 @@ public:
for (ui32 height = 0; height < meta.LevelCount && ready; height++) {
if (height == 0) {
- ready &= tryHandleNode(TChildState(meta, 0, meta.RowCount));
+ ready &= tryHandleNode(TChildState(meta.PageId, 0, meta.RowCount));
} else {
iterateLevel(tryHandleNode);
}
@@ -334,41 +388,64 @@ public:
}
if (!ready) { // some index pages are missing, do not continue
- ready &= DoPrechargeGroups(chargeGroups, beginRowId, endRowId); // precharge groups using the latest row bounds
+ ready &= DoPrechargeGroupsReverse(chargeGroups, beginRowId, endRowId, chargeGroupsItemsLimit, bytesLimit); // precharge groups using the latest row bounds
return {ready, false};
}
// flat index doesn't treat key placement within data page, so let's do the same
// TODO: remove it later
- bool overshot = beginRowId == sliceBeginRowId;
+ overshot &= beginRowId == sliceBeginRowId;
if (meta.LevelCount == 0) {
- ready &= tryHandleDataPage(TChildState(meta, 0, meta.RowCount));
+ ready &= tryHandleDataPage(TChildState(meta.PageId, 0, meta.RowCount));
} else {
iterateLevel(tryHandleDataPage);
}
- ready &= DoPrechargeGroups(chargeGroups, beginRowId, endRowId); // precharge groups using the latest row bounds
+ ready &= DoPrechargeGroupsReverse(chargeGroups, beginRowId, endRowId, chargeGroupsItemsLimit, bytesLimit); // precharge groups using the latest row bounds
return {ready, overshot};
}
private:
- bool DoPrechargeGroups(bool chargeGroups, TRowId beginRowId, TRowId endRowId) const noexcept {
+ bool DoPrechargeGroups(bool chargeGroups, TRowId beginRowId, TRowId endRowId, ui64 itemsLimit, ui64 bytesLimit) const noexcept {
+ bool ready = true;
+
+ if (chargeGroups && beginRowId < endRowId) {
+ if (itemsLimit && endRowId - beginRowId - 1 >= itemsLimit) {
+ endRowId = beginRowId + itemsLimit + 1;
+ }
+
+ for (auto groupId : Groups) {
+ ready &= DoPrechargeGroup(groupId, beginRowId, endRowId, bytesLimit);
+ }
+ }
+
+ return ready;
+ }
+
+ bool DoPrechargeGroupsReverse(bool chargeGroups, TRowId beginRowId, TRowId endRowId, ui64 itemsLimit, ui64 bytesLimit) const noexcept {
bool ready = true;
if (chargeGroups && beginRowId < endRowId) {
+ if (itemsLimit && endRowId - beginRowId - 1 >= itemsLimit) {
+ beginRowId = endRowId - itemsLimit - 1;
+ }
+
for (auto groupId : Groups) {
- ready &= DoPrechargeGroup(groupId, beginRowId, endRowId);
+ ready &= DoPrechargeGroup(groupId, beginRowId, endRowId, bytesLimit);
}
}
return ready;
}
- bool DoPrechargeGroup(TGroupId groupId, TRowId beginRowId, TRowId endRowId) const noexcept {
+private:
+ bool DoPrechargeGroup(TGroupId groupId, TRowId beginRowId, TRowId endRowId, ui64 bytesLimit) const noexcept {
bool ready = true;
+ Y_UNUSED(bytesLimit);
+
const auto& meta = groupId.IsHistoric() ? Part->IndexPages.BTreeHistoric[groupId.Index] : Part->IndexPages.BTreeGroups[groupId.Index];
TVector<TNodeState> level, nextLevel(::Reserve(3));
@@ -383,10 +460,11 @@ private:
to = node.Seek(endRowId - 1) + 1;
}
for (TRecIdx pos : xrange(from, to)) {
- auto child = node.GetChild(pos);
- TRowId beginRowId = pos ? node.GetChild(pos - 1).RowCount : node.BeginRowId;
+ auto child = node.GetShortChild(pos);
+ auto prevChild = pos ? node.GetShortChildRef(pos - 1) : nullptr;
+ TRowId beginRowId = prevChild ? prevChild->RowCount : node.BeginRowId;
TRowId endRowId = child.RowCount;
- ready &= tryHandleChild(TChildState(child, beginRowId, endRowId));
+ ready &= tryHandleChild(TChildState(child.PageId, beginRowId, endRowId));
}
}
};
@@ -401,7 +479,7 @@ private:
for (ui32 height = 0; height < meta.LevelCount && ready; height++) {
if (height == 0) {
- ready &= tryHandleNode(TChildState(meta, 0, meta.RowCount));
+ ready &= tryHandleNode(TChildState(meta.PageId, 0, meta.RowCount));
} else {
iterateLevel(tryHandleNode);
}
@@ -414,7 +492,7 @@ private:
}
if (meta.LevelCount == 0) {
- ready &= tryHandleDataPage(TChildState(meta, 0, meta.RowCount));
+ ready &= tryHandleDataPage(TChildState(meta.PageId, 0, meta.RowCount));
} else {
iterateLevel(tryHandleDataPage);
}
@@ -458,6 +536,10 @@ private:
: (left.size() > right.size() ? -1 : 1);
}
+ bool LimitExceeded(ui64 value, ui64 limit) const noexcept {
+ return limit && value > limit;
+ }
+
private:
const TPart* const Part;
const TPartScheme &Scheme;
diff --git a/ydb/core/tablet_flat/ut/ut_btree_index_iter_charge.cpp b/ydb/core/tablet_flat/ut/ut_btree_index_iter_charge.cpp
index 8f4b624c972..feb6d560644 100644
--- a/ydb/core/tablet_flat/ut/ut_btree_index_iter_charge.cpp
+++ b/ydb/core/tablet_flat/ut/ut_btree_index_iter_charge.cpp
@@ -36,7 +36,8 @@ namespace {
TMap<TGroupId, TSet<TPageId>> Touched;
};
- void AssertLoadedTheSame(const TPartStore& part, const TTouchEnv& bTree, const TTouchEnv& flat, const TString& message, bool allowFirstLastPageDifference = false) {
+ void AssertLoadedTheSame(const TPartStore& part, const TTouchEnv& bTree, const TTouchEnv& flat, const TString& message,
+ bool allowAdditionalFirstLastPartPages = false, bool allowAdditionalFirstLoadedPage = false, bool allowLastLoadedPageDifference = false) {
TSet<TGroupId> groupIds;
for (const auto &c : {bTree.Loaded, flat.Loaded}) {
for (const auto &g : c) {
@@ -59,14 +60,21 @@ namespace {
// Note: it's possible that B-Tree index touches extra first / last page because it doesn't have boundary keys
// this should be resolved using slices (see ChargeRange)
- if (allowFirstLastPageDifference) {
+ if (allowAdditionalFirstLastPartPages) {
for (auto additionalPageId : {IndexTools::GetFirstPageId(part, groupId), IndexTools::GetLastPageId(part, groupId)}) {
if (bTreeDataPages.contains(additionalPageId)) {
flatDataPages.insert(additionalPageId);
}
}
}
- UNIT_ASSERT_VALUES_EQUAL_C(flatDataPages, bTreeDataPages,
+ // Note: due to implementation details it is possible that B-Tree index touches an extra page
+ if (groupId.IsMain() && allowAdditionalFirstLoadedPage && flatDataPages.size() + 1 == bTreeDataPages.size()) {
+ flatDataPages.insert(*bTreeDataPages.begin());
+ }
+ if (groupId.IsMain() && allowLastLoadedPageDifference && flatDataPages.size() + 1 == bTreeDataPages.size()) {
+ flatDataPages.insert(*bTreeDataPages.rbegin());
+ }
+ UNIT_ASSERT_VALUES_EQUAL_C(flatDataPages, bTreeDataPages,
TStringBuilder() << message << " Group {" << groupId.Index << "," << groupId.IsHistoric() << "}");
}
}
@@ -123,7 +131,7 @@ namespace {
// making part with key gaps
const TVector<ui32> secondCells = {1, 3, 4, 6, 7, 8, 10};
- for (ui32 i : xrange(0u, 40u)) {
+ for (ui32 i : xrange<ui32>(0, 40)) {
cook.Add(*TSchemedCookRow(*lay).Col(i / 7, secondCells[i % 7], i, static_cast<ui64>(i), TString("xxxxxxxxxx_" + std::to_string(i))));
}
@@ -267,8 +275,8 @@ Y_UNIT_TEST_SUITE(TPartBtreeIndexIt) {
}
void CheckSeekRowId(const TPartStore& part) {
- for (TRowId rowId1 : xrange(part.Stat.Rows + 1)) {
- for (TRowId rowId2 : xrange(part.Stat.Rows + 1)) {
+ for (TRowId rowId1 : xrange<TRowId>(0, part.Stat.Rows + 1)) {
+ for (TRowId rowId2 : xrange<TRowId>(0, part.Stat.Rows + 1)) {
TTouchEnv bTreeEnv, flatEnv;
TPartBtreeIndexIt bTree(&part, &bTreeEnv, { });
TPartIndexIt flat(&part, &flatEnv, { });
@@ -307,7 +315,7 @@ Y_UNIT_TEST_SUITE(TPartBtreeIndexIt) {
}
void CheckSeekKey(const TPartStore& part, const TKeyCellDefaults *keyDefaults) {
- for (bool reverse : {false, true}) {
+ for (bool reverse : {false}) {
for (ESeek seek : {ESeek::Exact, ESeek::Lower, ESeek::Upper}) {
for (ui32 firstCell : xrange<ui32>(0, part.Stat.Rows / 7 + 1)) {
for (ui32 secondCell : xrange<ui32>(0, 14)) {
@@ -333,7 +341,7 @@ Y_UNIT_TEST_SUITE(TPartBtreeIndexIt) {
void CheckNextPrev(const TPartStore& part) {
for (bool next : {true, false}) {
- for (TRowId rowId : xrange(part.Stat.Rows)) {
+ for (TRowId rowId : xrange<TRowId>(0, part.Stat.Rows)) {
TTouchEnv bTreeEnv, flatEnv;
TPartBtreeIndexIt bTree(&part, &bTreeEnv, { });
TPartIndexIt flat(&part, &flatEnv, { });
@@ -416,48 +424,63 @@ Y_UNIT_TEST_SUITE(TChargeBTreeIndex) {
Y_UNREACHABLE();
}
- void CheckChargeRowId(const TPartStore& part, TTagsRef tags, const TKeyCellDefaults *keyDefaults, bool reverse) {
- for (TRowId rowId1 : xrange(part.Stat.Rows - 1)) {
- for (TRowId rowId2 : xrange(rowId1, part.Stat.Rows - 1)) {
- TTouchEnv bTreeEnv, flatEnv;
- TChargeBTreeIndex bTree(&bTreeEnv, part, tags, true);
- TCharge flat(&flatEnv, part, tags, true);
+ void CheckChargeRowId(const TPartStore& part, TTagsRef tags, const TKeyCellDefaults *keyDefaults) {
+ for (bool reverse : {false, true}) {
+ for (ui32 itemsLimit : TVector<ui64>{0, 1, 2, 5, 13, 19, part.Stat.Rows - 2, part.Stat.Rows - 1}) {
+ for (TRowId rowId1 : xrange<TRowId>(0, part.Stat.Rows - 1)) {
+ for (TRowId rowId2 : xrange<TRowId>(rowId1, part.Stat.Rows - 1)) {
+ TTouchEnv bTreeEnv, flatEnv;
+ TChargeBTreeIndex bTree(&bTreeEnv, part, tags, true);
+ TCharge flat(&flatEnv, part, tags, true);
- TString message = TStringBuilder() << (reverse ? "ChargeRowIdReverse " : "ChargeRowId ") << rowId1 << " " << rowId2;
- DoChargeRowId(bTree, bTreeEnv, rowId1, rowId2, 0, 0, reverse, *keyDefaults, message);
- DoChargeRowId(flat, flatEnv, rowId1, rowId2, 0, 0, reverse, *keyDefaults, message);
- AssertLoadedTheSame(part, bTreeEnv, flatEnv, message);
+ TString message = TStringBuilder() << (reverse ? "ChargeRowIdReverse " : "ChargeRowId ") << rowId1 << " " << rowId2 << " items " << itemsLimit;
+ DoChargeRowId(bTree, bTreeEnv, rowId1, rowId2, itemsLimit, 0, reverse, *keyDefaults, message);
+ DoChargeRowId(flat, flatEnv, rowId1, rowId2, itemsLimit, 0, reverse, *keyDefaults, message);
+ AssertLoadedTheSame(part, bTreeEnv, flatEnv, message,
+ false, reverse && itemsLimit, !reverse && itemsLimit);
+ }
+ }
}
}
}
- void CheckChargeKeys(const TPartStore& part, TTagsRef tags, const TKeyCellDefaults *keyDefaults, bool reverse) {
- for (ui32 firstCellKey1 : xrange<ui32>(0, part.Stat.Rows / 7 + 1)) {
- for (ui32 secondCellKey1 : xrange<ui32>(0, 14)) {
- for (ui32 firstCellKey2 : xrange<ui32>(0, part.Stat.Rows / 7 + 1)) {
- for (ui32 secondCellKey2 : xrange<ui32>(0, 14)) {
- TVector<TCell> key1 = MakeKey(firstCellKey1, secondCellKey1);
- TVector<TCell> key2 = MakeKey(firstCellKey2, secondCellKey2);
+ void CheckChargeKeys(const TPartStore& part, TTagsRef tags, const TKeyCellDefaults *keyDefaults) {
+ for (bool reverse : {false, true}) {
+ for (ui32 itemsLimit : TVector<ui64>{0, 1, 2, 5, 13, 19, part.Stat.Rows - 2, part.Stat.Rows - 1}) {
+ for (ui32 firstCellKey1 : xrange<ui32>(0, part.Stat.Rows / 7 + 1)) {
+ for (ui32 secondCellKey1 : xrange<ui32>(0, 14)) {
+ for (ui32 firstCellKey2 : xrange<ui32>(0, part.Stat.Rows / 7 + 1)) {
+ for (ui32 secondCellKey2 : xrange<ui32>(0, 14)) {
+ TVector<TCell> key1 = MakeKey(firstCellKey1, secondCellKey1);
+ TVector<TCell> key2 = MakeKey(firstCellKey2, secondCellKey2);
- TTouchEnv bTreeEnv, flatEnv;
- TChargeBTreeIndex bTree(&bTreeEnv, part, tags, true);
- TCharge flat(&flatEnv, part, tags, true);
+ TTouchEnv bTreeEnv, flatEnv;
+ TChargeBTreeIndex bTree(&bTreeEnv, part, tags, true);
+ TCharge flat(&flatEnv, part, tags, true);
- TStringBuilder message = TStringBuilder() << (reverse ? "ChargeKeysReverse " : "ChargeKeys ") << "(";
- for (auto c : key1) {
- message << c.AsValue<ui32>() << " ";
- }
- message << ") (";
- for (auto c : key2) {
- message << c.AsValue<ui32>() << " ";
- }
- message << ")";
+ TStringBuilder message = TStringBuilder() << (reverse ? "ChargeKeysReverse " : "ChargeKeys ") << "(";
+ for (auto c : key1) {
+ message << c.AsValue<ui32>() << " ";
+ }
+ message << ") (";
+ for (auto c : key2) {
+ message << c.AsValue<ui32>() << " ";
+ }
+ message << ") items " << itemsLimit;
- bool bTreeOvershot = DoChargeKeys(part, bTree, bTreeEnv, key1, key2, 0, 0, reverse, *keyDefaults, message);
- bool flatOvershot = DoChargeKeys(part, flat, flatEnv, key1, key2, 0, 0, reverse, *keyDefaults, message);
-
- UNIT_ASSERT_C(bTreeOvershot == flatOvershot, message);
- AssertLoadedTheSame(part, bTreeEnv, flatEnv, message, true);
+ bool bTreeOvershot = DoChargeKeys(part, bTree, bTreeEnv, key1, key2, itemsLimit, 0, reverse, *keyDefaults, message);
+ bool flatOvershot = DoChargeKeys(part, flat, flatEnv, key1, key2, itemsLimit, 0, reverse, *keyDefaults, message);
+
+ if (!itemsLimit) {
+ UNIT_ASSERT_VALUES_EQUAL_C(bTreeOvershot, flatOvershot, message);
+ } else if (bTreeOvershot) {
+ // Note: due to implementation details it is possible that b-tree precharge is more precise
+ UNIT_ASSERT_VALUES_EQUAL_C(bTreeOvershot, flatOvershot, message);
+ }
+ AssertLoadedTheSame(part, bTreeEnv, flatEnv, message,
+ true, reverse && itemsLimit, !reverse && itemsLimit);
+ }
+ }
}
}
}
@@ -473,10 +496,8 @@ Y_UNIT_TEST_SUITE(TChargeBTreeIndex) {
tags.push_back(c.Tag);
}
- CheckChargeRowId(part, tags, eggs.Scheme->Keys.Get(), false);
- CheckChargeRowId(part, tags, eggs.Scheme->Keys.Get(), true);
- CheckChargeKeys(part, tags, eggs.Scheme->Keys.Get(), false);
- CheckChargeKeys(part, tags, eggs.Scheme->Keys.Get(), true);
+ CheckChargeRowId(part, tags, eggs.Scheme->Keys.Get());
+ CheckChargeKeys(part, tags, eggs.Scheme->Keys.Get());
}
Y_UNIT_TEST(NoNodes) {
@@ -505,6 +526,20 @@ Y_UNIT_TEST_SUITE(TChargeBTreeIndex) {
}
Y_UNIT_TEST_SUITE(TPartBtreeIndexIteration) {
+ void MakeRuns(const TPartEggs& eggs, TRun& btreeRun, TRun& flatRun) {
+ const auto part = *eggs.Lone();
+
+ auto flatPart = part.CloneWithEpoch(part.Epoch);
+ for (auto& slice : *part.Slices) {
+ btreeRun.Insert(eggs.Lone(), slice);
+ auto pages = (TVector<TBtreeIndexMeta>*)&flatPart->IndexPages.BTreeGroups;
+ pages->clear();
+ pages = (TVector<TBtreeIndexMeta>*)&flatPart->IndexPages.BTreeHistoric;
+ pages->clear();
+ flatRun.Insert(flatPart, slice);
+ }
+ }
+
void AssertEqual(const TRunIt& bTree, EReady bTreeReady, const TRunIt& flat, EReady flatReady, const TString& message) {
UNIT_ASSERT_VALUES_EQUAL_C(bTreeReady, flatReady, message);
UNIT_ASSERT_VALUES_EQUAL_C(bTree.IsValid(), flat.IsValid(), message);
@@ -542,15 +577,7 @@ Y_UNIT_TEST_SUITE(TPartBtreeIndexIteration) {
const auto part = *eggs.Lone();
TRun btreeRun(*eggs.Scheme->Keys), flatRun(*eggs.Scheme->Keys);
- auto flatPart = part.CloneWithEpoch(part.Epoch);
- for (auto& slice : *part.Slices) {
- btreeRun.Insert(eggs.Lone(), slice);
- auto pages = (TVector<TBtreeIndexMeta>*)&flatPart->IndexPages.BTreeGroups;
- pages->clear();
- pages = (TVector<TBtreeIndexMeta>*)&flatPart->IndexPages.BTreeHistoric;
- pages->clear();
- flatRun.Insert(flatPart, slice);
- }
+ MakeRuns(eggs, btreeRun, flatRun);
auto tags = TVector<TTag>();
for (auto c : eggs.Scheme->Cols) {
@@ -599,15 +626,7 @@ Y_UNIT_TEST_SUITE(TPartBtreeIndexIteration) {
const auto part = *eggs.Lone();
TRun btreeRun(*eggs.Scheme->Keys), flatRun(*eggs.Scheme->Keys);
- auto flatPart = part.CloneWithEpoch(part.Epoch);
- for (auto& slice : *part.Slices) {
- btreeRun.Insert(eggs.Lone(), slice);
- auto pages = (TVector<TBtreeIndexMeta>*)&flatPart->IndexPages.BTreeGroups;
- pages->clear();
- pages = (TVector<TBtreeIndexMeta>*)&flatPart->IndexPages.BTreeHistoric;
- pages->clear();
- flatRun.Insert(flatPart, slice);
- }
+ MakeRuns(eggs, btreeRun, flatRun);
auto tags = TVector<TTag>();
for (auto c : eggs.Scheme->Cols) {
@@ -615,30 +634,32 @@ Y_UNIT_TEST_SUITE(TPartBtreeIndexIteration) {
}
for (bool reverse : {false, true}) {
- for (ui32 firstCellKey1 : xrange<ui32>(0, part.Stat.Rows / 7 + 1)) {
- for (ui32 secondCellKey1 : xrange<ui32>(0, 14)) {
- for (ui32 firstCellKey2 : xrange<ui32>(0, part.Stat.Rows / 7 + 1)) {
- for (ui32 secondCellKey2 : xrange<ui32>(0, 14)) {
- TVector<TCell> key1 = MakeKey(firstCellKey1, secondCellKey1);
- TVector<TCell> key2 = MakeKey(firstCellKey2, secondCellKey2);
+ for (ui64 itemsLimit : part.Slices->size() > 1 ? TVector<ui64>{0} : TVector<ui64>{0, 1, 2, 5, 13, 19, part.Stat.Rows - 2, part.Stat.Rows - 1}) {
+ for (ui32 firstCellKey1 : xrange<ui32>(0, part.Stat.Rows / 7 + 1)) {
+ for (ui32 secondCellKey1 : xrange<ui32>(0, 14)) {
+ for (ui32 firstCellKey2 : xrange<ui32>(0, part.Stat.Rows / 7 + 1)) {
+ for (ui32 secondCellKey2 : xrange<ui32>(0, 14)) {
+ TVector<TCell> key1 = MakeKey(firstCellKey1, secondCellKey1);
+ TVector<TCell> key2 = MakeKey(firstCellKey2, secondCellKey2);
- TTouchEnv bTreeEnv, flatEnv;
-
- TStringBuilder message = TStringBuilder() << (reverse ? "ChargeReverse " : "Charge ") << "(";
- for (auto c : key1) {
- message << c.AsValue<ui32>() << " ";
- }
- message << ") (";
- for (auto c : key2) {
- message << c.AsValue<ui32>() << " ";
- }
- message << ")";
+ TTouchEnv bTreeEnv, flatEnv;
+
+ TStringBuilder message = TStringBuilder() << (reverse ? "ChargeReverse " : "Charge ") << "(";
+ for (auto c : key1) {
+ message << c.AsValue<ui32>() << " ";
+ }
+ message << ") (";
+ for (auto c : key2) {
+ message << c.AsValue<ui32>() << " ";
+ }
+ message << ") items " << itemsLimit;
- // TODO: limits
- Charge(btreeRun, tags, bTreeEnv, key1, key2, 0, 0, reverse, *eggs.Scheme->Keys, message);
- Charge(flatRun, tags, flatEnv, key1, key2, 0, 0, reverse, *eggs.Scheme->Keys, message);
+ Charge(btreeRun, tags, bTreeEnv, key1, key2, itemsLimit, 0, reverse, *eggs.Scheme->Keys, message);
+ Charge(flatRun, tags, flatEnv, key1, key2, itemsLimit, 0, reverse, *eggs.Scheme->Keys, message);
- AssertLoadedTheSame(part, bTreeEnv, flatEnv, message);
+ AssertLoadedTheSame(part, bTreeEnv, flatEnv, message,
+ false, reverse && itemsLimit, !reverse && itemsLimit);
+ }
}
}
}
diff --git a/ydb/core/tablet_flat/ut/ut_btree_index_nodes.cpp b/ydb/core/tablet_flat/ut/ut_btree_index_nodes.cpp
index a881183d4ef..d31131d83b9 100644
--- a/ydb/core/tablet_flat/ut/ut_btree_index_nodes.cpp
+++ b/ydb/core/tablet_flat/ut/ut_btree_index_nodes.cpp
@@ -55,7 +55,11 @@ namespace {
}
TChild MakeChild(ui32 index) {
- return TChild{index + 10000, index + 100, index + 1000, index + 30};
+ return {index + 10000, index + 100, index + 1000, index + 30};
+ }
+
+ TShortChild MakeShortChild(ui32 index) {
+ return {index + 10000, index + 100, index + 1000};
}
void Dump(TChild meta, const TPartScheme::TGroupInfo& groupInfo, const TStore& store, ui32 level = 0) noexcept
@@ -65,7 +69,14 @@ namespace {
intend += " |";
}
- auto dumpChild = [&] (TChild child) {
+ auto dumpChild = [&] (TBtreeIndexNode node, TRecIdx pos) {
+ TChild child;
+ if (node.IsShortChildFormat()) {
+ auto shortChild = node.GetShortChild(pos);
+ child = {shortChild.PageId, shortChild.RowCount, shortChild.DataSize, 0};
+ } else {
+ child = node.GetChild(pos);
+ }
if (child.PageId < 1000) {
Dump(child, groupInfo, store, level + 1);
} else {
@@ -85,7 +96,7 @@ namespace {
<< label.Size << "b}"
<< Endl;
- dumpChild(node.GetChild(0));
+ dumpChild(node, 0);
for (TRecIdx i : xrange(node.GetKeysCount())) {
Cerr << intend << " | > ";
@@ -101,7 +112,7 @@ namespace {
}
Cerr << Endl;
- dumpChild(node.GetChild(i + 1));
+ dumpChild(node, i + 1);
}
Cerr << Endl;
@@ -145,6 +156,13 @@ namespace {
UNIT_ASSERT_EQUAL(node.GetShortChild(i), shortChild);
}
}
+
+ void CheckShortChildren(const NPage::TBtreeIndexNode& node, const TVector<TShortChild>& children) {
+ UNIT_ASSERT_VALUES_EQUAL(node.GetKeysCount() + 1, children.size());
+ for (TRecIdx i : xrange(node.GetKeysCount() + 1)) {
+ UNIT_ASSERT_EQUAL(node.GetShortChild(i), children[i]);
+ }
+ }
}
Y_UNIT_TEST_SUITE(TBtreeIndexNode) {
@@ -271,9 +289,9 @@ Y_UNIT_TEST_SUITE(TBtreeIndexNode) {
keys.push_back(TSerializedCellVec::Serialize(cells));
}
- TVector<TChild> children;
+ TVector<TShortChild> children;
for (ui32 i : xrange(keys.size() + 1)) {
- children.push_back(MakeChild(i));
+ children.push_back(MakeShortChild(i));
}
for (auto k : keys) {
@@ -281,8 +299,7 @@ Y_UNIT_TEST_SUITE(TBtreeIndexNode) {
writer.AddKey(deserialized.GetCells());
}
for (auto &c : children) {
- c.ErasedRowCount = 0;
- writer.AddChild(c);
+ writer.AddChild({c.PageId, c.RowCount, c.DataSize, 0});
}
auto serialized = writer.Finish();
@@ -291,7 +308,7 @@ Y_UNIT_TEST_SUITE(TBtreeIndexNode) {
Dump(serialized, writer.GroupInfo);
CheckKeys(node, keys, writer.GroupInfo);
- CheckChildren(node, children);
+ CheckShortChildren(node, children);
}
Y_UNIT_TEST(History) {
@@ -316,9 +333,9 @@ Y_UNIT_TEST_SUITE(TBtreeIndexNode) {
keys.push_back(TSerializedCellVec::Serialize(cells));
}
- TVector<TChild> children;
+ TVector<TShortChild> children;
for (ui32 i : xrange(keys.size() + 1)) {
- children.push_back(MakeChild(i));
+ children.push_back(MakeShortChild(i));
}
for (auto k : keys) {
@@ -326,8 +343,7 @@ Y_UNIT_TEST_SUITE(TBtreeIndexNode) {
writer.AddKey(deserialized.GetCells());
}
for (auto &c : children) {
- c.ErasedRowCount = 0;
- writer.AddChild(c);
+ writer.AddChild({c.PageId, c.RowCount, c.DataSize, 0});
}
auto serialized = writer.Finish();
@@ -336,7 +352,7 @@ Y_UNIT_TEST_SUITE(TBtreeIndexNode) {
Dump(serialized, writer.GroupInfo);
CheckKeys(node, keys, writer.GroupInfo);
- CheckChildren(node, children);
+ CheckShortChildren(node, children);
UNIT_ASSERT_VALUES_EQUAL(node.GetKeyCellsIter(12, writer.GroupInfo.ColsKeyIdx).At(0).AsValue<TRowId>(), 12);
UNIT_ASSERT_VALUES_EQUAL(node.GetKeyCellsIter(12, writer.GroupInfo.ColsKeyIdx).At(1).AsValue<ui64>(), 120);
diff --git a/ydb/core/tablet_flat/ut/ut_charge.cpp b/ydb/core/tablet_flat/ut/ut_charge.cpp
index e5072d3a44b..76f9ccf1648 100644
--- a/ydb/core/tablet_flat/ut/ut_charge.cpp
+++ b/ydb/core/tablet_flat/ut/ut_charge.cpp
@@ -761,7 +761,7 @@ Y_UNIT_TEST_SUITE(Charge) {
});
me.To(102).CheckByKeys(5, 13, 7, TMap<TGroupId, TArr>{
- {TGroupId{0}, {1, 2, 3, 4_I}},
+ {TGroupId{0}, {1, 2, 3, 4_f}},
{TGroupId{1}, {1_g, 2_g, 3, 4}}, // pages 3, 4 are always needed
{TGroupId{2}, {3_g, 4_g, 5_g, 6, 7, 8, 9_g}} // pages 6, 7, 8 are always needed
});
@@ -773,19 +773,19 @@ Y_UNIT_TEST_SUITE(Charge) {
});
me.To(104).CheckByKeys(5, 13, 5, TMap<TGroupId, TArr>{
- {TGroupId{0}, {1, 2, 3_f, 4_f}},
+ {TGroupId{0}, {1, 2, 3_f}},
{TGroupId{1}, {1_g, 2_g, 3, 4}},
{TGroupId{2}, {3_g, 4_g, 5_g, 6, 7, 8}}
});
me.To(105).CheckByKeys(5, 13, 4, TMap<TGroupId, TArr>{
- {TGroupId{0}, {1, 2, 3_f, 4_f}},
+ {TGroupId{0}, {1, 2, 3_f}},
{TGroupId{1}, {1_g, 2_g, 3, 4_f}}, // here we touch extra pages, but it's fine
{TGroupId{2}, {3_g, 4_g, 5_g, 6, 7, 8_f}} // here we touch extra pages, but it's fine
});
me.To(106).CheckByKeys(7, 13, 3, TMap<TGroupId, TArr>{
- {TGroupId{0}, {1, 2, 3_f, 4_f}},
+ {TGroupId{0}, {1, 2, 3_f}},
{TGroupId{1}, {2_g, 3, 4}},
{TGroupId{2}, {5_g, 6, 7, 8}}
});
@@ -933,7 +933,7 @@ Y_UNIT_TEST_SUITE(Charge) {
});
me.To(202).CheckByKeysReverse(15, 5, 5, TMap<TGroupId, TArr>{
- {TGroupId{0}, {3, 2, 1_f, 0_f}},
+ {TGroupId{0}, {3, 2, 1_f}},
{TGroupId{2}, {11_g, 10_g, 9_g, 8, 7, 6}}
});
generated by cgit v1.3 (git 2.53.0) at 2026-07-21 12:19:08 +0000