Generalised Uncertainty Relations from Finite-Accuracy Measurements

Matthew J<EMAIL_ADDRESS>Marek
<EMAIL_ADDRESS>Ray<EMAIL_ADDRESS>and
Tomasz Paterekg,h

_a National Astronomical Research Institute of Thailand,
260 Moo 4, T. Donkaew, A. Maerim, Chiang Mai 50180, Thailand
_ _b Department of Physics and Materials Science,
Faculty of Science, Chiang Mai University,
239 Huaykaew Road, T. Suthep, A. Muang, Chiang Mai 50200, Thailand
_ _c School of Physics, Sun Yat-Sen University,
Guangzhou 510275, People’s Republic of China
_ _d Department of Physics, Babeş-Bolyai University,
Mihail Kogălniceanu Street 1, 400084 Cluj-Napoca, Romania
_ _e Office of Research Administration, Chiang Mai University,
239 Huaykaew Rd, T. Suthep, A. Muang, Chiang Mai 50200, Thailand
_ _f Centre for Quantum Optical Technologies, Centre of New Technologies,
University of Warsaw, Banacha 2c, 02-097 Warsaw, Poland
_ _g Department of Physics, Xiamen University Malaysia, 43900 Sepang, Malaysia
_ _h Institute of Theoretical Physics and Astrophysics,
Faculty of Mathematics, Physics and Informatics,
University of Gdańsk, 80-308 Gdańsk, Poland_

###### Abstract

In this short note we show how the Generalised Uncertainty Principle (GUP) and
the Extended Uncertainty Principle (EUP), two of the most common generalised
uncertainty relations proposed in the quantum gravity literature, can be
derived within the context of canonical quantum theory, without the need for
modified commutation relations. A GUP-type relation naturally emerges when the
standard position operator is replaced by an appropriate Positive Operator
Valued Measure (POVM), representing a finite-accuracy measurement that
localises the quantum wave packet to within a spatial region $\sigma_{g}>0$.
This length scale is the standard deviation of the envelope function, $g$,
that defines the POVM elements. Similarly, an EUP-type relation emerges when
the standard momentum operator is replaced by a POVM that localises the wave
packet to within a region $\tilde{\sigma}_{g}>0$ in momentum space. The usual
GUP and EUP are recovered by setting $\sigma_{g}\simeq\sqrt{\hbar G/c^{3}}$,
the Planck length, and $\tilde{\sigma}_{g}\simeq\hbar\sqrt{\Lambda/3}$, where
$\Lambda$ is the cosmological constant. Crucially, the canonical Hamiltonian
and commutation relations, and, hence, the canonical Schrödinger and
Heisenberg equations, remain unchanged. This demonstrates that GUP and EUP
phenomenology can be obtained without modified commutators, which are known to
lead to various pathologies, including violation of the equivalence principle,
violation of Lorentz invariance in the relativistic limit, the reference
frame-dependence of the ‘minimum’ length, and the so-called soccer ball
problem for multi-particle states.

##

Keywords: Generalised uncertainty relations, generalised uncertainty
principle, extended uncertainty principle, finite-accuracy measurements, POVM

##  1 Introduction

In canonical quantum mechanics the Heisenberg uncertainty principle (HUP)
implies a fundamental trade-off between the precisions of position and
momentum measurements. 444In classical error analysis the term ‘precision’ is
used to refer to the statistical spread of the results whereas the term
‘accuracy’ refers to the discrepancy between the measured value of a quantity
and its true value. In keeping with this general usage, we use the term
precision to refer to the quantum mechanical uncertainty and accuracy to refer
to the width of the error bars associated with each individual measurement. It
can be introduced heuristically, via the famous Heisenberg microscope thought
experiment, giving [1, 2]

$\displaystyle\Delta x^{i}\,\Delta
p_{j}\gtrsim\frac{\hbar}{2}\delta^{i}{}_{j}\,,$ (1.1)

or derived rigorously from the canonical quantum formalism, yielding [3, 4]

$\displaystyle\Delta_{\psi}x^{i}\,\Delta_{\psi}p_{j}\geq\frac{\hbar}{2}\delta^{i}{}_{j}\,.$
(1.2)

The inequality in Eq. (1.2) is exact and, unlike the heuristic uncertainties
$\Delta x^{i}$ and $\Delta p_{j}$ in Eq. (1.1), $\Delta_{\psi}x^{i}$ and
$\Delta_{\psi}p_{j}$ represent well-defined standard deviations of the
probability distributions $|\psi(\bf{x})|^{2}$ and
$|\tilde{\psi}_{\hbar}(\bf{p})|^{2}$, respectively, where the momentum space
representation of the particle wave function is given by the $\hbar$-scaled
Fourier transform of its position space representation:

$\displaystyle\tilde{\psi}_{\hbar}({\bf
p})=\left(\frac{1}{\sqrt{2\pi\hbar}}\right)^{3}\int\psi({\bf
x})e^{-\frac{i}{\hbar}{\bf p}.{\bf x}}{\rm d}^{3}{\rm x}\,.$ (1.3)

We emphasise the scale-dependence of the canonical quantum Fourier transform,
which is often neglected in standard treatments, by introducing the subscript
$\hbar$. The relation (1.2) is obtained by combining the Schrödinger-Robertson
relation for arbitrary Hermitian operators, $\hat{O}_{1}$ and $\hat{O}_{2}$
[5, 6],

$\displaystyle\Delta_{\psi}O_{1}\,\Delta_{\psi}O_{2}\geq\frac{1}{2}|\langle\psi|[\hat{O}_{1},\hat{O}_{2}]|\psi\rangle|\,,$
(1.4)

with the canonical position-momentum commutator,

$\displaystyle[\hat{x}^{i},\hat{p}_{j}]=i\hbar\delta^{i}{}_{j}\
\hat{\mathbb{I}}\,.$ (1.5)

In recent years, thought experiments in quantum gravity research have
suggested the existence of generalised uncertainty relations (GURs). By
reconsidering Heisenberg’s 1927 gedanken experiment, and accounting for the
gravitational interaction between the massive particle and the probing photon,
we obtain the generalised uncertainty principle (GUP),

$\displaystyle\Delta x^{i}\gtrsim\frac{\hbar}{2\Delta
p_{j}}\delta^{i}{}_{j}\left[1+\alpha_{0}\frac{2G}{\hbar c^{3}}(\Delta
p_{j})^{2}\right]\,,$ (1.6)

where $\alpha_{0}$ is a numerical constant of order unity [7, 8, 9]. By
minimising the right-hand side with respect to $\Delta p_{j}$, the GUP implies
the existence of a minimum position uncertainty of the order of the Planck
length, $l_{\rm Pl}=\sqrt{\hbar G/c^{3}}\simeq 10^{-33}\,{\rm cm}$.

Reconsidering Heisenberg’s arguments in the presence of a constant dark energy
density $\rho_{\Lambda}=\Lambda c^{2}/(8\pi G)\simeq 10^{-30}\,{\rm
g\,.\,cm^{-3}}$ [10, 11], or, equivalently, an asymptotically de Sitter
background with minimum scalar curvature of the order of the cosmological
constant, $\Lambda\simeq 10^{-56}\,{\rm cm^{-2}}$ [12, 13], gives the extended
uncertainty principle (EUP),

$\displaystyle\Delta p_{j}\gtrsim\frac{\hbar}{2\Delta
x^{i}}\delta^{i}{}_{j}\left[1+2\eta_{0}\Lambda(\Delta x^{i})^{2}\right]\,,$
(1.7)

where $\eta_{0}$ is of order one [14, 15, 16]. The EUP implies the existence
of a minimum momentum uncertainty of the order of the de Sitter momentum,
$m_{\rm dS}c=\hbar\sqrt{\Lambda/3}\simeq 10^{-56}\,{\rm g\,.\,cm\,s^{-1}}$.
This is physically reasonable since it is the minimum momentum that a
canonical quantum particle can possess, when its wave function is localised
within the asymptotic de Sitter horizon, which is comparable to the present
day radius of the Universe $r_{\rm U}(t_{0})\simeq l_{\rm
dS}=\sqrt{3/\Lambda}\simeq 10^{28}\,{\rm cm}$.

Combining both effects yields the extended generalised uncertainty principle
(EGUP),

$\displaystyle\Delta x^{i}\Delta
p_{j}\gtrsim\frac{\hbar}{2}\delta^{i}{}_{j}\left[1+\alpha_{0}\frac{2G}{\hbar
c^{3}}(\Delta p_{j})^{2}+2\eta_{0}\Lambda(\Delta x^{i})^{2}\right]\,,$ (1.8)

which implies the existence of both minimum length and momentum scales in
nature [14, 15, 16]. Like their forebearer (1.1) all three relations (1.6),
(1.7) and (1.8) are heuristic in nature and it remains an open problem how to
rigorously derive GURs from within a modified quantum formalism.

Perhaps the simplest way to obtain the GUP, EUP or EGUP, given the relation
(1.4), is to modify the canonical position-momentum commutation relation (1.5)
and it is clear that a modification of the form

$\displaystyle[\hat{x}^{i},\hat{p}_{j}]=i\hbar\delta^{i}{}_{j}\
\hat{\mathbb{I}}\mapsto[\hat{X}^{i},\hat{P}_{j}]=i\hbar\delta^{i}{}_{j}\left(\hat{\mathbb{I}}+\alpha_{0}\frac{2G}{\hbar
c^{3}}(\hat{P}_{j})^{2}+2\eta_{0}\Lambda(\hat{X}^{i})^{2}\right)$ (1.9)

gives rise to an EGUP-type uncertainty relation, at least when both
$\langle\hat{P}_{j}\rangle_{\psi}=0$ and $\langle\hat{X}^{i}\rangle_{\psi}=0$
[17]. Here, we use capital letters to denote modified operators, which
generate modified commutators, and lower case letters to denote their
canonical quantum counterparts. However, the assumption above is problematic
since, even if both $\langle\hat{P}_{j}\rangle_{\psi}=0$ and
$\langle\hat{X}^{i}\rangle_{\psi}=0$ in a given frame of reference, a simple
shift of coordinate origin or a Galilean velocity boost of the observer alters
the numerical value of the associated Schrödinger-Robertson bound:

$\displaystyle\Delta_{\psi}X^{i}\Delta_{\psi}P_{j}\geq\frac{\hbar}{2}\delta^{i}{}_{j}\left\\{1+\alpha_{0}\frac{2G}{\hbar
c^{3}}[(\Delta_{\psi}P_{j})^{2}+\langle\hat{P}_{j}\rangle_{\psi}^{2}]+2\eta_{0}\Lambda[(\Delta_{\psi}X^{i})^{2}+\langle\hat{X}^{i}\rangle_{\psi}^{2}]\right\\}\,.$
(1.10)

This leads immediately to the reference frame-dependence of the (supposedly
invariant) minimum length. In fact, the situation is even worse since even a
redefinition of the position-coordinate origin alters the value of the bound
on the right-hand side. This gives rise to a coordinate-dependent ‘minimum’
length, which is clearly unphysical, and which strongly suggests that GUR
models based on modified commutation relations are not mathematically self-
consistent [18, 19]

