# Introduction

While we have several ways for computing good linearizations for a cluster from scratch, sometimes we don’t start from scratch. We may have our own linearization already, but receive (through so far unspecified means) another linearization from a peer. If it’s strictly better, we could just switch to it. But what if our linearization is better in some places, and theirs is better in other places? Can we somehow combine the “smarts” that they’re based on, to construct an even better linearization?

As a reminder, we compare linearizations by computing all cumulative (size, fee) points after every chunk, and connecting them by straight lines. Each linearization has such a segmented line, which we call the fee-size diagram. If a linearization A has a diagram that is nowhere below that of linearization B, and at least in some places above it, we say A is strictly better than B. If the diagrams coincide everywhere, they’re equal. If one diagram is on top in some place(s) and the other is on top in others, we call them incomparable.

Due to the (~~so far unproven, but accepted~~ EDIT: now proven, thanks to this thread) property that every cluster has a well-defined non-empty set of optimal linearizations (which are all equal to each other, and all strictly better than all other linearizations), it must be the case that if two incomparable linearizations exist, there *must* exist at least one linearization that’s strictly better than both. This topic is about finding such combined linearizations.

# Algorithms

## Best-chunk merging

We’ve known a simple merging algorithm for a while:

- Given two linearizations
*L*and_{1}*L*:_{2}- While not all transactions have been processed:
- Find highest-feerate prefix
*P*among all unprocessed transactions in_{1}*L*._{1} - Find highest-feerate prefix
*P*among all unprocessed transactions in_{2}*L*._{2} - Include the transactions from the higher-feerate of
*P*and_{1}*P*in output linearization._{2} - Mark the included transactions as processed

- Find highest-feerate prefix

- While not all transactions have been processed:

This algorithm can have \mathcal{O}(n^2) runtime in the number of transactions, because there can be *n* iterations, and each can require \mathcal{O}(n) work to find the highest-feerate prefix. In \mathcal{O}(n) time we can of course also compute the full chunking of *L _{1}* and

*L*(rather than just the first chunk), and it may be possible to reuse part of that computation across iterations; that may enable a lower complexity, but it seems nontrivial. And given the fact that in every case we’ll probably want to run at least an ancestor-set based linearization from scratch ourselves (which is also \mathcal{O}(n^2)), it’s probably fine to target the same complexity for a merging algorithm.

_{2}Sadly, this algorithm doesn’t always produce an output that’s better or equal than both inputs. It will produce a linearization whose diagram is at no point below the *lowest* of the two input diagrams, but that’s not a particularly high bar. We could instead just stick with either one of the inputs instead to achieve that level of quality. In typical cases it’ll be better of course, but there are no guarantees. And it is easy to find examples where the result is just one of the inputs, and thus still incomparable to the other one.

See the example below (labels are `fee/size`

):

```
graph BT
T0["A: 1/3"];
T1["B: 2/1"];
T2["C: 2/1"] --> T0;
T3["D: 7/1"] --> T0;
T4["E: 6/1"] --> T0;
T4 --> T1;
T5["F: 7/3"] --> T1;
```

- The first input linearization is the ancestor set sort: [B,F,A,D,E,C], which is chunked as [BFADE,C].
- The second input is [B,A,E,C,D,F], which is chunked as [BAECD,F]. The BAECD chunk has higher feerate (18/7=2.571) than BFADE (23/9=2.556), but during the F part it is overtaken by BFADE.
- The result of merging is just the second input again.
- The optimal linearization would be [B,A,D,E,F,C], chunked as [BADE,F,C].

What we observe is that there is actually a common subset (BADE) of the two initial chunks that can be moved to the front, but the merging algorithm does not consider this.

## Intersection merging

In an attempt to address that, let’s add a step to the merging algorithm to consider intersections:

- Given two linearizations
*L*and_{1}*L*:_{2}- While not all transactions have been processed:
- Find highest-feerate prefix
*P*among all unprocessed transactions in_{1}*L*._{1} - Find highest-feerate prefix
*P*among all unprocessed transactions in_{2}*L*._{2} - Let
*P*be the intersection of_{3}*P*and_{1}*P*. This is necessarily topologically valid._{2} - Include the transactions from the highest-feerate of
*P*,_{1}*P*, and_{2}*P*in output linearization._{3} - Mark the included transactions as processed

