The subject technology performs a locking operation on a first set of keys by a first statement of a first transaction. The subject technology determines that a conflict occurred between the first statement and a second transaction. The subject technology determines that the second transaction has yet to complete after a predetermined period of time. The subject technology performs a deadlock detection process where the subject technology stores a key and value in a table indicating the first transaction and the second transaction, detects, based at least in part on a graph traversal of the table starting from the first transaction, a cycle between the first transaction and the second transaction, and determines that the first transaction is a youngest transaction in the detected cycle. The subject technology ceases execution of the first transaction in response to the first transaction being a youngest transaction in a detected cycle.