In addition, the modified position-momentum commutator (1.9) implies a
modification of the canonical Heisenberg equation, which immediately gives
rise to mass-dependent accelerations for quantum particles, violating the
equivalence principle [20, 21]. Such models also violate Lorentz invariance in
the relativistic limit and suffer from the so-called soccer ball problem, so
that sensible GUP-compatible multi-particle states cannot be defined [22, 23].
555In [23] an ingenious solution to the soccer ball problem was proposed by
Amelino-Camelia. In this approach, the generalised momentum operators of a
given modified commutator model are defined to be the generators of
‘generalised spatial translations’. The unitary transformation
$\hat{\mathcal{U}}({\bf X}):=\exp[(i/\hbar){\bf X}.\hat{{\bf P}}]$, which acts
nontrivially only on the $\hat{X}^{i}$ operators, is required to leave the
modified $[\hat{X}^{i},\hat{P}_{j}]$, $[\hat{X}^{i},\hat{X}^{j}]$ and
$[\hat{P}_{i},\hat{P}_{j}]$ algebras, as well as the multi-particle
Hamiltonian of the model, $\hat{\mathcal{H}}$, invariant. This defines the
‘generalised translation symmetries’ of the system and, when these symmetries
hold, the corresponding Noether charge for an $N$-particle state is
represented by the operator $\hat{{\bf P}}_{\rm
Total}:=\sum_{I=1}^{N}\hat{{\bf P}_{I}}$, where $[\hat{{\bf P}}_{\rm
Total},\hat{\mathcal{H}}]=0$. The usual law of linear momentum addition
therefore holds for multi-particle states but a different nonlinear addition
law, derived ultimately from the notion of spatial locality, holds for
transfers of momentum between individual particles, due to the interactions
specified by $\hat{\mathcal{H}}$ [23]. Unfortunately for GUP models, in the
example system considered in [23], the definition of the generalised spatial
translations required to maintain the linear addition law also requires one of
the position-momentum commutators to equal zero, i.e.,
$[\hat{X}^{i},\hat{P}_{i}]=0$, for some $i$. In this case there is no
Heisenberg uncertainty principle, let alone a GUP, even though a minimum
length scale $l$ still appears in the model via the position-position
commutator, e.g. $[\hat{X}_{1},\hat{X}_{2}]=il\hat{X}_{1}$. This illustrates a
general point, that it is by no means certain whether a particular modified
momentum operator, corresponding to a particular modification of the canonical
Heisenberg algebra, and, hence, a particular form of the GUP, is compatible
with a linear addition law derived via Amelino-Camelia’s procedure. Therefore,
although this procedure represents a useful criterion for defining physically
viable GUP models, it is clear that arbitrary deformations of the canonical
Heisenberg algebra are not consistent with the existence of a linear momentum
addition law and that further work is required to determine which models truly
suffer from a soccer ball problem and which ones do not. Though some GUP
models may be free from this pathology, a great many could still be afflicted
by it.

The heuristic, model-independent nature of the gedanken experiments that lead
to the relations (1.6), (1.7) and (1.8), together with the pathologies
displayed by modified commutator models, motivate us to consider alternative
ways to generate GUP, EUP and EGUP phenomenology, without modifying the
canonical Heisenberg algebra. In this paper, we consider one way in which such
a scheme can be implemented from within the canonical quantum formalism. The
physical basis of the model is the notion of a finite-accuracy measurement and
these are represented mathematically by the construction of appropriate POVM.
Roughly speaking, since errors add in quadrature for independent random
variables, finite-accuracy measurements of position and momentum with
detection ‘sweet spots’ of width $\sigma_{g}\simeq l_{\rm Pl}$ and
$\tilde{\sigma}_{g}\simeq m_{\rm dS}c$, respectively, give rise to the GUP and
EUP, to first order in the relevant Taylor expansion. These individual
relations may then be combined to give the EGUP.

##  2 GUR from finite-accuracy measurements described by POVM

In this section, we show that GUP, EUP and EGUP-type uncertainty relations can
be derived in an effective model, where position and momentum measurements in
canonical quantum theory are not perfectly accurate and are described by
POVMs, rather than perfect projective measurements.

Let us begin by replacing the usual position-measurement operator, $\hat{{\bf
x}}$, with POVM elements corresponding to the result ${\bf x}$:

$\hat{E}_{\bf{x}}:=\int g({\bf x}^{\prime}-{\bf x})|{\bf
x}^{\prime}\rangle\langle{{\bf x}^{\prime}}|{\rm d}^{3}{\rm x}^{\prime}\,,$
(2.1)

where $g({\bf x}^{\prime}-{\bf x})$ is any normalised function, $\int|g({\bf
x}^{\prime}-{\bf x})|^{2}{\rm d}^{3}{\rm x}^{\prime}=1$. These elements
satisfy the relations $\hat{E}_{{\bf x}}^{\dagger}\hat{E}_{{\bf x}}\geq 0$ and
$\int\hat{E}_{{\bf x}}^{\dagger}\hat{E}_{{\bf x}}{\rm d}^{3}{\rm
x}=\hat{\mathbb{I}}$, as required, so that Eq. (2.1) defines a standard POVM
in canonical quantum mechanics [24]. From here on, we refer to $g$ as the
‘envelope function’ of the measure. For spherically symmetric functions the
envelope is centred on the value $\bf{x}$, and, for the sake of concreteness,
we may imagine $|g({\bf x}^{\prime}-{\bf x})|^{2}$ as a three-dimensional
Gaussian distribution with mean ${\bf x}$ and standard deviation $\sigma_{g}$.

Finite-accuracy position measurements, conducted on an arbitrary state
$|\psi\rangle$, then give rise to the first and second order moments

$\displaystyle\langle E_{{\bf x}}\rangle_{\psi}$ $\displaystyle=$
$\displaystyle\int{\bf x}\langle\psi|\hat{E}_{{\bf x}}^{\dagger}\hat{E}_{{\bf
x}}|\psi\rangle{\rm d}^{3}{\rm x}=\langle{\bf x}\rangle_{g}+\langle{\bf
x}\rangle_{\psi}\,,$ $\displaystyle\langle E_{{\bf x}}^{2}\rangle_{\psi}$
$\displaystyle=$ $\displaystyle\int{\bf x}^{2}\langle\psi|\hat{E}_{{\bf
x}}^{\dagger}\hat{E}_{{\bf x}}|\psi\rangle{\rm d}^{3}{\rm x}=\langle{\bf
x}^{2}\rangle_{g}+\langle{\bf x}^{2}\rangle_{\psi}\,,$ (2.2)

where $\langle{\bf x}^{n}\rangle_{f}:=\int{\bf x}^{n}\,|f({\bf x})|^{2}\,{\rm
d}^{3}{\rm x}$ with $f({\bf x})=g({\bf x})$ or $\psi({\bf x})$. Since $|g({\bf
x}^{\prime}-{\bf x})|^{2}$ is a normalised function centred on ${\bf
x}^{\prime}={\bf x}$, $\langle{\bf x}\rangle_{g}=0$, and the corresponding
variance is given by

$\displaystyle(\Delta_{\psi}E_{{\bf x}})^{2}=(\Delta_{\psi}{\bf
x})^{2}+\bm{\sigma}_{g}^{2}\,,$ (2.3)

where $\bm{\sigma}_{g}:=$$\,\sigma_{g}^{i}$${\bf e}_{i}$ and $\sigma_{g}^{i}$
denotes the width of $|g|^{2}$ in each coordinate direction $x^{i}$. By
spherical symmetry, $\sigma_{g}^{i}=\sigma_{g}$ for all $i$, and we may
rewrite Eq. (2.3) in terms of the individual components as

$\displaystyle(\Delta_{\psi}E_{i})^{2}=(\Delta_{\psi}x^{i})^{2}+\sigma_{g}^{2}\,,$
(2.4)

where we have used the shorthand notation
$\Delta_{\psi}E_{i}\equiv\Delta_{\psi}E_{x^{i}}$.

In like manner, finite-accuracy momentum measurements may be introduced via
the operators

$\hat{\mathbb{E}}_{{\bf p}}:=\int\tilde{g}({\bf p}^{\prime}-{\bf p})|{\bf
p}^{\prime}\rangle\langle{\bf p^{\prime}}|{\rm d}^{3}{\rm p}^{\prime}\,,$
(2.5)

where $\int|\tilde{g}({\bf p}^{\prime}-{\bf p})|^{2}{\rm d}{\rm
p}^{\prime}=1$, but it is important to note that there is no intrinsic
relation between the functions $g$ and $\tilde{g}$, which may be chosen
independently for a given POVM model. Nevertheless, if both $|g|^{2}$ and
$|\tilde{g}|^{2}$ represent Gaussian distributions, which is perhaps the most
natural choice for an envelope function, then $g$ and $\tilde{g}$ are related
via a Fourier transform,

$\tilde{g}({\bf p}^{\prime}-{\bf p})=\int g({\bf x}^{\prime}-{\bf
x})e^{\frac{i}{\beta}({\bf x}^{\prime}-{\bf x}).({\bf p}^{\prime}-{\bf
p})}{\rm d}^{3}{\rm x}^{\prime}\,,$ (2.6)

where the new action scale $\beta\neq\hbar$ is given by

$\beta:=2\sigma_{g}\tilde{\sigma}_{g}\,,$ (2.7)

and $\tilde{\sigma}_{g}$ is the standard deviation of $|\tilde{g}|^{2}$.
However, it is equally important to note that there is nothing fundamental
about the relation (2.6). Unlike the $\hbar$-scaled Fourier transform relating
the position and momentum space representations of the quantum wave function,
Eq. (1.3), the $\beta$-scaled transform relates the ‘envelope functions’ of
the model.

Finite-accuracy momentum measurements, conducted on an arbitrary state
$|\psi\rangle$, then give rise to the first and second order moments

$\displaystyle\langle\mathbb{E}_{{\bf p}}\rangle_{\psi}$ $\displaystyle=$
$\displaystyle\int{\bf p}\langle\psi|\hat{\mathbb{E}}_{{\bf
p}}^{\dagger}\hat{\mathbb{E}}_{{\bf p}}|\psi\rangle{\rm d}^{3}{\rm
p}=\langle{\bf p}\rangle_{g}+\langle{\bf p}\rangle_{\psi}\,,$
$\displaystyle\langle\mathbb{E}_{{\bf p}}^{2}\rangle_{\psi}$ $\displaystyle=$
$\displaystyle\int{\bf p}^{2}\langle\psi|\hat{\mathbb{E}}_{{\bf
p}}^{\dagger}\hat{\mathbb{E}}_{{\bf p}}|\psi\rangle{\rm d}^{3}{\rm
p}=\langle{\bf p}^{2}\rangle_{g}+\langle{\bf p}^{2}\rangle_{\psi}\,,$ (2.8)

