Bounding the Makespan of Transaction Schedules

Transaction processing is a core aspect of every database system. In most systems it is implemented through concurrency control, a set of principled protocols which orchestrate access to resources shared by multiple threads of execution. In the database systems literature, this aspect of the system is evaluated by measuring its throughput, or the amount of transactions it can commit to the database per second, on various predetermined workloads such as YCSB [7] or TPC-C [8]. Reliably executing the same workload on different systems is not always evident, as is demonstrated by numerous papers attempting to make this evaluation method less biased [1, 10, 26, 33, 34]. As database theorists, it is therefore pertinent for us to consider a formal theory of schedule efficiency, to investigate the space of all possible efficient schedules, and to identify whether there is room for improvement.

The current theory about transactions largely centers around safety properties [18, 23], and we elaborate on this work’s relation to this literature in Section 7. In its most elementary form, safety is about deciding if a given schedule is valid according to a definition of validity, the gold standard being conflict serializability. In other words, the main purpose is to delineate the space of schedules that is valid. In this work, we are concerned with identifying the space of optimal schedules within that space of valid ones.

Concretely, we formalize schedules as assignments of all operations in a set of transactions to positive integers, intuitively representing their point of execution in time. This enables us to explicitly reason about operations that run in parallel, rather than observing the total order of operations after execution has taken place. Moreover, it lets us quantify efficiency as the elapsed duration between a schedule’s beginning and end, a quantity better known in the scheduling literature as the makespan [4, 25].

For integers $i$ and $j$, we write $[i,j]$ as shorthand notation for $\{i,i+1,\mathrm{\dots },j\}$, and write $[i]$ as a shorthand for $[1,i]$. By ${\mathbb{N}}_0$ we denote the positive integers, including $0$.

We fix an infinite set of objects $𝒪=\{a,b,c,\mathrm{\dots }\}$. A transaction $T$ over $𝒪$ is a sequence of operations $T=o_1{o}_2\mathrm{\dots }{o}_{\mathrm{\ell }}$. We write $|T|$ to mean the number of operations $\mathrm{\ell }$ in $T$. To every operation $o\in T$ we associate a $\text{type}(o)\in \{\text{R},\text{W}\}$ and an $\text{obj}(o)\in 𝒪$. We say that $o$ is a read if $\text{type}(o)=\text{R}$ and that it is a write if $\text{type}(o)=\text{W}$. Furthermore, we say that $o$ is an operation on object $\text{obj}(o)$.

For an integer $i\in [\mathrm{\ell }]$, we write $T[i]$ to denote the $i$th operation of $T$. That is, $T[i]=o_i$. Slightly abusing notation, we will often treat transactions as sets of objects, allowing to write $o\in T$ to mean that $o$ is one of its operations. For two operations $T[i],T[j]$ of $T$, we write $T[i]{\le }_{T}T[j]$ to mean $i\le j$, and to mean . We will leave $𝒪$ implicit when it can be derived from the context and say transaction $T$ instead of transaction $T$ over $𝒪$.

When considering a set of transactions $𝒯$, we will assume that every transaction has a unique id $i$, and we write $T_i$ to make this id explicit. For notational convenience we assume that each transaction can read to each object at most once, and write to each object at most once. This is an assumption commonly made in other literature [18, 19, 30, 31], and the problems we consider become computationally more difficult if this is not the case. It also allows us to refer to a specific operation $o$ in $T_i\in 𝒯$, using the notation ${\text{R}}_i[x]$ (resp., ${\text{W}}_i[x]$), with $x=\text{obj}(o)$ and $\text{type}(o)=\text{R}$ (resp., $\text{type}(o)=\text{W}$).

As usual, we say that two operations $o$ and $p$ occurring in transactions in $𝒯$ are conflicting if they are from different transactions in $𝒯$, and with $\text{obj}(o)=\text{obj}(p)$ and $\text{W}\in \{\text{type}(o),\text{type}(p)\}$.

We define schedules as functions assigning integers to the operations of transactions, intuitively representing the timing of these operations.

