KIKIMR-19521 BTreeIndex Loader & Dump

8 files changed, 68 insertions, 31 deletions

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 58e5e2052a..3491d58602 100644
--- a/ydb/core/tablet_flat/flat_part_btree_index_iter.h
+++ b/ydb/core/tablet_flat/flat_part_btree_index_iter.h
@@ -129,6 +129,14 @@ public:
         return DoSeek<TSeekRowId>({rowId});
     }
 
+    EReady SeekLast() override {
+        if (Y_UNLIKELY(GetEndRowId() == 0)) {
+            Y_DEBUG_ABORT_UNLESS(false, "TPart can't be empty");
+            return Exhaust();
+        }
+        return Seek(GetEndRowId() - 1);
+    }
+
     /**
      * Searches for the first page that may contain given key with specified seek mode
      *
diff --git a/ydb/core/tablet_flat/flat_part_dump.cpp b/ydb/core/tablet_flat/flat_part_dump.cpp
index eca651c0bf..976fe8fbc2 100644
--- a/ydb/core/tablet_flat/flat_part_dump.cpp
+++ b/ydb/core/tablet_flat/flat_part_dump.cpp
@@ -1,6 +1,6 @@
 #include "flat_part_dump.h"
 #include "flat_part_iface.h"
-#include "flat_part_index_iter.h"
+#include "flat_part_index_iter_iface.h"
 #include "flat_page_data.h"
 #include "flat_page_frames.h"
 #include "flat_page_blobs.h"
@@ -52,10 +52,10 @@ namespace {
         BTreeIndex(part);
 
         if (depth > 2) {
-            auto index = TPartIndexIt(&part, Env, { });
+            auto index = CreateIndexIter(&part, Env, { });
             
             for (ssize_t i = 0; ; i++) {
-                auto ready = i == 0 ? index.Seek(0) : index.Next();
+                auto ready = i == 0 ? index->Seek(0) : index->Next();
                 if (ready != EReady::Data) {
                     if (ready == EReady::Page) {
                         Out << " | -- the rest of the index rows aren't loaded" << Endl;
@@ -65,7 +65,7 @@ namespace {
 
                 Out << Endl;
 
-                DataPage(part, index.GetPageId());
+                DataPage(part, index->GetPageId());
             }
         }
     }
diff --git a/ydb/core/tablet_flat/flat_part_index_iter.h b/ydb/core/tablet_flat/flat_part_index_iter.h
index addfe16236..c6e2e5c74f 100644
--- a/ydb/core/tablet_flat/flat_part_index_iter.h
+++ b/ydb/core/tablet_flat/flat_part_index_iter.h
@@ -36,36 +36,36 @@ public:
         return DataOrGone();
     }
 
-    EReady Seek(ESeek seek, TCells key, const TKeyCellDefaults *keyDefaults) override {
+    EReady SeekLast() override {
         auto index = TryGetIndex();
         if (!index) {
             return EReady::Page;
         }
-
-        Iter = index->LookupKey(key, GroupInfo, seek, keyDefaults);
+        Iter = (*index)->End();
+        if (Iter.Off() == 0) {
+            return EReady::Gone;
+        }
+        Iter--;
         return DataOrGone();
     }
 
-    EReady SeekReverse(ESeek seek, TCells key, const TKeyCellDefaults *keyDefaults) override {
+    EReady Seek(ESeek seek, TCells key, const TKeyCellDefaults *keyDefaults) override {
         auto index = TryGetIndex();
         if (!index) {
             return EReady::Page;
         }
 
-        Iter = index->LookupKeyReverse(key, GroupInfo, seek, keyDefaults);
+        Iter = index->LookupKey(key, GroupInfo, seek, keyDefaults);
         return DataOrGone();
     }
 
-    EReady SeekLast() {
+    EReady SeekReverse(ESeek seek, TCells key, const TKeyCellDefaults *keyDefaults) override {
         auto index = TryGetIndex();
         if (!index) {
             return EReady::Page;
         }
-        Iter = (*index)->End();
-        if (Iter.Off() == 0) {
-            return EReady::Gone;
-        }
-        Iter--;
+
+        Iter = index->LookupKeyReverse(key, GroupInfo, seek, keyDefaults);
         return DataOrGone();
     }
 
diff --git a/ydb/core/tablet_flat/flat_part_index_iter_iface.h b/ydb/core/tablet_flat/flat_part_index_iter_iface.h
index 02da8c5773..1e31599c66 100644
--- a/ydb/core/tablet_flat/flat_part_index_iter_iface.h
+++ b/ydb/core/tablet_flat/flat_part_index_iter_iface.h
@@ -9,6 +9,7 @@ namespace NKikimr::NTable {
         using TCells = NPage::TCells;
 
         virtual EReady Seek(TRowId rowId) = 0;
+        virtual EReady SeekLast() = 0;
         virtual EReady Seek(ESeek seek, TCells key, const TKeyCellDefaults *keyDefaults) = 0;
         virtual EReady SeekReverse(ESeek seek, TCells key, const TKeyCellDefaults *keyDefaults) = 0;
         virtual EReady Next() = 0;
diff --git a/ydb/core/tablet_flat/flat_part_keys.h b/ydb/core/tablet_flat/flat_part_keys.h
index f23171abbe..088e9ca645 100644
--- a/ydb/core/tablet_flat/flat_part_keys.h
+++ b/ydb/core/tablet_flat/flat_part_keys.h
@@ -1,10 +1,9 @@
 #pragma once
 #include "flat_part_iface.h"
-#include "flat_part_index_iter.h"
+#include "flat_part_index_iter_iface.h"
 #include "flat_part_slice.h"
 #include "flat_sausage_fetch.h"
 #include "flat_sausagecache.h"
-#include "util_fmt_abort.h"
 
 namespace NKikimr {
 namespace NTable {
@@ -82,7 +81,7 @@ namespace NTable {
         explicit TKeysLoader(const TPart* part, IPages* env)
             : Part(part)
             , Env(env)
-            , Index(Part, Env, {})
+            , Index(CreateIndexIter(part, env, {}))
         {
         }
 
@@ -151,7 +150,7 @@ namespace NTable {
                     return true;
                 }
 
-                auto ready = Index.Seek(rowId);
+                auto ready = Index->Seek(rowId);
                 if (ready == EReady::Page) {
                     return false;
                 } else if (ready == EReady::Gone) {
@@ -161,11 +160,11 @@ namespace NTable {
                     return true;
                 }
 
-                Y_ABORT_UNLESS(Index.GetRowId() <= rowId, "SeekIndex invariant failure");
-                if (!LoadPage(Index.GetPageId())) {
+                Y_ABORT_UNLESS(Index->GetRowId() <= rowId, "SeekIndex invariant failure");
+                if (!LoadPage(Index->GetPageId())) {
                     return false;
                 }
-                Y_ABORT_UNLESS(Page.BaseRow() == Index.GetRowId(), "Index and data are out of sync");
+                Y_ABORT_UNLESS(Page.BaseRow() == Index->GetRowId(), "Index and data are out of sync");
                 auto lastRowId = Page.BaseRow() + (Page->Count - 1);
                 if (lastRowId < rowId) {
                     // Row is out of range for this page
@@ -180,16 +179,16 @@ namespace NTable {
 
         bool SeekLastRow() noexcept
         {
-            auto hasLast = Index.SeekLast();
+            auto hasLast = Index->SeekLast();
             if (hasLast == EReady::Page) {
                 return false;
             }
             Y_ABORT_UNLESS(hasLast != EReady::Gone, "Unexpected failure to find the last index record");
 
-            if (!LoadPage(Index.GetPageId())) {
+            if (!LoadPage(Index->GetPageId())) {
                 return false;
             }
-            Y_ABORT_UNLESS(Page.BaseRow() == Index.GetRowId(), "Index and data are out of sync");
+            Y_ABORT_UNLESS(Page.BaseRow() == Index->GetRowId(), "Index and data are out of sync");
             auto lastRowId = Page.BaseRow() + (Page->Count - 1);
             LoadRow(lastRowId);
             return true;
@@ -227,7 +226,7 @@ namespace NTable {
         IPages* Env;
         TRowId RowId = Max<TRowId>();
         TPageId PageId = Max<TPageId>();
-        TPartIndexIt Index;
+        THolder<IIndexIter> Index;
         NPage::TDataPage Page;
         TSmallVec<TCell> Key;
     };
diff --git a/ydb/core/tablet_flat/ut/ut_btree_index.cpp b/ydb/core/tablet_flat/ut/ut_btree_index.cpp
index 45d173db70..88bf2fb4b3 100644
--- a/ydb/core/tablet_flat/ut/ut_btree_index.cpp
+++ b/ydb/core/tablet_flat/ut/ut_btree_index.cpp
@@ -916,6 +916,13 @@ Y_UNIT_TEST_SUITE(TPartBtreeIndexIt) {
     }
 
     template<typename TIter>
+    EReady SeekLast(TIter& iter, const TString& message, ui32 failsAllowed = 10) {
+        return Retry([&]() {
+            return iter.SeekLast();
+        }, message, failsAllowed);
+    }
+
+    template<typename TIter>
     EReady SeekKey(TIter& iter, ESeek seek, bool reverse, TCells key, const TKeyCellDefaults *keyDefaults, const TString& message, ui32 failsAllowed = 10) {
         return Retry([&]() {
             if (reverse) {
@@ -967,6 +974,19 @@ Y_UNIT_TEST_SUITE(TPartBtreeIndexIt) {
     }
 
     template<typename TEnv>
+    void CheckSeekLast(const TPartStore& part) {
+        TEnv env;
+        TPartBtreeIndexIt bTree(&part, &env, { });
+        TPartIndexIt flat(&part, &env, { });
+
+        TString message = TStringBuilder() << "SeekLast<" << typeid(TEnv).name() << ">";
+        EReady bTreeReady = SeekLast(bTree, message);
+        EReady flatReady = SeekLast(flat, message);
+        UNIT_ASSERT_VALUES_EQUAL(bTreeReady, EReady::Data);
+        AssertEqual(bTree, bTreeReady, flat, flatReady, message);
+    }
+
+    template<typename TEnv>
     void CheckSeekKey(const TPartStore& part, const TKeyCellDefaults *keyDefaults) {
         for (bool reverse : {false, true}) {
             for (ESeek seek : {ESeek::Exact, ESeek::Lower, ESeek::Upper}) {
@@ -1055,6 +1075,8 @@ Y_UNIT_TEST_SUITE(TPartBtreeIndexIt) {
 
         CheckSeekRowId<TTestEnv>(part);
         CheckSeekRowId<TTouchEnv>(part);
+        CheckSeekLast<TTestEnv>(part);
+        CheckSeekLast<TTouchEnv>(part);
         CheckSeekKey<TTestEnv>(part, eggs.Scheme->Keys.Get());
         CheckSeekKey<TTouchEnv>(part, eggs.Scheme->Keys.Get());
         CheckNextPrev<TTestEnv>(part);
diff --git a/ydb/core/tablet_flat/ut/ut_slice_loader.cpp b/ydb/core/tablet_flat/ut/ut_slice_loader.cpp
index d8c8cfc993..1571085d2b 100644
--- a/ydb/core/tablet_flat/ut/ut_slice_loader.cpp
+++ b/ydb/core/tablet_flat/ut/ut_slice_loader.cpp
@@ -26,6 +26,7 @@ namespace {
         NPage::TConf conf{ true, 2 * 1024 };
 
         conf.Group(0).IndexMin = 1024; /* Should cover index buffer grow code */