where $\langle{\bf p}^{n}\rangle_{f}:=\int{\bf p}^{n}\,|\tilde{f}({\bf
p})|^{2}\,{\rm d}^{3}{\rm p}$ with $\tilde{f}({\bf p})=\tilde{g}(\bf{p})$ or
$\tilde{\psi}_{\hbar}(\bf{p})$. Since $|\tilde{g}({\bf p}^{\prime}-{\bf
p})|^{2}$ is normalised and centred at ${\bf p}^{\prime}={\bf p}$,
$\langle{\bf p}\rangle_{g}=0$, and

$\displaystyle(\Delta_{\psi}\mathbb{E}_{{\bf p}})^{2}=(\Delta_{\psi}{\bf
p})^{2}+\bm{\tilde{\sigma}}_{g}^{2}\,,$ (2.9)

where $\bm{\tilde{\sigma}}_{g}:=$$\,\tilde{\sigma}_{gj}$${\bf e}^{j}$ and
$\tilde{\sigma}_{gj}$ denotes the width of $|\tilde{g}|^{2}$ in each momentum
space direction $p_{j}$. Again employing spherical symmetry,
$\tilde{\sigma}_{gj}=\tilde{\sigma}_{g}$ for all $j$, so that (2.9) may be
rewritten in terms of the individual components as

$\displaystyle(\Delta_{\psi}\mathbb{E}_{j})^{2}=(\Delta_{\psi}p_{j})^{2}+\tilde{\sigma}_{g}^{2}\,,$
(2.10)

where we have again used the shorthand
$\Delta_{\psi}\mathbb{E}_{j}\equiv\Delta_{\psi}\mathbb{E}_{p_{j}}$.

To obtain a GUP-type relation from Eq. (2.4) we simply take the square root,
Taylor expand the right-hand side to first order, and substitute for
$\Delta_{\psi}x^{i}$ from the HUP (1.2). Likewise, an EUP-type relation is
obtained from (2.10) by taking the square root, Taylor expanding to first
order, and substituting for $\Delta_{\psi}p_{j}$. Next, using the
substitutions

$\displaystyle\sigma_{g}:=\sqrt{2\alpha_{0}}\,l_{\rm
Pl}\,,\quad\tilde{\sigma}_{g}:=\sqrt{6\eta_{0}}\,m_{\rm dS}c\,,$ (2.11)

where

$\displaystyle l_{\rm Pl}:=\sqrt{\hbar G/c^{3}}\,,\quad m_{\rm
dS}c:=\hbar\sqrt{\Lambda/3}\,,$ (2.12)

immediately gives

$\displaystyle\Delta_{\psi}X^{i}\gtrsim\frac{\hbar}{2\Delta_{\psi}p_{j}}\delta^{i}{}_{j}\left[1+\alpha_{0}\frac{2G}{\hbar
c^{3}}(\Delta_{\psi}p_{j})^{2}\right]\,,$ (2.13)
$\displaystyle\Delta_{\psi}P_{j}\gtrsim\frac{\hbar}{2\Delta_{\psi}x^{i}}\delta^{i}{}_{j}\left[1+2\eta_{0}\Lambda(\Delta_{\psi}x^{i})^{2}\right]\,,$
(2.14)

where we have relabelled $\Delta_{\psi}E_{i}\equiv\Delta_{\psi}X^{i}$ and
$\Delta_{\psi}\mathbb{E}_{j}\equiv\Delta_{\psi}P_{j}$, for convenience. These
expressions are formally analogous to the heuristic relations (1.6) and (1.7),
respectively, but with $\Delta p_{j}$ and $\Delta x^{i}$ on the right replaced
by the well-defined standard deviations $\Delta_{\psi}p_{j}$ and
$\Delta_{\psi}x^{i}$.

This proves that GUP- and EUP-type relations can be derived rigorously, from
within the canonical quantum formalism, but a remaining criticism of the
formulae above is that the uncertainties on the right-hand sides of Eqs.
(2.13)-(2.14) are not equivalent to the uncertainties on the left. Indeed,
according to the POVM model, $\Delta_{\psi}p_{j}$ and $\Delta_{\psi}x^{i}$ are
not operationally observable quantities. They arise only in the limits
$\sigma_{g}\rightarrow 0$ and $\tilde{\sigma}_{g}\rightarrow 0$, respectively,
in which both (2.13) and (2.14) reduce to the standard HUP (1.2). This
objection can be overcome, however, by first substituting for
$\Delta_{\psi}x^{i}$ from (1.2) in Eq. (2.4) and then again for
$\Delta_{\psi}p_{i}$ from (2.10). This gives rise to an uncertainty relation
between the observable standard deviations,
$\Delta_{\psi}E_{i}\equiv\Delta_{\psi}X^{i}$ and
$\Delta_{\psi}\mathbb{E}_{j}\equiv\Delta_{\psi}P_{j}$. It is straightforward
to show that, taking the square root, Taylor expanding to first order, and
neglecting the final term of order $\sigma_{g}\tilde{\sigma}_{g}\simeq l_{\rm
Pl}\,.\,m_{\rm dS}c$, this relation reduces to

$\displaystyle\Delta_{\psi}X^{i}\Delta_{\psi}P_{j}\gtrsim\frac{\hbar}{2}\delta^{i}{}_{j}\left[1+\alpha_{0}\frac{2G}{\hbar
c^{3}}(\Delta_{\psi}P_{j})^{2}+2\eta_{0}\Lambda(\Delta_{\psi}X^{i})^{2}\right]\,.$
(2.15)

Therefore, the EGUP can be rigorously derived within the canonical quantum
formalism. The GUP and EUP proper then arise as limits of this more
fundamental relation.

We stress that, in this model, $\Delta_{\psi}E_{i}\equiv\Delta_{\psi}X^{i}$
and $\Delta_{\psi}\mathbb{E}_{j}\equiv\Delta_{\psi}P_{j}$ represent the
physically observable precisions, obtained from generalised position and
momentum measurements with finite accuracies $\sigma_{g}>0$ and
$\tilde{\sigma}_{g}>0$. By contrast, the canonical Hamiltonian is determined
by the canonical (projective) position and momentum operators, $\hat{\bf{x}}$
and $\hat{\bf{p}}$, via $\hat{H}=\hat{\bf{p}}^{2}/(2m)+V(\hat{\bf{x}})$, where
the former obey the canonical Heisenberg algebra:
$[\hat{x}^{i},\hat{p}_{j}]=i\hbar\delta^{i}{}_{j}\ \hat{\mathbb{I}}$,
$[\hat{x}^{i},\hat{x}^{j}]=0$, $[\hat{p}_{i},\hat{p}_{j}]=0$. This leaves the
canonical Heisenberg and Schrödinger equations unchanged and neatly evades the
pathologies that afflict modified commutator models [18, 19, 20, 21, 22].

##  3 Discussion

We have shown that the three most common GURs studied in the quantum gravity
literature, the GUP, EUP and EGUP, can be derived from within the formalism of
canonical quantum mechanics. A GUP-type uncertainty relation is obtained when
the standard (projective) position operator is replaced by an appropriate
POVM, representing finite-accuracy measurements with error bars of width
$\sigma_{g}>0$ in real space. In like manner, an EUP-type relation is obtained
from finite-accuracy measurements with error bars of width
$\tilde{\sigma}_{g}>0$ in momentum space. These can be combined to give a
relation that is formally analogous to the EGUP and the standard EGUP is
recovered by setting $\sigma_{g}\simeq l_{\rm Pl}$, the Planck length, and
$\tilde{\sigma}_{g}\simeq m_{\rm dS}c$, where $m_{\rm
dS}=(\hbar/c)\sqrt{\Lambda/3}$ is the de Sitter mass.

This work suggests that GUP, EUP and EGUP phenomenology can be understood in a
physically intuitive way, as a simple and natural outcome of finite-accuracy
measurements. Such measurements are capable of generating all three GURs and
the same phenomenology is obtained, at the level of the uncertainty relations,
regardless of whether the limits $(\Delta_{\psi}X^{i})_{\rm min}=\sigma_{g}$
and $(\Delta_{\psi}P_{j})_{\rm min}=\tilde{\sigma}_{g}$ are fundamental, or
merely effective, as an outcome of an imperfect measurement scheme.

We propose that this should give pause for thought to the GUP community. If
modified commutators are not necessary for GUP phenomenology, and, after
nearly 30 years of research, we are no closer to resolving the pathologies
that have afflicted these models since they were first proposed in the
mid-1990’s, then serious attempts should be made to find alternative
mathematical structures that give rise to GURs. These should be capable of
generating, via rigorous derivation, the uncertainty relations predicted by
model-independent gedanken experiments, but without the problems associated
with modified commutation relations.

In this paper, we have proposed one such model, within the context of
canonical quantum theory. Another, more radical, alternative is to consider
additional quantum mechanical degrees of freedom, not present in the canonical
theory, which are capable of describing quantum fluctuations of the background
geometry. Such a model was proposed in a recent series of works [25, 26, 27,
28, 29] and shares many features with the model described here, including the
existence of a new action scale that relates the accuracies of generalised
position and momentum measurements,
$\beta:=2\sigma_{g}\tilde{\sigma}_{g}\simeq 10^{-61}\hbar$ (*). The
fundamental difference between the two models is the existence of new degrees
of freedom in the latter. From this, it follows that the new action scale
$\beta$ implies a modified de Broglie relation of the form
$\bf{p}^{\prime}=\hbar\bf{k}+\beta(\bf{k}^{\prime}-\bf{k})$, where, here,
$\bf{p}^{\prime}$ denotes the observable momentum. Heuristically, the non-
canonical term $\beta(\bf{k}^{\prime}-\bf{k})$ can be interpreted as an
additional momentum ‘kick’, transferred to the canonical wave function by a
quantum fluctuation of the background. The interested reader is referred to
[18, 19, 25, 26, 27, 28, 29] for further details.

At first glance, this more radical alternative has nothing to do with the POVM
approach described here. It requires extra degrees of freedom associated with
the quantum state of the background geometry, contrary to the POVM formalism,
which remains entirely within the context of canonical quantum theory. It
follows from Stinespring’s dilation theorem [30, 31], however, that the two
formalisms are equivalent if we assume the particular values,
$\sigma_{g}\simeq l_{\rm Pl}$ and $\tilde{\sigma}_{g}\simeq m_{\rm dS}c$, and
hence the relation (*) above. The POVM picture results from tracing out the
${\bf x}^{\prime}$ (${\bf p}^{\prime}$) degrees of freedom associated with
quantum fluctuations of the background and the ${\bf x}^{\prime}$ (${\bf
p}^{\prime}$) degrees of freedom appear as a consequence of dilating the POVM.