For notational convenience, we will sometimes represent a schedule for $𝒯$ as a sequence of sets of operations $A_1{A}_2\mathrm{\dots }{A}_k$ (with every operation of a transaction in $𝒯$ occurring in precisely one of the sets $A_i$), which then should be interpreted as the schedule for $𝒯$ with $s(o)=i-1$ if $o\in A_i$. In other words, the set $A_i$ represents all operations that are executed at precisely time $i$.

Henceforth, we will only consider schedules having the next two additional properties:

1. 1.

   for operations $\{o,p\}\subseteq T$ with , we have ;

2. 2.

   for conflicting operations $\{o,p\}\subseteq O_s$ we have or .

Property (1) expresses that $s$ must preserve the order in which operations occur in the transaction they belong to. Property (2) guarantees that conflicting operations are not executed at precisely the same time.

We call a schedule $s$ dense if for every operation $o\in O_s$, either $s(o)=0$ or there is an operation $p\in O_s$ with $s(o)=s(p)+1$ and either $p$ conflicts with $o$ or it is from the same transaction as $o$. In other words, a schedule is dense if none of its operations can be moved one time unit to the left without invalidating Property (1) or Property (2).

We remark that this definition of schedules differs from most literature¹¹1[32] has a definition based on partial orders, but does not use them to reason about schedule efficiency., e.g. [11, 18, 19, 30, 31], which typically defines schedules as total orders on operations. We deviate from this because we need to reason about the specific length of a schedule $s$. Two operations $o$ and $p$ in $O_s$ that execute in parallel, that is $s(o)=s(p)$ in our model, are usually reduced to a freely chosen order on $\{o,p\}$ in the total order definition. Since the length of a schedule matters in our setting, we make this parallelism more explicit.

We are interested in precisely those schedules that maximally execute operations in parallel, while simultaneously exhibiting the same outcome as a schedule that executes each transaction one by one. We first define the latter condition, and then discuss what it means to maximally parallelize operations.

If a schedule $s$ for $𝒯$ executes transactions one by one we say it is serial. Formally, a schedule $s$ is serial if it has no concurrent operations (i.e., for every pair of different operations $o$, $p$ in $O_s$, we either have or ) and it is non-interleaving (i.e., for every pair of different transactions $T_i$, $T_j$ in $𝒯$, and every pair of different operations $o,p$ in $T_i$, with there is no $q\in T_j$ with ).

If $o$ conflicts with $p$ and , then $p$ depends on $o$ in $s$, which is written as $o{\to }_{s}p$. We now define conflict serializable schedules, which formalizes one notion of what it means for a schedule to have the same outcome as a serial schedule.

We can test whether a schedule $s$ is serializable by creating a conflict graph for $s$, which is a directed graph $\mathrm{CG}(s)=(𝒯,E)$, where $(T_i,T_j)\in E$ if there exists $o{\to }_{s}p$ with $o\in T_i$ and $p\in T_j$ for distinct $\{T_i,T_j\}\subseteq 𝒯$. We can then apply the next textbook result to obtain a decision procedure.

To be able to compare the efficiency of schedules, we associate every schedule with a cost that equals its makespan. The makespan of a schedule $s$ is defined as

Intuitively, $\text{span}(s)$ can be thought of as the completion time of the final operation in the given schedule.

We define the precedence graph ${\mathrm{P}}_s$ of a schedule $s$ for some set $𝒯$ of transactions as the directed graph ${\mathrm{P}}_s=(V,E)$ with $V=O_s$ and

Further on in this paper, we will refer to the precedence graph ${\mathrm{P}}_{\mathrm{\Sigma }}$. This is notation for the precedence graph of the unique dense serializable schedule for $𝒯$ originating from a total order $\mathrm{\Sigma }=(𝒯,{\le }_{𝒯})$ on $𝒯$. More formally one replaces $\{(o,p)\in O_s\times O_s\mid o{\to }_{s}p\}$ in the above definition by all $(o,p)$ such that $o\in T$, $p\in T^{\prime }$ with $\{T,T^{\prime }\}\subseteq 𝒯$, $T\ne T^{\prime }$ and $T{\le }_{𝒯}{T}^{\prime }$.

