diff --git a/sql/rpl_trx_tracking.cc b/sql/rpl_trx_tracking.cc
index 11c8a2500ef..9568716e606 100644
--- a/sql/rpl_trx_tracking.cc
+++ b/sql/rpl_trx_tracking.cc
@@ -258,16 +258,20 @@ void Writeset_trx_dependency_tracker::get_dependency(THD *thd,
     int64 last_parent = m_writeset_history_start;
     for (std::vector<uint64>::iterator it = writeset->begin();
          it != writeset->end(); ++it) {
-      Writeset_history::iterator hst = m_writeset_history.find(*it);
+      Writeset_history::iterator hst = m_writeset_history.end();
+      if (!exceeds_capacity) {
+        auto ret = m_writeset_history.emplace(*it, sequence_number);
+        if (!ret.second) {
+          hst = ret.first;
+        }
+      } else {
+        hst = m_writeset_history.find(*it);
+      }
       if (hst != m_writeset_history.end()) {
         if (hst->second > last_parent && hst->second < sequence_number)
           last_parent = hst->second;
 
         hst->second = sequence_number;
-      } else {
-        if (!exceeds_capacity)
-          m_writeset_history.insert(
-              std::pair<uint64, int64>(*it, sequence_number));
       }
     }