Recursive Ordering

We previously covered fractional indexing which is useful for cases where:

1. You have a large number of rows
2. You want to provide an order to those rows
3. Changing the order of one row, with respect to the others, should not require modifying any row except the one being moved
4. Retrieving rows in sorted order should be fast

But it had some downsides

1. A fraction will lose precision quickly
2. Arbitrary precision floats could get very large in pathological cases
3. In a distributed setting, fractional indices can collide preventing insertions of items between the collision
4. In a distributed setting, concurrent edits based on fractional index will interleave

Recursive ordering gets around these drawbacks and it is possible to efficiently order by a recurisve relationship -- even in a relational database. To skip how the algorithm works and jump directly to implementing it in sqlite, see recursive-ordering-in-sqlite.

How Recursive Ordering Works

This first pass at recursive ordering will assume we're dealing with a centralized rather than distributed system. Later explorations will create derivations of the algorithm that work in a distributed setting.

Recursive ordering leverages relationships between items to create an order. The simplest example of this is a linked list. The order of the linked list provides the order of the items.

Note that we link each item to the thing it was inserted after. This will become useful later.

If we order things like this, updating the position of something is just a matter of updating a few pointers rather than re-numbering all of the items in the set.

• Worst case, 3 pointers
• Best case, 1 pointer

You can create a linked list in a table through a schema like the following:

CREATE TABLE node (
  id primary key NOT NULL,
  parent_id,
  content,
);
CREATE INDEX node_parent_id ON node (parent_id);

Where each node has an id and points to the id of its parent, providing the ordering. You're likely wondering:

• How do you order a table by a relationship?
• Is ordering tables through relationships even performant?

See recursive-ordering-in-sqlite.

Pros

• Insertions only requiring updating at most 3 records
• If you have a given start node you can easily find all nodes before it by traversing pointers
• If you need to go in both directions, you can store the other direction of the relationship without much extra cost to insertion time

Cons

• Without additional constraints, this will not work in a distributed setting where writers can update the ordering without coordinating. Someone could move B before D on one node and D before B on another, creating a cycle and breaking the list. See recursive-ordering-in-sqlite.

Why is it "recursive"

This is a considered a recursive ordering since determining the total ordering of the set requires recursively following pointers until arriving at the root.