Turns Out AI Is Not Good at Database Transaction Scheduling (adrs-ucb.notion.site)

Researchers used OpenEvolve, an AI-driven program-synthesis framework, to tackle transaction scheduling — the hard problem of reordering concurrent database transactions to prevent costly contention. In the online setting (decisions made in real time with unknown read/write sets), the state-of-the-art is Shortest Makespan First (SMF), a linear-time, conflict-aware greedy sampler that appends the transaction that minimally increases total makespan. OpenEvolve’s open search starting from random policies rediscovered SMF (likely due to training contamination), underscoring how tight the online constraints (instant decisions, limited info, ACID guarantees) make further gains difficult. Where the framework excelled was offline scheduling, where the full batch of transactions is known and heavier compute is allowed. In under two hours and <$20 of cloud compute across an ensemble (80% Gemini 2.5 Pro, 20% OpenAI o3), OpenEvolve evolved a novel offline algorithm that cuts makespan by 34% versus SMF. Key innovations: smart initialization (sorting by cheap transaction features like write count/length), exhaustive greedy construction (trying each candidate in every possible position), and local refinement (pair-swap hill-climbing plus randomized restarts). The result demonstrates AI’s ability to both reproduce SOTA and synthesize genuinely new algorithms for settings where more lookahead and compute are feasible — promising big throughput wins for deterministic/batched DBs while highlighting the enduring difficulty of real-time transaction scheduling.