* Kaplan et al. (2008) Kaplan, D. L., Chatterjee, S., Gaensler, B. M., & Anderson, J. 2008, ApJ, 677, 1201, doi: 10.1086/529026
  * Karuppusamy et al. (2010) Karuppusamy, R., Stappers, B. W., & van Straten, W. 2010, A&A, 515, A36, doi: 10.1051/0004-6361/200913729
  * Keimpema et al. (2015) Keimpema, A., Kettenis, M. M., Pogrebenko, S. V., et al. 2015, Experimental Astronomy, 39, 259, doi: 10.1007/s10686-015-9446-1
  * Lawrence et al. (1995) Lawrence, S. S., MacAlpine, G. M., Uomoto, A., et al. 1995, AJ, 109, 2635, doi: 10.1086/117477
  * Loken et al. (2010) Loken, C., Gruner, D., Groer, L., et al. 2010, Journal of Physics: Conference Series, 256, 012026, doi: 10.1088/1742-6596/256/1/012026
  * Losovsky et al. (2019) Losovsky, B. Y., Dumsky, D. V., & Belyatsky, Y. A. 2019, Astronomy Reports, 63, 830, doi: 10.1134/S1063772919090051
  * Lyne et al. (1993) Lyne, A. G., Pritchard, R. S., & Graham Smith, F. 1993, MNRAS, 265, 1003, doi: 10.1093/mnras/265.4.1003
  * Lyne et al. (2001) Lyne, A. G., Pritchard, R. S., & Graham-Smith, F. 2001, MNRAS, 321, 67, doi: 10.1046/j.1365-8711.2001.03998.x
  * Lyubarskii (1996) Lyubarskii, Y. E. 1996, A&A, 311, 172
  * Lyutikov (2021) Lyutikov, M. 2021, The Astrophysical Journal, 922, 166, doi: 10.3847/1538-4357/ac1b32
  * Mahajan & Lin (2022) Mahajan, N., & Lin, R. 2022, theXYZT/pulsarbat: pulsarbat 0.0.8, v0.0.7, Zenodo, doi: 10.5281/zenodo.6934355
  * Main et al. (2021) Main, R., Lin, R., van Kerkwijk, M. H., et al. 2021, ApJ, 915, 65, doi: 10.3847/1538-4357/ac01c6
  * Martin et al. (2021) Martin, T., Milisavljevic, D., & Drissen, L. 2021, MNRAS, 502, 1864, doi: 10.1093/mnras/staa4046
  * McKee et al. (2018) McKee, J. W., Lyne, A. G., Stappers, B. W., Bassa, C. G., & Jordan, C. A. 2018, MNRAS, 479, 4216, doi: 10.1093/mnras/sty1727
  * Michilli et al. (2018) Michilli, D., Seymour, A., Hessels, J. W. T., et al. 2018, Nature, 553, 182, doi: 10.1038/nature25149
  * Moffett & Hankins (1996) Moffett, D. A., & Hankins, T. H. 1996, ApJ, 468, 779, doi: 10.1086/177734
  * Muslimov & Harding (2004) Muslimov, A. G., & Harding, A. K. 2004, The Astrophysical Journal, 617, 471, doi: 10.1086/425227
  * Nimmo et al. (2021) Nimmo, K., Hessels, J. W. T., Keimpema, A., et al. 2021, Nature Astronomy, 5, 594, doi: 10.1038/s41550-021-01321-3
  * Nimmo et al. (2022) Nimmo, K., Hessels, J. W. T., Kirsten, F., et al. 2022, Nature Astronomy, 6, 393, doi: 10.1038/s41550-021-01569-9
  * Osterbrock (1957) Osterbrock, D. E. 1957, PASP, 69, 227, doi: 10.1086/127053
  * Pen et al. (2014) Pen, U. L., Macquart, J. P., Deller, A. T., & Brisken, W. 2014, MNRAS, 440, L36, doi: 10.1093/mnrasl/slu010
  * Petroff et al. (2022) Petroff, E., Hessels, J. W. T., & Lorimer, D. R. 2022, A&A Rev., 30, 2, doi: 10.1007/s00159-022-00139-w
  * Philippov et al. (2019) Philippov, A., Uzdensky, D. A., Spitkovsky, A., & Cerutti, B. 2019, ApJ, 876, L6, doi: 10.3847/2041-8213/ab1590
  * Ponce et al. (2019) Ponce, M., van Zon, R., Northrup, S., et al. 2019, CoRR, abs/1907.13600.  https://arxiv.org/abs/1907.13600
  * Rankin & Counselman (1973) Rankin, J. M., & Counselman, C. C., I. I. I. 1973, ApJ, 181, 875, doi: 10.1086/152099
  * Rickett (1990) Rickett, B. J. 1990, ARA&A, 28, 561, doi: 10.1146/annurev.aa.28.090190.003021
  * Romani & Yadigaroglu (1995) Romani, R. W., & Yadigaroglu, I. A. 1995, ApJ, 438, 314, doi: 10.1086/175076
  * Rudnitskii et al. (2016) Rudnitskii, A. G., Karuppusamy, R., Popov, M. V., & Soglasnov, V. A. 2016, Astronomy Reports, 60, 211, doi: 10.1134/S1063772916020116
  * Ryan & Vandenberg (1980) Ryan, J. W., & Vandenberg, N. R. 1980, in Bulletin of the American Astronomical Society, Vol. 12, 457.  https://ui.adsabs.harvard.edu/abs/1980BAAS...12..457R
  * Sallmen et al. (1999) Sallmen, S., Backer, D. C., Hankins, T. H., Moffett, D., & Lundgren, S. 1999, ApJ, 517, 460, doi: 10.1086/307183
  * Shearer et al. (2003) Shearer, A., Stappers, B., O’Connor, P., et al. 2003, Science, 301, 493, doi: 10.1126/science.1084919
  * Shearer et al. (2012) Shearer, A., Collins, S., Naletto, G., et al. 2012, in Astronomical Society of the Pacific Conference Series, Vol. 466, Electromagnetic Radiation from Pulsars and Magnetars, ed. W. Lewandowski, O. Maron, & J. Kijak, 11.  https://ui.adsabs.harvard.edu/abs/2012ASPC..466...11S
  * Smirnova et al. (1996) Smirnova, T. V., Shishov, V. I., & Malofeev, V. M. 1996, in Astronomical Society of the Pacific Conference Series, Vol. 105, IAU Colloq. 160: Pulsars: Problems and Progress, ed. S. Johnston, M. A. Walker, & M. Bailes, 475\.  https://ui.adsabs.harvard.edu/abs/1996ASPC..105..475S
  * Smits et al. (2017) Smits, R., Bassa, C. G., Janssen, G. H., et al. 2017, Astronomy and Computing, 19, 66, doi: 10.1016/j.ascom.2017.02.002
  * Sobey et al. (2019) Sobey, C., Bilous, A. V., Grießmeier, J. M., et al. 2019, MNRAS, 484, 3646, doi: 10.1093/mnras/stz214
  * Spitler et al. (2016) Spitler, L. G., Scholz, P., Hessels, J. W. T., et al. 2016, Nature, 531, 202, doi: 10.1038/nature17168
  * Staelin & Reifenstein (1968) Staelin, D. H., & Reifenstein, Edward C., I. I. I. 1968, Science, 162, 1481, doi: 10.1126/science.162.3861.1481
  * Thompson et al. (2017) Thompson, A. R., Moran, J. M., & Swenson, George W., J. 2017, Interferometry and Synthesis in Radio Astronomy, 3rd Edition (Springer), doi: 10.1007/978-3-319-44431-4
  * Trimble (1968) Trimble, V. 1968, AJ, 73, 535, doi: 10.1086/110658
  * Trimble (1973) —. 1973, PASP, 85, 579, doi: 10.1086/129507
  * Van Kerkwijk et al. (2020) Van Kerkwijk, M. H., Zhu, C. C., Guo, S. G., et al. 2020, mhvk/baseband, v4.0.3, Zenodo, doi: 10.5281/zenodo.4292543
  * van Straten et al. (2010) van Straten, W., Manchester, R. N., Johnston, S., & Reynolds, J. E. 2010, Publications of the Astronomical Society of Australia, 27, 104, doi: 10.1071/as09084
  * Vandenberg (1976) Vandenberg, N. R. 1976, ApJ, 209, 578, doi: 10.1086/154753
  * Wolszczan & Cordes (1987) Wolszczan, A., & Cordes, J. 1987, Astrophys. J., 320, L35, doi: 10.1086/184972
  * Yalinewich & Pen (2022) Yalinewich, A., & Pen, U.-L. 2022, MNRAS, 515, 5682, doi: 10.1093/mnras/stac2087


# A Note on Squares in Binary Words

Tero Harju
Department of Mathematics and Statistics
University of Turku, Finland
<EMAIL_ADDRESS>

###### Abstract

We consider words over a binary alphabet. A word $w$ is overlap-free if it
does not have factors (blocks of consecutive letters) of the form $uvuvu$ for
nonempty $u$. Let $M(w)$ denote the number of positions that are middle
positions of squares in $w$. We show that for overlap-free binary words,
$2M(w)\leq|w|+3$, and that there are infinitely many overlap-free binary words
for which $2M(w)=|w|+3$.