The following property follows directly from Theorem 4:

Note that for schedules that are not serializable, the precedence graph must be cyclic.

Let us now denote for an acyclic directed graph $G$ by $\text{max-path}(G)$ the maximum number of nodes occurring in any directed path of $G$. Then, $\text{max-path}(P_{\mathrm{\Sigma }})$ for a totally ordered set of transactions $\mathrm{\Sigma }=(𝒯,{\le }_{𝒯})$ corresponds to the makespan of a particular schedule for $𝒯$.

It is straightforward to verify that canonical schedules are dense by construction.

Next we will show that a minimal cost schedule can be found among the canonical schedules. For this, let $\text{cost}(𝒯)=\min \left\{\text{span}(s)\mid s\text{ is a serializable schedule for }𝒯\right\}$. The following corollary is immediate.

Notice that this implies $\text{cost}(𝒯)=\min \{\text{span}(\text{canonical}(\mathrm{\Sigma }))\mid \mathrm{\Sigma }\text{ is a total order for }𝒯\}$.

Unfortunately, it is unlikely that there are tractable algorithms that find an optimal serialization order for arbitrary sets of transactions. In this section, we consider a decision variant²²2There exists an analog definition of NP-completeness for optimization problems called NPO-complete. One possible way to show membership in this class is precisely by showing that the decision problem we consider, often called the threshold problem, is an NP-complete decision problem [9, 15, 21]. of our scheduling problem asking for a set $𝒯$ of transactions and number $k$ if a serializable schedule $s$ for $𝒯$ exists with $\text{span}(s)\le k$ and show that it is $\mathrm{NP}\text{-}\mathrm{complete}$.

Schedulability input: a set of transactions $𝒯$ and positive integer $k\in {\mathbb{N}}_0$. output: true if a serializable schedule $s$ for $𝒯$ with $\text{span}(s)\le k$ exists; false otherwise.

By Proposition 8, we can also give a total order $\mathrm{\Sigma }$ for $𝒯$ with $\text{span}(\text{canonical}(\mathrm{\Sigma }))\le k$.

First, we argue that Schedulability is straightforwardly in $\mathrm{NP}$, because, if for $𝒯$ and $k$ a schedule $s$ exists with $\text{span}(s)\le k$, then $s$ trivially serves as polynomial-sized witness.

To show that Schedulability is $\mathrm{NP}\text{-}\mathrm{hard}$, we make a reduction from a simpler problem called 2-Orientability. For its definition, let $G=(V,E)$ be an undirected graph and let ${\le }_V$ be a total order on its nodes. Then by $\text{OG}(G,{\le }_V)$ we denote the orientation of $G$ based on ${\le }_V$, that is, the directed graph with nodes $V$ and with the directed edges $\{(u,v)\mid \{u,v\}\in E,u{\le }_{V}v\}$. Now, 2-Orientability asks for an undirected graph $G$ if there exists a total order ${\le }_V$ on the nodes in $G$ such that the length (number of edges) of every directed path in $\text{OG}(G,{\le }_V)$ is at most $2$.

2-Orientability input: an undirected graph $G=(V,E)$. output: true if a total order ${\le }_V$ on $V$ exists such that the length of the longest path in $\text{OG}(G,{\le }_V)$ is at most 2; false otherwise.

The next result follows from the Gallai-Roy-Vitaver Theorem [5].

We now conclude the proof for Theorem 10 by showing there exists a polynomial-time reduction from this problem to Schedulability.

Given some graph $G=(V,E)$ as input for 2-Orientability, we will explain the construction of a set $𝒯$ of transactions and will then argue that:

For the construction, we first fix an arbitrarily chosen order on the edges of $E$, which allows referring to them as $e_1$, $e_2$, …, $e_{|E|}$. We also associate to every edge $e_i$ three different and unique objects $x_i$, $y_i$, and $z_i$. Then, the set $𝒯$ that we construct, will consist of precisely $|V|$ transactions, such that there is one transaction for each node in $V$. We write $T_v$ to denote the transaction associated to node $v\in V$. Every transaction $T_v$ consists of precisely $3|E|$ operations, namely

The objects these operations interact with are chosen as follows: if $v\in e_i$, then ${\chi }_i$, ${\gamma }_i$ and ${\zeta }_i$ are the earlier defined objects $x_i$, $y_i$, and $z_i$, respectively. Otherwise, if $v\notin e_i$, then ${\chi }_i$, ${\gamma }_i$ and ${\zeta }_i$ are (all different) unique objects not occurring anywhere else in our construction.

We remark that this construction is indeed polynomial. To conclude the proof of Proposition 12, we make use of Proposition 8 and the next result.

Some visual intuition for this lemma, in particular the construction of these longest paths through $P_{\mathrm{\Sigma }}$, can be seen in Figure 3.

We now turn our attention to instance optimal scheduling algorithms. That is, we will identify a restriction on transaction sets that will enable us to compute schedules with a minimal makespan, for any set adhering to this restriction, in polynomial time.

To this extent, we define the contention points of $𝒯$ as a set of objects $𝒞(𝒯)\subseteq 𝒪$ such that if $o$ and $p$ are conflicting operations in $𝒯$, then $\text{obj}(o)\in 𝒞(𝒯)$. The converse does not necessarily have to hold, not every contention point must appear in a conflicting operation. We will refer to an element of $𝒞(𝒯)$ as a contention point, and say that a $T\in 𝒯$ contends if $T$ contains an operation on a contention point.

We now define ${𝕋}_{\mathrm{\ell },m,n}$ as a set of transaction sets with $𝒯\in {𝕋}_{\mathrm{\ell },m,n}$ if $|T|\le \mathrm{\ell }$ for all $T\in 𝒯$, $|𝒞(𝒯)|\le m$, and $|𝒯|\le n$. Exclusively in this section, we write ${𝕋}_m$ instead of ${𝕋}_{\mathrm{\ell },m,n}$, as all results can be phrased such that $\mathrm{\ell }$ is the length of the longest transaction in our set, and we can let $n=|𝒯|$. We also define ${𝕋}_m^{+}$ with $𝒯\in {𝕋}_m^{+}$ if $𝒯\in {𝕋}_m$ and $T$ contends for all $T\in 𝒯$.

Given $𝒯\in {𝕋}_1^{+}$, we can see each $T\in 𝒯$ as a sequence:

where $r$ is the position in $T$ such that $T[r]=\text{W}[a]$, and $T$ consists of a (potentially empty) subsequence of operations, followed by a conflicting operation to the contention point $a$, and another (potentially empty) subsequence of operations. In the above sequence we can also replace $\text{W}[a]$ by $\text{R}[a]$ as long as it is a conflicting operation, we typically use $\text{W}[a]$ throughout this section, this does not impact the generality of our results. We call the former subsequence the prefix of $T$; the latter is the suffix of $T$. We define $\text{pre}(T)$ and $\text{suf}(T)$ to be the number of operations before the first (respectively, after the last) contention point.

We will also denote the inverse of ${\alpha }_k$ by ${\alpha }_k^{-1}$. Notice that, $[0,k]$ means there are $k+1$ bins in total, as we start counting from 0.