The POVM approach describes a quantum measurement of finite accuracy. The
minimum resolution of the measurement may be due to technical limitations, or
it can reflect the fact that the minimum length and momentum scales are
fundamentally related. We postulate that in a universe with both fundamental
and technological limitations to measurement accuracy, the complete
description of a realistic quantum measurement should be a POVM extension of
the model presented in [25, 26]. We expect that this would give rise to two
additional contributions to the position and momentum variances, i.e.,
$\sigma_{g}^{2}+\sigma_{h}^{2}$ and
$\tilde{\sigma}_{g}^{2}+\tilde{\sigma}_{h}^{2}$, respectively, where $g$ is
the fundamental smearing function that models the quantum indeterminacy of
space-time, and $h$ is the envelope function of a realistic detector. In the
limit $\sigma_{h}\gg\sigma_{g}$, $\tilde{\sigma}_{h}\gg\tilde{\sigma}_{g}$,
which corresponds to all present-day measurements, the latter are expected to
dominate the former.

## Acknowledgments

ML acknowledges the Department of Physics and Materials Science, Faculty of
Science, Chiang Mai University, for providing research facilities, and the
Natural Science Foundation of Guangdong Province, grant no. 008120251030.

## References

  * [1] W. Heisenberg, Über den anschaulichen Inhalt der quantentheoretischen Kinematik und Mechanik, Z. Phys. 43, 172 (1927).
  * [2] W. Heisenberg, The physical principles of the quantum theory, New York, Dover (1930).
  * [3] A. I. M. Rae, Quantum Mechanics, 4th ed., Taylor & Francis: London, U.K. (2002).
  * [4] C. J. Isham, Lectures on Quantum Theory: Mathematical and Structural Foundations, Imperial College Press, London (1995).
  * [5] H. P. Robertson, The Uncertainty Principle, Phys. Rev. 34, 163 (1929).
  * [6] E. Schrödinger, About Heisenberg uncertainty relation, Bulg. J. Phys. 26, 193 (1999) [Sitzungsber. Preuss. Akad. Wiss. Berlin (Math. Phys. ) 19, 296 (1930)].
  * [7] M. Maggiore, A Generalized uncertainty principle in quantum gravity, Phys. Lett. B 304, 65 (1993).
  * [8] R. J. Adler and D. I. Santiago, On gravity and the uncertainty principle, Mod. Phys. Lett. A 14, 1371 (1999).
  * [9] F. Scardigli, Generalized uncertainty principle in quantum gravity from micro - black hole Gedanken experiment, Phys. Lett. B 452, 39 (1999).
  * [10] A. G. Riess et al., Observational Evidence from Supernovae for an Accelerating Universe and a Cosmological Constant, Astron. J. 116, 1009 (1998).
  * [11] S. Perlmutter et al., Measurements of $\Omega$ and $\Lambda$ from 42 high-redshift supernovae, Astrophys. J. 517, 565 (1999).
  * [12] M. Betoule et al. [SDSS Collaboration], Improved cosmological constraints from a joint analysis of the SDSS-II and SNLS supernova samples, Astron. Astrophys. 568, A22 (2014).
  * [13] P. A. R. Ade et al. [Planck Collaboration], Planck 2013 results. XVI. Cosmological parameters, Astron. Astrophys. 571, A16 (2014).
  * [14] B. Bolen and M. Cavaglia, (Anti-)de Sitter black hole thermodynamics and the generalized uncertainty principle, Gen. Rel. Grav. 37, 1255 (2005).
  * [15] M. i. Park, The Generalized Uncertainty Principle in (A)dS Space and the Modification of Hawking Temperature from the Minimal Length, Phys. Lett. B 659, 698 (2008).
  * [16] C. Bambi and F. R. Urban, Natural extension of the Generalised Uncertainty Principle, Class. Quant. Grav. 25, 095006 (2008).
  * [17] A. Kempf, G. Mangano and R. B. Mann, Hilbert space representation of the minimal length uncertainty relation, Phys. Rev. D 52, 1108-1118 (1995).
  * [18] M. J. Lake, A New Approach to Generalised Uncertainty Relations, to appear in Touring the Planck scale: Antonio Aurilia memorial volume, Piero Nicolini, ed., Fundamental Theories of Physics, Springer [arXiv:2008.13183 [gr-qc]] (2020).
  * [19] M. J. Lake and A. Watcharapasorn, Problems with modified commutators, Front. Astron. Space Sci., 10, 1118647 (2023).
  * [20] A. N. Tawfik and A. M. Diab, Generalized Uncertainty Principle: Approaches and Applications, Int. J. Mod. Phys. D 23, no. 12, 1430025 (2014). doi:10.1142/S0218271814300250 [arXiv:1410.0206 [gr-qc]].
  * [21] A. N. Tawfik and A. M. Diab, Review on Generalized Uncertainty Principle, Rept. Prog. Phys. 78, 126001 (2015)
  * [22] S. Hossenfelder, Minimal Length Scale Scenarios for Quantum Gravity, Living Rev. Rel. 16, 2 (2013).
  * [23] G. Amelino-Camelia, Planck-scale soccer-ball problem: a case of mistaken identity, Entropy 19, no.8, 400 (2017).
  * [24] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge (2000).
  * [25] M. J. Lake, M. Miller, R. F. Ganardi, Z. Liu, S. D. Liang and T. Paterek, Generalised uncertainty relations from superpositions of geometries, Class. Quant. Grav. 36, no.15, 155012 (2019).
  * [26] M. J. Lake, A Solution to the Soccer Ball Problem for Generalized Uncertainty Relations, Ukr. J. Phys. 64, no. 11, 1036 (2019).
  * [27] M. J. Lake, M. Miller and S. D. Liang, Generalised uncertainty relations for angular momentum and spin in quantum geometry, Universe 2020, 6, 56 (2020).
  * [28] M. J. Lake, How Does the Planck Scale Affect Qubits?, Quantum Rep. 3, no.1, 196-227 (2021).
  * [29] M. J. Lake, Why space could be quantised on a different scale to matter, SciPost Phys. Proc. 4, 014 (2021).
  * [30] W. F. Stinespring, Positive Functions on C*-algebras, Proceedings of the American Mathematical Society, 6, 211–216 (1955).
  * [31] V. Paulsen, Completely Bounded Maps and Operator Algebras, Cambridge University Press, Cambridge, U.K. (2003).


# BitE : Accelerating Learned Query Optimization in a Mixed-Workload
Environment

Yuri Kim<EMAIL_ADDRESS>0009-0003-3338-3749 Korea University SAP Labs
KoreaSeoulKorea ,  Yewon Choi<EMAIL_ADDRESS>0009-0003-3738-3738 Ewha
Womans University SAP Labs KoreaSeoulKorea ,  Yujung Gil<EMAIL_ADDRESS>Dongguk University SAP Labs KoreaSeoulKorea ,  Sanghee Lee
<EMAIL_ADDRESS>SAP Labs KoreaSeoulKorea ,  Heesik Shin
<EMAIL_ADDRESS>SAP Labs KoreaSeoulKorea and  Jaehyok Chong
<EMAIL_ADDRESS>SAP Labs KoreaSeoulKorea

(2023)

###### Abstract.

Although the many efforts to apply deep reinforcement learning to query
optimization in recent years, there remains room for improvement as query
optimizers are complex entities that require hand-designed tuning of workloads
and datasets. Recent research present learned query optimizations results
mostly in bulks of single workloads which focus on picking up the unique
traits of the specific workload. This proves to be problematic in scenarios
where the different characteristics of multiple workloads and datasets are to
be mixed and learned together. Henceforth, in this paper, we propose BitE, a
novel ensemble learning model using database statistics and metadata to tune a
learned query optimizer for enhancing performance. On the way, we introduce
multiple revisions to solve several challenges: we extend the search space for
the optimal Abstract SQL Plan(represented as a JSON object called ASP) by
expanding hintsets, we steer the model away from the default plans that may be
biased by configuring the experience with all unique plans of queries, and we
deviate from the traditional loss functions and choose an alternative method
to cope with underestimation and overestimation of reward. Our model achieves
19.6% more improved queries and 15.8% less regressed queries compared to the
existing traditional methods whilst using a comparable level of resources.

Query optimization, Q-error, Abstract SQL Plan, Ensemble, Machine Learning

††copyright: acmcopyright††journalyear: 2023††doi: XXXXXXX.XXXXXXX††booktitle:
EDBT/ICDT 2024 Joint Conference, 25th - 28th March, 2024, Paestum,
Italy††price: 15.00††isbn: 978-1-4503-XXXX-X/18/06††copyright: none††ccs:
Information systems Query optimization

##  1\. Introduction

Recently, there have been many attempts to apply machine learning techniques
to database systems(b1, ; b2, ), especially to query optimization. Diverse
approaches exist depending on various factors, for instance, the learning
methods (e.g. supervised, reinforcement), algorithms of the model (e.g. CNN,
decision tree), and the target of the value network (e.g. cardinality, cost).
However, to the best of our knowledge, we noticed that recent research work is
still limited in that it greatly focuses on a learning model per workload(b3,
; b4, ; b5, ; b6, ; b7, ; b8, ; b9, ) and poses several discussion points
concerning the efficiency of query optimization in mixed-workload
environments. We mainly tested our hypothesis and expanded on Bao(b4, ) as our
baseline model in connection to the expert optimizer(HANA), a high-speed in-
memory database.

(1) Expandability If the value networks are dependent on workloads, newly
introduced workloads will not be able to be integrated right away as their
performance will not match any of the original models and therefore a new
model will have to be set up for it. This strays from our objective to
construct a more generalized version of a query optimizer.

(2) Expensive to build and manage In order to construct individual models for
each workload, extra resources are exhausted to train and pertain the model in
areas such as memory and GPU usage(See Section 6.2). In addition, as the
pretrained models are retrained regularly to optimize performance when user
input queries are accumulated, a repetitive process will occur, retraining
take place for multiple models.

(3) Limited Performance In most of the aforementioned applications of ML for
query optimization, metrics for evaluation of performance are provided
individually on separate workloads without being mixed together or otherwise
were focused only on the join problems. While many of the ML models show
impressive accomplishment in single-workload driven query optimization, it
begs the question, is the performance also sustainable in environments that
take in multiple workloads at once?

Figure 1. Q-error for never-before-seen queries. Q-error shows the loss of the
model. Scope-S, M, L denotes the experiments that have differing number of
workloads used as training data, in ascending order. Scope-S which is based on
a single workload shows significantly better performance compared to Scope-L
which uses 9 workloads at once.

To this end, we went over a series of experiments and learned that performance
really does show correlation with the diversity in workloads(Figure 1, further
elaborated in Section 2.1). We propose a plausible solution of BitE(Bias-
tuning Ensemble Model) that utilizes the complexity of database statistics to
classify models. BitE labels the workloads into two classifications - Light
and Heavy - and shape them into a two-way ensemble model based on the
complexity characteristics of the workloads. While the complexity and weight
of the execution of a query depend on many elements, we mainly focus on three
aspects of workloads to determine the classification of each workload.

  * •

Scale factor : Workloads such as TPCH and TPCDS have scale factors which stand
for the predetermined size of the tables data. In the case of TPC-DS
benchmark, fact tables which are the tables with the biggest number of records
determine the scale factor.

  * •