Keywords. Overlap-free words, squares, centre of a square, binary words.

##  1 Introduction

Overlap-free words were first studied by Axel Thue in two papers [5, 6] in
1906 and 1912. In particular he proved that there are infinite overlap-free
binary words.

In the following we consider binary words, and choose the alphabet
$\Sigma=\\{0,1\\}$ for these words. An _overlap_ is a word of the form $uvuvu$
where $u$ is nonempty. A word $w$ is said to be _overlap-free_ if it has no
overlaps as factors, i.e., consecutive blocks of letters. Equally well, we can
presume in the definition that $x$ is a letter. The most well known overlap-
free words are the factors of the infinite _Thue-Morse word_ $\mathbf{t}$ that
is obtained by iterating the morphism $\mu\colon\Sigma^{*}\to\Sigma^{*}$ with

$\mu(0)=01\ \text{ and }\ \mu(1)=10$

on the initial word $0$. Therefore

$\mathbf{t}=011010011001011010010110\cdots$

The morphism $\mu$ preserves overlap-freeness, i.e., if $w$ is overlap-free,
then so is $\mu(w)$; see e.g. Chapter 2 of Lothaire [3] or Berstel and Séébold
[1].

Let $|w|$ denote the length of $w$. An integer $p$ with $1\leq p<|w|$ is a
_position_ in $w$. It denotes the place after the prefix of length $p$. A
nonempty word $u$ is a _square at position_ $p=|x|$ in $w=xy$ if there are,
possibly empty, words $x^{\prime}$ and $y^{\prime}$ such that $x=x^{\prime}u$
and $y=uy^{\prime}$. In this case we say that $p$ is a _centre of a square_.

Let $\varepsilon$ denote the empty word. If $w=xuy$ then $u$ is a  _factor_ of
$w$. It is a _prefix_ if $x=\varepsilon$, and a _suffix_ if $y=\varepsilon$.
The word $w$ is said to be _bordered_ if there exists a nonempty word $v$,
with $v\neq w$, that is both a prefix and a suffix of $w$. For a word $w=uv$,
we denote by $u=wv^{-1}$ the prefix of $w$ when the suffix $v$ is deleted.

##  2 On the maximum number of centres

We consider the number of centres of squares in binary words. We follow Harju
and Kärki [2], and define

$M(w)=\\#\\{p\mid\text{$p$ is a centre of a square in $w$}\\}.$

In [2] the authors count ‘frames’, i.e., unbordered squares. The number of
these equals $M(w)$ since if $uu$ is a square at position $p$ then for the
border $v$ of $u$ of minimal length also $vv$ is a square at $p$.

In the general binary case the paper [2, Theorem 4] gives the minimum number
of centres of squares:

######  Theorem 1.

For binary words of length $n\geq 3$,

$\min_{|w|=n}M(w)=\left\lceil\frac{n}{2}\right\rceil-2.$

The problem for $\max_{|w|=n}M(w)$ is trivial. Indeed, the unary word $0^{n}$
has a square at every position, i.e., $M(0^{n})=n-1$. On the other hand, in
the ternary case, i.e., words over a three letter alphabet, the minimum is
zero since there are (infinite) square-free words in this case. Here we shall
consider the maximum problem for the binary overlap-free words.

The next technical lemma will be used for short prefixes $x$ in the proof of
Theorem 5.

######  Lemma 2.

Let $s$ be the longest common suffix of the binary words $x$ and $w$. Assume
that $xw$ and $ww$ are overlap-free. Then $xw(ws^{-1})$ is overlap-free.

###### Proof.

Assume that there is a square $xuxu$ as a prefix of $xww$ such that
$|uxu|\geq|w|$. Then $u$ is a prefix $w$, i.e., $w=uy=vt$ for $y$ and $t$ with
$xu=yv$; see Fig. 1.

The word $u$ is a suffix of $yv\ (=xu)$ and a prefix of $w=vt\ (=uy)$. The
occurrences of $u$ cannot overlap in the overlap-free $ww$. Therefore either
(1) $u=v$ or (2) $v=uzu$ for some $z$.

(1) Suppose first that $u=v$ and thus that $y=x$ and $t=x$. Then $x$ is a
suffix of the common suffix $s$ and $xw(wx^{-1})=xuxu$. Therefore $xuxu$ does
not extend to an overlapping factor $xuxua$ of $xw(ws^{-1})$.

(2) Assume then that $v=uzu$ and hence that $y=zut$ and $w=uzut$. Then
$xu=yv=zutuzu$, and finally, $xw=xuy=zutuzuzut$ which contains an overlap
$uzuzu$ (since $u\neq\varepsilon$); a contradiction with the overlap-freeness
of $xw$. ∎

$w$$w$$x$$u$$y$$v=uzu$$t$ Figure 1: Overlapping factor: $xu=yv$.

In particular, if in the above $s=\varepsilon$ and $xw$ and $ww$ are overlap-
free then also $xww$ is overlap-free.

The next lemma was proved in [2, Lemma 10]. We note that in the Thue-Morse
word $\mathbf{t}$ there are no consecutive centres of squares. This can be
seen by looking at the short factors of $\mathbf{t}$. Indeed, the unbordered
squares in $\mathbf{t}$ are of the form $uu$ for $u\in\\{0,1,01,10\\}$; see
Pansiot [4].

######  Lemma 3.

Let $w$ be a factor of even length $n\geq 4$ of the Thue-Morse word starting
at an even position. Then all squares are at even positions, and hence
$M(w)=n/2-1$.

We show in the next thorem that if an overlap-free word satisfies the
maximality condition $2M(w)=|w|+3$ then $w$ has the form $w=auu$ (or
symmetrically $uua$). In Theorem 5 we then construct overlap-free words for
which $M(w)$ reaches the upper bound.

We call the words $001001$ and $110110$ _prefix special_ and their reversed
words $100100$ and $011011$ _suffix special_. These special words can occur
only as a prefix (resp., suffix) of an overlap-free word since they cannot be
extended to the left (resp., right) without violating overlap-freeness.

######  Theorem 4.

For overlap-free binary words $w$, we have
$M(w)\leq\left\lceil\frac{|w|}{2}\right\rceil+1$, i.e.,

$2M(w)\leq|w|+3\,.$ (1)

###### Proof.

A word of length $n$ has $n-1$ positions of which $\left[n/2\right]$ are odd
positions and $\left[n/2\right]-1$ or $\left[n/2\right]$ even positions
depending if $n$ is even or odd. For the bound (1) we look for the positions
where the consecutive positions $p$ and $p+1$ are centres of squares.

Let $|w|=n$. If $w$ has a special prefix $001001$ or $110110$ then the
positions $3$ and $4$ are centres of squares. Similarly if $w$ has a suffix
$100100$ or $011011$ then the positions $n-4$ and $n-3$ are centres of
squares.

Suppose then that $5\leq p\leq n-5$, and assume that there are minimal length,
and thus unbordered, squares $u$ and $v$ at positions $p$ and $p+1$. By
appealing to symmetry, we can assume that $|u|\geq|v|$. To avoid the overlap
$ccc$ (with $c\in\\{0,1\\}$) that happens when $|u|=1=|v|$, necessarily
$u=au^{\prime}b$ for different letters $a,b$. Also, $|u|\geq 3$ since if
$u=ab$ then $uu=abab$ yields that $v=ba$ and there is an overlap $ababa$ in
$w$.

(A) Assume first that $uu$ is not a prefix of $w$.

Claim 1. The square $uu$ is a suffix of $w$.

Indeed, $\beta=auu$ is a factor of $w$ since $buu$ would be an overlapping
factor. Hence $ab$ is a prefix of $u$.

If $u=abb$ then $\beta=aabbabb$ ends in a special word. In this case there
does not exist a square at $p+1$. (There is one at $p-1$.) Therefore $|u|\geq
4$.

In order for $u$ to avoid $ab$ as a border, $bb$ must be a suffix of $u$.
Hence $\beta=a(abxabb)(abxabb)$ for some $x$. It follows that $\beta$ is a
suffix of $w$ since $\beta a$ and $\beta b$ have overlapping factors,
$(abxabb)(abxabb)a$ and $bbb$, respectively. This proves Claim 1.

Claim 2. $w=\beta$ .

We have $x\neq\varepsilon$ since if $x=\varepsilon$, then $\beta=aababbababb$
has an overlapping factor $babab$. Then $x$ has a prefix $a$ in order for $u$
to avoid $abb$ as a border. So far we have $\beta=a(abayabb)(abayabb)$. In
particular, $vv=baba$ is the minimal square at $p+1$. Now, either
$y=\varepsilon$ or, in order to avoid the factor $babab$, $ab$ is a prefix of
$y$, i.e., $\beta=a(abaabzabb)(abaabzabb)$ for a word $z$. In both cases, the
prefix is $aabaab$ that can occur only at the beginning of $w$. Hence
$\beta=w$, and therefore

