Gap Based Sequence - Tohir Corner

TL;DR
Use gap-based sequences for frequent re-ordering
It will optimize your update queries

Intro

I’ve been given a task to build an API that supports re-ordering in Planner Menu. The planner works like Trello cards, where you can freely move items around.

First Attempt

When I heard “re-ordering” in a collection of tasks/orders, the first thing that came to my mind was a simple sequential order like 1, 2, 3… and so on.

task id	sequence
task-1	1
task-2	2
task-3	3
task-4	4
task-5	5

The idea is simple: assign sequential numbers and voila, the task are ordered. Now, let’s say we want to move task-5 to the position of task-2. The result would be:

task id	sequence
task-1	1
task-5	2 <- task-5 gets sequence 2 and the rest are re-synced
task-2	3
task-3	4
task-4	5

The re-ordering works! But now let’s see it from the database perspective.

When we update the sequence of task-5 from 5 to 2, we also need to update the affected tasks. So we will:

Query the task to check if it exists
Update its sequence
Update every affected task

So the total update queries for one operation is 5 for 5 rows. This seems fine at first, but now imagine 100 tasks. That would becomes 100 update queries!.

And since re-ordering will happen frequently, we need a better approach.

Research & Exploration

I needed a way to handle frequent ordering more efficiently. How can I minimize the number of updates in the database for one drag and drop operation?

Luckily, I found a question on StackExchange about ordering. Gap-based sequencing seems more suitable in my case because it can handle frequent re-ordering with far fewer update queries. (Usually only one row is affected ).

If the gap is becomes to small, we can rebalance the sequence. This does update all tasks, but only happens when the gaps are exhausted.

Second Attempt

I’m using default gap value of 100, so the table looks like this:

task id	sequence
task-1	100
task-2	200
task-3	300
task-4	400
task-5	500

Now, if we want to move the task-5 to the position between task-1 and task-2, we need the previous and next sequences around the target:

Previous sequence is task-1 with sequence of 100
Next sequence is task-2 with sequence of 200

Now we can calculate the new sequence for our task-5:

int previous = 100;
int next = 200;

int gap = next - previous; // 100
int newSequence = previous + (gap /2) // 100 + (100 /2) = 150

task id	sequence
task-1	100
task-5	150 <— midpoint of 200/100
task-2	200
task-3	300
task-4	400

On the database side, we only need to update 1 row.

Handle Edge Case

how to handle if I move the items to the beginning?

int? previous = null;
int next = 100;
int newSequence = next / 2;

how to handle if I move the items to the end?

const DEFAULT_GAP_VALUE = 100;

int previous = 500;
int? next = null;

int newSequence = previous + DEFAULT_GAP_VALUE;

how to rebalance if the gap become too small?
We can set the sequence of the collections to its initial sequence using default sequence value This is a snippet from my implementation of the GapSequencer class.

public class GapSequencer
{
    public const int DEFAULT_GAP_SIZE = 100;
    private readonly int _gapSize;
    private int _currentSequence = 0;

    public GapSequencer() : this(DEFAULT_GAP_SIZE)
    {
    }

    public GapSequencer(int gapSize)
    {
        _gapSize = gapSize;
    }

    public int GetSequence()
    {
        _currentSequence += _gapSize;
        return _currentSequence;
    }

    public void Reset()
    {
        _currentSequence = 0;
    }

    public void InitializeSequences<T>(IEnumerable<T> items, Action<T, int> setSequence)
    {
        Reset();
        foreach (var item in items)
        {
            setSequence(item, GetSequence());
        }
    }

    /// <summary>
    /// Calculates a new sequence number to insert between <paramref name="previousSequence"/> and <paramref name="nextSequence"/>.
    /// At least one of the two must be provided. The result maintains order and avoids collisions.
    /// </summary>
    /// <param name="previousSequence">The sequence number before the insertion point (nullable).</param>
    /// <param name="nextSequence">The sequence number after the insertion point (nullable).</param>
    /// <returns>A new integer sequence value strictly between previous and next (if both provided).</returns>
    /// <exception cref="ArgumentException">
    /// Thrown when both inputs are null or when previousSequence >= nextSequence.
    /// </exception>
    /// <exception cref="InvalidOperationException">
    /// Thrown when there's insufficient gap to insert a value without collision.
    /// </exception>
    public static int CalculateNewSequence(int? previousSequence, int? nextSequence)
    {
        if (!previousSequence.HasValue && !nextSequence.HasValue)
        {
            throw new ArgumentException("At least one of previousSequence or nextSequence must be set");
        }

        if (!previousSequence.HasValue && nextSequence.HasValue)
        {
            if (nextSequence.Value <= 1)
            {
                throw new InvalidOperationException("Gap between sequences is too small. Consider rebalancing the gap size.");
            }

            return nextSequence.Value / 2;
        }

        if (!nextSequence.HasValue && previousSequence.HasValue)
        {
            return previousSequence.Value + DEFAULT_GAP_SIZE;
        }

        int prev = previousSequence!.Value;
        int next = nextSequence!.Value;

        if (prev >= next)
        {
            throw new ArgumentException($"previousSequence ({prev}) must be less than nextSequence ({next})");
        }

        int gap = next - prev;

        if (gap <= 1)
        {
            throw new InvalidOperationException("Gap between sequences is too small. Consider rebalancing the gap size.");
        }

        return prev + (gap / 2);
    }

    public static void RebalanceSequences<T>(IEnumerable<T> items, Action<T, int> setSequence)
    {
        var sequencer = new GapSequencer();
        sequencer.InitializeSequences(items, setSequence);
    }
}

Conclusion

When working on a feature, we often have a solution in mind right away. We know the requirement, we know what to do, so let’s start!

But sometimes we later realize there’s much better approach.

Sequential ordering is simple and works,
but if the order is changing frequently, a gap based sequence is far more efficient.