Skewness : Skew in filter, aggregation and join operations make query
optimization more challenging. In this category, the JCCH workload introduces
correlations and skewness from the original TPCH queries so that filter
predicates alters the frequency and join-fan-out-distributions of the plan
operators.

  * •

Magnitude of tables : Apart from scale factors, the general magnitude of the
workload also affects query execution. Even for JOB, JOB-m, JOB-e, JOB-light,
JOB-light-ranges benchmarks that mainly root from the same IMDB workload, the
number of tables, columns and maximum records of a table actually used and
referred to differ.

This way, the proposed method would address the three limitations that the
individual workload models have.

(1) Expandable for new workloads Even when unseen workloads are put through
our model, only a simple stage of labeling the workload to either Light or
Heavy would be required in a similar manner using statistical information of
the workload. Then, instead of training an entire model which could take
hours, the classified workload or set of queries could be used immediately for
query optimization and hintset prediction.

(2) Untroublesome to build and manage Rather than having infinite sets of
models accounting for each workload, we would only need to maintain two
networks to be later on put in our ensemble model. No matter how many
workloads we work with, the number of classifications remains the same.

Figure 2. Comparison between baseline model(Bao) and BitE of mean execution
time for a subset of target queries that do not fall in the scope of timeouts.
CPU and elapsed time are each in the unit of seconds and milliseconds.

(3) Better performance with multiple workloads We compare the mean taken CPU
and elapsed time to execute approximately 1500 target queries, each using the
plans generated by our baseline model and BitE, which takes into account the
complexity of different workloads. Based on Figure 2, BitE shows 59% and 35%
improvement each in total CPU and elapsed execution time, far outperforming
the baseline model in its efficiency in mixed-workload environments.

We also introduce additional key contributions to accelerate query
optimization of BitE in the upcoming sections:

Expanding hintsets. Since the expert optimizer targets and supports hundreds
of logical enumeration hints(b10, ), with full utilization, the search space
of the model becomes extremely large with $2^{n}$ cases for $n$ hints(e.g. For
100 hints, $2^{100}$ hintsets are created as each hints can be turned on or
off). Therefore it is important to select and compress effective hintsets to
reduce our search space. We group hints that are frequently used together and
at the same time consider logical sense of the sets for efficiency(Section
3.1). In a sense, we find the optimum numbers of hintsets to fully take
advantage of and expand the search space for optimal query plans but at the
same time, limit hintsets so that the overhead of executing hintsets for each
query doesn’t grow too big as a burden on our system. To control this overhead
in growing number of hintsets, we later introduce parallel compilation
(Section 4.3) and integrate it into our learning method.

Removing bias in query optimization. In the original experiment methods of the
baseline model, it collects initial data with no-hint plans, that is the
default plans generated from the expert optimizer, which can invoke bias of
the model to prefer no-hint. Even though no-hint plans will be safe enough
since it relies on the expert optimizer, our goal is finding ‘new’ plans that
perform better than the traditional optimizer. So, we construct experiments to
remove the bias and find more of the new unbiased, but more efficient plans
(Section 3.2). To eliminate the bias of learning according to the pattern of
the plan preferred by the expert optimizer, we accumulate initial training
data by generating all plans from every hintset instead of only generating
‘no-hint’ plans. We also replace Q-error as our new training loss to give all
queries equal weight in forming BitE, eliminating the bias towards heavy
queries(Section 3.3).

##  2\. Implementing Ensemble Models for Multiple Workloads

Even though Learned models are not intended to learn logical enumeration
patterns workload-dependently, through a series of experiments, we noticed
that the more tables are brought in the dataset, the worse the predictability
becomes. Hence we set up a series of experiments to prove if the diversity in
workloads really do show correlation with query performance in Section 2.1. We
then go into how to identify the complexity of the workloads using the
statistical information in Section 2.2. Finally, Section 2.3 illustrates the
specifics of implementing BitE which we proposed in Section 1, a plausible
solution of measuring the complexity of the individual workloads to later
group them together to form a ensemble model.

###  2.1. Regression in Mixed-Workloads Environment

workload | # Queries |  | Cumulative
---
Total
Experiment set
JOB | 100 | 100 |  | scope-S, scope-M,
---
scope-L
TPCDS_SF1 | 73 | 173 | scope-M, scope-L
TPCDS_SF10 | 28 | 201 | scope-M, scope-L
STACK | 99 | 300 | scope-M, scope-L
TPCH_SF1 | 22 | 322 | scope-L
TPCH _SF10 | 22 | 344 | scope-L
TPCH_SF100 | 22 | 366 | scope-L
JCCH | 22 | 388 | scope-L
TPCDS_SF10 | 50 | 438 | scope-L
Corporate | 62 | 500 | scope-L

Table 1. Number of queries each used to train the scope experiment models. The experiment set name signifies the target coverage of various workload- L for large, M for medium and S for small- and which workloads were included in it. 50 more TPCDS-10 queries were extracted to extend the magnitude of scope-L. Corporate is an internal dataset and added to diversify the workloads for this experiment with 78 tables and 254M records for the largest table. Experiment set | # Improved | # Regressed | # Workloads
---|---|---|---
Scope-S | 32 | 7 | 1
Scope-M | 24 | 9 | 4
Scope-L | 23 | 10 | 9

Table 2. Results of experiment predictions. Evaluation performed upon 100
queries from the IMDB dataset

We set up three different workloads each for experiments to see if the variety
of workloads affect performance, each experiment set being incremental in the
number of workloads. Each experiment scope-S, scope-M, scope-L extracted 100,
300, 500 queries each from 1, 4 and 9 workloads, described in Table 1.

For each experiment set, we measured whether the predictions improved for 100
target queries. As shown in Table 2, the improvements were induced in
comparison with the execution of the queries with no hints, that is the
default optimal plan that the expert optimizer figures. With one workload used
solely as the training set, Scope-S had the most improved queries and at the
same time, the least regressed queries. As the workloads covered by the
different experiment sets grew, there were less improved queries and more
regressed queries. This served as evidence that clearly, the efficacy
decreases for multiple workloads as the models are tuned in multiple
directions.

For experiments with bigger loads of datasets of workloads as shown in Figure
1, which should enhance the prediction accuracy by providing the model with
more patterns to learn, the Q-error(loss for model, Section 3.3) seemed to be
bigger and slower to converge. Scope-L which had the most workloads showed a
greater variation even during training compared to the other sets, indicating
that with diverse workloads, it suffered from the danger of serious
regressions if the training is not stopped at the appropriate stage.
Therefore, we cope with these spikes in mixed-workload environments by
proposing BitE.

###  2.2. Accounting for Workload Complexity

As proposed in Section 1, we try to solve the problem by dividing the model
into two versions based on the statistical information of the workload - Light
and Heavy. This way, when a new workload query comes in, it can be classified
as either Light or Heavy and passed through the corresponding model based on
the statistical information, which doesn’t require any additional model setup.

As mentioned in Section 1, we turn to scale factors, skewness and the
magnitude of the workloads to determine the complexity weight of the workload.
For this matter, Table 5 includes a detailed table statistics for every
workload.

Why use table statistics and metadata to classify workloads and how are they
related to query optimization?

Although there exist attempts to provide a more generalized model for query
optimization(b21, ), we observed that most research work focus on a single-
workload environment as some traits of the plan are unique to workloads and
can’t be disconnected from the workload itself. In addition, another factor to
consider is that the magnitude or complexity of workloads are a determining
factor of execution time, as they establish the cost and size of queries.
Hence if we distinguish the characteristics of the workload and group it
together to create a ensemble model, this would preserve the workload
information and help create an efficient, high-performing model. In addition,
the action of manually classifying the complexity of each workload could
provide to the fact that cost and size estimations are often miscalculated as
size depends on a set of predefined rules with an assumption of data
distribution and would contribute to reducing the impact of the misguided
estimations by providing an general sense of how heavy the execution will be.

However, as there are several standards to tend to, there is no “one clear”
rule to follow when distinguishing the type of allotment. Henceforth, we move
on to find the best combination of workloads to achieve this in a rather
heuristic manner by trying out the options carefully designed and selected. We
also wanted to compare using metadata of the tables and the size of the
latency we experienced for the division while preparing for experiments and
the weight to see if the metadata is an accurate and optimal way of
constructing the model. Hence for Ensemble 1 and Ensemble 2, the separation
was based more on the CPU execution time while Ensemble 3 and Ensemble 4 was
purely based on the three factors mentioned above – scale factors, skewness
and magnitude of tables.

Experiment | JOB | JOB_m | JOB_light | JOB_e | JCCH |
---|---|---|---|---|---|---
Ensemble 1 | Heavy | Heavy | Light | Heavy | Heavy |
Ensemble 2 | Light | Light | Light | Light | Heavy |
Ensemble 3 | Light | Light | Light | Light | Heavy |
Ensemble 4 | Heavy | Heavy | Heavy | Heavy | Heavy |
Experiment | STACK | TPCDS1 | TPCDS10 | TPCH1 | TPCH10 |
Ensemble 1 | Heavy | Light | Heavy | Light | Heavy |
Ensemble 2 | Heavy | Heavy | Heavy | Heavy | Heavy |
Ensemble 3 | Heavy | Light | Light | Light | Heavy |
Ensemble 4 | Heavy | Light | Light | Light | Heavy |
Experiment | JOB_light_ranges | TPCH100 |  |  |
Ensemble 1 | Light |  | Heavy |  |  |
Ensemble 2 | Light |  | Heavy |  |  |
Ensemble 3 | Light |  | Heavy |  |  |
Ensemble 4 | Heavy |  | Heavy |  |  |
Table 3. Splitting workloads to Light and Heavy.

For example, for experiment Ensemble 3, the division of the workloads into
Light and Heavy are based on the scale factor, skewness of the data
distribution and the magnitude of tables, that is the number of tuples of the
biggest table. All four of the Heavy workloads have 60M records in the biggest
table within the schema while JCCH adds on with the fact that it proves to be
Heavy as its skewness acts as a hinderance to query optimization. The size and
complexity of the workload would lead on to having a much more intricate and
deeper neural network than the other, comparably simple “light” workloads and
hence would result in better performance when it comes to query optimization.

Algorithm 1 Train Ensemble model

Input Light workload queries, Heavy workload queries
Output Learned model

1: Construct(model_classifier) {Add linear classifier at the forefront to
classify the workload complexity with statistics}

2:

3: for EnsembleModel_class $\in$ $Heavy,Light$ do

4: for query $Q$ $\in$ model_class workload  do

5: asps ← parallel_compilation(Q) {Extract all 225 abstract sql plans for all
hintsets}

6: asps ← unique(asps) {Remove duplicate plans}

7: for asp in asps do

8: reward ← execute(asp) {Execute plan and get execution time}

9: end for

10: Experience ← save(reward, asp){Insert reward into Experience along with
plan}

11: end for

12: end for