$w=auu=a(abaabzabb)(abaabzabb)\,.$

Let $|u|=2k$ or $|u|=2k+1$.

The positions $1$ and $2$ of $u$ are not centres of squares in $u$, and hence,
by itself, $u$ can have at most $k-1$ odd or even centres of squares. However,
the position $3$ of $w$ is a centre of $aabaab$ and the position $p+1$ of $w$
is centre of $vv$. Together with the centres of $uu$ and $aa$, we have
$M(w)\leq 2k+2$, and so $2M(w)\leq|w|+3$ where $|w|=4k+1$.

(B) The case where $uu$ is not a suffix of $w$ is symmetric to the case (A).
In this case, $w$ has the form $uua$.

(C) If $w=uu$ then $w$ cannot have special words in the prefix or in the
suffix. Hence $M(w)\leq|w|/2+1$, i.e., $2M(w)\leq|w|+2$.

Finally, suppose that $w$ does not have centres of squares $p$ for $5\leq
p\leq|w|-5$. Then the consecutive centres of squares are in the special words.
E.g., by considering a possible factorisation $w=(00100)11x00(11011)$ with
special words at the ends, we obtain $M(w)\leq(|w|-10)/2+6=|w|/2+1$, and so
$2M(w)\leq|w|+2$. ∎

By the proof of Theorem 4, the bound $\left\lceil\frac{|w|}{2}\right\rceil+1$
can be obtained only by overlap-free words of odd length.

######  Theorem 5.

There are infinitely many overlap-free binary words $w$ such that

$M(w)=\left\lceil\frac{|w|}{2}\right\rceil+1.$

###### Proof.

The the upper bound for $M(w)$ is given in Lemma 4. For equality we rely on
the factors of the Thue-Morse word $\mathbf{t}$. Let $\alpha_{n}$ denote the
factor of $\mathbf{t}$ of length $3{\cdot}2^{n}$ that starts at position 5,
e.g.,

$\alpha_{1}=100110,\ \text{ and }\ \alpha_{2}=100110010110\,.$

Then $|\mu(\alpha_{n})|=2|\alpha_{n}|=|\alpha_{n+1}|$, and
$\mu(\alpha_{n})=1001{\cdot}0110\cdots 0110{\cdot}1001$, where
$\mu(\alpha_{n})$ starts after $\mu(0110)$ at position 9 of $\mathbf{t}$.
Hence $\alpha_{n+1}=1001{\cdot}1001\cdots 0110$ is a conjugate of
$\mu(\alpha_{n})$. In particular, as a factor of $\mathbf{t}$,
$1001\mu(\alpha_{n})$ is overlap-free for all $n$.

We show inductively that $\alpha_{n}\alpha_{n}$ is overlap-free for all $n$.
To begin with $\alpha_{1}\alpha_{1}=100110100110$ is overlap-free. For $n\geq
1$, we have

$\displaystyle\alpha_{n+1}\alpha_{n+1}$
$\displaystyle=1001\,\mu(\alpha_{n})(1001)^{-1}(1001)\,\mu(\alpha_{n})(1001)^{-1}$
$\displaystyle=1001\,\mu(\alpha_{n})\mu(\alpha_{n})(1001)^{-1}$
$\displaystyle=1001\,\mu(\alpha_{n}\alpha_{n})(1001)^{-1}\,,$

where $1001\,\mu(\alpha_{n})$ is overlap-free and, by the induction
hypothesis, so is $\mu(\alpha_{n})\mu(\alpha_{n})$ since $\mu$ preserves
overlap-freeness. Lemma 2 applied to $1001\,\mu(\alpha_{n}\alpha_{n})$ gives
that $1001\,\mu(\alpha_{n}\alpha_{n})(1001)^{-1}$ is overlap-free. Therefore
$\alpha_{n+1}\alpha_{n+1}$ is overlap-free.

Denote by $\overline{\alpha}$ the prefix of $\alpha$ of length $|\alpha|-1$,
i.e., truncate the last letter of $\alpha$. Let

$w_{n}=00\alpha_{n}\overline{\alpha}_{n}=0(0\overline{\alpha}_{n})(0\overline{\alpha}_{n})$

By Lemma 2, $0\alpha_{n}\overline{\alpha}_{n}$ is overlap-free. Also,
$00\alpha_{n}\overline{\alpha}_{n}$ has a special prefix $001001$, and hence
$w_{n}$ is overlap-free.

By Lemma 3, $M(\alpha_{n}\alpha_{n})=(2|\alpha_{n}|/2-1)+1=|\alpha_{n}|-1$
where the $+1$ comes from the middle position. The centres of squares have
even positions in $\alpha_{n}\alpha_{n}$. Therefore also
$M(\alpha_{n}\overline{\alpha}_{n})=|\alpha_{n}|-1$. The squares $001001$ and
$00$ are at the consecutive positions $3$ and $4$ of $w_{n}$, and in the
middle portion we have $(0\overline{\alpha}_{n})(0\overline{\alpha}_{n})$ next
to the squares $00$ and $1010$ (of even positions). Since
$|w_{n}|=2|\alpha_{n}|+1$, we have

$M(w_{n})=|\alpha_{n}|-1+3\ \text{ and so }\ 2M(w_{n})=|w_{n}|+3$

as required. ∎

## References

  * [1] J. Berstel and P. Séébold.  A characterization of overlap-free morphisms.  Discrete Appl. Math., 46(3):275–281, 1993.
  * [2] T. Harju and T. Kärki.  On the number of frames in binary words.  Theor. Comput. Sci., 412(39):5276–5284, 2011.
  * [3] M. Lothaire.  Combinatorics on Words, volume 17 of Encyclopedia of Mathematics.  Addison-Wesley, Reading, Massachusetts, 1983.
  * [4] J. J. Pansiot.  The Morse sequence and iterated morphisms.  Inf. Process. Lett., 12:68–70, 1981.
  * [5] A. Thue.  Über unendliche Zeichenreihen.  Norske Vid. Selsk. Skr., I Mat.-nat. Kl. Christiania, 7:1–22, 1906\.
  * [6] A. Thue.  Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen.  Norske Vid. Selsk. Skr., I Mat.-nat. Kl. Christiania, 1:1–67, 1912\.


The configuration of the SUT must be reported to include the following:

  1. 1.

The used LDBC specification, driver and data generator version.

  2. 2.

Complete configuration files of the DBMS, including any general server
configuration files, any configuration scripts run on the DBMS for setting up
the benchmark run etc.

  3. 3.

Complete schema of the DBMS, including eventual specification of storage
layout.

  4. 4.

Any OS configuration parameters if other than default, `vm.swappiness`,
`vm.max_map_count` in Linux.

  5. 5.

Complete source code of any server-side logic, stored procedures, triggers.

  6. 6.

Complete source code of driver-side benchmark implementation.

  7. 7.

Description of the benchmark environment, including software versions, OS
kernel version, DBMS version as well as versions of other major software
components used for running the benchmark (Docker, Java Virtual Machine,
Python, etc.).

  8. 8.

The SUT’s highest configurable isolation level and the isolation level used
for running the benchmark.

#####  8.3.6.4 Audit of System Configuration

The auditor must ascertain that a reported run has indeed taken place on the
SUT in the disclosed configuration. The full disclosure shall contain any
relevant parameters of the benchmark execution itself, including:

  1. 1.

Parameters, switches, configuration file for data generation.

  2. 2.

Complete text of any data loading script or program.

  3. 3.

Parameters, switches, configuration files for any test driver. If the test
driver is not an LDBC supplied open source package or is a modification of
such, then the complete text or diff against a specific LDBC package must be
disclosed.

  4. 4.

Test driver output files shall be part of the disclosure. In general, these
must at least detail the following:

    1. i)

Time and duration of data load and the timed portion of the benchmark
execution.

    2. ii)

Count of each workload item (query, transaction) successfully executed within
the measurement window.

    3. iii)

Min/average/max execution time of each workload item, the specific benchmark
shall specify additional details.

Given this information, the number of concurrent database sessions at each
point in the execution must be clearly stated. In the case of a cluster
database, the possible spreading of connections across multiple server
processes must be disclosed.

All parameters included in this section must be reported in the full
disclosure report to guarantee that the benchmark run can be reproduced
exactly in the future. Similarly, the test sponsor will inform the auditor of
the scale factor to test. Finally, a clean test system with enough space to
store the initial data set, the update streams, substitution parameters and
anything that is part of the input and output as well as the benchmark run
must be provided.

####  8.3.7 Benchmark Specifics

Similarly to TPC benchmarks, the LDBC benchmarks prohibit so-called benchmark
specials (extra software modules implemented in the core DBMS logic just to
make a selected benchmark run faster are disallowed). Furthermore, upon
request of the auditor, the test sponsor must provide all the source codes
relevant to the benchmark.

###  8.4 Auditing Rules for the Transaction Workload

This section specifies a checklist (in the form of individual sections) that a
benchmark audit shall cover in case of the FinBench Transaction workload. An
overview of the benchmark audit workflow is shown in Figure 8.1. The three
major phases of the audit are preparing the input data and validation query
results (captured by _Preparations_ in the figure), validating the correctness
of query results returned by the SUT using the validation scale factor and
running the benchmark with all the prescribed workloads (_Benchmarking_), and
creating the FDR (_Finalization_). The color codes capture the
responsibilities of performing a step or providing some data in the workflow.