For any allocation of a $𝒯\in {𝕋}_1^{+}$ to $[0,k]$, we can use the allocation as an ordering on the transactions. Indeed, if ${\alpha }_k(T_i)\le {\alpha }_k(T_j)$ for $\{T_i,T_j\}\subseteq 𝒯$, then we define an order $\text{ord}({\alpha }_k)=(𝒯,{\le }_{{\alpha }_k})$ such that $T_i{\le }_{{\alpha }_k}{T}_j$. Conversely, we can define an allocation $\text{alloc}(\mathrm{\Sigma },k)$ to $[0,k]$ based on a total order $\mathrm{\Sigma }$ with $\text{span}(\text{canonical}(\mathrm{\Sigma }))\le k+1$. Let this total order be $T_1,T_2,\mathrm{\dots },T_n$. Then for each $T_i$, with $i\in [n]$, we define $\text{alloc}(\mathrm{\Sigma },k)(T_i)=j$ such that $j\in [0,k]$ is the minimal bin with $\text{pre}(T_i)\le j$, $\text{suf}(T_i)\le k-j$, and for all . We then have the following result.

The former characterization gives us a tool for constructing an optimal order, provided we have an algorithm for allocations. To that end, we define an algorithm $\text{Allocate}(𝒯,k)$.

It is clear that $\text{Allocate}(𝒯,k)$ is sound by construction. That is, if it does not terminate with $\perp$, it terminates with a valid allocation of $𝒯$ to $[0,k]$. Showing completeness, that is, termination with $\perp$ implies there exists no valid allocation from $𝒯$ to $[0,k]$, requires slightly more argumentation. The following lemma is a useful tool.

Completeness follows from assuming a smaller allocation exists despite the algorithm yielding $\perp$, and then showing it contradicts Lemma 16. Proposition 15 ensures no order exists either.

We can repeat the algorithm with a $k$ that starts at the length of the largest transaction, incrementing whenever it yields $\perp$. We terminate when the first allocation is returned. We remark that $k$ is at most ${\sum }_{T\in 𝒯}|T|$, hence $k$ depends entirely on the transaction set, and therefore its time complexity is polynomial and entirely dependent on $𝒯$.

Until now, we have considered transactions from ${𝕋}_1^{+}$, but this restriction can be easily relaxed to any $𝒯\in {𝕋}_1$ by only considering the transactions in $𝒯$ which contend. To obtain an ordering for the full $𝒯$ we can append the remaining transactions arbitrarily onto the allocation order. The corollary then readily follows from Proposition 15 and Theorem 17.

The algorithm in this section resembles an instance optimal algorithm for the Job Shop Scheduling problem called Johnson’s Rule [16]. We illustrate it is subtly different.

We now look at the transaction scheduling problem from the perspective of worst-case analysis. More specifically, we derive a worst-case optimal bound on the makespan for any transaction set, and in doing so, construct algorithms for any transaction set which yield schedules with a makespan that never exceeds this bound. Additionally, on the worst-behaving transaction sets, the resulting schedules must be optimal.

We define the worst-case optimal cost for ${𝕋}_{\mathrm{\ell },m,n}$ as

Since we are concerned with a worst-case scenario, we will consider transactions to be long enough for them to contain operations on each contention point, that is, $\mathrm{\ell }\ge m$. Alongside this, we always have $n\ge 1$ and $m\ge 0$.

For ${𝕋}_{\mathrm{\ell },m,1}$, ${𝕋}_{\mathrm{\ell },0,n}$, and ${𝕋}_{\mathrm{\ell },1,n}$, this cost is trivial to determine. Indeed, if $n=1$ the makespan of all schedules is simply $\mathrm{\ell }$. Similarly, if $m=0$ we can always execute all transactions entirely in parallel, hence $\text{wco-cost}({𝕋}_{\mathrm{\ell },0,n})=\text{wco-cost}({𝕋}_{\mathrm{\ell },m,1})=\mathrm{\ell }$. Lastly, if $m=1$, the lone operation on the contention point occurs in the same position in every transaction $T$ in all instances $𝒯$ for which $\text{cost}(𝒯)$ is maximal. An optimal schedule will shift each operation in each consecutive transaction forwards by one time unit, hence $\text{wco-cost}({𝕋}_{\mathrm{\ell },1,n})=\mathrm{\ell }+n-1$ given $n\ge 2$. Determining the worst-case optimal makespan for $m\ge 2$ and $n\ge 2$ is non-trivial, and concerns the rest of this section.