- Find highest-feerate prefix

- While not all transactions have been processed:

While it adds a step, the complexity is unchanged. Unfortunately, it still doesn’t always result in a better linearization:

```
graph BT
T0["D: 1"]
T1["F: 11"];
T2["G: 22"];
T3["A: 1"];
T4["E: 21"];
T5["C: 20"];
T6["B: 13"];
T2 --> T0;
T2 --> T4;
T1 --> T5 --> T3;
T4 --> T3;
T4 --> T6;
```

- The first input linearization is the ancestor set sort: [B,A,E,D,G,C,F], which is chunked as [B,AEDGC,F].
- The second input is [B,A,C,F,E,D,G], which is chunked as [BACFE,DG]. The BACFE chunk has higher feerate (66/5=13.5) than B (13) initially, but gets overtaken by the AEDGC chunk.
- The result of merging is equal to the second input.
- The optimal linearization would be [B,A,C,E,D,G,F], chunked as [BACE,DG,F].

Again the crux is discovering an intersection (BACE), but this time between the BACFE chunk and not one but two chunks of the other input (B and AEDGC).

## Prefix-intersection merging

The solution is to attempt more intersections. Observe that a linearization is really a way of constraining the search for subsets to just prefixes of the linearization. Given the intuition gained above that incomparabilities always seem to be due to a non-considered intersection between the two linearizations, it seems worthwhile try all intersections between prefixes of the first with prefixes of the second linearization. There can be a quadratic number of such intersections however, but maybe we can limit ourselves to just intersections that involve the best chunk of one of both linearizations at least:

- Given two linearizations
*L*and_{1}*L*:_{2}- While not all transactions have been processed:
- Find highest-feerate prefix
*P*among all unprocessed transactions in_{1}*L*._{1} - Find highest-feerate prefix
*P*among all unprocessed transactions in_{2}*L*._{2} - Find the highest-feerate set among all these:
- Intersections between
*P*and all prefixes of_{1}*L*._{2} - Intersections between
*P*and all prefixes of_{2}*L*._{1}

- Intersections between
- Include the transactions from that set in the output linearization.
- Mark the included transactions as processed

- Find highest-feerate prefix

- While not all transactions have been processed:

The various intersections between *P _{1}* and prefixes of

*L*can be computed incrementally (keep adding transactions from

_{2}*L*if they’re in

_{2}*P*, and remember the best one), and similarly for

_{1}*P*with prefixes of

_{2}*L*. This, like finding the

_{1}*P*in the first place, can be done in \mathcal{O}(n) time. The result is still an \mathcal{O}(n^2) algorithm.

_{i}Surprisingly, this algorithm seems powerful enough to always find a linearization that’s strictly better than both inputs if they’re incomparable (and at least as good as the best of the two if they are comparable). This works regardless of the quality of the input linearizations (e.g. they don’t need to be ancestor sort or better), and does not require connected chunks (see linearization post-processing). No proof, though.

## Update: simpler and proven merging

See the discussion further in this thread (thanks, @ajtowns).

It appears that it suffices to only consider the intersections between the higher-feerate out of P_1 and P_2, with all prefixes of the linearization of the other input:

- Given two linearizations L_1 and L_2:
- While not all transactions have been processed:
- Find highest-feerate prefix
*P*among all unprocessed transactions in_{1}*L*._{1} - Find highest-feerate prefix
*P*among all unprocessed transactions in_{2}*L*._{2} - If P_1 has lower feerate than P_2, swap P_1 with P_2 and L_1 with L_2.
- Find the highest-feerate set among all intersections between P_1 and the prefixes of L_1.
- Include the transactions from that set in the output linearization.
- Mark the included transactions as processed

- Find highest-feerate prefix

- While not all transactions have been processed:

Instead of describing the resulting set as an intersection, it can also be seen as the highest-feerate prefix of P_2, reordered according to the order these transactions have in L_1.

A proof for this scheme can be found in this thread.