Database

Narabe.Ecto keeps the order in your database: a move applied in one transaction, positions for new rows, a scope's keys spread out again, and the order to read it in. It works the same on Postgres, MySQL and SQLite.

Position keys

Each row keeps a position key among the rows of its scope: its list, its board's column, or its parent in a tree. A key is a short text that sorts between its neighbours (Narabe.Position, fractional indexing in base 62):

Narabe.Position.between(nil, nil)    #=> "a0"
Narabe.Position.between("a0", nil)   #=> "a1"
Narabe.Position.between("a0", "a1")  #=> "a0V"

A move writes the moved rows only: their key, and their column or parent when that changes. No other row is renumbered, so a move costs about the same in a list of ten or of a million, and two people moving at once do not write each other's rows. The browser has the same keys (between and betweenMany in the narabe package).

The column

Keys compare byte by byte. Narabe.Migration.position/2 adds a :string column with the collation that does: COLLATE "C" on Postgres, utf8mb4_bin on MySQL; SQLite compares bytes already.

create table(:cards) do
  add :title, :string
  add :column_id, references(:columns)
  position()
end

create index(:cards, [:column_id, :position])

Index the position after the scope. For a position column added before Narabe, Narabe.Migration.alter_position/2 changes its collation in an alter table.

The options

Declare them once on the schema with use Narabe.Ordered; an option given to a call wins over the schema's.

:serialize is given to each call (see below).

A move

{:ok, cards} = Narabe.Ecto.move(Repo, where(Card, board_id: ^board.id), move)

Narabe.Ecto.move/4 gives {:ok, items}, the moved rows as they are now, in their new order, or {:error, reason} with nothing changed. The queryable is the whole of what may be moved: an item, or a new parent, outside it is :not_found. The rules give :into_itself, :not_accepted and :too_deep.

The items land right after move.after, among the rows of the new scope as they are now; else right before move.before; else at move.index; else at the end.

Narabe.Ecto.move_multi/5 is the same move as a step of an Ecto.Multi, for a transaction that does more:

Ecto.Multi.new()
|> Narabe.Ecto.move_multi(:move, Card, move)
|> Ecto.Multi.insert(:log, fn %{move: cards} -> Activity.moved(user, cards) end)
|> Repo.transaction()

Narabe.Live.reply/1 reads its result too.

New rows

Narabe.Ecto.insert_position/4 gives a key at :last (the default), :first, {:after, id} or {:before, id}, in the queryable, or with in: value among its rows whose :group is that value. Narabe.Ecto.put_position/4 puts one in a changeset that has none, in the scope of the changeset's :group value:

%Card{}
|> Card.changeset(attrs)
|> Narabe.Ecto.put_position(Repo)
|> Repo.insert()

Reading in order

Narabe.Ecto.ordered/2 orders a queryable by key, then by id:

Card |> where(column_id: ^id) |> Narabe.Ecto.ordered() |> Repo.all()

Two rows can get the same key: two drops into the same gap at the same moment, or two rows inserted at once at the same place. Ordered by id after the key, they show in the same order on every screen.

Serialize

serialize: takes a queryable of the row that owns the list (the board, the playlist's user). The move locks it (FOR UPDATE) before it reads anything, so that moves in one list run one after the other and two drops into the same gap get different keys:

Narabe.Ecto.move(Repo, where(Card, board_id: ^board.id), move,
  serialize: where(Board, id: ^board.id)
)

SQLite locks the whole database as it writes, and has no row locks.

Rebalance

Keys grow only when items keep landing in the same gap. When a key in the scope grows past :rebalance_at, the move writes every key of that scope anew, evenly, in the same transaction. Narabe.Ecto.rebalance/3 does it on demand, and gives how many rows it wrote:

Narabe.Ecto.rebalance(Repo, where(Card, column_id: ^id))

A table that had no positions needs nothing: rows without a key get keys in their current order (by key, then id) as a move first touches their scope. Or rebalance each scope once.

Trees

Narabe reads a tree's ancestors and descendants with one recursive query each (WITH RECURSIVE, on all three databases), however deep. A move checks the new parent's ancestors, and, only when the rules have a :max_depth, the levels under the moved items. Narabe.Ecto.ancestors/4 and Narabe.Ecto.descendants/4 give the ids.

MySQL stops a recursive query at 1,000 levels (cte_max_recursion_depth).

MySQL

Give the repo socket_options: [nodelay: true]. Without it, delayed ACKs add about 40 ms to each statement, and a move has several:

config :my_app, MyApp.Repo,
  socket_options: [nodelay: true]

How long it takes

Measured locally, with MIX_ENV=test mix run bench/ecto.exs in Narabe's repository: