From b33246adf882e0cda564384e6574d684e6cf7c6e Mon Sep 17 00:00:00 2001
From: Henrik Edin <henrik.edin@mongodb.com>
Date: Tue, 16 Jun 2020 14:57:46 -0400
Subject: SERVER-48746 Radix tree merge compresses nodes if needed and does not
 leave leaf nodes without data

---
 src/mongo/db/storage/biggie/store.h        | 24 ++++++++---
 src/mongo/db/storage/biggie/store_test.cpp | 67 ++++++++++++++++++++++++++++++
 2 files changed, 85 insertions(+), 6 deletions(-)

(limited to 'src/mongo/db/storage')

diff --git a/src/mongo/db/storage/biggie/store.h b/src/mongo/db/storage/biggie/store.h
index a2f74a29945..3ef7fab3e0d 100644
--- a/src/mongo/db/storage/biggie/store.h
+++ b/src/mongo/db/storage/biggie/store.h
@@ -1351,11 +1351,11 @@ private:
      * Merges changes from base to other into current. Throws merge_conflict_exception if there are
      * merge conflicts.
      */
-    void _merge3Helper(Node* current,
-                       const Node* base,
-                       const Node* other,
-                       std::vector<Node*>& context,
-                       std::vector<uint8_t>& trieKeyIndex) {
+    Node* _merge3Helper(Node* current,
+                        const Node* base,
+                        const Node* other,
+                        std::vector<Node*>& context,
+                        std::vector<uint8_t>& trieKeyIndex) {
         context.push_back(current);
 
         // Root doesn't have a trie key.
@@ -1423,7 +1423,17 @@ private:
                 if (node->_trieKey == baseNode->_trieKey &&
                     baseNode->_trieKey == otherNode->_trieKey && node->_data == baseNode->_data &&
                     baseNode->_data == otherNode->_data) {
-                    _merge3Helper(node, baseNode, otherNode, context, trieKeyIndex);
+                    Node* updatedNode =
+                        _merge3Helper(node, baseNode, otherNode, context, trieKeyIndex);
+                    if (!updatedNode->_data) {
+                        // Drop if leaf node without data, that is not valid. Otherwise we might
+                        // need to compress if we have only one child.
+                        if (updatedNode->isLeaf()) {
+                            current->_children[key] = nullptr;
+                        } else {
+                            _compressOnlyChild(updatedNode);
+                        }
+                    }
                 } else {
                     _mergeResolveConflict(node, baseNode, otherNode);
                     _rebuildContext(context, trieKeyIndex);
@@ -1444,6 +1454,8 @@ private:
         context.pop_back();
         if (!trieKeyIndex.empty())
             trieKeyIndex.pop_back();
+
+        return current;
     }
 
     Node* _begin(Node* root) const noexcept {
diff --git a/src/mongo/db/storage/biggie/store_test.cpp b/src/mongo/db/storage/biggie/store_test.cpp
index a61c1fe978f..5dc07e35df3 100644
--- a/src/mongo/db/storage/biggie/store_test.cpp
+++ b/src/mongo/db/storage/biggie/store_test.cpp
@@ -1649,6 +1649,73 @@ TEST_F(RadixStoreTest, MergeBaseKeyNegativeCharTest) {
     ASSERT_EQ(thisStore.find("aac")->second, "c");
 }
 
+TEST_F(RadixStoreTest, MergeWillRemoveEmptyInternalLeaf) {
+    baseStore.insert({"aa", "a"});
+    baseStore.insert({"ab", "b"});
+    baseStore.insert({"ac", "c"});
+    baseStore.insert({"ad", "d"});
+
+    otherStore = baseStore;
+    otherStore.erase("ac");
+    otherStore.erase("ad");
+
+    thisStore = baseStore;
+    thisStore.erase("aa");
+    thisStore.erase("ab");
+
+    thisStore.merge3(baseStore, otherStore);
+
+    // The store is in a valid state that is traversable and we should find no nodes
+    ASSERT_EQ(std::distance(thisStore.begin(), thisStore.end()), 0);
+}
+
+TEST_F(RadixStoreTest, MergeWillRemoveEmptyInternalLeafWithUnrelatedBranch) {
+    baseStore.insert({"aa", "a"});
+    baseStore.insert({"ab", "b"});
+    baseStore.insert({"ac", "c"});
+    baseStore.insert({"ad", "d"});
+    baseStore.insert({"b", "b"});
+
+    otherStore = baseStore;
+    otherStore.erase("ac");
+    otherStore.erase("ad");
+    otherStore.erase("b");
+
+    thisStore = baseStore;
+    thisStore.erase("aa");
+    thisStore.erase("ab");
+
+    thisStore.merge3(baseStore, otherStore);
+
+    // The store is in a valid state that is traversable and we should find no nodes
+    ASSERT_EQ(std::distance(thisStore.begin(), thisStore.end()), 0);
+}
+
+TEST_F(RadixStoreTest, MergeWillCompressNodes) {
+    baseStore.insert({"aa", "a"});
+    baseStore.insert({"ab", "b"});
+    baseStore.insert({"ac", "c"});
+    baseStore.insert({"ad", "d"});
+
+    otherStore = baseStore;
+    otherStore.erase("ab");
+    otherStore.erase("ac");
+
+    thisStore = baseStore;
+    thisStore.erase("aa");
+
+    thisStore.merge3(baseStore, otherStore);
+
+    // The store is in a valid state that is traversable and we should find a single node
+    ASSERT_EQ(thisStore.find("ad")->second, "d");
+    ASSERT_EQ(std::distance(thisStore.begin(), thisStore.end()), 1);
+
+    // Removing this node should not result in an internal leaf node without data
+    thisStore.erase("ad");
+
+    ASSERT_EQ(std::distance(thisStore.begin(), thisStore.end()), 0);
+}
+
 TEST_F(RadixStoreTest, MergeConflictingModifications) {
     value_type value1 = std::make_pair("foo", "1");
     value_type value2 = std::make_pair("foo", "2");
-- 
cgit v1.2.1