13: Train(EnsembleModel_class)

14: return EnsembleModel_class

Algorithm 2 Predict hintset for query with Ensemble model

Input Query $Q$
Output Hintset that returns optimal performance for the given query execution

1: Ensemble ←Classify($Workload_{Q}$) {Classify the workload the query is
based on to either Light or Heavy and load the according Ensemble model}

2:

3: for hintset $\in$ range(0, 225) do

4: $rewards_{hintset}$ ← Ensemble($Q_{hintset}$) {Predict reward for every
hintset with the Ensemble model}

5: end for

6:

7: Optimal Hintset ← argmin(rewards)

8: return Optimal Hintset

In Section 6.2, we present and evaluate our proposal and our experimental
runs, confirming the efficiency of the method.

###  2.3. System Architecture

Figure 3. System architecture

In this phase we go over the architecture overview by discussing the process
of how BitE works side to side with the expert optimizer, and showing how we
extract the necessary components to the final evaluation of each model. The
detailed architecture is shown in Figure 3.

Training The main reason for choosing Bao as our baseline model among other
learned query optimizers in this paper is that it takes advantage of fully
utilizing the knowledge of underlying expert optimizer. It is robust to
changes in schema, data, or workload so there is no need to train from scratch
when changes in the workload itself occur. Also, no modification to the expert
optimizer is required while integrating the baseline model into it, while all
features and knowledge supported by the underlying optimizer can be utilized.
Our model is initially trained by queries generated with all predefined
hintsets and retrained when new user queries come into the system(Algorithm
1).

Prediction Input queries are first classified by our pre-built classifier to
decide which model between Light and Heavy that the query will be passed
into(Algorithm 2). The expert optimizer then compiles the query with all
target hintsets and returns the abstract sql plan for each hintset through a
built-in procedure. Returned ASPs represent estimated size, cost, and metadata
information for the relationship of each operator. These ASPs of hintsets are
put into learned model as an input. Once it passes the network, the model -
constructed with several layers of tree CNNs, normalization as well as a
pooling, fully connected and an activation layer - learns the affiliated
patterns and costs existing in the plan. It returns a predicted value for the
reward(i.e. the target of our learned model - CPU execution time) of each
target hintset and of all the predicted rewards, the model picks the hintset
with the optimal reward which should be the lowest execution time. We refer to
this as the optimal predicted hintset. This selected hint is then appended to
the query using the existing optimizer, and the resulting reward is stored in
the experience, providing feedback to the model. Unless mentioned otherwise,
CPU time is defined as our reward which is stored in an internal statistics
view.

Evaluation metrics and sources Once we collect enough experience to train our
model, we start the training and evaluation. Evaluation is carried out on
never-before-seen query $k_{n+1}$. Essentially, when a new query comes in, it
is passed through the network, trained only with the initial queries, to
predict the reward. It is not until this process is over that we actually
calculate the loss to give feedback to the model through backpropagation,
which constructs a model with +1 queries. This way, it is much more efficient
and provides a timelier manner to evaluate our model, instead of having a
separate set of validation queries to be executed every epoch or model to get
the real CPU time which should be costly as well.

##  3\. Accelerating Query Optimization

In this section, we aim to describe experiments conducted to further tune and
accelerate BitE for better performance. To achieve this, we identify and
mitigate the limitations associated with the narrow hintset search
space(Section 3.1) and the two types of bias that exist in our baseline
learned model(Section 3.2 and 3.3).

###  3.1. Expanding hintsets

Expanding hintsets from the minimum set of join problems, which many commonly
approach query optimization with, is a crucial step to query optimization as
it provides a sufficient search space. However, this must be dealt with
caution as if it is overdone, the number of cases could grow exponentially and
rather be detrimental to the learning steps.

Out of the hundreds of hints of the expert optimizer, we mark 15 significant
hints (Table 4) and combine them to come up with meaningful hintsets that will
lead to potential optimal plans. 15 logical enumeration hintsets were chosen
as distinct hints that will affect query optimization, and with each hint,
there exists an option to turn it either on or off. However, if we just
naively apply this to generate hintsets, it would result in $2^{15}$(more than
30,000) bandits which would not be feasible to compile all in real time.
Therefore, we pick out and exclude combinations of hints that logically do not
make sense. For example,

(1) hash_join, index_join

It is logically impossible for the expert optimizer to choose both join
predicates. They are mutually exclusive; therefore, one should be off while
the other one is turned on. However, we do not eliminate the hintset of both
being turned off, as another join predicate can be chosen instead of the pre-
selected two.

(2) [range_join, hashed_range_join],
[hash_join, index_join]

The former two join predicate groups are applied only in queries with
inequality (greater than, less than, or between) predicates, comparing the
values of columns. When there are no inequality filters in queries, the latter
two will mostly be exercised. Therefore, we place the hints into two
independent groups and henceforth reduce the combinations of hints to half of
the possible combinations.

$set(range\\_join,hashed\\_range\\_join,hash\\_join,index\\_join)=\\\
set(range\\_join,hashed\\_range\\_join)\cup set(hash\\_join,index\\_join)$

(3) join_thru_aggr, aggr_thru_join

The hints differ only in the order of logical enumeration plans. Hence when
they come together, they bear no meaning as they are contrastive to each
other.

Category | # Hints | Examples of hints
---|---|---
Joins(Enumeration) | 4 |  | HASH_JOIN
---
RANGE_JOIN
Logical Enumeration | 11 |  | AGGR_BEFORE_UNION
---
FILTER_THRU_JOIN

Table 4. Hints used to build our learned model.

We end up with 225 hintsets, reducing the number of bandits to under 1% of the
original targeted combinations of hints. The number of hintsets are critical
to query optimization as compilation is required for every single hintset -
which would result in great latency if it were to grow too large. We found
these to be the optimal number of hintsets: If too many, the latency would
become too large and if too little, it would not provide a sufficient search
space to find the optimal hintset.

###  3.2. Removing Bias with Entire Hintsets

Originally, the baseline model undergoes an initial chunk where it goes
through a process of model initialization. This process involves executing
queries with ‘no-hint’ and in the n-chunk approach afterwards, the process
involves iteratively sampling a subset of queries for prediction and
retraining.

However, there exists a drawback in this approach. If the model initialization
is performed by accumulating experience using the default expert optimizer in
the first chunk, it can lead to a bias, leaning towards the original plans
generated by the expert optimizer. When bias occurs, there is a higher
likelihood of selecting hints according to the expert optimizer’s preferred
methods, which may neglect the possibility of better plans in alternative
spaces. To address this issue, we have devised the following method.

In the first chunk, we introduce the ‘Unbiased’ method, a modified model
initialization process where each sampled query’s execution was accompanied by
appending all 225 predefined hints. This process allowed for accumulating
experience while executing the 225 predefined hints for each query. In the
N-chunks, we maintained the original approach of the baseline model. However,
a potential issue arises when attempting to execute all 225 hints for each
query in the first chunk, as it can lead to an exponential increase in
training time proportional to the number of predefined hints.

To overcome this limitation, we examined whether there were any overlapping
ASPs when appending the predefined hints to the queries. On average, we found
that there were around 20-30 distinct ASPs, with a maximum of approximately
40. Therefore, we applied a method to remove duplicates and executed the
queries only with hints that had distinct ASPs, storing the results in the
experience.

###  3.3. Removing Bias in Loss Function with Q-error

Loss functions commonly used in learned query optimization cost models are the
Mean Squared Error(MSE) loss. However as it takes the magnitude of all queries
into account, naturally the queries with bigger running time heavily influence
the model. With the purpose of managing regressions for long and substantial
queries, MSE loss would be the primary go-to loss function.

However, as an observation of our previous experiments (Figure 6), there was a
performance gap between queries with short cpu time and those with long cpu
time. In our first experiment, 21.4% of former (i.e. short) queries improved
while 26.3% of latter (i.e. long) queries improved. Naturally, the model
already finds substantial better plans for short-cpu-time queries, but
matching the ratio of the two can be an important improvement point. If the
model works to make better predictions only for long-cpu-time queries as the
previous model with MSE does, then the value of using the model for other
short-cpu-time queries will diminish. The more similar the ratio of the two,
the fairer prediction becomes possible no matter what queries actually come
in, which means the model becomes more practical and valuable.

Therefore, we adapted a revision of a new loss function, Q-error. Q-error, a
popular evaluation metric in the context of cardinality estimation(b22, ; b23,
; b24, ), mediates queries of all costs (i.e. rewards), disregarding the
magnitude of queries as it is somewhat of a ratio. Q-error is effective in
that it is able to cope with both overestimation and underestimation of query
execution times. Therefore, we take the q-error for CPU time and subtract 1
from it, to make a perfect prediction close to 0(Equation 1). However, for
convenience, it is replaced by the name Q-error.

