Fractional Indexing

To enable user provided ordering of rows, most people reach for a fractional index. They're great given they let you change the position of one row without modifying any other rows. Fractional indices have a number of gotchas, however.

How It Works

Take the following array where each item records its order

window.rows = [ { id: 'a', order: 1 }, { id: 'b', order: 2 }, { id: 'c', order: 3 }, { id: 'd', order: 4 }, { id: 'e', order: 5 }, { id: 'f', order: 6 }, ];

If you want to insert something between 1 & 2, you'll have to re-number 2 and everything after it. This isn't great -- especially in a setting where you could have millions of rows.

Enter fractional indices.

Fractional indices let us insert between existing items by inserting at the midpoint between them.

return (rows[0].order + rows[1].order) / 2

obviously this is great for a database table that stores rows with some user defined order. You can change the order of a row without ever having to touch other rows.

Sounds like heaven, right? Almost...

Fractional Indexing - Gotchas

Fractional indices have some gotchas that aren't apparent at first.

Precision

You might think 52 bits of precision (for JS floats) would be plenty to continuously insert between two items. Since inserts divide the space by 2, you will actually run out of precision after 53 insertions in the wrong spot. Demonstrated below

let lower = 1; let upper = 2; let midpoint = null;

for (let i = 0; i < 52; ++i) { midpoint = (upper + lower) / 2; upper = midpoint; }

const afterFiftyTwo = upper;

midpoint = (upper + lower) / 2; upper = midpoint;

const afterFiftyThree = upper;

return [afterFiftyTwo, afterFiftyThree];

As you can see, our value collapses back to 1 after picking the insert to always be between a specific item and the last insertion after that item.

This is worked around by using arbitrary precision floats. You can, however, run into cases where your index length becomes incredibly large in order to maintain precision.

Conflicts

In a distributed setting, fractional indices have problems when it comes to resolving conflicts

Say peer A inserts item X and peer B inserts item Y and both of them give X & Y position 1.5. When the peers merge, nobody will ever be able to insert between X & Y sine X & Y have the same order.

A workaround for this is to add random jitter to your index.

Another workaround would be to allow collisions.

Imagine two peers P and Q creating this set of data:

A [1, P]
B [2, P]
C [3, P]

X [1, Q]
Y [2, Q]
Z [3, Q]

Now when we merge, everything collides but that's fine. We put the entries from the larger peer after the entries from the lesser peer.

A [1, P]
X [1, Q]
B [2, P]
Y [2, Q]
C [3, P]
Z [3, Q]

When a user wants to insert between a collision we open up space at the collision point for that insertion.

This keeps all the LWW semantics and doesn't introduce anything new. The drawback is that moving something in between a collision requires updating 2 or 3 rows instead of 1.

To prevent exponential growth of your fractional index, insertions at the end should be whole increments and insertions at the beginning should be whole decrements.

I.e.,

-2 <-- start of list
-1
0
1
2 <-- end of list

Interleaving

This is only a problem for certain use cases but another issue that comes up in distributed settings is interleaving. Say I have a document that I'm sharing with myself which says "hi".

I have a copy of this doc on my phone and desktop and then add to it on both devices to say -

Phone: "hi there"
Desktop: "hi dude"

When merging these two docs via fractional indexing, I'll end up interleaving there and dude. Example below.

const jitter = () => Math.random() * 0.0001; // not a _real_ productiom impl of jitter const doc = [ { c: "h", order: 0 }, { c: "i", order: 1 } ];

const phoneDoc = doc.concat([ { c: " ", order: 2 + jitter() }, { c: "t", order: 3 + jitter() }, { c: "h", order: 4 + jitter() }, { c: "e", order: 5 + jitter() }, { c: "r", order: 6 + jitter() }, { c: "e", order: 7 + jitter() } ]); const desktopDoc = doc.concat([ { c: " ", order: 2 + jitter() }, { c: "d", order: 3 + jitter() }, { c: "u", order: 4 + jitter() }, { c: "d", order: 5 + jitter() }, { c: "e", order: 6 + jitter() } ]);

const mergedDoc = Object.values( doc .concat(phoneDoc) .concat(desktopDoc) .reduce((l, r) => { l[r.order] = r; return l; }, {}) ) .sort((l, r) => l.order - r.order) .map((o) => o.c) .join(""); return mergedDoc;

Something Better

Is it possible to do better? To keep the main benefit of a fractional index (only having to touch a constant number of rows & efficient order by queries) and eliminate its drawbacks (precision, conflicts, interleaving)?

Maybe. We can order by a recurisve relationship and even do this efficiently but we'll hit tradeoffs when enabling this in a distributed setting. Read about this in blog/recursive-ordering.