+        conf.Group(0).BTreeIndexNodeTargetSize = 512; /* Should cover up/down moves */
         conf.SmallEdge = 19;  /* Packed to page collection large cell values */
         conf.LargeEdge = 29;  /* Large values placed to single blobs */
         conf.SliceSize = conf.Group(0).PageSize * 4;
@@ -53,6 +54,11 @@ namespace {
         return part;
     }
 
+    bool IsBTreeIndex()
+    {
+        return Eggs0().Lone()->IndexPages.BTreeGroups.size();
+    }
+
     class TTestPartPageCollection : public NPageCollection::IPageCollection {
     public:
         TTestPartPageCollection(TIntrusiveConstPtr<NTest::TPartStore> part, ui32 room)
@@ -187,7 +193,7 @@ Y_UNIT_TEST_SUITE(TPartSliceLoader) {
 
     Y_UNIT_TEST(RestoreMissingSlice) {
         auto result = RunLoaderTest(Part0(), nullptr);
-        UNIT_ASSERT_C(result.Pages == 3, // index + first + last
+        UNIT_ASSERT_C(result.Pages == (IsBTreeIndex() ? 5 : 1) + 2, // index + first + last
             "Restoring slice bounds needed " << result.Pages << " extra pages");
     }
 
@@ -199,7 +205,7 @@ Y_UNIT_TEST_SUITE(TPartSliceLoader) {
                 TIntrusiveConstPtr<TScreen> screen = new TScreen(std::move(holes));
                 auto result = RunLoaderTest(Part0(), screen);
 
-                UNIT_ASSERT_VALUES_EQUAL_C(result.Pages, 3, // index + first + last
+                UNIT_ASSERT_VALUES_EQUAL_C(result.Pages, (IsBTreeIndex() ? 5 : 1) + 2, // index + first + last
                     "Restoring slice [" << startOff << ", " << IndexTools::GetEndRowId(*Part0()) + endOff << "] bounds needed "
                         << result.Pages << " extra pages");
             }
@@ -227,7 +233,7 @@ Y_UNIT_TEST_SUITE(TPartSliceLoader) {
             screen = new TScreen(std::move(holes));
         }
         auto result = RunLoaderTest(Part0(), screen);
-        UNIT_ASSERT_VALUES_EQUAL_C(result.Pages, 1 + IndexTools::CountMainPages(*Part0()), // index + all data pages
+        UNIT_ASSERT_VALUES_EQUAL_C(result.Pages, (IsBTreeIndex() ? 70 : 1) + IndexTools::CountMainPages(*Part0()), // index + all data pages
             "Restoring slice bounds needed " << result.Pages << " extra pages");
     }
 
@@ -254,7 +260,7 @@ Y_UNIT_TEST_SUITE(TPartSliceLoader) {
             screen = new TScreen(std::move(holes));
         }
         auto result = RunLoaderTest(Part0(), screen);
-        UNIT_ASSERT_VALUES_EQUAL_C(result.Pages, 1 + IndexTools::CountMainPages(*Part0()), // index + all data pages
+        UNIT_ASSERT_VALUES_EQUAL_C(result.Pages, (IsBTreeIndex() ? 70 : 1) + IndexTools::CountMainPages(*Part0()), // index + all data pages
             "Restoring slice bounds needed " << result.Pages << " extra pages");
     }
 
@@ -283,7 +289,7 @@ Y_UNIT_TEST_SUITE(TPartSliceLoader) {
             screen = new TScreen(std::move(holes));
         }
         auto result = RunLoaderTest(Part0(), screen);
-        UNIT_ASSERT_VALUES_EQUAL_C(result.Pages, screen->Size() + 1, // index + data pages
+        UNIT_ASSERT_VALUES_EQUAL_C(result.Pages, (IsBTreeIndex() ? 70 : 1) + screen->Size(), // index + data pages
             "Restoring slice bounds needed " << result.Pages <<
             " extra pages, expected " << screen->Size());
     }
diff --git a/ydb/core/tablet_flat/ut/ut_stat.cpp b/ydb/core/tablet_flat/ut/ut_stat.cpp
index 1998849365..f567f0465c 100644
--- a/ydb/core/tablet_flat/ut/ut_stat.cpp
+++ b/ydb/core/tablet_flat/ut/ut_stat.cpp
@@ -30,6 +30,7 @@ namespace {
         conf.Groups.resize(groups);
         for (size_t group : xrange(groups)) {
             conf.Group(group).IndexMin = 1024; /* Should cover index buffer grow code */
+            conf.Group(group).BTreeIndexNodeTargetSize = 512; /* Should cover up/down moves */
         }
         conf.SmallEdge = 19;  /* Packed to page collection large cell values */
         conf.LargeEdge = 29;  /* Large values placed to single blobs */