\emph{Database isolation} is a formal contract concerning the level of data consistency that a database provides to its clients.
In order to achieve low latency, high throughput, and partition tolerance, modern databases forgo strong transaction isolation for \emph{weak isolation} guarantees.
However, several production databases have been found to suffer from \emph{isolation bugs}, breaking their data-consistency contract.
\emph{Black-box testing} is a prominent technique for detecting isolation bugs, by checking whether histories of database transactions adhere to a prescribed isolation level.

In order to test databases on realistic workloads of large size, isolation testers must be as efficient as possible, a requirement that has initiated a study of the complexity of isolation testing.
Although testing strong isolation has been known to be NP-complete,
weak isolation levels were recently shown to be testable in polynomial time,
which has propelled the scalability of testing tools.
However, existing testers have a large polynomial complexity, restricting testing to workloads of only moderate size, which is not typical of large-scale databases.
\emph{How efficiently can we provably test weak database isolation?}

In this work, we develop AWDIT, \emph{a highly-efficient and provably optimal tester for weak database isolation}.
Given a history $H$ of size $n$ and $k$ sessions, AWDIT tests whether $H$ satisfies the most common weak isolation levels of Read Committed (\textsf{RC}), Read Atomic (\textsf{RA}), and Causal Consistency (\textsf{CC}) in time $O(n^{3/2})$, $O(n^{3/2})$, and $O(n\cdot k)$, respectively, improving significantly over the state of the art.
Moreover, we prove that AWDIT is essentially \emph{optimal}, in the sense that there is a lower bound of $n^{3/2}$, based on the combinatorial BMM hypothesis, for \emph{any} weak isolation level between \textsf{RC} and \textsf{CC}.
Our experiments show that AWDIT is significantly faster than existing, highly optimized testers; e.g., for the $\sim$20% largest histories, AWDIT obtains an average speedup of $245\times$, $193\times$, and $62\times$ for \textsf{RC}, \textsf{RA}, and \textsf{CC}, respectively, over the best baseline.