(1) $\scalebox{0.8}{$Q-error=\sum_{1}^{n}(max(\frac{Predicted\ CPU\
time_{i}}{Real\ CPU\ time_{i}},\frac{Real\ CPU\ time_{i}}{Predicted\ CPU\
time_{i}})-1)$}\\\ \scalebox{0.8}{$,0\leq i\leq\\#experience$}$

##  4\. Learning Requirements

In this section, we discuss the main environments and preparations necessary
to set up and configure our model aligned with the expert optimizer. The
characteristics of the datasets that we used for shaping the value network are
described in Section 4.1 and then in Section 4.2, the system environments are
briefly introduced. We next address the challenges that arose in integrating a
learned model into the expert optimizer, specifically in reducing latency to
make prediction performance comparable with the HANA engine in Section 4.3.

###  4.1. Dataset

Workload | # Columns | # Tables |  | # Records of table
---
with the most records
JOB | 60 | 21 | 36M
JOB-Light | 8 | 6 | 36M
JOB-LR | 13 | 6 | 36M
JOB-E | 41 | 16 | 36M
JOB-M | 16 | 16 | 36M
TPCH SF1 | 53 | 8 | 6M
TPCH SF10 | 53 | 8 | 60M
TPCH SF100 | 53 | 8 | 600M
JCCH | 53 | 8 | 60M
TPCDS SF1 | 248 | 24 | 3M
TPCDS SF10 | 248 | 24 | 30M
STACK | 39 | 10 | 92M

Table 5. Full list of workloads mainly used to comprise the training set.
Number of records of table with the most records nearly represents scale
factor, which is taken into account when splitting workloads for Ensemble.
JOB-LR and JOB-E each stand for JOB-Light-Ranges and JOB-Extended.

Our training dataset were extracted from the workloads listed in Table 5.

JOB are original 113 queries from IMDB dataset, an augmentation of the Join
Order Benchmark(b15, ). Similarly, JOB-light is a benchmark popularly used in
cardinality estimation studies. It contains 70 queries with 6 table-schema and
each query joins 2-5 tables. JOB-light-ranges contain more complex filters are
added based on JOB-light while JOB-M(b16, ) contains more complicated join
conditions and each query joins 2–11 tables. JOB-Extended (b17, ) use same
relations and different sematics compared to JOB. We modified some queries so
that HANA database can compile them successfully. TPCH(b18, ) and TPCDS(b19, )
are a decision support benchmark with each of 22 and 99 queries. There are
various scaling factors for TPCH and TPCDS benchmark. For example, SF10
consists of the 10 times larger base row size than SF1, since different
scaling factors represent different dataset sizes. JCCH(b20, ) has a skewed
version of TPCH SF10 schemas but uses the same TPCH queries. STACK is real-
world dataset and workload from Bao (b3, ).

###  4.2. Environment settings

System specification All experiments were performed on a corporate server,
using a machine of 2 NVIDIA TITAN Xp GPUs coupled with 22 CPU cores and 1009
GB of DDR4 RAM.

System configurations To ensure the consistency of query execution environment
and performance, 25 system configurations were altered and fixed(e.g. such as
enforcing execution processing engine version, compile time sampling size and
to collect and use runtime feedback).

Why CPU instead of elapsed time? When a query is executed, it is run in
parallel over several threads. The number of threads used to execute the query
varies for every query or situation, hence it fails to be a coherent value to
predict. Therefore, we prefer to work with CPU time which should be the total
time taken to execute each query, taking every thread into consideration.

Stable execution time CPU average execution time can often be fluctuant
depending on how burdened the machine is in the status quo, how many jobs are
running and what version of DB build it is using. Also, the initial executions
of queries are much slower than the latter comings as the plan cache is non-
existent for unseen queries. Therefore to achieve a stable, consistent CPU
time we clear the cache before the initial execution and warm up the cache 3
times. Then we take the following 3 executions and take the average to be the
reward of each query which leads CPU execution times to be coherent and viable
to construct our value model with.

###  4.3. Soft landing and Parallel compilation

####  4.3.1. Parallel compilation

To predict the optimal plan out of 225 hintsets, we first need to compile and
capture all ASPs. To reduce the redundancy in compilation time and prevent
regression, the abstract sql plans for each hintset are run in parallel. As we
work with large amounts of threads, we ensure that there are no abnormally
hanging threads or database connections by limiting the max pool size to 225.

####  4.3.2. Soft landing with timeout

One of the notable challenges we faced during building the model was that
query execution can be extremely slow. Sometimes, it is the matter of
inefficient plan generation, while a lot of the times, it is due to the fact
that the query itself is too heavy. Out of the queries we executed with the
default plan generated from the expert optimizer, the maximum elapsed
execution time was approximately 130 minutes with the average elapsed
execution time being 4 seconds. Considering that we execute each query 6 times
to retrieve the warmed-up average of the execution time, only the data
extraction itself would overpower the training time of the model itself.

This is problematic in that to collect data, we execute queries in real time
with the database engine, sufficient enough to train a deep reinforcement
learning model. Another point to keep in mind is that we also need to extract
catastrophic plans and its reward time to learn its patterns and prevent the
model to choose such plans.

Therefore as a soft landing mechanism, we opt for timeouts to limit the
execution of queries with disastrous plans. Queries that take longer than the
preset connection timeout will be terminated and not be included in the
experience. Most common values used for timeouts are 10 and 20 seconds.

Does this hinder the learning of queries that take longer execution?

We observed that the prediction does not degrade even for queries and plans
that take longer than the connection timeout. 10 seconds of time limit
provides a window just enough to capture the relationship of complex plans but
not elongate the query execution phase excessively. Once the pattern of the
plan tree is learned, size and cost are taken into context together to predict
the CPU execution time.

##  5\. Related Works

The modern DBMS optimizer uses the cost model to select the best plan among
the best query execution plans (QEPs). A key part of query optimization is to
improve cardinality estimation, and the latest research is trying to apply
machine learning to these cost models. Recently, many studies have been
conducted on 1) how to improve cardinality estimation using supervised and
unsupervised learning or 2) how to generate query plans after learning using
cost model or runtime.

Many studies have been conducted to increase the acuity of cardinality
estimation as a way to improve runtime. Rong et al. stated that FLAT (b11, )
has emerged to solve the existing problem of cardinality estimation, slow
probability computing. It has fast probability computing, light weight for
model size, and pretty accurate estimation quality. Based on IMDB benchmark,
query execution time has improved by 12.9%.

The query-driven method has limitations in that it has dependency on training
query and the quality of training query affects the estimation quality. The
data-driven method has fewer limitations and higher adaptability compared to
query-driven method. For this reason, FACE (b12, ) used data-driven methods
and proposed the model by capturing the dependency of column and large domain
size for high accuracy, high inference efficiency, and achieving lightweight
model size. It improved latency and memory usage compared to previous
research, on the contrary, there are still constraints for acyclic joins or
other predicates.

Reference (b13, ) implemented an unified deep autoregressive model that
attempts to narrow the gap between data-driven and query-driven model. It
operates learning joint data distribution using both data and query workload.
There is improvement in that it supports group-by-clauses and learns both data
and query, but constraints still exist for various joins.

LEO (b14, ) is one of the earliest applications, and it is operated by
estimating cardinality with a query execution plan. It develops by comparing
the predicted value to the actual value of each step of the actual QEP and
giving feedback to learn from the past mistake. Stillger et al. asserted that
this model showed successful performance for similar queries.

NEO (b4, ) is the first fully learned system for creating QEPs. It predicts
the smallest cost through featurization with the value among the various QEPs,
throwing a selected plan, and using a latency with the actual execution for
experience. However, the model has limitations in that it has database
dependency.

Marcus et al. (b3, ) implemented a model which can create QEPs by attaching
predefined hints respectively and predicts hints that have the smallest cost
among the plans using the TCNN structure. It has the advantage of being able
to operate by attaching this model to the existing optimizer, and there is no
database dependency. NEO gives a plan as output, however, Bao returns a hint
that can have good performance for a specific query as an output. Unlike NEO,
the input requires cardinality and cost, and the information must be obtained
from the existing optimizer such as HANA. In addition, Bao is a workload-
driven method, so the query execution of a large set of training queries is
required.

##  6\. Experiments and Results

Our key evaluation is whether our enhanced model successfully removes bias of
the baseline model to prefer patterns of no-hint plans generated from
underlying expert optimizer (Section 3.2) and performs better on mixed-
workload environment with ensemble method (Section 2.1). Here we present and
visualize the key findings of experiments mentioned above.

###  6.1. Results for Removing Bias

Figure 4. Improved and Regressed percentage of each experiment: Sampling + MSE
denotes original baseline model.

We aimed to increase the possibility of finding better plans than those
preferred by the expert optimizer by addressing the bias issue.

####  6.1.1. Utilizing entire hintsets

To achieve this, we first adopted the approach of utilizing all hint sets, as
introduced in Section 3.2. The experimental results of the original approach -
which stacks initial data with no-hint - are well represented in the first row
of Table 6. The ”No-hints” category indicates that using the existing
optimizer without any additional hints was the best approach, with a predicted
ratio of 42.4% while both the ”Improved” and ”Regressed” categories had a
ratio of 18.2% and 26.5%.

Experiment | # Improved | # Regressed | # No-hints
---|---|---|---
Baseline Model | 18.2% | 26.5% | 42.4%
BitE(Unbiased) | 24.3% | 15.9% | 42.5%

Table 6. No-hint predictions and queries with less of an 10% CPU time change
are excluded from improved and regressed counts. 18.2% of the queries have
shown more than 10% better performance with the hint our learned model has
selected compared to HANA default plan.

With entire hint sets, the ratio of ”no-hint” increased from the original
42.4% to 42.5%, a reduction of approximately 0.1%. This might question the
effectiveness of reducing bias based on this outcome. However, regression
decreased from 26.5% to 15.9%, a reduction of approximately 10.6%. This
outcome can be explained by comparing the actual execution times which shows
it is evident that there are queries where ’no hint’ emerges as the optimal
choice. Also, the percentage of queries that were improved increased from
18.2% to 24.3%, a gain of approximately 6.1%. By expanding the search space
for queries that were initially selected with no-hint, we were able to steer
the model to make more assertive decisions.

Furthermore, it can be observed that queries that previously made incorrect
selections undergo a transition towards making appropriate selections with
bold choices. As shown in Figure 4, enhancements were seen in both the number
of improved and regressed queries. This suggests that by reducing the tendency
of the model to learn patterns favored by the expert optimizer, we were able
to discover good plans that were previously overlooked due to the bias
existing in the expert optimizer and conduct more aggressive exploration,
which involves exploring a broader search space instead of relying on plans
selected by the expert optimizer.

(a) Baseline model(Sampling + MSE)

(b) Unbiased + MSE

(c) Unbiased + Q-error

Figure 5.  Cpu time comparison between HANA plan and the plan selected by the
learned model in the experiments

####  6.1.2. Q-error loss function.

Nevertheless, a problem exists that the prediction results were better for
queries with long cpu time. To solve this, Q-error was introduced to our losss
function. A remarkable point of the results of using Q-error is that
improvement of short-cpu-time queries have increased to a similar degree of
long-cpu-time-queries. As shown in Figure 6, the difference between Short
improved and Long improved was 4.9% before, and with Q-error the difference of
the two decreased to 2.6%. This indicates that Q-error fairly improves
prediction on all queries and the distribution becomes more even. Figure 5(b)
and 5(c) visualize the results again with more improved queries of short-cpu-
time queries. Also the results were meaningful even when viewed as a
whole(Figure 4) rather than looking at short-time-queries and long-time-
queries separately. Improvement of all queries increased compared to MSE loss
function.

Figure 6. Improved and Regressed percentage of each experiment. Short and Long
each denote the set of queries divided by the average CPU execution time.

(a) Median Q-Error

(b) Mean L1 Loss

Figure 7.  Median Qloss and L1 loss comparison between model with MSE and
Q-error loss function. Short-cpu-time (e.g. Short) queries and long-cpu-time
(e.g. Long) queries are divided based on median value of HANA cpu time for
pre-extracted queries.

Figure 7 show the Qloss of two experiments, our previous experiment with MSE
loss function and our new experiment with Q-error loss function measured in
training phase. As we trained the model with mean Qloss to reduce tail
latency, mean Qloss decreased by about 10% compared to the model with MSE
loss. Since the mean value reflects and takes into account predictions of all
queries, Qloss of quantile 90 also decreased by 30%, which indicates Q-error
improved the tail performance. Extra median Qloss and L1 loss were measured.
Q-error performed better than MSE for median Qloss by about 10% and L1 loss
also reduced by about 30%.

Another point is that training time it takes for median Qloss to converge to
the same percentage – say 0.298, the converged Qloss in MSE version - have
shortened by about two times in Q-error version. Additionally, with Q-error,
it takes about two and a half hours of training time, and during that time,
20,000 records are processed for median Qloss to reach 0.14 and mean Qloss to
reach a level of 0.6.

###  6.2. Ensemble Learning results

