在PostgreSQL中选择最适合的事务组合

Question

I need to select best bitcoin transaction combination for sending. I achieved result using PHP, but it uses a lot of memory and there is huge possibility that database will handle that better.

Whole list of transactions:

+------------------+------+--------+
|  Transaction ID  | Vout | Amount |
+------------------+------+--------+
| transactionid1   |    0 | 10     |
| transactionid1   |    1 | 1.5    |
| transactionid2   |    0 | 0.5    |
| transactionid3   |    0 | 0.7    |
+------------------+------+--------+

I need to create some kind of function or select query which will return me following row when i provide amount = 0.4

+------------------+------+--------+
|  Transaction ID  | Vout | Amount |
+------------------+------+--------+
| transactionid2   |    0 | 0.5    |
+------------------+------+--------+

When i provide amount = 2.1

+------------------+------+--------+
|  Transaction ID  | Vout | Amount |
+------------------+------+--------+
| transactionid1   |    1 | 1.5    |
| transactionid3   |    0 | 0.7    |
+------------------+------+--------+

So it's kind of Knapsack problem with leftover. Here is how i resolved my problem using combinatorics. I've flatten transaction data into $key => $value array, where $key is transactionid_vout and value is amount.

$flatterTransactions = array(4) (
  [transactionid1_0] => (int) 10
  [transactionid1_1] => (float) 1.5
  [transactionid2_0] => (float) 0.5
  [transactionid3_0] => (float) 0.7
)

Then i create combinations from that transactions

$combinations = array(15) (
    [0] => Array
        (
            [transactionid1_0] => 10
        )

    [1] => Array
        (
            [transactionid1_1] => 1.5
        )

    [2] => Array
        (
            [transactionid2_0] => 0.5
        )

    [3] => Array
        (
            [transactionid3_0] => 0.7
        )

    [4] => Array
        (
            [transactionid1_0] => 10
            [transactionid1_1] => 1.5
        )

    [5] => Array
        (
            [transactionid1_0] => 10
            [transactionid2_0] => 0.5
        )

    [6] => Array
        (
            [transactionid1_0] => 10
            [transactionid3_0] => 0.7
        )

    [7] => Array
        (
            [transactionid1_1] => 1.5
            [transactionid2_0] => 0.5
        )

    [8] => Array
        (
            [transactionid1_1] => 1.5
            [transactionid3_0] => 0.7
        )

    [9] => Array
        (
            [transactionid2_0] => 0.5
            [transactionid3_0] => 0.7
        )

    [10] => Array
        (
            [transactionid1_0] => 10
            [transactionid1_1] => 1.5
            [transactionid2_0] => 0.5
        )

    [11] => Array
        (
            [transactionid1_0] => 10
            [transactionid1_1] => 1.5
            [transactionid3_0] => 0.7
        )

    [12] => Array
        (
            [transactionid1_0] => 10
            [transactionid2_0] => 0.5
            [transactionid3_0] => 0.7
        )

    [13] => Array
        (
            [transactionid1_1] => 1.5
            [transactionid2_0] => 0.5
            [transactionid3_0] => 0.7
        )

    [14] => Array
        (
            [transactionid1_0] => 10
            [transactionid1_1] => 1.5
            [transactionid2_0] => 0.5
            [transactionid3_0] => 0.7
        )

)

Then i go through combinations and create summed combination array with scoring. Scoring goal here is to use less transactions.

$summedCombinations[$key] = array(
                'sum' => $sum,
                'count' => count($combination),
                'score' => $sum * (count($combination) * 2)
            );

After all i filter array by sum field to leave only transactions which cover my amount. Order by score and receiving best match.

Answer 1

Best is a bit problematic here, but here's how I would go about it. No matter how you do it, you have to deal with an algorithm for selecting the combination.

 WITH target AS (select ? as target),
 RECURSIVE largest_txs AS (
      select transaction_id, vout, amount, amount as running_total
        from transactions
  CROSS JOIN target 
       where amount < target.target
    order by amount desc limit 1
   UNION ALL
      SELECT t.transaction_id, t.vout, t.amount, t.amount + l.running_total
        FROM transactions
        JOIN (select * from largest_txs order by amount asc limit 1) l
  CROSS JOIN target 
       WHERE amount < target.target + l.running_total AND t.transaction_id NOT IN
             (select transaction_id from largest_txs)
 )
 SELECT transaction_id, vout, amount, running_total FROM largest_txs
  UNION
 SELECT t.transaction_id, t.vout, t.amount, null
   FROM transactions t 
  WHERE t.transaction_id NOT IN (select transaction_id from largest_txs)
  ORDER BY amount asc limit 1;

This should perform as well as can be expected. You will definitely want an index on amount if the table gets to be of any size though.