Figure 8.1: Benchmark execution and auditing workflow. For non-audited runs,
the implementers perform the steps of the auditor.

A key objective of the auditing guidelines for the Transaction workload is to
_allow a broad range of systems_ to implement the benchmark. Therefore, they
do not impose constraints on the data model (graph, relational, triple,
representations are allowed) or on the query language (both declarative and
imperative languages are allowed).

####  8.4.1 Scaling Factors

The scale factor of a FinBench data set is the size of the data set in GiB of
CSV (comma-separated values) files. The size of a data set is characterized by
scale factors: SF0.1, SF1, SF3 (see Section 3.4.2). All data sets contain data
for three years of financial activities.

The _validation run_ shall be performed on the SF1 data set (see Section
8.4.6.1). Note that the auditor may perform additional validation runs of the
benchmark implementation using smaller data sets (SF1) and issue queries.

Audited _benchmark runs_ of the Transaction workload shall use SF10. The
rationale behind this decision is to ensure that there is a sufficient number
of update operations available to guarantee 2.5 hours of continuous execution
(see Section 8.4.7.2).

####  8.4.2 Data Model

FinBench may be implemented with different data models (relational, RDF, and
different graph data models). The reference schema is provided in the
specification using a UML-like notation.

####  8.4.3 Precomputation

Precomputation of query results (both interim and end results) is allowed.
However, systems must ensure that precomputed results (materialized views) are
kept consistent upon updates.

####  8.4.4 Benchmark Software Components

LDBC provides a test driver, data generator, and summary reporting scripts.
Benchmark implementations shall use a stable version of the test driver. The
SUT’s database software should be a stable version that is available publicly
or can be purchased at the time of the release of the audit. Please see
Section 1.4 for more details.

#####  8.4.4.1 Adaptation of the Test Driver to a DBMS

A qualifying run must use a test driver that adapts the provided test driver
to interface with the SUT. Such an implementation, if needed, must be provided
by the test sponsor. The parameter generation, result recording, and workload
scheduling parts of the test driver should not be changed. The auditor must be
given access to the test driver source code used in the reported run.

The test driver produces the following artifacts for each execution as a by-
product of the run: Start and end timestamps in wall clock time, recorded with
microsecond precision. The identifier of the operation and any substitution
parameters.

#####  8.4.4.2 Summary of Benchmark Results

A separate test summary tool provided with the test driver analyses the test
driver log(s) after a measurement window is completed.

The tool produces for each of the distinct queries and transactions the
following summary:

  * •

Run time of query in wall clock time.

  * •

Count of executions.

  * •

Minimum/mean/percentiles/maximum execution time.

  * •

Standard deviation from the average execution time.

The tool produces for the complete run the following summary:

  * •

Operations per second for a given SF (throughput). This is the primary metric
of this workload.

  * •

The total execution time in wall clock time.

  * •

The total number of completed operations.

####  8.4.5 Implementation Language and Data Access Transparency

The queries and updates may be implemented in a domain-specific query language
or as procedural code written in a general-purpose programming language (using
the API of the database).

#####  8.4.5.1 Implementations Using a Domain-Specific Query Language

If a domain-specific query language is used, SPARQL, SQL, Cypher, or Gremlin,
then explicit query plans are prohibited in all read-only queries.111If the
queries are not declarative clearly, the auditor must ensure that they do not
specify explicit query plans by investigating their source code and
experimenting with the query planner of the system (using SQL’s EXPLAIN
command). The update transactions may still consist of multiple statements,
effectively amounting to explicit plans.

Explicit query plans include but are not limited to:

  * •

Directives or hints specifying a join order or join type

  * •

Directives or hints specifying an access path, which index to use

  * •

Directives or hints specifying an expected cardinality, selectivity, fanout or
any other information that pertains to the expected number of results or cost
of all or part of the query.

> _Rationale behind the applied restrictions._ The updates are effectively
> OLTP and, therefore, the customary freedoms apply, including the use of
> stored procedures, however subject to access transparency. Declarative
> queries in a benchmark implementation should be such that they could
> plausibly be written by an application developer. Therefore, their
> formulation should not contain system-specific aspects that an application
> developer would be unlikely to know. In other words, making a benchmark
> implementation should not require uncommon sophistication on behalf of the
> developer. This is a regular practice in analytical benchmarks, TPC-H.

#####  8.4.5.2 Implementations Using a General-Purpose Programming Language

Implementations using a general-purpose programming language for specifying
the queries (including procedural, imperative, and API-based implementations)
are expected to respect the rules described in Section 8.3.4. For these
implementations, the rules in Section 8.4.5.1 do not apply.

####  8.4.6 Correctness of Benchmark Implementation

#####  8.4.6.1 Validation data set

The scale factor 1 shall be used as a validation data set.

#####  8.4.6.2 ACID Compliance

The Transaction workload requires full ACID support (Section 8.3.2) from the
SUT. This is tested using the LDBC ACID test suite. For the specification of
this test suite, see Chapter 7 and the related software repository at
https://github.com/ldbc/ldbc_finbench_acid.

###### Expected level of isolation

If a transaction reads the database with the intent to update, the DBMS must
guarantee no dirty reads. In other words, this corresponds to read committed
isolation.

###### Durability and checkpoints

A checkpoint is defined as the operation which causes data persisted in a
transaction log to become durable outside the transaction log. Specifically,
this means that A SUT restart after instantaneous failure following the
completion of the checkpoint may not have recourse to transaction log entries
written before the end of the checkpoint.

A checkpoint typically involves a synchronization barrier at which all data
committed before the moment is required to be in durable storage that does not
depend on the transaction log. Not all DBMSs use a checkpoint mechanism for
durability. For example, a system may rely on redundant storage of data for
durability guarantees against the instantaneous failure of a single server.

The measurement window may contain a checkpoint. If the measurement window
does not contain one, then the restart test will involve redoing all the
updates in the window as part of the recovery test.

The timed window ends with an instantaneous failure of the SUT.
Instantaneously killing all the SUT process(es) is adequate for simulating
instantaneous failure. All these processes should be killed within one second
of each other with an operating system action equivalent to the Unix `kill
-9`. If such is not available, then powering down each separate SUT component
that has an independent power supply is also possible.

The restart test consists of restarting the SUT process(es) and finishes when
the SUT is back online with all its functionality and the last successful
update logged by the driver can be seen to be in effect in the database.

If the SUT hardware was powered down, the recovery period does not include the
reboot and possible file system check time. The recovery time starts when the
DBMS software is restarted.

###### Recovery

The SUT is to be restarted after the measurement window and the auditor will
verify that the SUT contains the entirety of the last update recorded by the
test driver(s) as successfully committed. The driver or the implementation has
to make this information available. The auditor may also check the _audit log_
of the SUT (if available) to confirm that the operations issued by the driver
were saved.

Once an official run has been validated, the recovery capabilities of the
system must be tested. The system and the driver must be configured in the
same way as in during the benchmark execution. After a warm-up period,
execution of the benchmark will be performed under the same terms as in the
previous measured run.

###### Measuring recovery time

At an arbitrary point close to 2 hours of wall clock time during the run, the
machine will be shut down. Then, the auditor will restart the database system
and will check that the last committed update (in the driver log file) is
actually in the database. The auditor will measure the time taken by the
system to recover from the failure. Also, all the information about how
durability is ensured must be disclosed. If checkpoints are used, these must
be performed for a period of 10 minutes at most.

####  8.4.7 Benchmarking Workflow

A benchmark execution is divided into the following processes (these processes
are also shown in Figure 8.1):

Generate data

This includes running the data generator, placing the generated files in a
staging area, configuring storage, setting up the SUT configuration and
preparing any data partitions in the SUT. This may include preallocating
database space but may not include loading any data or defining any schema
having to do with the benchmark.

Preprocessing

If needed, the output from the data generator is to preprocess the data set
(Section 8.3.3).

Create validation data

Using one of the reference implementations of the benchmark, the reference
validation data is obtained in JSON format.

Data loading

The test sponsor must provide all the necessary documentation and scripts to
load the data set into the database to test. This includes defining the
database schema, if any, loading the initial database population, making this
durably stored and gathering any optimizer statistics. The system under test
must support the different data types needed by the benchmark for each of the
attributes at their specified precision. No data can be filtered out,
everything must be loaded. The test sponsor must provide a tool to perform
arbitrary checks of the data or a shell to issue queries in a declarative
language if the system supports it.

Run cross-validation

This step uses the data loader to populate the database, but the load is not
timed. The validation data set is used to verify the correctness of the SUT.
The auditor must load the provided data set and run the driver in validation
mode, which will test that the queries provide the official results. The
benchmarking workflow will not go beyond this point unless the results match
the expected output.

Warm-up

Benchmark runs are preceded by a warm-up which must be performed using the
LDBC driver.

Run benchmark

