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[^3]|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:
Coins:

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

Messages:

key: nonce	amount	sender	recipient	data	da_height
M1	54321	Alice	Alice	[]	12
M2	54321	Bob	Bob	[1, 2]	13

Corresponding index_db:

key1	value
Alice-BASE-0-000000000000d431-M1	CoinTypeId(Message)2
Alice-BTC-0-0000000000000001-X1	CoinTypeId(Coin)
Alice-BTC-0-000000000000000a-X3	CoinTypeId(Coin)
Alice-BTC-0-0000000000000064-X2	CoinTypeId(Coin)
Alice-ETH-0-0000000000000014-X4	CoinTypeId(Coin)
Bob-BASE-1-000000000000d431-M2	CoinTypeId(Message)
Bob-LCK-0-0000000000003039-Y2	CoinTypeId(Coin)
Bob-LCK-0-000000000000d431-Y1	CoinTypeId(Coin)

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 random amount of remaining slots with dust coins (smallest ones)
5. Observe if the added dust coins can "replace" the big coins selected in step 1 - if so, remove the "big coin".
   • this will promote spending the dust coins if applicable, but if a user wants to spend "big" coins, he can always send query with lower max

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? - Nope - see here.
   • ⚠ The duplicate check is not included in the PoC

---

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 1) owner, 2) asset_id, 3) single byte which is 1 for coins and non-retryable messages and 0 for retryable messages, 4) big-endian encoded amount, 5) utxo_id/nonce (for conflict avoidance and coin exclusion) ↩

2. CoinTypeId is and repr u8 enum with the following variants: {Coin, Message}. This will be used to disambiguate between "coins with base asset id" and "messages". ↩

[rafal-ch]

Current flow:

1. coinsToSpend() arrives at the GraphQL API
2. Coins are collected
   1. off_chain DB is queried for "owned coin ids"
      • these are taken from OwnedCoins storage
   2. coin exclusion filter is applied
   3. coins are read from on_chain DB (coins_iter())
      • these are taken from Coins storage
3. if querying for base_asset_id, the above is repeated for "messages":
   1. off_chain DB is queried for "owned message ids"
      • these are taken from OwnedMessageIds storage
   2. messages are read from on_chain DB (messages_iter())
      • these are taken from Messages storage
4. random_improve() algo is used to select coins
   • if it cannot satisfy the request, fallback to largest_first() algorithm

[rafal-ch]

For coins the key bytes represent:
| owner | asset_id | retryable flag | amount bytes | utxo_id |
where retryable flag is always set to false

For messages the key bytes represent:
| owner | base_asset_id | retryable flag | amount bytes | nonce |

[rafal-ch]

Also, to disambiguate between "coins with base asset id" and "message" we'll use the "value" in the DB.