Update schema for "tx_outputs" to use array containing amount output indices

This speeds up wallet refresh by directly retrieving a tx's amount output indices.

It removes the indirection and walking the amount output duplicate list
for every amount in each requested tx.

"tx_outputs" is used by:
Amount output indices are needed for wallet refresh.
Global output indices are needed for removing a tx.

Both amount output indices and global output indices are now stored in
an array of 64-bit unsigned ints:

tx_outputs[<tx_hash>] -> [ <a1_oi, a1_gi, a2_oi, a2_gi, ...> ]

Previously it was:
tx_outputs[<tx_hash>] -> duplicate list of <a1_gi, a2_gi, a3_gi, ...>

The amount output list had to be walked for every amount in order to
find each amount's output index, by comparing the amount's global output
index with each one in the duplicate list until a match was found.

See also d045dfa7ce0bf131681193c97560da26f9f37900

4 files changed, 131 insertions, 119 deletions

diff --git a/src/blockchain_db/blockchain_db.cpp b/src/blockchain_db/blockchain_db.cpp
index a66f4a403..b1b233b58 100644
--- a/src/blockchain_db/blockchain_db.cpp
+++ b/src/blockchain_db/blockchain_db.cpp
@@ -84,12 +84,19 @@ void BlockchainDB::add_transaction(const crypto::hash& blk_hash, const transacti
 
   add_transaction_data(blk_hash, tx, tx_hash);
 
+  std::vector<uint64_t> amount_output_indices;
+  std::vector<uint64_t> global_output_indices;
+
   // iterate tx.vout using indices instead of C++11 foreach syntax because
   // we need the index
   for (uint64_t i = 0; i < tx.vout.size(); ++i)
   {
-    add_output(tx_hash, tx.vout[i], i, tx.unlock_time);
+    uint64_t amount_output_index, global_output_index;
+    add_output(tx_hash, tx.vout[i], i, tx.unlock_time, amount_output_index, global_output_index);
+    amount_output_indices.push_back(amount_output_index);
+    global_output_indices.push_back(global_output_index);
   }
+  add_amount_and_global_output_indices(tx_hash, amount_output_indices, global_output_indices);
 }
 
 uint64_t BlockchainDB::add_block( const block& blk
diff --git a/src/blockchain_db/blockchain_db.h b/src/blockchain_db/blockchain_db.h
index 3396b8c20..2cdaaea6f 100644
--- a/src/blockchain_db/blockchain_db.h
+++ b/src/blockchain_db/blockchain_db.h
@@ -297,7 +297,19 @@ private:
   virtual void remove_transaction_data(const crypto::hash& tx_hash, const transaction& tx) = 0;
 
   // tells the subclass to store an output
-  virtual void add_output(const crypto::hash& tx_hash, const tx_out& tx_output, const uint64_t& local_index, const uint64_t unlock_time) = 0;
+  virtual void add_output(const crypto::hash& tx_hash,
+      const tx_out& tx_output,
+      const uint64_t& local_index,
+      const uint64_t unlock_time,
+      uint64_t& amount_output_index,
+      uint64_t& global_output_index
+      ) = 0;
+
+  // tells the subclass to store indices for a tx's outputs, both amount output indices and global output indices
+  virtual void add_amount_and_global_output_indices(const crypto::hash& tx_hash,
+      const std::vector<uint64_t>& amount_output_indices,
+      const std::vector<uint64_t>& global_output_indices
+      ) = 0;
 
   // tells the subclass to remove an output
   virtual void remove_output(const tx_out& tx_output) = 0;
@@ -501,9 +513,13 @@ public:
 
   virtual bool can_thread_bulk_indices() const = 0;
 
-  // return a vector of indices corresponding to the global output index for
-  // each output in the transaction with hash <h>
-  virtual std::vector<uint64_t> get_tx_output_indices(const crypto::hash& h) const = 0;
+  // return two vectors of indices: vector of amount output indices and global
+  // output indices, corresponding to each output in the transaction with hash
+  // <h>
+  virtual void get_amount_and_global_output_indices(const crypto::hash& h,
+    std::vector<uint64_t>& amount_output_indices,
+    std::vector<uint64_t>& global_output_indices) const = 0;
+
   // return a vector of indices corresponding to the amount output index for
   // each output in the transaction with hash <h>
   virtual std::vector<uint64_t> get_tx_amount_output_indices(const crypto::hash& h) const = 0;
diff --git a/src/blockchain_db/lmdb/db_lmdb.cpp b/src/blockchain_db/lmdb/db_lmdb.cpp
index 8955072b5..0be2728a9 100644
--- a/src/blockchain_db/lmdb/db_lmdb.cpp
+++ b/src/blockchain_db/lmdb/db_lmdb.cpp
@@ -687,7 +687,12 @@ void BlockchainLMDB::remove_transaction_data(const crypto::hash& tx_hash, const
     throw1(DB_ERROR(lmdb_error("Failed to add removal of tx outputs to db transaction: ", result).c_str()));
 }
 
-void BlockchainLMDB::add_output(const crypto::hash& tx_hash, const tx_out& tx_output, const uint64_t& local_index, const uint64_t unlock_time)
+void BlockchainLMDB::add_output(const crypto::hash& tx_hash,
+    const tx_out& tx_output,
+    const uint64_t& local_index,
+    const uint64_t unlock_time,
+    uint64_t& amount_output_index,
+    uint64_t& global_output_index)
 {
   LOG_PRINT_L3("BlockchainLMDB::" << __func__);
   check_open();
@@ -696,7 +701,6 @@ void BlockchainLMDB::add_output(const crypto::hash& tx_hash, const tx_out& tx_ou
   int result = 0;
 
   CURSOR(output_txs)
-  CURSOR(tx_outputs)
   CURSOR(output_indices)
   CURSOR(output_amounts)
   CURSOR(output_keys)
@@ -707,9 +711,6 @@ void BlockchainLMDB::add_output(const crypto::hash& tx_hash, const tx_out& tx_ou
   result = mdb_cursor_put(m_cur_output_txs, &k, &v, MDB_APPEND);
   if (result)
     throw0(DB_ERROR(lmdb_error("Failed to add output tx hash to db transaction: ", result).c_str()));
-  result = mdb_cursor_put(m_cur_tx_outputs, &v, &k, 0);
-  if (result)
-    throw0(DB_ERROR(lmdb_error("Failed to add <tx hash, global output index> to db transaction: ", result).c_str()));
 
   MDB_val_copy<uint64_t> val_local_index(local_index);
   result = mdb_cursor_put(m_cur_output_indices, &k, &val_local_index, MDB_APPEND);
@@ -721,6 +722,14 @@ void BlockchainLMDB::add_output(const crypto::hash& tx_hash, const tx_out& tx_ou
   if (result)
     throw0(DB_ERROR(lmdb_error("Failed to add output amount to db transaction: ", result).c_str()));
 
+  size_t num_elems = 0;
+  result = mdb_cursor_count(m_cur_output_amounts, &num_elems);
+  if (result)
+    throw0(DB_ERROR(std::string("Failed to get number of outputs for amount: ").append(mdb_strerror(result)).c_str()));
+
+  amount_output_index = num_elems - 1;
+  global_output_index = m_num_outputs;
+
   if (tx_output.target.type() == typeid(txout_to_key))
   {
     output_data_t od;
@@ -741,40 +750,57 @@ void BlockchainLMDB::add_output(const crypto::hash& tx_hash, const tx_out& tx_ou
   m_num_outputs++;
 }
 
-void BlockchainLMDB::remove_tx_outputs(const crypto::hash& tx_hash, const transaction& tx)
+void BlockchainLMDB::add_amount_and_global_output_indices(const crypto::hash& tx_hash,
+    const std::vector<uint64_t>& amount_output_indices,
+    const std::vector<uint64_t>& global_output_indices)
 {
   LOG_PRINT_L3("BlockchainLMDB::" << __func__);
-
+  check_open();
   mdb_txn_cursors *m_cursors = &m_wcursors;
-  MDB_val_copy<crypto::hash> k(tx_hash);
-  MDB_val v;
   CURSOR(tx_outputs)
 
-  auto result = mdb_cursor_get(m_cur_tx_outputs, &k, &v, MDB_SET);
-  if (result == MDB_NOTFOUND)
+  int result = 0;
+
+  MDB_val_copy<crypto::hash> k(tx_hash);
+
+  int num_outputs = amount_output_indices.size();
+  std::unique_ptr<uint64_t[]> paired_indices(new uint64_t[2*num_outputs]);
+  for (int i = 0; i < num_outputs; ++i)
   {
-    LOG_PRINT_L2("tx has no outputs, so no global output indices");
+    paired_indices[2*i] = amount_output_indices[i];
+    paired_indices[2*i+1] = global_output_indices[i];
   }
-  else if (result)
+
+  MDB_val v;
+  v.mv_data = (void*)paired_indices.get();
+  v.mv_size = sizeof(uint64_t) * 2 * num_outputs;
+  // LOG_PRINT_L1("tx_outputs[tx_hash] size: " << v.mv_size);
+
+  result = mdb_cursor_put(m_cur_tx_outputs, &k, &v, 0);
+  if (result)
+    throw0(DB_ERROR(std::string("Failed to add <tx hash, amount output index array> to db transaction: ").append(mdb_strerror(result)).c_str()));
+}
+
+void BlockchainLMDB::remove_tx_outputs(const crypto::hash& tx_hash, const transaction& tx)
+{
+  LOG_PRINT_L3("BlockchainLMDB::" << __func__);
+
+  // only need global_output_indices
+  std::vector<uint64_t> amount_output_indices, global_output_indices;
+  get_amount_and_global_output_indices(tx_hash, amount_output_indices, global_output_indices);
+
+  if (global_output_indices.empty())
   {
-    throw0(DB_ERROR("DB error attempting to get an output"));
+    if (tx.vout.empty())
+      LOG_PRINT_L2("tx has no outputs, so no global output indices");
+    else
+      throw0(DB_ERROR("tx has outputs, but no global output indices found"));
   }
-  else
-  {
-    mdb_size_t num_elems = 0;
-    mdb_cursor_count(m_cur_tx_outputs, &num_elems);
-
-    mdb_cursor_get(m_cur_tx_outputs, &k, &v, MDB_LAST_DUP);
 
-    for (uint64_t i = num_elems; i > 0; --i)
-    {
-      const tx_out tx_output = tx.vout[i-1];
-      remove_output(*(const uint64_t*)v.mv_data, tx_output.amount);
-      if (i > 1)
-      {
-        mdb_cursor_get(m_cur_tx_outputs, &k, &v, MDB_PREV_DUP);
-      }
-    }
+  for (uint64_t i = tx.vout.size(); i > 0; --i)
+  {
+    const tx_out tx_output = tx.vout[i-1];
+    remove_output(global_output_indices[i-1], tx_output.amount);
   }
 }
 
@@ -1066,7 +1092,7 @@ void BlockchainLMDB::open(const std::string& filename, const int mdb_flags)
   lmdb_db_open(txn, LMDB_TXS, MDB_CREATE, m_txs, "Failed to open db handle for m_txs");
   lmdb_db_open(txn, LMDB_TX_UNLOCKS, MDB_CREATE, m_tx_unlocks, "Failed to open db handle for m_tx_unlocks");
   lmdb_db_open(txn, LMDB_TX_HEIGHTS, MDB_CREATE, m_tx_heights, "Failed to open db handle for m_tx_heights");
-  lmdb_db_open(txn, LMDB_TX_OUTPUTS, MDB_DUPSORT | MDB_CREATE, m_tx_outputs, "Failed to open db handle for m_tx_outputs");
+  lmdb_db_open(txn, LMDB_TX_OUTPUTS, MDB_CREATE, m_tx_outputs, "Failed to open db handle for m_tx_outputs");
 
   lmdb_db_open(txn, LMDB_OUTPUT_TXS, MDB_INTEGERKEY | MDB_CREATE, m_output_txs, "Failed to open db handle for m_output_txs");
   lmdb_db_open(txn, LMDB_OUTPUT_INDICES, MDB_INTEGERKEY | MDB_CREATE, m_output_indices, "Failed to open db handle for m_output_indices");
@@ -1081,7 +1107,6 @@ void BlockchainLMDB::open(const std::string& filename, const int mdb_flags)
   lmdb_db_open(txn, LMDB_PROPERTIES, MDB_CREATE, m_properties, "Failed to open db handle for m_properties");
 
   mdb_set_dupsort(txn, m_output_amounts, compare_uint64);
-  mdb_set_dupsort(txn, m_tx_outputs, compare_uint64);
   mdb_set_compare(txn, m_spent_keys, compare_hash32);
   mdb_set_compare(txn, m_block_heights, compare_hash32);
   mdb_set_compare(txn, m_txs, compare_hash32);
@@ -1881,112 +1906,62 @@ tx_out_index BlockchainLMDB::get_output_tx_and_index(const uint64_t& amount, con
   return indices[0];
 }
 
-std::vector<uint64_t> BlockchainLMDB::get_tx_output_indices(const crypto::hash& h) const
+void BlockchainLMDB::get_amount_and_global_output_indices(const crypto::hash& h,
+    std::vector<uint64_t>& amount_output_indices,
+    std::vector<uint64_t>& global_output_indices) const
 {
   LOG_PRINT_L3("BlockchainLMDB::" << __func__);
+
   check_open();
-  std::vector<uint64_t> index_vec;
 
+  // If a new txn is created, it only needs to read.
+  //
+  // This must existence of m_write_txn too (not only m_batch_active), as
+  // that's what remove_tx_outputs() expected to use instead of creating a new
+  // txn, regardless of batch mode. Otherwise, remove_tx_outputs() would now
+  // create a new read-only txn here, which is incorrect.
   TXN_PREFIX_RDONLY();
   const mdb_txn_cursors *m_cursors = m_write_txn ? &m_wcursors : &m_tinfo->m_ti_rcursors;
   RCURSOR(tx_outputs);
 
+  int result = 0;
   MDB_val_copy<crypto::hash> k(h);
   MDB_val v;
-  auto result = mdb_cursor_get(m_cur_tx_outputs, &k, &v, MDB_SET);
+
+  result = mdb_cursor_get(m_cur_tx_outputs, &k, &v, MDB_SET);
   if (result == MDB_NOTFOUND)
-    throw1(OUTPUT_DNE("Attempting to get an output by tx hash and tx index, but output not found"));
+    LOG_PRINT_L0("WARNING: Unexpected: tx has no amount and global indices stored in "
+        "tx_outputs, but it should have an empty entry even if it's a tx without "
+        "outputs");
   else if (result)
-    throw0(DB_ERROR("DB error attempting to get an output"));
-
-  mdb_size_t num_elems = 0;
-  mdb_cursor_count(m_cur_tx_outputs, &num_elems);
+    throw0(DB_ERROR("DB error attempting to get data for tx_outputs[tx_hash]"));
 
-  mdb_cursor_get(m_cur_tx_outputs, &k, &v, MDB_FIRST_DUP);
+  uint64_t* paired_indices = (uint64_t*)v.mv_data;
+  int num_elems = v.mv_size / sizeof(uint64_t);
+  if (num_elems % 2 != 0)
+    throw0(DB_ERROR("tx_outputs[tx_hash] does not have an even numer of indices"));
+  int num_outputs = num_elems / 2;
 
-  for (uint64_t i = 0; i < num_elems; ++i)
+  for (int i = 0; i < num_outputs; ++i)
   {
-    mdb_cursor_get(m_cur_tx_outputs, &k, &v, MDB_GET_CURRENT);
-    index_vec.push_back(*(const uint64_t *)v.mv_data);
-    mdb_cursor_get(m_cur_tx_outputs, &k, &v, MDB_NEXT_DUP);
+    // LOG_PRINT_L0("amount output index[" << 2*i << "]" << ": " << paired_indices[2*i] << "  global output index: " << paired_indices[2*i+1]);
+    amount_output_indices.push_back(paired_indices[2*i]);
+    global_output_indices.push_back(paired_indices[2*i+1]);
   }
+  paired_indices = nullptr;
 
   TXN_POSTFIX_RDONLY();
-
-  return index_vec;
 }
 
 std::vector<uint64_t> BlockchainLMDB::get_tx_amount_output_indices(const crypto::hash& h) const
 {
   LOG_PRINT_L3("BlockchainLMDB::" << __func__);
-  check_open();
-  std::vector<uint64_t> index_vec;
-  std::vector<uint64_t> index_vec2;
-
-  // get the transaction's global output indices first
-  index_vec = get_tx_output_indices(h);
-  // these are next used to obtain the amount output indices
-
-  transaction tx = get_tx(h);
-
-  TXN_PREFIX_RDONLY();
-  const mdb_txn_cursors *m_cursors = m_write_txn ? &m_wcursors : &m_tinfo->m_ti_rcursors;
-  RCURSOR(output_amounts);
-
-  uint64_t i = 0;
-  uint64_t global_index;
-  BOOST_FOREACH(const auto& vout, tx.vout)
-  {
-    uint64_t amount =  vout.amount;
-
-    global_index = index_vec[i];
-
-    MDB_val_copy<uint64_t> k(amount);
-    MDB_val v;
 
-    auto result = mdb_cursor_get(m_cur_output_amounts, &k, &v, MDB_SET);
-    if (result == MDB_NOTFOUND)
-      throw1(OUTPUT_DNE("Attempting to get an output index by amount and amount index, but amount not found"));
-    else if (result)
-      throw0(DB_ERROR("DB error attempting to get an output"));
-
-    mdb_size_t num_elems = 0;
-    mdb_cursor_count(m_cur_output_amounts, &num_elems);
-
-    mdb_cursor_get(m_cur_output_amounts, &k, &v, MDB_FIRST_DUP);
-
-    uint64_t amount_output_index = 0;
-    uint64_t output_index = 0;
-    bool found_index = false;
-    for (uint64_t j = 0; j < num_elems; ++j)
-    {
-      mdb_cursor_get(m_cur_output_amounts, &k, &v, MDB_GET_CURRENT);
-      output_index = *(const uint64_t *)v.mv_data;
-      if (output_index == global_index)
-      {
-        amount_output_index = j;
-        found_index = true;
-        break;
-      }
-      mdb_cursor_get(m_cur_output_amounts, &k, &v, MDB_NEXT_DUP);
-    }
-    if (found_index)
-    {
-      index_vec2.push_back(amount_output_index);
-    }
-    else
-    {
-      // not found
-      TXN_POSTFIX_RDONLY();
-      throw1(OUTPUT_DNE("specified output not found in db"));
-    }
-
-    ++i;
-  }
-
-  TXN_POSTFIX_RDONLY();
+  std::vector<uint64_t> amount_output_indices, global_output_indices;
+  // only need amount_output_indices
+  get_amount_and_global_output_indices(h, amount_output_indices, global_output_indices);
 
-  return index_vec2;
+  return amount_output_indices;
 }
 
 
diff --git a/src/blockchain_db/lmdb/db_lmdb.h b/src/blockchain_db/lmdb/db_lmdb.h
index e58643efa..8f80b8c7e 100644
--- a/src/blockchain_db/lmdb/db_lmdb.h
+++ b/src/blockchain_db/lmdb/db_lmdb.h
@@ -246,7 +246,10 @@ public:
   virtual void get_output_tx_and_index(const uint64_t& amount, const std::vector<uint64_t> &offsets, std::vector<tx_out_index> &indices);
   virtual void get_output_global_indices(const uint64_t& amount, const std::vector<uint64_t> &offsets, std::vector<uint64_t> &indices);
 
-  virtual std::vector<uint64_t> get_tx_output_indices(const crypto::hash& h) const;
+  virtual void get_amount_and_global_output_indices(const crypto::hash& h,
+    std::vector<uint64_t>& amount_output_indices,
+    std::vector<uint64_t>& global_output_indices) const;
+
   virtual std::vector<uint64_t> get_tx_amount_output_indices(const crypto::hash& h) const;
 
   virtual bool has_key_image(const crypto::key_image& img) const;
@@ -298,7 +301,18 @@ private:
 
   virtual void remove_transaction_data(const crypto::hash& tx_hash, const transaction& tx);
 
-  virtual void add_output(const crypto::hash& tx_hash, const tx_out& tx_output, const uint64_t& local_index, const uint64_t unlock_time);
+  virtual void add_output(const crypto::hash& tx_hash,
+      const tx_out& tx_output,
+      const uint64_t& local_index,
+      const uint64_t unlock_time,
+      uint64_t& amount_output_index,
+      uint64_t& global_output_index
+      );
+
+  virtual void add_amount_and_global_output_indices(const crypto::hash& tx_hash,
+      const std::vector<uint64_t>& amount_output_indices,
+      const std::vector<uint64_t>& global_output_indices
+      );
 
   virtual void remove_output(const tx_out& tx_output);