The bulk load time is reported and is equal to the amount of elapsed wall
clock time between starting the schema definition and receiving the
confirmation message of the end of statistics gathering. The workflow runs
begin after the bulk load is completed. If the run does not directly follow
the bulk load, it must start at a point in the update stream that has not
previously been played into the database. In other words, a run may only
include update events whose timestamp is later than the latest message
creation date in the database before the start of the run. The run starts when
the first of the test drivers sends its first message to the SUT. If the SUT
is running in the same process as the driver, the window starts when the
driver starts. Also, make sure that the `-rl/--results_log` is enabled. Make
sure that all operations are enabled, and the frequencies are those for the
selected scale factor (see the exact specification of the frequencies in
Appendix B).

#####  8.4.7.1 Query Timing During Benchmark Run

A valid benchmark run must last at least 2 hours of wall clock time and at
most 2 hours and 15 minutes. In order to be valid, a benchmark run needs to
meet the “95% on-time requirement”. The results_log.csv file contains the
$\mathsf{actual\\_start\\_time}$ and the $\mathsf{scheduled\\_start\\_time}$
of each of the issued queries. To have a valid run, 95% of the queries must
meet the following condition:

$\mathsf{actual\\_start\\_time}-\mathsf{scheduled\\_start\\_time}<1\
\mathrm{second}$

If the execution of the benchmark is valid, the auditor must retrieve all the
files from the directory specified by `--results_dir` which includes
configuration settings used, results log and results summary. All of which
must be disclosed.

#####  8.4.7.2 Measurement Window

Benchmark runs execute the workload on the SUT in two phases (Figure 8.2).
First, the SUT must undergo a warm-up period that takes at least 30 minutes
and at most 35 minutes. The goal of this is to put the system in a steady
state which reflects how it would behave in a normal operating environment.
The performance of the operations during warm-up is not considered. Next, the
SUT is benchmarked during a two-hour measurement window. Operation times are
recorded and checked to ensure the “95% on-time requirement” is satisfied.

Figure 8.2: Warm-up and measurement window for the benchmark run.

The FinBench DataGen produces 3 years worth data of which 3% is used for
updates (LABEL:sec:transaction-workload-data-sets), approximately $3\times
365\times 0.03=32.85~{}\text{days}=788.4~{}\text{hours}$. To ensure that the
2.5 hours wall clock period has enough input data, the lower bound of TCR is
defined as 0.001 (if $2628$ hours of updates are played back at more than
$1000\times$ speed, the benchmark framework runs out of updates to execute). A
system that can achieve a better compression (lower TCR value) on a given
scale factor should use larger SFs for their benchmark runs – otherwise their
total runs will be less than 2.5 hours, making them unsuitable for auditing.

####  8.4.8 Full Disclosure Report

Upon successful completion of the audit, an FDR is compiled. In addition to
the general requirements, the full disclosure shall cover the following:

  * •

General terms: an executive summary and declaration of the credibility of the
audit

  * •

Conflict of Interest Statement between the auditor and the test sponsor, if
needed.

  * •

System description and pricing summary

  * •

Data generation and data loading

  * •

Test driver details

  * •

Performance metrics

  * •

Validation results

  * •

ACID compliance

  * •

List of supplementary materials

To ensure the reproducibility of the audited results, a supplementary package
is attached to the full disclosure report. This package should contain:

  * •

A README file with instructions specifying how to set up the system and run
the benchmark

  * •

Configuration files of the database, including database-level configuration
such as buffer size and schema descriptors (if necessary)

  * •

Source code or binary of a generic driver that can be used to interact with
the DBMS

  * •

