Optimize GraphQL "coins to spend" query

[rafal-ch]

The source of this issue is #623.

Initially, the idea was to remove all complex queries from fuel-core and make it part of the indexer's responsibility. But the SDK is deeply integrated with these basic queries, that we need to support them on fuel-core. For that, we need to optimize the following query by aggregating some information in the off-chain worker or adding new indexes to the database:

• The coins_to_spend query is very complex and requires n^2 operations where n is the number of coins and messages. The algorithm itself can use additional indexes from RocksDB to solve the issue with dust coins and works fast.

Extracted from the #1965, which initially covered optimizations for 3 different areas: balances, coins to spend, dry run.

[rafal-ch]

This issue will be delivered in at least 2 PRs:

1. Add ability to store coins to spend in an sorted way
2. Leverage the fact that coins are sorted in the selection algorithm

How to achieve pt. 1:

1. We'll use two DBs/columns:
   1. main_db - the current one
   2. index_db - the new, indexation DB
2. Use the separate DB/column to build an "reverse lookup index" which will use the RocksDB key sorting capabilities
   1. RocksDB uses lexicographical sort
   2. To maintain the ordering, the integer representing the amount will be converted to big-endian bytes
   3. Each entry will have a key USER|ASSET|AMOUNT, and value is going to be a key from the main_db
      • this will allow querying by USER|ASSET prefix, getting all coins in sorted order
      • TODO [needed, useful?]: Add ability to retrieve only coins "not greater" and/or "not less" than X
3. To solve the conflicts (for example: user has two coins with same value for the same asset ID), each coin entry will have an unique suffix (utxo_id). This suffix will also be used to quickly exclude coins.

Example DB structure:
main_db

key: utxo_id	amount	block_created	tx_created_idx	asset_id	owner
X1	1	3	12	BTC	Alice
X2	100	3	10	BTC	Alice
X3	10	3	11	BTC	Alice
Y1	54321	4	101	LCK	Bob
Y2	12345	4	100	LCK	Bob
X4	20	3	14	ETH	Alice

Corresponding index_db, assuming that the coins were added in the order presented above:

key1	value
Alice-BTC-0000000000000001-X1	empty
Alice-BTC-000000000000000a-X3	empty
Alice-BTC-0000000000000064-X2	empty
Alice-ETH-0000000000000014-X4	empty
Bob-LCK-0000000000003039-Y2	empty
Bob-LCK-000000000000d431-Y1	empty

How to achieve pt. 2:

1. We try to fulfill the request using the biggest coins available
2. If there is not enough value, return empty set
3. If there is enough value, put the coins into the set
4. If there are still free slots available (ie. user provided higher limit that the number of coins we found in the point above), fill the remaining slots with dust coins (smallest ones)

Remarks:

1. Both main coins and dust coins should respect the "excluded" filter
2. Coins selected as main coins should not be added as dust later in the process

Questions:

1. Can we specify the same asset multiple times in coins_to_spend query?

---

The PoC implementation of the above is available here: https://github.com/rafal-ch/coins_to_spend_poc

Footnotes

1. key is a concatenation of owner, asset_id, big-endian encoded amount, utxo_id (for conflict avoidance and coin exclusion) ↩