Here, we discuss and evaluate the results of the ensemble run in comparison
with the outcomes in Section 2.1. For the ensemble runs, we adopt Q-error,
proven to show better efficiency, to tune our model and learn from the unique
abstract sql plans among 225 hintsets, while we take on utilizing separate
models for Light and Heavy workloads. As proposed in Table 3, the training of
the Light and Heavy models are performed on the predetermined workloads based
on their database metadata and complexity. The same logic applies for the
predictions evaluation, where a query is put in and at the forefront, its
complexity is classified by its workload and is sent into the ensemble model.

Figure 8. Improved and regressed percentage of 4 experiments.

Is using table statistics and metadata the optimal way? Compared to the
results of Ensemble 1 and 2 which were based more on our experience of latency
during real execution, Ensemble 3 and 4 were divided by a clear and objective
rule using the three factors(Section 1). Its results both excel in the
improved and regressed queries in comparison with the former two experiments.
Figure 8 also illustrates the performance of each of the separate complexity
models which show that Ensemble 3 shows a powerful improvement for Light
workloads meanwhile Ensemble 4 has a surprising low percentage of Light
regression queries with a strong improvement in the Heavy improved queries.

(a) Time taken to train learned model per data point

(b) Process GPU utilization of Ensemble model(i.e. two-way model)

(c) Process GPU utilization of a one-way model(i.e. baseline model)

Figure 9. Comparison of resource usage for different models. (9(a)) Training
time for n-way models. N represents how many classifications of workloads
exist to consist the Ensemble model. (9(b)) Process GPU Utilization for
training Light and Heavy Ensemble model. The latter increase denotes
utilization for Heavy (9(c)) Process GPU utilization of the baseline model

Figure 10. Comparison of CPU execution time with plans produced by Bao and
BitE(Ensemble 3). The difference between the query latency is shown for a
subset of JOB_light_ranges queries.

Do BitE have an edge over the original baseline model? Figure 8 shows that no
matter how complexity for the ensemble methods is divided, its results are
significantly better both in the number of improved and regressed queries out
of 20,000 records that cover all mentioned workloads. It also illustrates that
even when the balance between the number of workloads that consist of the
Light and Heavy components is unequal, such as Ensemble 3 and Ensemble 4
(according to Table 3), the results are far acceptable than the original model
which is a melting pot of all workloads. This proves that the segmentation of
the entire model by grouping workloads that have similar complexity is
significantly efficient.

Memory and GPU usage Apart from the inference results, an important question
of resource usage is left to be addressed as well. If the training is done
separately for the Light and Heavy complexity, does it require more resources
than simply constructing one model that covers all workloads? Does dividing
into more ensemble models always guarantee better performance? We answer this
question by looking into the time spent and GPU utilization during the
training. Figures 6.a shows the time taken to train the model per data point
each for the models that are divided into 1, 2 and 4 types of workload
ensemble models. The more ensemble models we distinguish, the longer it takes
to converge(Figure 9(a)).

This leads to an increase in GPU utilization. Figure 9(b) and 9(c) show that
the average process GPU utilization for Ensemble training of 17.1% is slightly
lower than for the single model of 17.5%. At the same time, the Ensemble
training displays difference in training time of 20,000 records with a
reduction of 3% of the total training time in comparison to the single model.
Hence we far-outperform the original single model with our proposed ensemble
method with less or at least, a comparable level of resource usage.

Safe Tail-latency Plans Figure 10 depicts a detailed understanding of how good
BitE really is-lower execution time being better. It not only manages to
reduce the tail-latency in execution time by avoiding catastrophic choices but
it also easily surpasses the performance of the baseline model in most queries
of the JOB light ranges workload. Out of 100 target queries, 87% queries
successfully find better plans to enhance and accelerate query execution with
BitE. For the rest of the 13%, the queries do fall into regression compared
with Bao. However, the found hintsets are still acceptable as execution time
increases by, at most, only 25% while some of the improved plans tune and
reduce their execution time almost to a striking 80%.

In summary, BitE succeeds to find better plans and outperform the existing
learned query optimization methods by taking advantage of the workload
characteristics and tuning certian elements to remove underlying bias. The
Ensemble methods are simple, reproducible yet not expensive to implement on
top of any expert database optimizer.

##  7\. Conclusion and Future Work

In this paper, we presented novel methods to accelerate query optimization and
enhance its performance. In a mixed-workload environment, the ensemble model
is divided and trained based on the complexity and characteristics of
different workloads. Along the way, we introduced three novel propositions and
ideas of expanding hintsets, deviating from the default plan bias and revising
the loss function to generalize query optimization for queries with varying
weight. This provides a more acute grasp of query optimization and efficiently
outperforms the base work provided by the baseline model.

In the future, we find it an interesting direction to expand the search space
of optimal plans with additional hintsets and to narrow down the traits of
queries that some hintsets are more likely to apply to. Furthermore, the
number of unique plans (as certain hints may not apply to queries) per query
or workload can be considered as another factor to determine the complexity
and build the ensemble model.

## References

  * (1) J. Sun and G. Li. An end-to-end learning-based cost estimator. Proceedings of the VLDB Endowment, 13(3):307–319, Nov. 2019.
  * (2) P. Negi, R. Marcus, H. Mao, N. Tatbul, T. Kraska, and M. Alizadeh. Cost-Guided Cardinality Estimation: Focus Where it Matters. In Workshop on Self-Managing Databases, SMDB @ ICDE ’20, 2020.
  * (3) Ryan Marcus, Parimarjan Negi, Hongzi Mao, Nesime Tatbul, Mohammad Alizadeh, and Tim Kraska. 2021. Bao: Making Learned Query Optimization Practical. In Proceedings of the 2021 International Conference on Management of Data (SIGMOD ’21), June 20–25, 2021, Virtual Event, China. ACM, New York, NY, USA, 14 pages. https://doi.org/10.1145/3448016.3452838
  * (4) R. Marcus, P. Negi, H. Mao, C. Zhang, M. Alizadeh, T. Kraska, O. Papaemmanouil, and N. Tatbul. Neo: A Learned Query Optimizer. PVLDB, 12(11):1705–1718, 2019., doi: https://doi.org/10.14778/3342263.3342644.
  * (5) T. Kraska, M. Alizadeh, A. Beutel, Ed Chi, Ani Kristo, Guillaume Leclerc, Samuel Madden, Hongzi Mao, and Vikram Nathan. SageDB: A Learned Database System. In 9th Biennial Conference on Innovative Data Systems Research, CIDR ’19, 2019.
  * (6) Z. Yang, A. Kamsetty, S. Luan, E. Liang, Y. Duan, X. Chen, and I. Stoica. NeuroCard: One Cardinality Estimator for All Tables. PVLDB, 14(1): 61 - 73, 2021. doi:10.14778/3421424.3421432
  * (7) A. Ganapathi et al., Predicting Multiple Metrics for Queries: Better Decisions Enabled by Machine Learning. 2009 IEEE 25th International Conference on Data Engineering, Shanghai, China, 2009, pp. 592-603, doi: 10.1109/ICDE.2009.130.
  * (8) Gang Luo, Jeffrey F. Naughton, and Philip S. Yu. 2006. Multi-query SQL progress indicators. In Proceedings of the 10th international conference on Advances in Database Technology (EDBT’06). Springer-Verlag, Berlin, Heidelberg, 921–941. https://doi.org/10.1007/11687238_54
  * (9) J. Ortiz, M. Balazinska, J. Gehrke, and S. S. Keerthi. Learning State Representations for Query Optimization with Deep Reinforcement Learning. In 2nd Workshop on Data Managmeent for End-to-End Machine Learning, DEEM ’18, 2018.
  * (10) HANA SQL Hints, https://wiki.one.int.sap/wiki/display/ngdb/SQL+hints
  * (11) Benjamin Hilprecht and Carsten Binnig. 2022. Zero-shot cost models for out-of-the-box learned cost prediction. Proc. VLDB Endow. 15, 11 (July 2022), 2361–2374. https://doi.org/10.14778/3551793.3551799
  * (12) Z. Yang, E. Liang, A. Kamsetty, C. Wu, Y. Duan, X. Chen, P. Abbeel, J. M. Hellerstein, S. Krishnan, and I. Stoica. Deep unsupervised cardinality estimation. arXiv preprint arXiv:1905.04278, 2019.
  * (13) Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter A. Boncz, and Alfons Kemper. 2019. Learned Cardinalities: Estimating Correlated Joins with Deep Learning. In 9th Biennial Conference on Innovative Data Systems Research, CIDR 2019, Asilomar, CA, USA, January 13-16, 2019, Online Proceedings. www.cidrdb.org. http://cidrdb.org/cidr2019/papers/p101-kipf-cidr19.pdf
  * (14) V. Leis, B. Radke, A. Gubichev, A. Mirchev, P. Boncz, A. Kemper, and T. Neumann. Query optimization through the looking glass, and what we found running the join order benchmark. The VLDB Journal, pages 1–26, 2018.
  * (15) V. Leis, A. Gubichev, A. Mirchev, P. Boncz, A. Kemper, and T. Neumann. How Good Are Query Optimizers, Really? PVLDB, 9(3):204–215, 2015.
  * (16) JOB-m queries, https://github.com/neurocard/neurocard/tree/master/neurocard/queries
  * (17) JOB-e queries, https://github.com/RyanMarcus/imdb_pg_dataset/tree/master/job_extended
  * (18) TPC-H benchmark, http://www.tpc.org/tpch/
  * (19) Raghunath Othayoth Nambiar and Meikel Poess. 2006. The making of TPC-DS. In Proceedings of the 32nd international conference on Very large data bases (VLDB ’06). VLDB Endowment, 1049–1058.
  * (20) Boncz, P., Anatiotis, AC., Kläbe, S. (2018). JCC-H: Adding Join Crossing Correlations with Skew to TPC-H. In: Nambiar, R., Poess, M. (eds) Performance Evaluation and Benchmarking for the Analytics Era. TPCTC 2017. Lecture Notes in Computer Science(), vol 10661. Springer, Cham. https://doi.org/10.1007/978-3-319-72401-0_8
  * (21) Rong Zhu, Ziniu Wu, Yuxing Han, Kai Zeng, Andreas Pfadler, Zhengping Qian, Jingren Zhou, Bin Cui. FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation. PVLDB, pp. 1489–1502, 2021, doi:10.14778/3461535.3461539.
  * (22) Jiayi Wang, Chengliang Chai, Jiabin Liu, and Guoliang Li. FACE: A Normalizing Flow based Cardinality Estimator. PVLDB, pp. 72–84, 2022, doi:10.14778/3485450.3485458.
  * (23) Peizhi Wu and Gao Cong. 2021. A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation. In Proceedings of the 2021 International Conference on Management of Data (SIGMOD ’21). Association for Computing Machinery, New York, NY, USA, 2009–2022. https://doi.org/10.1145/3448016.3452830
  * (24) M. Stillger, G. M. Lohman, V. Markl, and M. Kandil. LEO - DB2’s LEarning Optimizer. In VLDB, VLDB’01, pages 19–28, 2001.