SUT-specific LDBC driver implementation (similarly to the projects in
https://github.com/ldbc/ldbc_finbench_transaction_impls)

  * •

Script or instructions to compile the LDBC Java driver implementation

  * •

Instructions on how to reach the server through CLI and/or web UI (if
applicable), the URL (including port number), username and password

  * •

LDBC configuration files (.properties), including the time_compression_ratio
values used in the audited runs

  * •

Scripts to preprocess the input files (if necessary) and to load the data sets
into the database

  * •

Scripts to create validation data sets and to run the benchmark

  * •

The implementations of the queries and the update operations, including their
complete source code (declarative queries specifications, stored procedures, )

  * •

Implementation of the ACID test suite

  * •

Binary package of the DBMS (.deb or .rpm)

##  Chapter 9 Related Work

> A detailed list of LDBC publications is curated at
> https://ldbcouncil.org/publications.

LDBC FinBench is designed based on the LDBC SNB [1, 2] and introduces the new
features in financial scenarios.

##  Appendix A Choke Points

### Introduction

An interesting benchmark should be designed with representative read-world
scenarios and also chokepoints embedded in the deeper technical level.
Chokepoints capture particularly challenging aspects of queries. The
correlations between chokepoints and read queries are displayed in Table A.1.
To help understand the following chokepoints, there are some annotations.

  * •

The capital abbreviations are short for the aspects the chokepoints affect.

    * •

_QOPT_ : Those aimed at testing aspects of the query optimizer.

    * •

_QEXE_ : Those aimed at testing aspects of the execution engine.

    * •

_STORAGE_ : Those aimed at testing aspects of the storage system.

    * •

_LANG_ : Those aimed at testing aspects of the expression capability of DSL.

    * •

_UPD_ : Those aimed at testing aspects of the update operation performance.

  * •

The gray boxes in the top right corner annotate the source of the chokepoints.

    * •

_TPC-H_ means the chokepoint is from the paper _TPC-H Analyzed_ [17]. You can
refer to the paper for the chokepoint details.

    * •

_From SNB_ means the chokepoint refers to the ones in LDBC SNB [2].

    * •

_New in FinBench_ means the chokepoint is summarized newly from FinBench.

Table A.1: Coverage of choke points by queries.

###  A.1 Aggregation Performance

#### CP-1.1: [QOPT] Interesting orders TPC-H 1.2

This choke point tests the ability of the query optimizer to exploit the
interesting orders induced by some operators. Apart from clustered indices
providing key order, other operators also preserve or even induce tuple
orderings. Sort-based operators create new orderings, typically on the probe-
side of a hash join conserves its order, etc.

###### Queries

TCR 5

#### CP-1.2: [QEXE] High cardinality group-by performance TPC-H 1.1

This choke point tests the ability of the execution engine to parallelize
group-by operations with a large number of groups. Some queries require
performing large group-by operations. In such a case, if an aggregation
produces a significant number of groups, intra-query parallelization can be
exploited as each thread may make its own partial aggregation. Then, to
produce the result, these have to be re-aggregated. In order to avoid this,
the tuples entering the aggregation operator may be partitioned by a hash of
the grouping key and be sent to the appropriate partition. Each partition
would have its own thread so that only that thread would write the
aggregation, hence avoiding costly critical sections as well. A high
cardinality distinct modifier in a query is a special case of this choke
point. It is amenable to the same solution with intra-query parallelization
and partitioning as the group-by. We further note that scale-out systems have
an extra incentive for partitioning since this will distribute the CPU and
memory pressure over multiple machines, yielding better platform utilization
and scalability.

###### Queries

TCR 7

#### CP-1.3: [QOPT] Top-k pushdown From SNB

This choke point tests the ability of the query optimizer to perform
optimizations based on top-$k$ selections. Many times queries demand for
returning the top-$k$ elements based on some property. Engines can exploit
that once $k$ results are obtained, extra restrictions in a selection can be
added based on the properties of the $k$th element currently in the top-$k$,
being more restrictive as the query advances, instead of sorting all elements
and picking the highest $k$.

#### CP-1.4: [QEXE] Low cardinality group-by performance TPC-H 1.3

This choke point tests the ability to efficiently perform group-by evaluation
when only a very limited set of groups is available. This can require special
strategies for parallelization, pre-aggregation when possible. This case also
allows using special strategies for grouping like using array lookup if the
domain of keys is small.

###  A.2 Join Performance

#### CP-2.1: [QOPT] Rich join order optimization TPC-H 2.3

This choke point tests the ability of the query optimizer to find optimal join
orders. A graph can be traversed in different ways. In the relational model,
this is equivalent to different join orders. The execution time of these
orders may differ by orders of magnitude. Therefore, finding an efficient join
(traversal) order is important, which in general, requires enumeration of all
the possibilities. The enumeration is complicated by operators that are not
freely re-orderable like semi-, anti-, and outer-joins. Because of this
difficulty most join enumeration algorithms do not enumerate all possible
plans, and therefore can miss the optimal join order. Therefore, this choke
point tests the ability of the query optimizer to find optimal join
(traversal) orders.

#### CP-2.2: [QOPT] Late projection TPC-H 2.4

This choke point tests the ability of the query optimizer to delay the
projection of unneeded attributes until late in the execution. Queries where
certain columns are only needed late in the query. In such a situation, it is
better to omit them from initial table scans, as fetching them later by row-id
with a separate scan operator, which is joined to the intermediate query
result, can save temporal space, and therefore I/O. Late projection does have
a trade-off involving locality, since late in the plan the tuples may be in a
different order, and scattered I/O in terms of tuples/second is much more
expensive than sequential I/O. Late projection specifically makes sense in
queries where the late use of these columns happens at a moment where the
amount of tuples involved has been considerably reduced; for example after an
aggregation with only few unique group-by keys or a top-$k$ operator.

#### CP-2.3: [QOPT] Join type selection From SNB

This choke point tests the ability of the query optimizer to select the proper
join operator type, which implies accurate estimates of cardinalities.
Depending on the cardinalities of both sides of a join, a hash or an index-
based join operator is more appropriate. This is especially important with
column stores, where one usually has an index on everything. Deciding to use a
hash join requires a good estimation of cardinalities on both the probe and
build sides. In TPC-H, the use of hash join is almost a foregone conclusion in
many cases, since an implementation will usually not even define an index on
foreign key columns. There is a break even point between index and hash based
plans, depending on the cardinality on the probe and build sides.

#### CP-2.4: [QOPT] Sparse foreign key joins TPC-H 2.2

This choke point tests the performance of join operators when the join is
sparse. Sometimes joins involve relations where only a small percentage of
rows in one of the tables is required to satisfy a join. When tables are
larger, typical join methods can be sub-optimal. Partitioning the sparse
table, using Hash Clustered indices or implementing Bloom-filter tests inside
the join are techniques to improve the performance in such situations [18].

#### CP-2.5: [QEXE] Worst-case optimal joins From SNB

This choke point tests the query engine’s ability to use multi-way, worst-case
optimal joins to evaluate cyclic queries which are required to efficiently
compute some dense subgraphs such as the triangle, the 4-cycle, and the
diamond (4-cycle with a cross-edge). The absence of multi-way joins (in
systems which only support binary joins), implies that join performance will
be provably suboptimal for cyclic queries.

#### CP-2.6: [QEXE] Factorized query execution From SNB

Query results produced by many-to-many joins often have redundancies when
represented as tuples. Factorization [19] provides a more compact (relational)
representation by eliminating repetitions, while still allowing some
operations (aggregation) to be performed without flattening the relation.

###  A.3 Data Access Locality

#### CP-3.1: [QOPT] Detecting correlation TPC-H 3.3

This choke point tests the ability of the query optimizer to detect data
correlations and exploiting them. If a schema rewards creating clustered
indices, the question then is which of the date or data columns to use as key.
In fact it should not matter which column is used, as range-propagation
between correlated attributes of the same table is relatively easy. One way is
through the creation of multi-attribute histograms after detection of
attribute correlation. With MinMax indices, range-predicates on any column can
be translated into qualifying tuple position ranges. If an attribute value is
correlated with tuple position, this reduces the area to scan roughly equally
to predicate selectivity.

#### CP-3.2: [STORAGE] Dimensional clustering From SNB

This choke point tests suitability of the identifiers assigned to entities by
the storage system to better exploit data locality. A data model where each
entity has a unique synthetic identifier, RDF or graph models, has some choice
in assigning a value to this identifier. The properties of the entity being
identified may affect this, type (label), other dependent properties,
geographic location, date, position in a hierarchy, etc., depending on the
application. Such identifier choice may create locality which in turn improves
efficiency of compression or index access.

###### Queries

TCR 1 TCR 2 TCR 3 TCR 4 TCR 5 TCR 6 TCR 7 TCR 8 TCR 9 TCR 10 TCR 11 TCR 12

#### CP-3.3: [QEXE] Scattered index access patterns From SNB

This choke point tests the performance of indices when scattered accesses are
performed. The efficiency of index lookup is very different depending on the
locality of keys coming to the indexed access. Techniques like vectoring non-
local index accesses by simply missing the cache in parallel on multiple
lookups vectored on the same thread may have high impact. Also detecting
absence of locality should turn off any locality dependent optimizations if
these are costly when there is no locality. A graph neighborhood traversal is
an example of an operation with random access without predictable locality.

#### CP-3.4: [STORAGE] Temporal access locality and performance New in
FinBench

When filtering edge in navigational pattern on a high-degree vertex, the
performance of queries with temporal window filters can be improved when the
edges are sorted by timestamp in the embedded storage. This placement
optimizes the data access locality for timestamps avoiding scanning.

###### Queries

TCR 1 TCR 2 TCR 3 TCR 4 TCR 5 TCR 6 TCR 7 TCR 8 TCR 9 TCR 10 TCR 11 TCR 12

###  A.4 Expression Calculation

#### CP-4.1: [QOPT] Common subexpression elimination TPC-H 4.2a

This choke point tests the ability of the query optimizer to detect common
sub-expressions and reuse their results. A basic technique helpful in multiple
queries is common subexpression elimination (CSE). CSE should recognize also
that avg aggregates can be derived afterwards by dividing a sum by the count
when those have been computed.

#### CP-4.2: [QOPT] Complex boolean expression joins and selections TPC-H 4.2d

This choke point tests the ability of the query optimizer to reorder the
execution of boolean expressions to improve the performance. Some boolean
expressions are complex, with possibilities for alternative optimal evaluation
orders. For instance, the optimizer may reorder conjunctions to test first
those conditions with larger selectivity [20].

#### CP-4.3: [QEXE] Low overhead expressions interpretation From SNB

This choke point tests the ability of efficiently evaluating simple
expressions on a large number of values. A typical example could be simple
arithmetic expressions, mathematical functions like floor and absolute or date
functions like extracting a year.

###  A.5 Correlated Sub-Queries

#### CP-5.1: [QOPT] Flattening sub-queries TPC-H 5.1

This choke point tests the ability of the query optimizer to flatten execution
plans when there are correlated sub-queries. Many queries have correlated sub-
queries and their query plans can be flattened, such that the correlated sub-
query is handled using an equi-join, outer-join or anti-join. In TPC-H Q21,
for instance, there is an EXISTS clause (for orders with more than one
supplier) and a NOT EXISTS clauses (looking for an item that was received too
late). To execute this query well, systems need to flatten both sub-queries,
the first into an equi-join plan, the second into an anti-join plan.
Therefore, the execution layer of the database system will benefit from
implementing these extended join variants.

The ill effects of repetitive tuple-at-a-time sub-query execution can also be
mitigated if execution systems by using vectorized, or blockwise query
execution, allowing to run sub-queries with thousands of input parameters
instead of one. The ability to look up many keys in an index in one API call
creates the opportunity to benefit from physical locality, if lookup keys
exhibit some clustering.

#### CP-5.2: [QEXE] Overlap between outer and sub-query TPC-H 5.3

This choke point tests the ability of the execution engine to reuse results
when there is an overlap between the outer query and the sub-query. In some
queries, the correlated sub-query and the outer query have the same joins and
selections. In this case, a non-tree, rather DAG-shaped [21] query plan would
allow to execute the common parts just once, providing the intermediate result
stream to both the outer query and correlated sub-query, which higher up in
the query plan are joined together (using normal query decorrelation
rewrites). As such, the benchmark rewards systems where the optimizer can
detect this and the execution engine supports an operator that can buffer
intermediate results and provide them to multiple parent operators.

#### CP-5.3: [QEXE] Intra-query result reuse TPC-H 5.2

This choke point tests the ability of the execution engine to reuse sub-query
results when two sub-queries are mostly identical. Some queries have almost
identical sub-queries, where some of their internal results can be reused in
both sides of the execution plan, thus avoiding to repeat computations.

###  A.6 Parallelism and Concurrency

#### CP-6.1: [QEXE] Inter-query result reuse TPC-H 6.3

This choke point tests the ability of the query execution engine to reuse
results from different queries. Sometimes with a high number of streams a
significant amount of identical queries emerge in the resulting workload. The
reason is that certain parameters, as generated by the workload generator,
have only a limited amount of parameters bindings. This weakness opens up the
possibility of using a query result cache, to eliminate the repetitive part of
the workload. A further opportunity that detects even more overlap is the work
on recycling, which does not only cache final query results, but also
intermediate query results of a “high worth”. Here, worth is a combination of
partial-query result size, partial-query evaluation cost, and observed (or
estimated) frequency of the partial-query in the workload.

#### CP-6.2: [QEXE] Intra-query parallelization on hub vertex New in FinBench

When traversing on hub vertex, the number of edges is beyond estimation based
on the degree distribution of the graph. This chokepoint tests the query
optimizer to automate the intra-query parallelization when traversing on hub
vertex to speed up.

###### Queries

TCR 1 TCR 2 TCR 3 TCR 4 TCR 5 TCR 6 TCR 7 TCR 8 TCR 9 TCR 10 TCR 11 TCR 12

#### CP-6.3: [QEXE] Write operation contention and conflicts New in FinBench

Read-write query is expected to execute inside a transaction. The transaction
like a possible write down to storage (I/O) after a long time read starting
with a write operation in memory. This means long time write transactions that
hold write locks longer than expected. This may result in contention and
conflicts between write operations to the same datum.

###  A.7 Graph Specifics

#### CP-7.1: [QEXE] Incremental path computation From SNB

This choke point tests the ability of the execution engine to reuse work
across graph traversals. For example, when computing paths within a range of
distances, it is often possible to incrementally compute longer paths by
reusing paths of shorter distances that were already computed.

###### Queries

TCR 1 TCR 2 TCR 5 TCR 8 TCR 12

#### CP-7.2: [QOPT] Cardinality estimation of transitive paths From SNB

This choke point tests the ability of the query optimizer to properly estimate
the cardinality of intermediate results when executing transitive paths. A
transitive path may occur in a “fact table” or a “dimension table” position. A
transitive path may cover a tree or a graph, descendants in a geographical
hierarchy graph neighborhood or transitive closure in a many-to-many connected
social network. In order to decide proper join order and type, the cardinality
of the expansion of the transitive path needs to be correctly estimated. This
could for example take the form of executing on a sample of the data in the
cost model or of gathering special statistics, the depth and fan-out of a
tree. In the case of hierarchical dimensions, geographic locations or other
hierarchical classifications, detecting the cardinality of the transitive path
will allow one to go to a star schema plan with scan of a fact table with a
selective hash join. Such a plan will be on the other hand very bad for
example if the hash table is much larger than the “fact table” being scanned.

#### CP-7.3: [QEXE] Execution of a transitive step From SNB

This choke point tests the ability of the query execution engine to
efficiently execute transitive steps. Graph workloads may have transitive
operations, for example finding the shortest path between vertices. This
involves repeated execution of a short lookup, often on many values at the
same time, while usually having an end condition, the target vertice being
reached or having reached the border of a search going in the opposite
direction. For the best efficiency, these operations can be merged or tightly
coupled to the index operations themselves. Also, parallelization may be
possible but may need to deal with a global state, set of visited vertices.
There are many possible tradeoffs between generality and performance.

#### CP-7.4: [QEXE] Efficient evaluation of termination criteria for
transitive queries From SNB

This tests the ability of a system to express termination criteria for
transitive queries so that not the whole transitive relation has to be
evaluated as well as efficient testing for termination.

###### Queries

TCR 1 TCR 2 TCR 5 TCR 11

#### CP-7.5: [QEXE] Unweighted shortest paths From SNB

A common problem in graph queries is determining the distance between a
vertice and a set of vertices. To compute the distance values, systems may
employ BFS or a single-source shortest path algorithm with uniform weights. To
compute the distance between two given vertices, systems can use bidirectional
search algorithms.

#### CP-7.6: [QEXE] Weighted shortest paths From SNB

Computing single-source shortest path is a fundamental problem in graph
queries. While there are well-known algorithms to compute it, Dijkstra’s
algorithm or the Bellman-Ford algorithm, system often use naïve approaches
such as enumerating all paths which makes these queries intractable.

#### CP-7.7: [QEXE] Composition of graph queries From SNB

In many cases, it is desirable to specify multiple graph queries, where the
first one defines an induced subgraph or an overlay graph on the original
graph, which is then passed two the next query, and so on. Expressing such
computations as a sequence of composable graph queries would be desirable from
both usability, optimization, and execution aspects. However, currently many
graph dabases lack support for composable graph queries.

The G-CORE [22] design language tackled problem this by introducing the _path
property graph_ data model (consisting of vertices, edges, and paths) and
defining queries such that they return a graph (while also providing means to
return a tabular output).

#### CP-7.8: [QEXE] Reachability between disconnected components From SNB

For path finding queries, the result is often that the specified path does not
exist in the graph. For example, for a single-source single-destination
search, when one of the endpoints is in a small component (the endpoint is an
isolated vertice), systems using a bidirectional search algorithm can quickly
determine that there is no path to be found.

#### CP-7.9: [STORAGE] Hub vertex storage balance New in FinBench

Especially in distributed systems, hub vertices means bigger data unit, shard,
which may need to split to balance the storage, load and inter-shard
communication.

#### CP-7.10: [STORAGE] Multiplicity support in Graph Model New in FinBench

Edge multiplicity requires that systems support multiple edges between the
same vertex pair. Another dimension is required to annotate the edge id.

#### CP-7.11: [QEXE] Intermediate Result Propagation New in FinBench

When calculating some final share or final ratio values, there is a common
pattern in computing that each value need to calculate with the value in last
hop which is similar to propagation, (label propagation). To make the
computation more efficient, some intermediate results should be cached to
reuse in the next computing stage.

###### Queries

TCR 11

###  A.8 Language Features

#### CP-8.1: [LANG] Complex patterns From SNB

###### Description.

A natural requirement for graph query systems is to be able to express complex
graph patterns.

###### Transitive edges.

Transitive closure-style computations are common in graph query systems, both
with fixed bounds (get vertices that can be reached through at least 3 and at
most 5 knows edges), and without fixed bounds (get all Messages that a Comment
replies to).

###### Negative edge conditions.

Some queries define _negative pattern conditions_. For example, the condition
that a certain Message does not have a certain Tag is represented in the graph
as the absence of a hasTag edge between the two vertices. Thus, queries
looking for cases where this condition is satisfied check for negative
patterns, also known as negative application conditions (NACs) in graph
transformation literature [23].

#### CP-8.2: [LANG] Complex aggregations From SNB

###### Description.

BI workloads are heavy on aggregation, including queries with _subsequent
aggregations_ , where the results of an aggregation serves as the input of
another aggregation. Expressing such operations requires some sort of query
composition or chaining (see also CP-8.4). It is also common to _filter on
aggregation results_ (similarly to the HAVING keyword of SQL).

#### CP-8.3: [LANG] Ranking-style queries From SNB

###### Description.

Along with aggregations, BI workloads often use _window functions_ , which
perform aggregations without grouping input tuples to a single output tuple. A
common use case for windowing is _ranking_ , selecting the top element with
additional values in the tuple (vertices, edges or attributes).111PostgreSQL
defines the OVER keyword to use aggregation functions as window functions, and
the rank() function to produce numerical ranks, see
https://www.postgresql.org/docs/9.1/static/tutorial-window.html for details.

#### CP-8.4: [LANG] Query composition From SNB

###### Description.

Numerous use cases require _composition_ of queries, including the reuse of
query results (vertices, edges) or using scalar subqueries (selecting a
threshold value with a subquery and using it for subsequent filtering
operations).

#### CP-8.5: [LANG] Dates and times From SNB

###### Description.

Handling dates and times is a fundamental requirement for production-ready
database systems. It is particularly important in the context of BI queries as
these often calculate aggregations on certain periods of time (on entities
created during the course of a month).

#### CP-8.6: [LANG] Handling paths From SNB

###### Description.

Handling paths as first-class citizens is one of the key distinguishing
features of graph database systems [22]. Hence, additionally to reachability-
style checks, a language should be able to express queries that operate on
elements of a path, calculate a score on each edge of the path. Also, some use
cases specify uniqueness constraints on paths [9]: _arbitrary path_ ,
_shortest path_ , _no-repeated-node semantics_ (also known as _simple paths_),
and _no-repeated-edge semantics_ (also known as _trails_). Other variants are
also used in rare cases, such as _maximal_ (non-expandable) or _minimal_ (non-
contractable) paths.

###### Note on terminology.

The _Glossary of graph theory terms_ page of
Wikipedia222https://en.wikipedia.org/wiki/Glossary_of_graph_theory_terms
defines _paths_ as follows: “A path may either be a walk (a sequence of
vertices and edges, with both endpoints of an edge appearing adjacent to it in
the sequence) or a simple path (a walk with no repetitions of vertices or
edges), depending on the source.” In this work, we use the first definition,
which is more common in modern graph database systems and is also followed in
a recent survey on graph query languages [9].

#### CP-8.7: [LANG] Concise temporal window expression New in FinBench

Temporal window filtering is a common expression pattern when filtering edges
in navigational pattern. The common scenario is that the whole pattern is
expected bounded by the timestamp filter, including _BEFORE_ , _AFTER_ and
_BETWEEN_. It is supported that adding timestamp filtering on each vertex and
edge in the pattern to express a temporal window, which is a verbose
expression. A more concise expression is desired. A possible solution is
adding keywords like _RANGE_SLICE_ , _LEFT_SLICE_ and _RIGHT_SLICE_ referring
to an extension of _Cypher_ [24].

###### Queries

TCR 1 TCR 2 TCR 3 TCR 4 TCR 5 TCR 6 TCR 7 TCR 8 TCR 9 TCR 10 TCR 11 TCR 12

#### CP-8.8: [LANG] Recursive path filtering pattern New in FinBench

Sometimes when tracing a fund flow, such a pattern is expected that find a
path with recursive filters. For example, filters are expected to assume a
path A -[${e_{1}}$]-> B -[${e_{2}}$]-> … -> X.

  * •

The timestamp order: ${e_{1}}$ < ${e_{2}}$ < … < ${e_{i}}$

  * •

The amount order: ${e_{1}}$ > ${e_{2}}$ > … > ${e_{i}}$

  * •

The time window: ${e_{i-1}}$ < ${e_{i}}$ < ${e_{i-1}}$ \+ $\vec{\Delta}$,
$\vec{\Delta}$ is a given constant.

Such queries that require _all timestamps in the transfer trace are in
ascending order_ or the _upstream_ edge are difficult to explain in plain
Cypher (or GQL or SQL/PGQ) because they require support for the category of
queries _Regular expression with memory_ as described in this paper[25].
Another possible solution is adding keywords like _SEQUENTIAL_ and _DELTA_
referring to an extension of _Cypher_ [24].

###### Queries

TCR 1 TCR 2 TCR 5

#### CP-8.9: [LANG] Traversal limit pattern New in FinBench

When traversing on hub vertex, the data amount touched may experience
exponential growth, which is a common challenge to systems. When the
performance is not enough to satisfy the queries on hub vertex, a language
feature is needed that the number of edges traversed out from the hub vertex
can be limited. Such keyword may be _truncation_limit_.

###  A.9 Update Operations

#### CP-9.1: [UPD] Insert vertice From SNB

This choke point tests the ability of the database to insert a vertice.

#### CP-9.2: [UPD] Insert edge From SNB

This choke point tests the ability of the database to insert an edge.

#### CP-9.3: [UPD] Delete vertice From SNB

This choke point tests the ability of the database to delete a vertice.

#### CP-9.4: [UPD] Delete edge From SNB

This choke point tests the ability of the database to delete an edge.

#### CP-9.5: [UPD] Delete recursively From SNB

This choke point tests the ability of the database to recursively perform a
delete operation, delete an entire message thread.

##  Appendix B Scale Factor Statistics

###  B.1 Number of Entities for FinBench Transaction v0.1.0

C | File | SF0.01 | SF0.1 | SF0.3 | SF1 | SF3 | SF10
---|---|---|---|---|---|---|---
N | account | 2 633 | 26 347 | 79 199 | 264 075 | 791 769 | 1 980 883
N | company | 2 633 | 4 000 | 12 000 | 40 000 | 120 000 | 300 000
E | companyApplyLoan | 524 | 5 332 | 15 761 | 52 820 | 158 678 | 397 060
E | companyGuarantee | 248 | 2 315 | 7 123 | 23 870 | 71 716 | 179 526
E | companyInvest | 860 | 8 639 | 25 853 | 86 092 | 259 884 | 650 190
E | companyOwnAccount | 864 | 8 805 | 26 356 | 88 119 | 264 352 | 660 625
E | deposit | 5 199 | 51 686 | 153 521 | 512 680 | 1 534 595 | 3 829 905
N | loan | 1 597 | 16 138 | 47 772 | 159 166 | 476 670 | 1 189 072
E | loanTransfer | 4 886 | 49 180 | 145 679 | 484 657 | 1 453 874 | 3 625 556
N | medium | 1 000 | 10 000 | 30 000 | 100 000 | 300 000 | 2 000 000
N | person | 800 | 8 000 | 24 000 | 80 000 | 240 000 | 600 000
E | personApplyLoan | 1 073 | 10 806 | 32 011 | 106 346 | 317 992 | 792 012
E | personGuarantee | 469 | 4 694 | 14 221 | 47 935 | 144 064 | 359 283
E | personInvest | 1 650 | 17 296 | 52 002 | 174 064 | 520 584 | 1 300 980
E | personOwnAccount | 1 769 | 17 542 | 52 843 | 175 956 | 527 417 | 1 320 258
E | repay | 5 046 | 50 495 | 149 559 | 497 033 | 1 488 916 | 3 715 487
E | signIn | 4 384 | 44 540 | 134 532 | 451 362 | 1 350 759 | 8 996 781
E | transfer | 14 145 | 138 209 | 411 882 | 1 379 527 | 4 136 803 | 11 005 032
E | withdraw | 20 557 | 201 119 | 609 548 | 2 011 359 | 6 013 709 | 15 056 721
Table B.1: The number of entities per SF and per file in the Transaction
workload (produced by the LDBC FinBench DataGen). To derive these numbers,
100% of the network was generated as an initial bulk data set with no update
streams. Notation – C: entity category, N: node, E: edge.

## References

  * [1] Renzo Angles et al. “The LDBC Social Network Benchmark” In _CoRR_ abs/2001.02299, 2020 arXiv: http://arxiv.org/abs/2001.02299
  * [2] ldbc “ldbc_snb_docs” URL: https://github.com/ldbc/ldbc_snb_docs
  * [3] Ant Group Co.,Ltd “Ant Group Homepage” URL: https://www.antgroup.com/en
  * [4] Renzo Angles et al. “The Linked Data Benchmark Council: A graph and RDF industry benchmarking effort” In _SIGMOD Record_ 43.1, 2014, pp. 27–31 DOI: 10.1145/2627692.2627697
  * [5] Mirko Spasic, Milos Jovanovik and Arnau Prat-Pérez “An RDF Dataset Generator for the Social Network Benchmark with Real-World Coherence” In _BLINK at ISWC_ , 2016 URL: http://ceur-ws.org/Vol-1700/paper-02.pdf
  * [6] Alexandru Iosup et al. “LDBC Graphalytics: A Benchmark for Large-Scale Graph Analysis on Parallel and Distributed Platforms” In _VLDB_ 9.13, 2016, pp. 1317–1328 DOI: 10.14778/3007263.3007270
  * [7] LDBC “Byelaws of the Linked Data Benchmark Council v1.3” https://ldbcouncil.org/docs/LDBC.Byelaws.1.3.ADOPTED.2021-01-14.pdf, 2021
  * [8] Jim Gray, Raymond A. Lorie, Gianfranco R. Putzolu and Irving L. Traiger “Granularity of Locks and Degrees of Consistency in a Shared Data Base” In _IFIP Working Conference on Modelling in Data Base Management Systems_ , 1976, pp. 365–394
  * [9] Renzo Angles et al. “Foundations of Modern Query Languages for Graph Databases” In _ACM Comput. Surv._ 50.5, 2017, pp. 68:1–68:40 DOI: 10.1145/3104031
  * [10] Nadime Francis et al. “Cypher: An Evolving Query Language for Property Graphs” In _SIGMOD_ ACM, 2018, pp. 1433–1445 DOI: 10.1145/3183713.3190657
  * [11] Peter Bailis et al. “Scalable Atomic Visibility with RAMP Transactions” In _ACM Trans. Database Syst._ , 2016 DOI: 10.1145/2909870
  * [12] Peter Bailis “Highly Available Transactions: Virtues and Limitations” In _VLDB_ , 2013 DOI: 10.14778/2732232.2732237
  * [13] Atul Adya “Weak consistency: A generalized theory and optimistic implementations for distributed transactions”, 1999
  * [14] Jack Waudby, Paul Ezhilchelvan, Jim Webber and Isi Mitrani “Preserving Reciprocal Consistency in Distributed Graph Databases” In _PaPoC at EuroSys_ ACM, 2020 DOI: 10.1145/3380787.3393675
  * [15] Alan Fekete et al. “Making snapshot isolation serializable” In _ACM Trans. Database Syst._ 30.2, 2005, pp. 492–528 DOI: 10.1145/1071610.1071615
  * [16] Oszkár Semeráth “Formal validation of domain-specific languages with derived features and well-formedness constraints” In _Softw. Syst. Model._ 16.2, 2017, pp. 357–392 DOI: 10.1007/s10270-015-0485-x
  * [17] Peter A. Boncz, Thomas Neumann and Orri Erling “TPC-H Analyzed: Hidden Messages and Lessons Learned from an Influential Benchmark” Springer, 2013, pp. 61–76 DOI: 10.1007/978-3-319-04936-6_5
  * [18] Goetz Graefe “Query Evaluation Techniques for Large Databases” In _ACM Comput. Surv._ 25.2, 1993, pp. 73–170 DOI: 10.1145/152610.152611
  * [19] Dan Olteanu and Maximilian Schleich “Factorized Databases” In _SIGMOD Rec._ 45.2, 2016, pp. 5–16 DOI: 10.1145/3003665.3003667
  * [20] Guido Moerkotte “Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing” In _PVLDB_ , 1998, pp. 476–487 URL: http://www.vldb.org/conf/1998/p476.pdf
  * [21] Thomas Neumann and Guido Moerkotte “A Framework for Reasoning about Share Equivalence and Its Integration into a Plan Generator” In _BTW_ , 2009, pp. 7–26 URL: http://subs.emis.de/LNI/Proceedings/Proceedings144/article5220.html
  * [22] Renzo Angles et al. “G-CORE: A Core for Future Graph Query Languages” In _SIGMOD_ ACM, 2018, pp. 1421–1432 DOI: 10.1145/3183713.3190654
  * [23] Annegret Habel, Reiko Heckel and Gabriele Taentzer “Graph Grammars with Negative Application Conditions” In _Fundam. Inform._ 26.3/4, 1996, pp. 287–313 DOI: 10.3233/FI-1996-263404
  * [24] OrangeLab “T-Cypher” URL: https://project.inria.fr/tcypher/
  * [25] Leonid Libkin and Domagoj Vrgoč “Regular Path Queries on Graphs with Data” In _Proceedings of the 15th International Conference on Database Theory_ , ICDT ’12 Berlin, Germany: Association for Computing Machinery, 2012, pp. 74–85 DOI: 10.1145/2274576.2274585

pricing tpc-pricing tpcc