Ordered Insertion Optimization in OrioleDB

Summary

When many sessions try to insert into the same B-tree leaf page, classic exclusive page locking serializes progress and wastes time on sleep/wake cycles. We’re introducing a batch page insertion path that lets the session holding the page lock insert for itself and its neighbors. The result: dramatically reduced lock waits, and big gains at high client counts (2X throughput boost starting from 64 clients in our benchmark). The problem: hot leaves and lock convoys​ In OrioleDB beta12, inserts into a B-tree leaf are performed under an exclusive page lock. If several backends target the same leaf page, they queue, sleep, and wake up in turn. That’s correct and simple — but not cheap: Every process waiting for the lock pays the cost of sleep → wake → re-check just to insert a tiny tuple. If the leaf is hot (e.g., time-ordered keys, skew, or tight key ranges), we get a huge queue on that single page. The lock hand-off cadence, not raw CPU, becomes the bottleneck. The idea: cooperate while you hold the page​ We introduced a cooperative scheme that transfers the insertion work to the process that already holds the leaf’s exclusive lock. Think of it as “group commit” for page inserts. How the new batch page insertion works​ Lockless list of waiting processes per page. The lock-protected queue of page-lock waiting processes is replaced with a lockless list (we will call it a “wait list”), so publishing intent is wait-free for followers. The waiting process publishes the tuple. Before a process queues for the page lock, it publishes its tuple (key + payload + a small control meta-information) into shared memory and links it into the page’s wait list. The lock holder process batch insert. When a process inserts into the leaf page (under the lock), it also scans the wait list, collects the already-published tuples whose keys belong to that page, and inserts as many as fit, along with its own tuple. Waking up is usually a no-op. When the original inserters wake, many find their ...