supp}\eta_{2}\neq\emptyset$.

###### Proof.

We shall prove the Lemma by contradiction. Suppose that ${\rm cl}I\cap{\rm
supp}\eta_{2}=\emptyset$. The idea of the proof is that at some moment, a line
dividing some $U(\beta,\beta)$ into $U(\beta+1,\beta+1)$ and
$U(\beta+1,\beta)$ lies above $I$ and cuts off only points that are above and
to the right of the left end of $I$, or almost so, and thus only cuts off
points, which do not belong to ${\rm supp}\eta_{2}$. Thus $\eta_{2}$ is zero
on the set $U(\beta+1,\beta)$ which was cut off, $\theta(U(\beta+1,\beta))=0$,
a contradiction. Now for a formal proof:

As $\theta(U(\gamma,\gamma))>0$, some point of $U(\gamma,\gamma)$ has to lie
inside ${\rm supp}\eta_{2}$, thus (as ${\rm supp}\eta_{2}$ is a c-set), the
lower left extremal point of $U(\gamma,\gamma)$ lies in ${\rm supp}\eta_{2}$.
Note, that as $\eta_{2}=0$ on $I$, $I$ has to be an upper edge, the lower edge
case is trivial here. Let $x_{2}<x_{0}$ be such that $(x_{2},y_{0})\not\in{\rm
supp}\eta_{2}$. Then let $y_{2}<y_{0}$ be a number so close to $y_{0}$ that
$(x_{2},y_{2})\not\in{\rm supp}\eta_{2}$ and $(x_{2},y_{2})\not\in
U(\gamma,\gamma)$. Take a $\beta<\gamma$ such that $(x_{2},y_{2})\not\in
U(\beta,\beta)$. As $U(\beta,\beta)$ is a lens set, no points $(x_{2},y)$ with
$y>y_{2}$ belong to $U(\beta,\beta)$.

As $U(\beta,\beta)$ is a strict lens set, and $I\subset U(\beta,\beta)$, there
exists a $y_{3}>y_{0}$ such that $(x_{1},y_{3})\in U(\beta,\beta)$. Take
$y_{3}$ to be so small that

$\frac{y_{3}-y_{0}}{x_{1}-x_{0}}<\frac{y_{0}-y_{2}}{x_{0}-x_{2}}.$ (6.3.1)

Let $\beta^{\prime}$ be the smallest such ordinal that $(x_{1},y_{3})\not\in
U(\beta^{\prime},\beta^{\prime})$. Of course $\beta^{\prime}>\beta$ and from
the inductive assumption $\beta^{\prime}$ is a successor ordinal.

Let $L$ be the line which divides $U(\beta^{\prime}-1,\beta^{\prime}-1)$ into
$U(\beta^{\prime},\beta^{\prime})$ and $U(\beta^{\prime},\beta^{\prime}-1)$.
$L$ intersects the interval $[(x_{1},y_{0}),(x_{1},y_{3})]$ and does not
intersect $I$, so, from (6.3.1), $L$ intersects the line $x=x_{2}$ at some
point above $(x_{2},y_{2})$. $U(\beta^{\prime},\beta^{\prime}-1)\subset
U(\beta^{\prime}-1,\beta^{\prime}-1)\subset U(\beta,\beta)$, thus
$U(\beta^{\prime},\beta^{\prime}-1)$ contains no points $(x_{2},y)$ with
$y>y_{2}$. Thus all points from $U(\beta^{\prime},\beta^{\prime}-1)$ lie above
and to the right of $(x_{2},y_{2})$. As ${\rm supp}\eta_{2}$ is a c-set and
$(x_{2},y_{2})\not\in{\rm supp}\eta_{2}$, we have
$U(\beta^{\prime},\beta^{\prime}-1)\cap{\rm supp}\eta_{2}=\emptyset$, thus
$\theta(U(\beta^{\prime},\beta^{\prime}-1))=0$. But as we assumed
$\theta(K)>0$ this means that $U(\beta^{\prime},\beta^{\prime}-1)$ is empty, a
contradiction. ∎

Thus we know that ${\rm cl}I\cap{\rm supp}\eta_{2}\neq\emptyset$, and as ${\rm
Int}\ {\rm supp}\eta_{1}\supset{\rm supp}\eta_{2}$, there is an interval
$I^{\prime}\subset I\cap\tilde{K}_{+}$ of positive length, which means
$\theta_{n-1}(y_{0};I\times{\mathbb{R}}^{n-2})$ is defined. The idea of the
proof in this case is to prove that
$\theta_{n-1}(y_{0};I\times{\mathbb{R}}^{n-2})=\theta(K)$, which from Lemma
4.33 and Lemma 5.6 will imply $U(\gamma,\gamma)$ is appropriate. We prove this
by selecting a moment at which the set $U(\beta+1,\beta)$ which is being cut
off lies above $I$, and comparing its $\theta$ (which we know to be
$\theta(K)$) to $\theta_{n-1}(x_{0};I\times{\mathbb{R}}^{n-2})$. The formal
proof goes as follows:

We assume $I$ is an upper horizontal edge. In the case of $I$ being a lower
horizontal edge, the below construction works centrally-symetrically.Recall
$(x_{0},y_{0})$ be the left end of $I$ and $(x_{1},y_{0})$ the right end. Take
any $0<{\varepsilon}<|I|$. Take $x_{2}=x_{0}-{\varepsilon}$ and $y_{2}<y_{0}$
and close enough that $(x_{2},y_{2})\not\in U(\gamma,\gamma)$. Take
$\beta_{1}<\gamma$ such that $(x_{2},y_{2})\not\in U(\beta_{1},\beta_{1})$.
Next take a point $(x_{1},y_{3})$ with $y_{3}>y_{0}$ such that (6.3.1) is
satisfied, and take $\gamma>\beta_{2}>\beta_{1}$ such that the upper extremal
point of $U(\beta_{2},\beta_{2})$ lies below $y_{3}$. Again, as in the proof
of Lemma 6.2, any line dividing some $U(\beta,\beta)$ for $\beta>\beta_{2}$
and crossing $x=x_{1}$ between $y_{3}$ and $y_{0}$ will exit $U(\beta,\beta)$
at some $x>x_{2}$. For $\gamma>\beta>\beta_{2}$ any line cutting off the upper
extremal point $p$ of $U(\beta,\beta)$ will cross $x=x_{1}$ between $y_{3}$
and $y_{0}$ because $p$ will lie below $y_{3}$ (as $U(\beta,\beta)\subset
U(\beta_{2},\beta_{2})$ and to the right of and above $(x_{1},y_{0})$ as
$U(\beta,\beta)\subset U(\gamma,\gamma)$ and the line has to go below $p$ and
above $(x_{1},y_{0})$ as $(x_{1},y_{0})\in U(\beta,\beta)$.

Let us consider the functions
${\tilde{\eta}}_{i}(x,y)=\int_{{\mathbb{R}}^{n-2}}\eta_{i}(x,y,t)dt$ for
$i=1,2$. The set $[x_{-},x_{+}]\times[y_{-},y_{+}]$ is compact and
${\tilde{\eta}}_{i}$ are continuous from property (S4) (recall $n>2$), thus we
can find a $\tilde{\delta}>0$ such that

$\|p_{1}-p_{2}\|<\tilde{\delta}\ \ {\Rightarrow}\ \
|{\tilde{\eta}}_{i}(p_{1})-{\tilde{\eta}}_{i}(p_{2})|<{\varepsilon}$

for $i=1,2$. Also, as $g$ (the density of $\mu$ with respect to $y$) is
$1/m$-concave, it is continuous on the interior of its support, and thus we
can take $\tilde{\delta}$ such that also $|g(p_{1})-g(p_{2})|<{\varepsilon}$.

If ${\tilde{\eta}}_{1}((x_{1},y_{0}))>0$ take $\delta=\tilde{\delta}$. If not,
then as ${\rm Int}\tilde{K}_{+}\supset{\rm supp}{\tilde{\eta}}_{2}$, there
exists an interval $J^{\prime}\subset I\cap({\rm
Int}\tilde{K}_{+}\setminus{\rm supp}{\tilde{\eta}}_{2})$ of positive length
$c$. As ${\mathbb{R}}_{x}\times{\mathbb{R}}_{y}\setminus{\rm
Int}\tilde{K}_{+}$ and ${\rm supp}{\tilde{\eta}}_{2}$ are closed, we may take
$\delta\leq\tilde{\delta}$ small enough, that there exists an interval
$J\subset I$ of length at least $c/2$, such that

$J\times[y_{0}-\delta,y_{0}+\delta]\subset{\rm Int}\tilde{K}_{+}\setminus{\rm
supp}{\tilde{\eta}}_{2}.$

Take $\gamma>\beta_{3}>\beta_{2}$ such that the whole set
$U(\beta_{3},\beta_{3})$ lies below the line $y=y_{0}+\delta$.

Now let $(x_{4},y_{4})$ be the upper right extremal point of
$U(\beta_{3},\beta_{3})$. Let $\beta_{4}$ be the first $\beta$ such that
$(x_{4},y_{4})\not\in U(\beta_{4},\beta_{4})$. The ordinal $\beta_{4}$ has to
be a successor, let $L^{\prime}$ be the line dividing
$U(\beta_{4}-1,\beta_{4}-1)$ into $U(\beta_{4},\beta_{4}-1)$ and
$U(\beta_{4},\beta_{4})$, and let $l$ be the inclination of $L^{\prime}$. Any
tangent to the upper-left border of $U(\beta_{4},\beta_{4})$ has inclination
no smaller than $l$. Let $\beta_{5}$ be the first ordinal greater than
$\beta_{4}$ for which some tangent to the upper left edge of
$U(\beta_{5},\beta_{5})$ has inlination strictly smaller than $l$. Again,
$\beta_{5}$ has to be a successor ordinal. Let $L$ be the line dividing
$U(\beta_{5}-1,\beta_{5}-1)$ into $U(\beta_{5},\beta_{5}-1)$ and
$U(\beta_{5},\beta_{5})$. This line has to go above $I$, to become a part of
the upper edge of $U(\beta_{5},\beta_{5})$. As the inclination of this line is
smaller than the inclination of any tangent to the upper left edge of
$U(\beta_{5}-1,\beta_{5}-1)$, the right end of $L\cap
U(\beta_{5}-1,\beta_{5}-1)$ lies on the lower right edge of
$U(\beta_{5}-1,\beta_{5}-1)$. It lies above $y_{0}$, as it goes above $I$ and
has positive inclination, and lies to the right of $x_{1}$, as the lower right
edge of $u(\beta_{5}-1,\beta_{5}-1)$ above $y_{0}$ lies to the right of
$x_{1}$.

Now we will prove some inequalities on $\theta$. In the case of $I$ being
lower edge, the inequalities are simply reversed. Let
${\tilde{D}}={\tilde{D}}({\varepsilon})$ be the part of
$U(\beta_{5},\beta_{5}-1)$ that lies to the left of $x=x_{1}$. As usual,
$D=D({\varepsilon})={\tilde{D}}({\varepsilon})\times{\mathbb{R}}^{n-2}$. As
$U(\beta_{5},\beta_{5}-1)$ is a lens set, from Lemma 4.33 we know

$\theta({\tilde{D}}\times{\mathbb{R}}^{n-2})\leq\theta(U(\beta_{5},\beta_{5}-1)\times{\mathbb{R}}^{n-2})=\theta(K).$

Remark that the line $L^{\prime\prime}$ that cut $(\beta_{5},\beta_{5}-1)$ off
contains the whole lower edge of ${\tilde{D}}$. Thus as the inclination of
$L^{\prime\prime}$ is smaller than the inclination of the upper edge of
${\tilde{D}}$ the function $x\mapsto\lambda_{1}({\tilde{D}}_{x})$, where
${\tilde{D}}_{x}$ is the section of ${\tilde{D}}$ at $x$, is strictly
increasing.

If ${\tilde{D}}$ has $\mu_{2}$ measure 0, then the lower extremal point
$p_{5}$ of $U(\beta_{5},\beta_{5}-1)$ lies above and to the right of any point
of $U(\gamma,\gamma)$. However, from property (T4)

$\theta_{n-2}(p_{5})\leq\theta(U(\beta_{5},\beta_{5}-1)\times{\mathbb{R}}^{n-2})=\theta(K),$

which means that from property (T4) for any point $p\in U(\gamma,\gamma)$ we
have

$\theta_{n-2}(p)\leq\theta_{n-2}(p_{5})\leq\theta(K).$

However, we know $\theta(U(\gamma,\gamma)\times{\mathbb{R}}^{n-2})=\theta(K)$,
which, from Fact 2.5 implies that for almost all points in $U(\gamma,\gamma)$
we have $\theta_{n-2}(p)=\theta(K)$. Thus any horizontal line divides
$U(\gamma,\gamma)$ into two sets with equal $\theta$, which from Lemma 5.6
implies $U(\gamma,\gamma)$ is appropriate. Hereafter we shall assume
$\mu_{2}({\tilde{D}})>0$.

Note that the whole set ${\tilde{D}}$ lies in the rectangle
$[x_{2},x_{1}]\times[y_{0}-\delta,y_{0}+\delta]$. It lies to the left of
$x_{1}$ from its definition. To the right of $x_{2}$ as $\beta_{5}>\beta_{2}$.
Below $y_{0}+\delta$ because $\beta_{5}>\beta_{3}$. Above $y_{0}-\delta$
because its lower edge is the line $L^{\prime\prime}$ which passes above
$(x_{0},y_{0})$, so if it dipped below $y_{0}-\delta$, it would also (as
${\varepsilon}<|I|$) have to reach above $y_{0}+\delta$.

Now we want to estimate $\theta_{n-1}(y_{0};I\times{\mathbb{R}}^{n-2})$ by
$\theta({\tilde{D}}\times{\mathbb{R}}^{n-2})$. This will, unfortunately,
involve quite a lot of technicalities. We begin with a lemma:

######  Lemma 6.3.

There exist two numbers $c_{1},c_{2}>0$ independent of ${\varepsilon}$ such
that for sufficiently small ${\varepsilon}>0$ and a set ${\tilde{D}}$
constructed as above for this ${\varepsilon}$ we have

$\lambda_{2}({\tilde{D}}\cap\\{(x,y):{\tilde{\eta}}_{i}(x,y)>c_{1}\\})>c_{2}\lambda_{2}({\tilde{D}}),$

for $i=1,2$.

###### Proof.

The proof for this lemma is a bit different for $I$ being a lower edge. First,
let us prove it for an upper edge.

First we prove the thesis for ${\tilde{\eta}}_{1}$. Suppose
${\tilde{\eta}}_{1}(x_{1},y_{0})>0$. Then supposing
${\varepsilon}<\frac{1}{2}{\tilde{\eta}}_{1}(x_{1},y_{0})$ for any
$(x,y)\in{\tilde{D}}$ we have

${\tilde{\eta}}_{1}(x,y)\geq{\tilde{\eta}}_{1}(x_{1},y)\geq{\tilde{\eta}}_{1}(x_{1},y_{0})-{\varepsilon}>\frac{1}{2}{\tilde{\eta}}_{1}(x_{1},y_{0}),$

as $|y-y_{0}|<\delta$ and ${\tilde{\eta}}_{1}$ is decreasing as $\eta_{1}$ is
decreasing, thus it is enough to have
$c_{1}<\frac{1}{2}{\tilde{\eta}}_{1}(x_{1},y_{0})$ and $c_{2}<1$.

In the case ${\tilde{\eta}}_{1}(x_{1},y_{0})=0$ let
$b_{1}=\sup\\{x:{\tilde{\eta}}_{1}(x,y_{0})>0\\}$. Recall that we constructed
an interval $J$ of length $c$ (independent of ${\varepsilon}$) such that
$J\times[y_{0}-\delta,y_{0}+\delta]\subset{\rm
supp}{\tilde{\eta}}_{1}\setminus{\rm supp}{\tilde{\eta}}_{2}$. Let
$J=[j_{0},j_{1}]$. Now as
${\tilde{D}}\subset[x_{2},x_{1}]\times[y_{0}-\delta,y_{0}+\delta]$ for $x\in
J$ and $(x,y)\in{\tilde{D}}$ we have ${\tilde{\eta}}_{2}(x,y)=0$ and
${\tilde{\eta}}_{1}(x,y)>0$, which means $j_{2}\leq b_{1}$. On the other hand
$\theta({\tilde{D}})\geq\theta(K)>0$, thus ${\tilde{D}}$ contains points with
positive $\eta_{2}$, and thus for these points $(x,y)$ we have $x<j_{0}$. Note
that as $\lambda_{1}({\tilde{D}}_{x})$ is strictly increasing, so if
${\tilde{D}}$ condains some point to the left of $j_{0}$, then for every $x\in
J$ the set ${\tilde{D}}_{x}$ has positive Lebesgue measure.

Let $j=\frac{j_{0}+j_{1}}{2}$ be the midpoint of $J$. If
${\varepsilon}<\frac{1}{2}{\tilde{\eta}}_{1}(j,y_{0})$ we have

$\displaystyle\lambda_{2}\Bigg{(}{\tilde{D}}\cap\Big{\\{}(x,y):{\tilde{\eta}}_{1}(x,y)>\frac{1}{2}{\tilde{\eta}}_{1}(j,y_{0})\Big{\\}}\Bigg{)}$
$\displaystyle\geq\lambda_{2}\Bigg{(}\Big{\\{}(x,y)\in{\tilde{D}}:{\tilde{\eta}}_{1}(x,y_{0})\geq{\tilde{\eta}}_{1}(j,y_{0})\Big{\\}}\Bigg{)}$
$\displaystyle\geq\lambda_{2}\Big{(}\big{\\{}(x,y)\in{\tilde{D}}:x<j\big{\\}}\Big{)}.$

Now we perform a similar operation as in Lemma 5.8. The function
$p(x)=\lambda({\tilde{D}}_{x})$ is concave on its support, $p(j_{0})\geq 0$,
thus for every $t\in[0,1]$ we have $p((1-t)j_{0}+tj)\geq tp(j)$ and for $t>1$
we have $p((1-t)j_{0}+tj)\leq tp(j)$. Thus

$\lambda_{2}\Big{(}\\{(x,y)\in{\tilde{D}}:x<j\\}\Big{)}=\int_{x<j}p(x)\geq|j-j_{0}|\int_{0}^{1}tp(j)=\frac{j-j_{0}}{2}p(j).$

In a similar vein

$\lambda_{2}\Big{(}\\{x,y)\in{\tilde{D}}:x\geq j\\}\Big{)}=\int_{x\geq
j}p(x)\leq|j-j_{0}|\int_{1}^{\frac{x_{1}-j_{0}}{j-j_{0}}}tp(j)=\frac{j-j_{0}}{2}\Bigg{(}\frac{(x_{1}-j_{0})^{2}}{(j-j_{0})^{2}}-1\Bigg{)}p(j),$

which gives us:

$\frac{\lambda_{2}({\tilde{D}})}{\lambda_{2}({\tilde{D}}\cap\\{(x,y):{\tilde{\eta}}_{i}(x,y)>\frac{1}{2}{\tilde{\eta}}_{1}(j,y_{0})\\})}\leq
1+\frac{\lambda_{2}(\\{x,y)\in{\tilde{D}}:x\geq
j\\})}{\lambda_{2}(\\{x,y)\in{\tilde{D}}:x<j\\})}\leq
1+\frac{(x_{1}-j_{0})^{2}}{(j-j_{0})^{2}}-1=\frac{(x_{1}-j_{0})^{2}}{(j-j_{0})^{2}},$

which gives the thesis for $c_{1}\leq\frac{1}{2}{\tilde{\eta}}_{1}(j,y_{0})$
and $c_{2}\leq\frac{(j-j_{0})^{2}}{(x_{1}-j_{0})^{2}}$.

To deal with ${\tilde{\eta}}_{2}$ first use Remark 6.1 to get

$\int_{\tilde{D}}{\tilde{\eta}}_{2}(x,y)d\mu_{2}(x,y)=\theta({\tilde{D}}\times{\mathbb{R}}^{n-2})\int_{{\tilde{D}}}{\tilde{\eta}}_{1}(x,y)d\mu_{2}(x,y)\geq\theta(K)c_{1}c_{2}f_{L}g_{L}\lambda_{2}({\tilde{D}}).$

On the other hand ${\tilde{\eta}}_{2}$ is bounded from above on ${\rm
supp}{\tilde{\eta}}_{2}$ by $M={\tilde{\eta}}_{2}(0,0)$, as it is continuous.
We have

$\displaystyle f_{L}g_{L}c_{1}c_{2}\theta(K)\lambda_{2}({\tilde{D}})$
$\displaystyle\leq\int_{D}{\tilde{\eta}}_{2}(x,y)d\mu_{2}(x,y)\leq
f_{U}g_{U}\int_{D}{\tilde{\eta}}_{2}(x,y)d\lambda_{2}$ $\displaystyle\leq
f_{U}g_{U}\big{(}M\lambda_{2}({\tilde{D}}\cap\\{{\tilde{\eta}}_{2}(x,y)>a\\})+a\lambda({\tilde{D}})\big{)}.$

The above holds for any $a$. Let us take
$2a=\frac{c_{1}c_{2}\theta(K)f_{L}g_{L}}{f_{U}g_{U}}$. Then we have

$\lambda_{2}({\tilde{D}}\cap\\{{\tilde{\eta}}_{2}(x,y)>a\\})\geq
a\lambda_{2}({\tilde{D}})/M,$

which implies (with the assumption ${\varepsilon}<a/2$)

$\lambda({\tilde{D}}\cap\\{{\tilde{\eta}}_{2}(x,y_{0})>a/2\\})\geq\lambda({\tilde{D}}\cap\\{{\tilde{\eta}}_{2}(x,y_{0})>a-{\varepsilon}\\})\geq(a/M)\lambda(D).$

Now, let us assume that $I$ is a lower horizontal edge. The proof is much
easier in that case. Since $\theta(U(\gamma,\gamma))>0$, there is a segment
$I^{\prime}\subset I$ starting at lower left end of $I$, such that
$I^{\prime}\subset{\rm supp}{\tilde{\eta}}_{2}$. Moreover, we can take such
$I^{\prime\prime}\subset I^{\prime}$, that on $I^{\prime\prime}$ we have
${\tilde{\eta}}_{2}>c$ for some $c$. Since $x\to\lambda({\tilde{D}}_{x})$ is
decreasing on $I$, we have

$\lambda_{2}({\tilde{D}}\cap\\{(x,y):{\tilde{\eta}}(x,y)>c\\})\geq\lambda_{2}({\tilde{D}}\cap
I^{\prime\prime}\times{\mathbb{R}})\geq\lambda_{2}({\tilde{D}})\frac{|I^{\prime\prime}|}{|I|}.$

∎

######  Corollary 6.4.

There exists a constant $c_{3}$ such that for all sufficiently small
${\varepsilon}$ we have

$\int_{\tilde{D}}{\tilde{\eta}}_{i}(x,y)d\mu_{2}(x,y)\geq
c_{3}\mu_{2}({\tilde{D}}).$

###### Proof.

$\int_{\tilde{D}}{\tilde{\eta}}_{i}(x,y)d\mu_{2}\geq\int_{\tilde{D}}{\tilde{\eta}}_{i}(x,y){\mathbf{1}}_{{\tilde{\eta}}_{i}(x,y)>c_{1}}d\mu_{2}\geq
c_{1}c_{2}\lambda_{2}({\tilde{D}})\geq
c_{1}c_{2}f_{L}g_{L}\mu_{2}({\tilde{D}}).$

∎

The rest of the proof is independent of the fact, whether $I$ is lower or
upper edge, we simply use already proven facts.

Now to estimate $\theta(D({\varepsilon}))$. As $\beta_{5}>\beta_{2}$ we know
$\|(x,y)-(x,y_{0})\|<\delta$, thus
$|{\tilde{\eta}}_{i}(x,y)-{\tilde{\eta}}_{i}(x,y_{0})|<{\varepsilon}$. Thus we
get:

$\displaystyle\theta(D({\varepsilon}))$
$\displaystyle=\frac{\int_{{\tilde{D}}({\varepsilon})}{\tilde{\eta}}_{2}(x,y)d\mu_{2}(x,y)}{\int_{{\tilde{D}}({\varepsilon})}{\tilde{\eta}}_{1}(x,y)d\mu_{2}(x,y)}\leq\frac{\int_{{\tilde{D}}({\varepsilon})}{\tilde{\eta}}_{2}(x,y_{0})+{\varepsilon}d\mu_{2}(x,y)}{\int_{{\tilde{D}}({\varepsilon})}{\tilde{\eta}}_{1}(x,y_{0})-{\varepsilon}d\mu_{2}(x,y)}$
$\displaystyle=\frac{\int_{{\tilde{D}}({\varepsilon})}{\tilde{\eta}}_{2}(x,y_{0})+{\varepsilon}d\mu_{2}(x,y)}{\int_{{\tilde{D}}({\varepsilon})}{\tilde{\eta}}_{2}(x,y_{0})d\mu_{2}(x,y)}\cdot\frac{\int_{{\tilde{D}}({\varepsilon})}{\tilde{\eta}}_{1}(x,y_{0})d\mu_{2}(x,y)}{\int_{{\tilde{D}}({\varepsilon})}{\tilde{\eta}}_{1}(x,y_{0})-{\varepsilon}d\mu_{2}(x,y)}\cdot\frac{\int_{{\tilde{D}}({\varepsilon})}{\tilde{\eta}}_{2}(x,y_{0})d\mu_{2}(x,y)}{\int_{{\tilde{D}}({\varepsilon})}{\tilde{\eta}}_{1}(x,y_{0})d\mu_{2}(x,y)}.$

The first and second fraction will both be bounded by 1 as
${\varepsilon}{\rightarrow}0$ from Corollary 6.4:

$\displaystyle\frac{\int_{{\tilde{D}}({\varepsilon})}{\tilde{\eta}}_{2}(x,y_{0})+{\varepsilon}\
d\mu_{2}(x,y)}{\int_{{\tilde{D}}({\varepsilon})}{\tilde{\eta}}_{2}(x,y_{0})d\mu_{2}(x,y)}-1=\frac{{\varepsilon}\int_{{\tilde{D}}({\varepsilon})}d\mu_{2}(x,y)}{\int_{{\tilde{D}}({\varepsilon})}{\tilde{\eta}}_{2}(x,y_{0})d\mu_{2}(x,y)}\leq\frac{{\varepsilon}\mu_{2}({\tilde{D}}({\varepsilon}))}{\int_{{\tilde{D}}({\varepsilon})}{\tilde{\eta}}_{2}(x,y)-{\varepsilon}\
d\mu_{2}(x,y)}=\frac{{\varepsilon}}{c_{3}-{\varepsilon}},$

and (here we prove that the lower bound for the reciprocal converges to 1,
which is equivalent)

$\displaystyle\frac{\int_{{\tilde{D}}({\varepsilon})}{\tilde{\eta}}_{1}(x,y_{0})-{\varepsilon}\
d\mu_{2}(x,y)}{\int_{{\tilde{D}}({\varepsilon})}{\tilde{\eta}}_{1}(x,y_{0})d\mu_{2}(x,y)}-1=\frac{-{\varepsilon}\int_{{\tilde{D}}({\varepsilon})}d\mu_{2}(x,y)}{\int_{{\tilde{D}}({\varepsilon})}{\tilde{\eta}}_{1}(x,y_{0})d\mu_{2}(x,y)}\geq\frac{-{\varepsilon}\mu_{2}({\tilde{D}}({\varepsilon}))}{\int_{{\tilde{D}}({\varepsilon})}{\tilde{\eta}}_{1}(x,y)-{\varepsilon}\
d\mu_{2}(x,y)}=\frac{-{\varepsilon}}{c_{3}-{\varepsilon}}.$

The third fraction is the one that should converge to (or at least, for very
small ${\varepsilon}$, be bounded by)
$\theta_{n-1}(y_{0};I\times{\mathbb{R}}^{n-2})$. Let
$I_{\varepsilon}=[x_{0}-{\varepsilon},x_{1}]=[x_{2},x_{1}]$. As
$\|(x,y)-(x,y_{0})\|<\delta$, we have:

$\displaystyle\frac{\int_{{\tilde{D}}({\varepsilon})}{\tilde{\eta}}_{2}(x,y_{0})d\mu_{2}(x,y)}{\int_{{\tilde{D}}({\varepsilon})}{\tilde{\eta}}_{1}(x,y_{0})d\mu_{2}(x,y)}=\frac{\int_{I_{\varepsilon}}\int_{{\tilde{D}}_{x}({\varepsilon})}{\tilde{\eta}}_{2}(x,y_{0})f(x)g(y)dxdy)}{\int_{I_{\varepsilon}}\int_{{\tilde{D}}_{x}({\varepsilon})}{\tilde{\eta}}_{1}(x,y_{0})f(x)g(y)dxdy)}\leq\frac{g(y_{0})+{\varepsilon}}{g(y_{0})-{\varepsilon}}\cdot\frac{\int_{I_{\varepsilon}}{\tilde{\eta}}_{1}(x,y_{0})f(x)\lambda({\tilde{D}}_{x})dx}{\int_{I_{\varepsilon}}{\tilde{\eta}}_{2}(x,y_{0})f(x)\lambda({\tilde{D}}_{x})dx}.$

The first of these fractions obviously tends to $1$ as $g(y_{0})\geq g_{L}>0$.
The second can be bounded using Lemma 2.3, part 3:

$\displaystyle\frac{\int_{I_{\varepsilon}}{\tilde{\eta}}_{1}(x,y_{0})f(x)\lambda({\tilde{D}}_{x})dx}{\int_{I_{\varepsilon}}{\tilde{\eta}}_{2}(x,y_{0})f(x)\lambda({\tilde{D}}_{x})dx}\leq\frac{\int_{I_{\varepsilon}}{\tilde{\eta}}_{1}(x,y_{0})f(x)dx}{\int_{I_{\varepsilon}}{\tilde{\eta}}_{2}(x,y_{0})f(x)dx}=\frac{\int_{I_{\varepsilon}}{\tilde{\eta}}_{1}(x,y_{0})f(x)g(y_{0})dx}{\int_{I_{\varepsilon}}{\tilde{\eta}}_{2}(x,y_{0})f(x)g(y_{0})dx}=\theta_{n-1}(y_{0};I_{\varepsilon}\times{\mathbb{R}}^{n-2})$

From property (T5) used for restrictions to $y=y_{0}$ we have
$\theta_{n-1}(y_{0};I_{\varepsilon}\times{\mathbb{R}}^{n-2}){\rightarrow}\theta_{n-1}(y_{0};I\times{\mathbb{R}}^{n-2})$
when ${\varepsilon}{\rightarrow}0$.

Putting all the estimates together we get
$\theta(K)\leq\theta(D({\varepsilon}))\leq
c({\varepsilon})\theta_{n-1}(y_{0};I\times{\mathbb{R}}^{n-2})$, where
$c({\varepsilon}){\rightarrow}1$. Thus we can go with ${\varepsilon}$ to 0 to
get $\theta(K)\leq\theta_{n-1}(y_{0};I\times{\mathbb{R}}^{n-2})$. On the other
hand from Lemma 4.33 we have
$\theta_{n-1}(y_{0};I\times{\mathbb{R}}^{n-2})\leq\theta(U(\gamma,\gamma))=\theta(K)$,
which means $\theta_{n-1}(y_{0};I\times{\mathbb{R}}^{n-2})=\theta(K)$. From
Lemma 4.32 this means that for any horizontal line $L$ intersecting
$U(\gamma,\gamma)$ we have $\theta(I)\leq\theta(U(\gamma,\gamma)\cap L)$,
which, from Lemma 4.33 implies that any horizontal line divides
$U(\gamma,\gamma)$ into two sets with equal $\theta$. Thus, from Lemma 5.6,
$U(\gamma,\gamma)$ is appropriate.

This finishes the proof of the inductive step in the limit ordinal case: the
assumption $U(\gamma,\gamma)$ has positive measure and is not a strict lens
set led us to the conclusion it is appropriate.

##  7 $\Theta$ functions on Orlicz balls

Our main target is proving Theorem 1.2:

Due to Lemma 2.1 we need to prove inequality (2.1.1) for any c-sets
$A\subset{\mathbb{R}}^{k}$ and $B\subset{\mathbb{R}}^{n-k}$. We shall attempt
to prove (2.1.1) using Theorem 5.1.

###  7.1 The one-dimensional case — the $\phi$ functions

First we need to apply the Brunn-Minkowski theorem to get a $\Theta$-like
condition:

######  Lemma 7.1.

Let $K\subset{\mathbb{R}}_{x}\times{\mathbb{R}}_{y}\times{\mathbb{R}}^{n-2}$
be a generalized Orlicz ball. Let $0\leq x_{1}\leq x_{2}\in{\mathbb{R}}_{x}$,
$0\leq y_{1}\leq y_{2}\in{\mathbb{R}}_{y}$. Let
$K_{x_{i},y_{j}}=K\cap(\\{(x_{i},y_{j})\\}\times{\mathbb{R}}^{n-2})$ for
$i,j\in\\{1,2\\}$. Let $\nu$ be a log-concave measure on ${\mathbb{R}}^{n-2}$.
Then

$\nu(K_{x_{1},y_{1}})\cdot\nu(K_{x_{2},y_{2}})\leq\nu(K_{x_{1},y_{2}})\cdot\nu(K_{x_{2},y_{1}}).$

###### Proof.

Let $f_{i}$, $i=1,2,\ldots,n$ be the Young functions of $K$, with $f_{1}$
defined on ${\mathbb{R}}_{x}$ and $f_{2}$ on ${\mathbb{R}}_{y}$. Let us
consider the generalized Orlicz ball $K^{\prime}\in{\mathbb{R}}^{n-1}$, with
the Young functions $\Phi_{i}=f_{i+1}$ for $i>1$ and $\Phi_{1}(t)=t$ — that
is, we replace the first two functions with a single identity function.

For any $x\in{\mathbb{R}}$ let $P_{x}$ denote the set
$K^{\prime}\cap(\\{x\\}\times{\mathbb{R}}^{n-2})$, and $|P_{x}|=\nu(P_{x})$.
As $K^{\prime}$ is a convex set, from the Brunn-Minkowski inequality (see for
instance [Ga02]) the function $x\mapsto|P_{x}|$ is a log-concave function,
which means that for any $t\in[0,1]$ we have

$|P_{tx+(1-t)y}|\geq|P_{x}|^{t}|P_{y}|^{1-t}.$

In particular, for given real non-negative numbers $a,b,c$ we have

$|P_{a+c}|\geq|P_{a}|^{b/(b+c)}|P_{a+b+c}|^{c/(b+c)},$
$|P_{a+b}|\geq|P_{a}|^{c/(b+c)}|P_{a+b+c}|^{b/(b+c)},$

and as a consequence when we multiply the two inequalities,

$|P_{a+b}|\ |P_{a+c}|\geq|P_{a}|\ |P_{a+b+c}|.$ (7.1.1)

Now let us take $a=f_{1}(x_{1})+f_{2}(y_{1})$, $b=f_{1}(x_{2})-f_{1}(x_{1})$
and $c=f_{2}(y_{2})-f_{2}(y_{1})$. As the Young functions are non-negative and
increasing on $[0,\infty)$, the numbers $a,b,c$ are non-negative. From the
definitions above we have:

$K_{x_{1},y_{1}}=\\{(z_{3},\ldots,z_{n})\in{\mathbb{R}}^{n-2}:f_{1}(x_{1})+f_{2}(y_{1})+\sum_{i=3}^{n}f_{i}(z_{i})\leq
1\\}=\\{(z_{i})_{i=3}^{n}:\Phi_{1}(a)+\sum_{i=3}^{n}\Phi_{i-1}(z_{i})\leq
1\\}=P_{a}.$

Similarily we have $K_{x_{2},y_{1}}=P_{a+b}$, $K_{x_{1},y_{2}}=P_{a+c}$ and
$K_{x_{2},y_{2}}=P_{a+b+c}$. Substituting those values into inequality (7.1.1)
we get the thesis. ∎

First we consider $K\subset{\mathbb{R}}^{n-1}\times{\mathbb{R}}_{z}$. Take any
$z_{2}>z_{1}>0$ and consider any c-set $B$ in ${\mathbb{R}}^{n-1}$. We define
$\phi_{1}(x)={\mathbf{1}}_{K}(x,z_{1})$ and
$\phi_{2}(x)={\mathbf{1}}_{K}(x,z_{2})$ for $x\in{\mathbb{R}}^{n-1}$. Let
$K_{+}^{\prime}=(K_{+})_{z=z_{1}}$. By Lemma 4.19 $K_{+}^{\prime}$ is a
positive quadrant of some generalized Orlicz ball $K^{\prime}$.

######  Lemma 7.2.

If $\bar{K}^{\prime}$ is a derivative of $K^{\prime}$, then there exists a
generalized Orlicz ball $\bar{K}$ such that $\phi_{j}(x)$ on
$\bar{K}^{\prime}$ is equal to ${\mathbf{1}}_{\bar{K}}(x,z_{j})$ for
$j\in\\{1,2\\}$.

###### Proof.

We have a sequence
$K^{\prime}=K_{0}^{\prime},K_{1}^{\prime},\ldots,K_{m}^{\prime}=\bar{K}^{\prime}$
where $K_{i+1}^{\prime}$ is some restriction of $K_{i}^{\prime}$. We can,
taking identical restrictions (that is, restrictions to hyperplanes defined by
the same equations or to the same intervals with respect to the same
variables), construct a sequence $K=K_{0},K_{1},\ldots,K_{m}=\bar{K}$ such
that $K_{i}^{\prime}=(K_{i})_{z=z_{1}}$. As $z$ was not a variable of
${\mathbb{R}}^{n-1}$ of which $K^{\prime}$ was a subset, on each step being a
hyperplane restriction $z$ does not appear in the equation of the restriction
hyperplane, thus we can speak of a $z$ variable in all $K_{i}$, and the
isometric immersion $u:\bar{K}\hookrightarrow K$ maps $(\bar{K})_{z=z_{j}}$
into $K_{z=z_{j}}$. Thus
${\mathbf{1}}_{\bar{K}}(x,z_{j})={\mathbf{1}}_{K}(u(x,z_{j}))$, which (when,
as always, we identify $\bar{K}$ with its image in $K$) gives the thesis. ∎

######  Lemma 7.3.

For any generalized Orlicz ball
$K\subset{\mathbb{R}}^{m-1}\times{\mathbb{R}}_{z}$, any $z_{2}>z_{1}>0$, any
coordinate-wise decomposition
${\mathbb{R}}^{m-1}={\mathbb{R}}^{k}\times{\mathbb{R}}^{m-k-1}$ and any proper
measure $\mu$ on $K^{\prime}=K_{z=z_{1}}$ the function

$\theta^{1}_{k}(y)=\frac{\int_{{\mathbb{R}}^{k}}{\mathbf{1}}_{K}(x,y,z_{2})d\mu_{|{\mathbb{R}}^{k}}(x)}{\int_{{\mathbb{R}}^{k}}{\mathbf{1}}_{K}(x,y,z_{1})d\mu_{|{\mathbb{R}}^{k}}(x)}$

is coordinate-wise decreasing on ${\mathbb{R}}^{m-k-1}$.

###### Proof.

Let $l=m-k-1$. Select any coordinate variable $y_{i}$ from ${\mathbb{R}}^{l}$
and fix all other variables $\mathbf{y}$ in ${\mathbb{R}}^{l}$ at some
$\mathbf{y}_{0}$. For $y_{1}\leq y_{2}$ we have to prove

$\frac{\int_{{\mathbb{R}}^{k}}{\mathbf{1}}_{K}(x,\mathbf{y}_{0},y_{1},z_{2})d\mu_{|{\mathbb{R}}^{k}}(x)}{\int_{{\mathbb{R}}^{k}}{\mathbf{1}}_{K}(x,\mathbf{y}_{0},y_{1},z_{1})d\mu_{|{\mathbb{R}}^{k}}(x)}\geq\frac{\int_{{\mathbb{R}}^{k}}{\mathbf{1}}_{K}(x,\mathbf{y}_{0},y_{2},z_{2})d\mu_{|{\mathbb{R}}^{k}}(x)}{\int_{{\mathbb{R}}^{k}}{\mathbf{1}}_{K}(x,\mathbf{y}_{0},y_{2},z_{1})d\mu_{|{\mathbb{R}}^{k}}(x)}.$

The intersection $K_{\mathbf{y}=\mathbf{y}_{0}}$ is a generalized Orlicz ball
from Lemma 4.19 and the restriction of $\mu$ is a proper measure from Lemma
4.27. Thus taking $K^{\prime\prime}=K_{\mathbf{y}=\mathbf{y}_{0}}$ we have to
prove

$\frac{\int_{{\mathbb{R}}^{k}}{\mathbf{1}}_{K^{\prime\prime}}(x,y_{1},z_{2})d\mu_{|{\mathbb{R}}^{k}}(x)}{\int_{{\mathbb{R}}^{k}}{\mathbf{1}}_{K^{\prime\prime}}(x,y_{1},z_{1})d\mu_{|{\mathbb{R}}^{k}}(x)}\geq\frac{\int_{{\mathbb{R}}^{k}}{\mathbf{1}}_{K^{\prime\prime}}(x,y_{2},z_{2})d\mu_{|{\mathbb{R}}^{k}}(x)}{\int_{{\mathbb{R}}^{k}}{\mathbf{1}}_{K^{\prime\prime}}(x,y_{2},z_{1})d\mu_{|{\mathbb{R}}^{k}}(x)}.$

Note that even if the density of $\mu$ changes with $y$, it cancels out in
both fractions, thus we can assume the density of $\mu$ changes only on
${\mathbb{R}}^{k}$. As a proper measure has a $1/m$-concave density, and thus
a log-concave density, we can apply Lemma 7.1 to get the thesis. ∎

######  Lemma 7.4.

The functions $\phi_{1}$ and $\phi_{2}$ defined as above define a $\Theta$
function on $K^{\prime}$.

###### Proof.

We have to check the four properties defining $\Theta$ functions. Property
(T1) is obvious, both $\phi_{1}$ and $\phi_{2}$ are bounded by one. Note that
$K$ is a c-set, as it is convex and 1-symmetric, which immediately gives
properties (T2) and (T3).

Condition (T4) is a consequence of Lemma 7.3. If $\bar{K}^{\prime}$ is any
derivative of $K^{\prime}$, then from Lemma 7.2 we have some $\bar{K}$ such
that $\phi_{j}$ restricted to $\bar{K}^{\prime}$ are equal to
${\mathbf{1}}_{\bar{K}}(\cdot,z_{j})$, and thus from Lemma 7.3 the appropriate
ratio of integrals is coordinate-wise decreasing. ∎

######  Lemma 7.5.

If $K$ is a proper generalized Orlicz ball, then $\phi_{1}$ and $\phi_{2}$
define a strict $\Theta$ function.

###### Proof.

The properties (S2) and (S4) are trivial. For property (S1) notice that as the
Young functions are strictly increasing, ${\rm Int}K_{z=z_{1}}\supset
K_{z=z_{2}}$.

To check property (S3) we have to prove that
$\int_{{\mathbb{R}}^{k}}{\mathbf{1}}_{K}(x,y,z_{j})d\mu_{|{\mathbb{R}}^{k}}(x)=\mu_{|{\mathbb{R}}^{k}}(K_{y,z_{j}})$
is continuous in $y$ for $j=1,2$ and $k>0$. Let $\mu_{k}$ denote
$\mu_{|{\mathbb{R}}^{k}}$. Let us take any sequence
$y^{i}{\rightarrow}y^{\infty}$. First note that as the Young functions $f_{l}$
do not assume the value $+\infty$, they are continuous. Thus $\sum
f_{l}(y_{l}^{i}){\rightarrow}\sum f_{l}(y_{l}^{i})$.

Let $L_{a}=\\{x\in{\mathbb{R}}^{k}:\sum f_{i}(x_{i})\leq 1-a\\}$, let
$a_{l}=\sum f_{l}(y_{l}^{i})+f_{z}(z_{j})$ and $a=\sum
f_{l}(y_{l})+f_{z}(z_{j})$. We know $a_{l}{\rightarrow}a$, we want to prove
$\mu_{k}(L_{a_{l}}){\rightarrow}\mu_{k}(L_{a})$. However,

$\displaystyle\lim_{l{\rightarrow}\infty}\mu_{k}(L_{a_{l}})\leq\lim_{t{\rightarrow}0^{+}}\mu_{k}(L_{a+t})=\mu_{k}(\bigcap_{t>0}L_{a+t})=\mu_{k}(L_{a})$

as measure is continuous with respect to the set, and

$\displaystyle\lim_{l{\rightarrow}\infty}\mu_{k}(L_{a_{l}})\geq\lim_{t{\rightarrow}0^{-}}\mu_{k}(L_{a+t})=\mu_{k}(\bigcap_{t<0}L_{a+t})=\mu_{k}(L_{a}),$

where we use the fact that $\mu_{k}(\\{x\in{\mathbb{R}}^{k}:\sum
f_{i}(x_{i})=1-a\\})=0$, as $f_{i}$ are strictly increasing. Thus
$\mu_{k}(K_{y_{l},z_{j}}){\rightarrow}\mu_{k}(L_{y,z_{j}})$, which proves
property (S3). ∎

######  Corollary 7.6.

For any generalized Orlicz ball $K$ the functions $\phi_{1}$ and $\phi_{2}$
define a non-degenerate $\Theta$ function.

###### Proof.

First we prove that $\phi_{1}$ and $\phi_{2}$ define a weakly non-degenerate
$\Theta$ function. From Lemma 4.20 we can approximate $K$ with a proper
generalized Orlicz ball $K^{\prime}$ satisfying $K^{\prime}\subset K$ and
$\lambda(K\setminus K^{\prime})<{\varepsilon}/2$. Additionally, from Corollary
4.21 we may take $z_{1}^{\prime}$ and $z_{2}^{\prime}$ such that
$K^{\prime}\cap\\{z=z_{j}^{\prime}\\}$ approximates $K\cap\\{z=z_{j}\\}$ up to
a set of $\lambda$ measure ${\varepsilon}$.

We take $\phi_{1}^{\prime}(x)={\mathbf{1}}_{K^{\prime}}(x,z_{1}^{\prime})$ and
$\phi_{2}^{\prime}(x)={\mathbf{1}}_{K^{\prime}}(x,z_{2}^{\prime})$. As the
intersections of $K^{\prime}$ at $z_{j}^{\prime}$ were good approximations of
intersections of $K$ at $z_{i}$, we have
$\int|\phi_{i}-\phi_{i}^{\prime}|d\lambda=\lambda(K_{z=z_{1}}\bigtriangleup
K^{\prime}_{z=z_{1}^{\prime}})\leq{\varepsilon}$. From Lemma 4.20 we know
$K^{\prime}$ is a proper generalized Orlicz ball and $K^{\prime}\subset K$.
From Lemma 7.5 we know that $\phi_{1}^{\prime}$ and $\phi_{2}^{\prime}$ define
a strict $\Theta$ function. Thus $\phi_{1}$ and $\phi_{2}$ define a weakly
non-degenerate $\Theta$ function.

As for the derivatives of the function defined by $\phi_{1}$ and $\phi_{2}$ by
Lemma 7.2 they are constructed in the same manner on some derivative of $K$,
and thus also define a weakly non-degenerate $\Theta$ function. Thus
$\phi_{1}$ and $\phi_{2}$ define a non-degenerate $\Theta$ function. ∎

######  Corollary 7.7.

For any generalized Orlicz ball $K\subset{\mathbb{R}}^{n}$ and any c-set
$A\subset{\mathbb{R}}^{n-1}$ the function

$z\mapsto\frac{\int_{\bar{A}}{\mathbf{1}}_{K}(z,x)d\mu(x)}{\int_{{\mathbb{R}}^{n-1}}{\mathbf{1}}_{K}(z,x)d\mu(x)}$

is a decreasing function of $z$ where defined.

###### Proof.

From Corollary 7.6 we can apply Theorem 5.1 to the $\Theta$ function defined
by $\phi_{1}$, $\phi_{2}$ to get for any $0\leq z_{1}<z_{2}$:

$\frac{\int_{A}{\mathbf{1}}_{K}(x,z_{2})d\mu(x)}{\int_{A}{\mathbf{1}}_{K}(x,z_{1})d\mu(x)}\geq\frac{\int_{\bar{A}}{\mathbf{1}}_{K}(x,z_{2})d\mu(x)}{\int_{\bar{A}}{\mathbf{1}}_{K}(x,z_{1})d\mu(x)},$
(7.1.2)

if both sides are defined. We can apply Fact 2.2 to make it

$\frac{\int_{{\mathbb{R}}^{n-1}}{\mathbf{1}}_{K}(x,z_{2})d\mu(x)}{\int_{{\mathbb{R}}^{n-1}}{\mathbf{1}}_{K}(x,z_{1})d\mu(x)}\geq\frac{\int_{\bar{A}}{\mathbf{1}}_{K}(x,z_{2})d\mu(x)}{\int_{\bar{A}}{\mathbf{1}}_{K}(x,z_{1})d\mu(x)}.$
(7.1.3)

Switching the left numerator with the right denominator we get the thesis.

If the right-hand side denominator in inequality (7.1.2) is zero, the right-
hand side numerator is also zero, as $z_{1}<z_{2}$ and $K_{+}$ is a c-set.
Thus both for $z_{1}$ and $z_{2}$ our function is either zero or undefined.

If the left-hand side denominator is zero and the right-hand side is defined,
again the left-hand side numerator is zero, thus in inequality (7.1.3) we have
an equality, which again gives the thesis. ∎

###  7.2 The general case — the $\psi$ function

Let $\lambda_{K}$ denote the Lebesgue measure restricted to $K_{+}$. Recall
that we set out to prove

$\lambda_{K}({\bar{A}}\times
B)\cdot\lambda_{K}(A\times{\bar{B}})\geq\lambda_{K}(A\times
B)\cdot\lambda_{K}({\bar{A}}\times{\bar{B}})$

for any c-sets $A\subset{\mathbb{R}}^{k}$ and $B\subset{\mathbb{R}}^{n-k}$.
This is equivalent to

$\lambda_{K}(A\times{\bar{B}})\cdot\lambda_{K}({\bar{A}}\times{\mathbb{R}}^{n-k})\geq\lambda_{K}({\bar{A}}\times{\bar{B}})\cdot\lambda_{K}(A\times{\mathbb{R}}^{n-k}).$

If either $\lambda_{K}(A\times{\mathbb{R}}^{n-k})$ or
$\lambda_{K}({\bar{A}}\times{\mathbb{R}}^{n-k})$ is zero, then respectively
either $\lambda_{K}(A\times{\bar{B}})$ or
$\lambda_{K}({\bar{A}}\times{\bar{B}})$ is zero and the thesis is satisfied.
Thus it suffices to prove

$\frac{\lambda_{K}(A\times{\bar{B}})}{\lambda_{K}(A\times{\mathbb{R}}^{n-k})}=\frac{\int_{A}\int_{\bar{B}}{\mathbf{1}}_{K}(z,x)dzdx}{\int_{A}\int_{{\mathbb{R}}^{n-k}}{\mathbf{1}}_{K}(z,x)dzdx}\geq\frac{\int_{\bar{A}}\int_{\bar{B}}{\mathbf{1}}_{K}(z,x)dzdx}{\int_{\bar{A}}\int_{{\mathbb{R}}^{n-k}}{\mathbf{1}}_{K}(z,x)dzdx}=\frac{\lambda_{K}({\bar{A}}\times{\bar{B}})}{\lambda_{K}({\bar{A}}\times{\mathbb{R}}^{n-k})},$

when both sides are defined, which means it is enough to prove
$\psi_{1}(x)=\int_{{\mathbb{R}}^{n-k}}{\mathbf{1}}_{K}(z,x)dz$ and
$\psi_{2}(x)=\int_{\bar{B}}{\mathbf{1}}_{K}(z,x)dz$ define a non-degenerate
$\Theta$ function on $K^{\prime}=K_{z=0}\subset{\mathbb{R}}^{k}$ and apply
Theorem 5.1.

######  Lemma 7.8.

If $\bar{K}^{\prime}$ is a derivative of $K^{\prime}$, then there exists a
generalized Orlicz ball $\bar{K}$ such that $\psi_{1}(x)$ on
$\bar{K}^{\prime}$ is equal to
$\int_{{\mathbb{R}}^{n-k}}{\mathbf{1}}_{\bar{K}}(z,x)dz$ and $\psi_{2}(x)$ is
equal to $\int_{\bar{B}}{\mathbf{1}}_{\bar{K}}(z,x)dz$.

The proof is identical to the proof of Lemma 7.2.

######  Proposition 7.9.

For any generalized Orlicz ball $K\subset{\mathbb{R}}^{n}$, any coordinate-
wise decomposition ${\mathbb{R}}^{n}={\mathbb{R}}^{k}\times{\mathbb{R}}^{n-k}$
and any c-set $B\subset{\mathbb{R}}^{n-k}$ the functions $\psi_{1}$ and
$\psi_{2}$ define a $\Theta$ function on $K$.

###### Proof.

Property T1 follows from the fact that $K$ is bounded. Property T2 follows
from the fact $K_{+}$ is a c-set. Property T3 follows from the fact that
$B\subset{\mathbb{R}}^{n-k}$. As before, the tricky part is to prove property
T4. Consider any coordinate-wise decomposition
${\mathbb{R}}^{k}={\mathbb{R}}^{k_{1}}\times{\mathbb{R}}^{k_{2}}$. Choose any
variable $v$ in ${\mathbb{R}}^{k_{1}}$ and fix all the others at some fixed
$\mathbf{v}_{0}$. We have:

$\frac{\int_{{\mathbb{R}}^{k_{2}}}\psi_{2}(v,\mathbf{v}_{0},y)d\mu(y)}{\int_{{\mathbb{R}}^{k_{2}}}\psi_{1}(v,\mathbf{v}_{0},y)d\mu(y)}=\frac{\int_{{\mathbb{R}}^{k_{2}}}\int_{\bar{B}}{\mathbf{1}}_{K}(v,\mathbf{v}_{0},y,z)d\mu(y)dz}{\int_{{\mathbb{R}}^{k_{2}}}\int_{{\mathbb{R}}^{n-k}}{\mathbf{1}}_{K}(v,\mathbf{v}_{0},y,z)d\mu(y)dz}=\frac{\int_{{\mathbb{R}}^{k_{2}}\times{\bar{B}}}{\mathbf{1}}_{K}(v,\mathbf{v}_{0},y,z)d\mu(y)dz}{\int_{{\mathbb{R}}^{l_{2}}\times{\mathbb{R}}^{k}}{\mathbf{1}}_{K}(v,\mathbf{v}_{0},y,z)d\mu(y)dz}.$

We have to prove this function is decreasing in $v$ where defined. Let us
restrict ourselves to the generalized Orlicz ball
$\hat{K}=K_{\mathbf{v}=\mathbf{v}_{0}}$. Notice that
${\mathbb{R}}^{l_{2}}\times A$ is a c-set in
${\mathbb{R}}^{l_{2}}\times{\mathbb{R}}^{k}$ and $\mu\otimes\lambda$ is a
proper measure in ${\mathbb{R}}^{l_{2}}\times{\mathbb{R}}^{k}$. We have to
prove

$\frac{\int_{{\mathbb{R}}^{l_{2}}\times{\bar{A}}}{\mathbf{1}}_{\hat{K}}(v,y,z)d(\mu\otimes\lambda)(y,z)}{\int_{{\mathbb{R}}^{l_{2}}\times{\mathbb{R}}^{k}}{\mathbf{1}}_{\hat{K}}(v,y,z)d(\mu\otimes\lambda)(y,z)}$

is decreasing in $v$, but this is exactly the thesis of Corollary 7.7.

Again, as in Lemma 7.4, due to Lemma 7.8, the appropriate ratio is also
decreasing for any derivative $\bar{K}$ of $K$. ∎

######  Proposition 7.10.

For any generalized Orlicz ball $K\subset{\mathbb{R}}^{n}$, any coordinate-
wise decomposition ${\mathbb{R}}^{n}={\mathbb{R}}^{k}\times{\mathbb{R}}^{n-k}$
and any c-set $B\subset{\mathbb{R}}^{n-k}$ the functions $\psi_{1}$ and
$\psi_{2}$ define a non-degenerate $\Theta$ function on $K$.

###### Proof.

Again the derivatives of $\psi$ are again functions formed as in Lemma 7.8, so
it is enough to prove $\psi$ is weakly non-degenerate.

Take any ${\varepsilon}>0$. From Lemma 4.20 we may take a proper generalized
Orlicz ball $\hat{K}\subset K$ with
$\lambda(K\setminus\hat{K})<{\varepsilon}\min\\{\lambda(K),1\\}/2$ and
$\lambda_{k}(K_{z=0}\setminus\hat{K}_{z=0})<{\varepsilon}\min\\{\lambda_{k}(K_{z=0}),1\\})$
from Lemma 4.21. Denote $\hat{K}_{z=0}$ by $\hat{K}^{\prime}$.

Let $z_{1}$ be any coordinate in ${\mathbb{R}}^{n-k}$, take
$B^{\prime}=B\cup(\\{\mathbf{z}:z_{1}<\delta\\}\cap K_{+})$, where $\delta$ is
so small that the addition is of $\lambda_{n-k}$ measure less than
${\varepsilon}/2$. $B^{\prime}$ is a sum of two c-sets and thus a c-set.

We define
$\psi_{1}^{\prime}(x)=\int_{{\mathbb{R}}^{n-k}}{\mathbf{1}}_{\hat{K}}(z,x)dz$
and
$\psi_{2}^{\prime}(x)=\int_{{\bar{B}}^{\prime}}{\mathbf{1}}_{\hat{K}}(z,x)dz$.
We have
$\lambda_{k}(K^{\prime}\setminus\hat{K}^{\prime})<{\varepsilon}\lambda_{k}(K^{\prime})$
from the definition of $\hat{K}$. Also $\psi_{1}^{\prime}$ and
$\psi_{2}^{\prime}$ are indeed good approximations of $\psi_{1}$ and
$\psi_{2}$, as

$\int_{{\mathbb{R}}^{k}}|\psi_{1}(x)-\psi_{1}^{\prime}(x)|dx\leq\int_{{\mathbb{R}}^{k}}\int_{{\mathbb{R}}^{n-k}}|{\mathbf{1}}_{K}(x,z)-{\mathbf{1}}_{\hat{K}}(x,z)|dzdx=\lambda(K\bigtriangleup\hat{K})\leq{\varepsilon}/2,$

and

$\displaystyle\int_{{\mathbb{R}}^{k}}|\psi_{2}(x)-\psi_{2}^{\prime}(x)|dx$
$\displaystyle=\int_{{\mathbb{R}}^{k}}\Big{|}\int_{{\mathbb{R}}^{n-k}}{\mathbf{1}}_{K}(x,z){\mathbf{1}}_{\bar{B}}(x,z)-{\mathbf{1}}_{\hat{K}}(x,z){\mathbf{1}}_{{\bar{B}}^{\prime}}(x,z)dz\Big{|}dx\leq\mu((K\cap{\bar{B}})\bigtriangleup(\hat{K}\cap{\bar{B}}^{\prime}))$
$\displaystyle\leq\lambda(K\setminus\hat{K})+\lambda_{K}({\bar{B}}\bigtriangleup{\bar{B}}^{\prime})=\lambda(K\setminus\hat{K})+\lambda_{K}(B\bigtriangleup
B^{\prime})\leq{\varepsilon}.$

Thus we only have to prove that $\psi_{1}^{\prime}$ and $\psi_{2}^{\prime}$
define a strict $\Theta$ function on $\hat{K}$.

Property (S2) is true as $\hat{K}$ is proper — $\hat{K}^{\prime}$ is defined
by those Young functions of $\hat{K}$ which act on the variables of
${\mathbb{R}}^{k}$. Property (S4) is obvious from the definition of
$\psi_{1}^{\prime}$. The function $\psi_{2}^{\prime}$ is 0 on the set $\sum
f_{i}(x_{i})>1-f_{z_{1}}(\delta)$ from the definition of $B^{\prime}$ — any
point in ${\bar{B}}^{\prime}$ has $z_{1}>\delta$, hence property (S1). Finally
(S3) is checked exactly as in Lemma 7.5. ∎

Thus $\psi_{1}$ and $\psi_{2}$ do define a non-degenerate $\Theta$ function,
which ends the proof of Theorem 1.2.

## References

  * [ABP03] M. Anttila, K. Ball and I. Perissinaki, The central limit problem for convex bodies. Trans. Amer. Math. Soc., 355 (2003), pp. 4723–-4735.
  * [BP98] K. Ball and I. Perissinaki, The subindependence of coordinate slabs in $\ell_{p}^{n}$ balls, Israel J. Math., 107 (1998), pp. 289-299.
  * [BGMN05] F. Barthe, O. Gudeon, S. Mendelson and A. Naor, A Probabilistic Approach to the Geometry of the $\ell_{p}^{N}$-ball, Annals of Probability, 33 (2005), pp. 480–513.
  * [Ga02] R. J. Gardner, The Brunn-Minkowski Inequality, Bull. Amer. Math. Soc. 39 (2002), pp. 355-405
  * [BN03] S. G. Bobkov, F. L. Nazarov, On convex bodies and log-concave probability measures with unconditional basis. Geometric aspects of functional analysis, 53–69, Lecture Notes in Math., 1807, Springer, Berlin, 2003.
  * [Bo74] C. Borell, Convex measures on locally convex spaces. Ark. Mat. 12 (1974), 239–252.
  * [FGP07] B. Fleury, O. Guedon, G. Paouris, A stability result for mean width of $L_{p}$-centroid bodies. Preprint. Available at http://www.institut.math.jussieu.fr/$\tilde{\ }$guedon/Articles/06/FGP-Accepted.pdf
  * [Gi03] A. A. Giannopoulos, Notes on isotropic convex bodies, Institute of Mathematics, Polish Academy of Sciences, Warsaw (2003), available at http://users.uoa.gr/$\tilde{}$apgiannop/isotropic-bodies.ps.
  * [K07,2] B. Klartag, A central limit theorem for convex sets, Invent. Math., Vol. 168, (2007), 91–131.
  * [K07] B. Klartag, Power-law estimates for the central limit theorem for convex sets, J. Funct. Anal., Vol. 245, (2007), pp. 284–310.
  * [KLO96] S. Kwapień, R. Latała and K. Oleszkiewicz, Comparison of Moments of Sums of Independent Random Variables and Differential Inequalities. Journal of Functional Analysis, 136 (1996), pp. 258–268.
  * [MM05] E. Meckes and M. Meckes, The Central Limit Problem for Random Vectors with Symmetries. Preprint. Available at http://arxiv.org/abs/math.PR/0505618.
  * [MP89] V. D. Milman and A. Pajor, Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed $n$-dimensional space. Lecture Notes in Mathematics, 1376 (1989), pp. 64–104.
  * [MS86] V. Milmanc G. Schechtman, Asymptotic theory of finite-dimensional normed spaces. With an appendix by M. Gromov. Lecture Notes in Mathematics, 1200. Springer-Verlag, Berlin, 1986.
  * [N84] C. M. Newman, Asymptotic independence and limit theorems for positively and negatively dependent random variables. In Y. L. Tong (ed.), Inequalities in Statistics and Probability, Hayward, CA, pp. 127–140.
  * [S00] Qi-Man Shao, A comparison theorem on moment inequalities between negatively associated and independent random variables, J. Theoret. Probab. 13 (2000), 343-356.
  * [W06] J. O. Wojtaszczyk, The square negative correlation property for generalized Orlicz balls. Preprint, to be published in GAFA. Available at http://www.mimuw.edu.pl/~onufry/papers/Orlicz.pdf


# Cost-Intelligent Data Analytics in the Cloud

Huanchen Zhang  Tsinghua University<EMAIL_ADDRESS>,  Yihao Liu
Tsinghua University<EMAIL_ADDRESS>and  Jiaqi Yan  Snowflake
<EMAIL_ADDRESS>
###### Abstract.

For decades, database research has focused on optimizing performance under
fixed resources. As more and more database applications move to the public
cloud, we argue that it is time to make cost a first-class citizen when
solving database optimization problems. In this paper, we introduce the
concept of cost intelligence and envision the architecture of a cloud data
warehouse designed for that. We investigate two critical challenges to
achieving cost intelligence in an analytical system: automatic resource
deployment and cost-oriented auto-tuning. We describe our system architecture
with an emphasis on the components that are missing in today’s cloud data
warehouses. Each of these new components represents unique research
opportunities in this much-needed research area.

##  1\. Introduction

From an economic perspective, databases are simply a type of goods or
services. A consumer pays a price of $C$ for the database product and earns
utility (which eventually translates to revenue) by receiving timely query
results. The utility function $U(p)$ is positively correlated with the query
performance $p$. A “better” (i.e., more competitive in the market) database,
therefore, is the one that maximizes consumer profit (i.e., $\Pi=U(p)-C$).
This fundamental logic has always remained the same throughout database
development.

For decades, database research has focused on optimizing the performance $p$
under a fixed amount of resources, leaving the cost $C$ behind. This is
rational because traditional distributed databases (Lamb et al., 2012; Lyu et
al., 2021; ter, 2023) typically dedicate a predetermined number of machines to
run the service. The dominating factor in $C$ is the sunk cost $C_{sunk}$ for
purchasing computing equipment, software licenses, and other supporting
facilities. The marginal cost $\Delta C$ attributed to database operations
(e.g., power consumption) is relatively small. There is little one can do to
increase the user profit by reducing the cost.

The situation has changed dramatically in the past decade as more and more
database applications move to the public cloud. The “pay-as-you-go” pricing
model eliminates the majority of the sunk cost and enables fine control over
the operational cost $\Delta C$. Technologies such as the disaggregation of
compute and storage allow recent cloud-native databases (Dageville et al.,
2016; Armenatzoglou et al., 2022; big, 2023) to further leverage the resource
elasticity at a fine granularity. Meanwhile, cost reduction is the driving
force behind most customers’ migration to cloud-native database services.
Performance is no longer the only criterion. A typical database user today
treats performance as a requirement rather than an optimization target (Ortiz
et al., 2015; Florescu and Kossmann, 2009) because the performance beyond
often contributes little to the application’s revenue (i.e., $U(p)$ is a step
function). Their goal is to minimize the cost while guaranteeing a performance
service-level agreement (SLA). Another user paradigm is to set a fixed budget
to spend on the database service and try to get the best performance out of
it.

We argue that it is time to make cost a first-class citizen when solving
database optimization problems. The demand for cost savings has always been
there, and the resource elasticity provided by the public cloud services makes
it possible to manipulate cost as a free variable rather than a near-constant.
Cost efficiency is equally important as performance because they both serve to
maximize user profit. Given this, optimization in a cloud-native database
should be bi-objective by default: any performance gain must be justified by
the potential trade-off in cost (and vice versa) to be considered valuable in
a specific application.

It is important to distinguish between user-observable cost (UOC) and
provider-observable cost (POC, often referred to as the cost of goods sold
financially). From a user’s perspective, their cost is the cloud bill which
reflects the amount of resources reserved/promised by the database service for
completing a task. A simple aggregation of the UOCs, however, does not equal
the cost borne by the service provider (i.e., POC). To support multi-tenancy,
a provider typically manages virtualized resource pools where smart scheduling
algorithms (sometimes overcommitting) could lead to a much higher resource
utilization overall compared to that of individual users (Narasayya and
Chaudhuri, 2021). To this end, UOC is the base cost that determines how cost-
competitive a database product is, while optimizing POC further improves the
service provider’s profit margin. The focus of this paper is on optimizing
UOC, that is, reducing the resource requirement and waste for completing a
user query while guaranteeing its performance SLA. This is primarily
orthogonal to the multi-tenancy techniques for POC optimization, and providers
are willing to spend effort reducing UOC to stay cost-competitive in the
market. Techniques for improving the efficiency of multi-tenancy in a data
center (Narasayya and Chaudhuri, 2021) is beyond the scope of this paper.

The idea of treating monetary cost as a database optimization target dates
back to the early days of cloud computing (Florescu and Kossmann, 2009). There
is a rich literature on optimizing the resource allocation in big data systems
with massive parallelism (Pimpley et al., 2022; Yint et al., 2018; Siddiqui et
al., 2020; Ferguson et al., 2012; Kllapi et al., 2011; Lyu et al., 2022).
Recent studies on cost-efficient cloud data warehouses concentrate mainly on
cloud configurations. For example, Leis and Kuschewski proposed a model-based
algorithm to select a cost-optimal instance configuration to run a workload
(Leis and Kuschewski, 2021). Tan et al. examined major cloud OLAP engines and
revealed the performance-cost trade-offs in the cloud storage hierarchy (e.g.,
AWS S3 vs. EBS) (Tan et al., 2019). Starling (Perron et al., 2020) and Lambada
(Müller et al., 2020) used cloud functions to execute queries to save cost by
avoiding resource over-provisioning. These solutions, however, are ad-hoc, and
they target only a single aspect of achieving cost efficiency in a cloud
analytics system. There is a need for a holistic design of the core database
architecture that treats performance and cost with equal importance and allows
a native bi-objective optimization. The reality is that cost control is still
difficult in state-of-the-art systems, and the burden of cost management is
mostly left to the users (Rajan et al., 2016; Pimpley et al., 2022).

In this paper, we envision the architecture of a cloud data warehouse designed
for cost intelligence. We begin by discussing the cost-control challenges in
today’s cloud data warehouses. We then present the concept of cost
intelligence and describe our architectural design for solving the critical
problems in automatic resource deployment in the foreground and automatic
database tuning in the background. The paper serves as both a system blueprint
and a research roadmap that identifies the missing/suboptimal components and
algorithms for achieving cost intelligence in the next-generation cloud data
warehouse.

##  2\. The Case For Cost Intelligence

Figure 1. Snowflake User Interface

Figure 2. Cost Intelligence

Despite the “pay-as-you-go” model in the public cloud, it is still difficult
for an average database user to leverage resource elasticity to control and
optimize their bills when using a cloud database service. In this section, we
identify the cost-optimization challenges in existing systems for both online
resource provisioning and offline database tuning. These challenges make the
case for a cost-intelligent database design that frees the users from the
burden of pursuing cost efficiency manually and ad hoc.

The first key challenge is automatic resource deployment during query
execution. Figure 2 shows a partial user interface (UI) for creating a virtual
warehouse (i.e., a stateless cluster for query processing) in Snowflake
(Dageville et al., 2016). Before submitting any queries, a user must determine
the cluster size by choosing a predefined “T-shirt” size, where a larger size
means more computing nodes and a more expensive unit price. This basic service
model for resource allocation is common in today’s cloud data warehouses.
However, this “one-shot” user-provisioning model often leads to inefficient
resource utilization.

First, average database users lack the expertise to accurately estimate the
resource necessary for their workloads. As a result, they often _over-
provision_ the cluster size to guarantee that their performance SLAs are met.
Second, the cluster size is predetermined and _fixed_ 111although some
services support auto-scaling to handle workload bursts (Armenatzoglou et al.,
2022). for the entire workload, regardless of the query complexity and data
volume changes during the execution. Such inflexibility prevents each pipeline
within an analytical query from reaching its cost-optimal degree of
parallelism (DOP).

Determining the cost-optimal DOP for each pipeline in a distributed query plan
is a pivotal step toward automatic resource deployment. An interesting logic
enabled by the resource elasticity in the cloud is that for a task that is
embarrassingly parallel, executing the task using 1 machine for 100 minutes
incurs the same dollar cost as executing the task using 100 machines for 1
minute, but the second configuration has a 100x performance advantage.
However, allocating more machines does not always bring performance boosts for
free because most database operators do not exhibit perfectly-linear
scalability. Many of them (e.g., hash partitioning) require exchanging data
between the machines where the network could become the system’s bottleneck.
Unlike in a map-reduce-based big data system (Pimpley et al., 2022;
Venkataraman et al., 2016), over-scaling the cluster size in a distributed
database not only wastes resources but also could have a negative impact on
query latency. A user may end up paying more for the same or even worse query
performance.

The second cost-optimization challenge is automatic database tuning in the
background. The goal is to allow databases to apply tuning actions (e.g.,
building indexes and materialized views) wisely and automatically to cut the
expenses on database administrators (DBAs). After decades of research and
practice, from the AutoAdmin project (Chaudhuri and Narasayya, 1998) to the
recent self-driving databases (Pavlo et al., 2017), there are sophisticated
algorithms and tools that can propose tuning actions beneficial to the overall
system performance.

These auto-tuning tools, however, are not designed to be cost-aware in the
cloud environment, and they do not provide a customer-understandable measure
that can clearly indicate the net gain (or loss) of a particular tuning
action. For example, suppose that a user is presented with a tuning suggestion
that proposes to recluster (or repartition) a petabyte-sized table T according
to a different attribute A. Although such a reclustering operation could speed
up queries that use A in the predicates or join columns, the cost of
repopulating a petabyte-sized table is enormous. Without a metric to evaluate
the pros and cons of a tuning action uniformly, users would hesitate to take
such suggestions. Consequently, they still have to rely on DBAs’ experience to
make informed decisions.

Because of both the online and offline cost-optimization challenges, users
today typically struggle to control their cloud bills when using a data
warehouse service. We, therefore, envision the next-generation cloud-native
system to be cost-intelligent. The concept of cost intelligence is defined as
the system’s ability to self-adapt to stay _Pareto-optimal_ in the
performance-cost trade-off under different workloads and user constraints. As
shown in Figure 2, a cost-intelligent data warehouse would (re)configure
itself automatically (e.g., through automatic cluster resizing and offline
tuning) to move toward Pareto efficiency so that users can easily make
performance and cost trade-offs based on their application needs by sliding
along the Pareto frontier without worrying about wasting resources.

Figure 3. System Architecture of a Cost-Intelligent Cloud Data Warehouse

To run a workload in a cost-intelligent data warehouse, users only need to
specify their constraints/preferences on performance and cloud budget (instead
of a list of “T-shirt” sizes), and the database would figure out how to
deliver the query results on time with minimal dollar costs. Additionally,
each database tuning proposal is associated with a report that uses the dollar
benefit/cost as the bridge to evaluate the trade-offs so that users can decide
whether to apply this tuning action without the need for expertise from
professional DBAs.

We next sketch our solutions to the problems of automatic resource deployment
(Section 3) and cost-oriented auto-tuning (Section 4). We will present the
architecture of a cost-intelligent cloud data warehouse with an emphasis on
the components and algorithms that are missing in today’s systems.

##  3\. Automatic Resource Deployment

In this section, we investigate the following problem: given an analytical
query, how many compute nodes should the cloud database allocate to achieve
minimal cost while satisfying the performance SLA (or to achieve optimal
performance within the cost budget). We assume that the nodes are symmetric.
Selecting the optimal hardware configuration for a query is beyond the scope
of this paper, and we refer the readers to (Leis and Kuschewski, 2021).

We adopt a basic system architecture similar to Snowflake with disaggregated
computing and storage (Dageville et al., 2016). As shown in Figure 3, the
bottom storage layer, hosted by cloud objects storage services such as AWS S3
and Azure Blob Storage, keeps the user data in hybrid-columnar formats such as
Parquet and ORC. On top of that, the elastic compute layer allows users to
acquire virtual machines on demand to execute database queries. These nodes
only provide computing power, and they do not hold any persistent states. Such
a disaggregated architecture enables the computation and storage resources to
scale independently. At the top, the multi-tenant query optimization service
parses SQL queries and generates distributed execution plans for the compute
nodes to work on. There is also a metadata service that provides low-latency
access to the system’s catalog and table statistics necessary for query
planning. In the rest of the paper, we assume private computations, i.e., the
(virtual) compute nodes are not shared among users. We also assume that the
database service provider maintains a warm server pool to facilitate rapid
cluster creation, resizing, and reclamation222Estimating the warm-pool size at
the service level is beyond the scope of this paper..

As discussed in Section 2, the diversity of database operators leads to a
different cost-optimal degree of parallelism for each pipeline within a
complex query. For example, scaling out a large table scan incurs less
performance overhead compared to scaling out a distributed hash join. There
are two types of methods to approach optimal DOP assignments. The first is to
determine the DOP of each pipeline at query optimization (i.e., static
planning). However, no matter how sophisticated the models and algorithms are,
these static assignments could be far from optimal if the cardinality
estimation is way off. On the other hand, the system can adopt a purely
dynamic approach where each pipeline starts with a default number of nodes
(e.g., one) and then gradually adjusts the DOP based on the real-time feedback
on the performance and resource utilization. This approach, however, often
leads to noticeable system overhead caused by excessive cluster resizing
operations.

We, therefore, propose a hybrid solution (shown in Figure 3). The initial DOP
for each pipeline (i.e., execution stage) is determined at query optimization
time through static planning that obeys user constraints on performance and
budget. This requires a relatively accurate time and cost estimation at a fine
granularity (Section 3.1) and an optimizer that considers both query latency
and monetary cost as it enumerates the plan space (Section 3.2). Additionally,
the system monitors the execution progress along with the resource utilization
and adjusts the DOP assignments at run time (Section 3.3) to ensure that the
performance SLA is met with minimal cost (or to obtain maximized performance
under the budget).

###  3.1. Cost Estimation

The ability to predict the cost of a plan fragment accurately is indispensable
to a cost-intelligent system. The cost estimator is at the center of our
proposed architecture, where it functions as a referee that ranks different
execution proposals (including background tuning tasks) to guide the system to
overall cost efficiency. Here, cost refers to both time and monetary costs.
The input to the cost estimator includes both logical information such as the
plan shape and the input/output cardinality for each operator as well as
physical parameters such as DOP assignments and other hardware characteristics
(e.g., memory size). The cost estimator then outputs the predicted time and
monetary cost of executing this plan fragment with the specified hardware
configuration. Because we assume private computation in the system, the
monetary cost of a workload is proportional to the total machine time instead
of the CPU time. For example, if a pipeline execution is blocked on a node
waiting for the input data, the user is still charged for the under-utilized
resources.

There are several desired properties of the cost estimator. First, the
_accuracy_ of the predictions determines the cost optimality of the selected
distributed execution plan. A misleading cost estimation may cause serious
under/over-provisioning of the compute nodes and sub-optimal query plans
(discussed in Section 3.2). Second, the cost estimator must be _lightweight_.
As the focal point of the architecture, the cost estimator is frequently
invoked by the foreground query optimizer and the background tuning modules,
and its complexity affects the overall system efficiency. Third, the models
used in the cost estimator should be _explainable_. Because estimation errors
are inevitable (due to cardinality misestimation), the system would
occasionally make bad decisions that lead to slow and expensive execution of
customer queries. The explainability of the cost estimator allows database
engineers to reason about the root causes and propose fixes to make the module
more robust along the way. When designing the algorithms in the cost
estimator, we are willing to trade some prediction accuracy for better
efficiency and explainability of the module because most sub-optimal DOP
assignments caused by the estimation errors can be recovered by the “DOP
monitor” at run time with a moderate system overhead.

There is a rich literature on query performance prediction. Although the
algorithms proposed in prior work are inspiring, they are insufficient for
solving our cost estimation problem. First, most prior models only predict
job/workload-level performance through learning the high-level job execution
patterns (Venkataraman et al., 2016; Pimpley et al., 2022; Ferguson et al.,
2012). They, however, are ignorant of the pipeline formation inside a complex
query and are thus unable to provide more fine-grained cost estimations.
Second, these models target big data systems with a simpler map-reduce
execution model. Compared to executing analytical queries in a relational
database, map-reduce jobs do not involve direct data transfer between
execution nodes, and they do not have pipelines running in parallel within a
job.

Many previous solutions rely heavily on machine learning (Ganapathi et al.,
2009; Tang et al., 2021; Akdere et al., 2012; Pimpley et al., 2022; Marcus and
Papaemmanouil, 2019; Fan et al., 2020). There are several issues with this
approach. First, they typically assume a recurrent workload (common in big
data systems) and train their models offline using features extracted from the
execution history (Pimpley et al., 2022; Ferguson et al., 2012; Siddiqui et
al., 2020). These models, however, may not be generalized enough to provide
accurate performance predictions for ad-hoc queries issued by data scientists
in a data warehouse. To obtain a robust performance prediction for an
arbitrary query, many performance prediction algorithms choose to profile the
query on small data samples to collect training data for their ML models
(Venkataraman et al., 2016; Rajan et al., 2016; Karampaglis et al., 2014).
Although the overhead of the training process can be bounded (Venkataraman et
al., 2016), it is unlikely that such a sampling-based estimation is
lightweight enough to be invoked frequently during query planning and
execution to adjust the DOP assignments. Furthermore, ML-based performance
predictors often feed high-level query features extracted from the SQL text
(e.g., word frequencies) and physical plan (e.g., number of operators) into
models such as XGBoost and SVM (Tang et al., 2021; Ganapathi et al., 2009;
Akdere et al., 2012; Fan et al., 2020). These models treat the query internals
as a black box and thus compromise the prediction explainability, a property
desired in our architecture.

Designing a cost estimator that is accurate, lightweight, and explainable is a
challenging research problem. In the rest of this section, we sketch a
possible solution that we are actively investigating. Our cost estimator
contains a set of per-operator models and a query-level simulator. For each
physical operator, we design a scalability model that outputs its processing
throughput given the data size and the degree of parallelism. The model also
refers to the relevant hardware parameters that are calibrated before the
service starts. We found that simple mathematical formulas are good enough to
model the scalability of most physical operators (e.g., scan, filter). To
improve the prediction accuracy for more complex operators (typically involve
data exchange between nodes), we pre-train regression models for them with
synthetic workloads that cover the parameter space. As discussed before, we
try to avoid using complex ML models (e.g., deep neural networks) that trade
explainability for further accuracy.

Based on the per-operator scalability models, we can compute the throughput of
an operator pipeline given a DOP assignment and thus estimate its execution
time and total machine time ($\propto$ cost). The query simulator then models
the data flow in each pipeline of a query plan. In a multi-pipeline query,
pipelines could be executed in parallel, and a downstream pipeline could be
blocked if the data from one of its parents is not ready. The query optimizer,
therefore, would invoke the simulator multiple times to find a cost-optimal
pipeline-level DOP assignments (e.g., the accumulated “blocked” time of the
pipelines is minimized).

###  3.2. Bi-Objective Query Optimization

Query optimization in a cost-intelligent cloud data warehouse must be bi-
objective. The optimizer receives user constraints (or preferences) on query
latency and cloud budget and produces distributed query plans that are most
efficient while satisfying these requirements. The bi-objective optimizer
invokes the cost estimator discussed in the previous subsection to be cost-
aware when searching the plan space. The key challenge in designing a bi-
objective optimizer is to keep its computational complexity low.

Previous studies proposed theoretical frameworks for solving the multi-
objective optimization problem in databases (Trummer and Koch, 2014). These
solutions target producing a set of physical plans that form the Pareto
frontier of the trade-offs of the multiple objectives. However, generating a
series of optimal plans with different trade-offs inevitably adds significant
computational complexity to the search algorithm. We argue that it may not be
necessary for a cost-intelligent database to present the full spectrum of
plans with different estimated times and costs for users to choose from. We
observe that it is more friendly to users to directly specify their latency or
budget constraints for a query. Therefore, we can “downgrade” the bi-objective
optimization problem into a constrained single-objective optimization problem
(i.e., find a plan with a minimal monetary cost that satisfies a latency
requirement, or find a plan with minimal query latency within a cloud budget)
to achieve a search complexity similar to a traditional cost-based optimizer.

A second source of complexity unique to our optimizer is the fine-grained DOP
planning. Ideally, DOP planning should be integrated into the unified cost-
based search (Graefe, 1995) to obtain an optimal distributed plan (Viswanathan
et al., 2018). However, enumerating the DOP for each pipeline while exploring
the physical plan shape makes the search space explode. Instead, we separate
the DOP planning from the DAG planning (i.e., the traditional single-machine
query optimization that produces an execution DAG) into a subsequent
optimization stage. Specifically, searching for an optimal DOP assignment only
applies to the “chosen” plan produced by the DAG-planning stage. Although the
separation of the stages misses the opportunities to reach a globally
optimized plan obtainable from a unified search, it keeps the search
complexity comparable to existing optimizers.

Because a pipeline cannot start until all of its dependent pipelines are
complete, a heuristic that we use to speed up DOP planning by pruning the
search space is to make sure that these (concurrent) dependent pipelines
finish roughly at the same time to minimize resource waste due to pipeline
waiting. Specifically, if the two dependent pipelines started at the time have
input cardinalities $C_{1}$ and $C_{2}$, and the throughput functions given by
the cost estimator are $T_{1}(\cdot)$ and $T_{2}(\cdot)$, we ensure that the
DOP assignments of the two pipelines satisfy
$\frac{C_{1}}{T_{1}(DOP_{1})}\approx\frac{C_{2}}{T_{2}(DOP_{2})}$.

A bi-objective query optimizer in a cloud system should leverage resource
elasticity to make judicious trade-offs between query latency and monetary
cost. Optimizing bushy joins is one of the most interesting problems in this
area. In a distributed environment with elastic resources, a “bushier” plan
enables more concurrency in pipeline executions and is more likely to have a
lower query latency. However, a bushier plan may not be optimal in terms of
join cardinalities, and it may, therefore, cost more computations (and total
machine time). Bushy joins are usually ignored in traditional optimizers for
single-machine (i.e., the DAG planning stage in our optimizer) to reduce the
search space. We propose to explore bushy plans in the DOP planning stage.
After receiving a left-deep plan from DAG planning, we would reorganize the
join shape to make a series of plan variants that are increasingly bushier.
The relations are chosen carefully in the above plan rewrite so that the join
cardinalities are bounded (e.g., non-expanding joins) (Chen et al., 2016). We
then apply DOP planning to each of the plan variants and choose the one that
makes the best time-cost trade-offs under user constraints.

###  3.3. Dynamic Cluster Resizing

A static DOP assignment produced in query optimization could suffer from
errors in cardinality estimations. We, therefore, introduce a DOP monitor that
dynamically adjusts the cluster size at run time to meet user requirements.
Prior auto-scaling strategies typically fall into two categories. The first is
to assess the execution progress after each fixed time interval and scale the
cluster if necessary to meet a performance SLA (Ferguson et al., 2012; Thamsen
et al., 2017). This approach works well for massively parallelizable jobs
(e.g., map-reduce). For complex analytical queries, however, scaling out the
entire cluster may not be cost-efficient. For example, if the execution is
bottlenecked by a particular pipeline, scaling out the concurrent (or
downstream) pipelines proportionally could hurt their resource utilization.

Therefore, we apply auto-scaling at the pipeline granularity. The DOP monitor
collects the true cardinalities, the pipeline flow rates, and the resource
utilization at run time. If the measures of a pipeline deviate from the
statically-planned values within a threshold, we correct the deviation by
adjusting the DOP of this pipeline only (according to the scalability models
in the cost estimator). If the deviation is substantial, we will reinvoke the
DOP planner with the collected run-time statistics to generate a new set of
DOP assignments for all the pipelines to ensure that user constraints are
satisfied efficiently.

The second category of auto-scaling strategies is to determine the resources
for the next execution stage after each data shuffle (Siddiqui et al., 2020;
Yint et al., 2018; big, 2023). For example, Google’s BigQuery (big, 2023)
would shrink the cluster size for the next stage if its shuffle service
detects severe overestimation of the output cardinality of the previous stage
(Edara and Pasumansky, 2021). This approach relies on materializing the
intermediate results at the pipeline breakers on persistent storage or in a
data shuffle service. Such “clean cuts” between execution stages impose
performance overhead, and we believe that they are nonessential to achieving
fine-grained auto-scaling. Our DOP monitor can not only re-plan the DOPs for
future stages but also adjust the cluster size of the current stage with
minimal resizing overhead. This is enabled by the morsel-driven scheduling
(Leis et al., 2014) in our execution engine, where the smaller tasks make
real-time cluster resizing more efficient. We also adopt a push-based
execution model (duc, 2023) so that we have centralized control over the data
flow to allow DOP changes promptly.

##  4\. Cost-Oriented Auto-Tuning

As discussed in Section 2, a key step toward automating the database tuning
process in the cloud is to use the _monetary cost_ as a common metric to
evaluate different aspects of a tuning action systematically. Physical
database tuning is a difficult problem in traditional DBMSs with fixed
resources. It relies heavily on DBAs’ experience because the resource
contentions are hard to quantify. For example, creating a materialized view
(MV) for an intermediate join result would speed up a group of queries and
thus improve the read throughput of the system. However, maintaining the
freshness of the MV would slow down writes to the database. And because of
fixed resources, spending extra computation on MV updates also hurts the
system’s read-throughput. This implicit resource contention between the read
and write operations complicates the tuning process.

We argue that the auto-tuning problem is more solvable in a cloud environment.
The key idea is to leverage the elastic resources to guarantee the same or
better performance after applying a tuning action and then evaluate whether
this action reduces the operational cost of the system in the long run.
Consider the same MV-creation example above, we would allocate separate
compute resources for MV maintenance to avoid resource contention so that it
does not hurt the performance of normal read and write operations. Then, we
estimate that the computation saved by substituting the MV into queries is
worth $x$ dollars per time unit, and the extra cost of storing and updating
the MV is $y$ dollars per time unit. If $x-y>0$, this tuning action is likely
to be beneficial. Using the dollar as a common metric simplifies the auto-
tuning logic and makes it possible to present the trade-offs of a tuning
action to average customers clearly.

To estimate the above dollar benefits/costs for a tuning action, the system
must be able to predict future workloads besides accurate cost estimation
described in Section 3.1. Recent work has focused on using various machine-
learning algorithms for the task (Ma et al., 2018).Although these algorithms
matter, we believe that a comprehensive and efficient _Statistics Service_ (as
shown in Figure 3) is the foundation of accurate workload predictions. For
each database instance, the Statistics Service collects the query execution
logs from all the tenants to form the “ground truth” for understanding
workload behaviors. The service computes in the background with these
collected traces to generate and maintain queryable workload summaries,
including file/attribute-access counts and weighted join graphs333A graph
where the vertices are table attributes and the weights on the edges indicate
how often the attributes are joined. for training workload-prediction models
and run-time resource usage for modeling the performance and monetary cost.

We identify several challenges in building an efficient Statistics Service.
First, the database must implement its own lightweight profiling tool that can
attribute the run-time resource measures to logical database tasks easily.
Most off-the-shelf profiling tools, such as Linux Perf, incur prohibitively
high system overhead when accompanying normal query execution, and they are
only good at capturing snapshots of entire processes. Second, although we
assume private computing at the user level, it is multi-tenant underneath for
the service provider. The ability to attribute the shared hardware usage to
each of the concurrent workloads are critical to the Statistics Service.
Finally, the Statistics Service itself must be cost-efficient as well. This
requires new algorithms to balance the generation cost and the
comprehensiveness of the statistics (e.g., by varying sampling rates). The
service could identify the hot and cold statistics and design different data
structures on tiered storage to trade-off between querying performance and
storage cost.

To complete the auto-tuning cycle, our system includes a What-if Service that
evaluates tuning proposals from existing auto-tuning tools (Chaudhuri and
Narasayya, 1998; Ma et al., 2018). For each tuning proposal, the What-if
Service generates a relevant workload prediction based on the Statistics
Service. Then it invokes the cost estimator to determine whether the tuning
action is “profitable” using the logic described at the beginning of this
section. Once the What-if Service accepts a tuning proposal (the process could
involve user approval), the job is sent to the background compute for
execution.

##  5\. Conclusion

We introduced the concept of cost intelligence, a much-desired property for
next-generation cloud data warehouses. The architecture proposed in the paper
allows both automatic resource deployment and cost-oriented auto-tuning. We
are actively building the system at Tsinghua University, and we hope that the
paper will inspire talented researchers in the community to tackle the
challenges presented in the paper together.

## References

  * (1)
  * big (2023) 2023\.  BigQuery Enterprise Data Warehouse.  https://cloud.google.com/bigquery.
  * duc (2023) 2023\.  DuckDB: Move to push-based execution model.  https://github.com/duckdb/duckdb/issues/1583.
  * ter (2023) 2023\.  TeraData Github.  https://github.com/Teradata.
  * Akdere et al. (2012) Mert Akdere, Ugur Çetintemel, Matteo Riondato, et al. 2012\.  Learning-based query performance modeling and prediction. In _IEEE ICDE’12_. 390–401.
  * Armenatzoglou et al. (2022) Nikos Armenatzoglou, Sanuj Basu, Naga Bhanoori, et al. 2022\.  Amazon Redshift Re-Invented. In _ACM SIGMOD’22_. 2205–2217.
  * Chaudhuri and Narasayya (1998) Surajit Chaudhuri and Vivek Narasayya. 1998.  AutoAdmin “what-if” index analysis utility.  _ACM SIGMOD Record_ 27, 2 (1998), 367–378.
  * Chen et al. (2016) Jack Chen, Samir Jindel, Robert Walzer, et al. 2016\.  The MemSQL Query Optimizer: A modern optimizer for real-time analytics in a distributed database.  _Proc. VLDB Endow_ 9, 13 (2016), 1401–1412.
  * Dageville et al. (2016) Benoit Dageville, Thierry Cruanes, Marcin Zukowski, et al. 2016\.  The snowflake elastic data warehouse. In _ACM SIGMOD’16_. 215–226.
  * Edara and Pasumansky (2021) Pavan Edara and Mosha Pasumansky. 2021.  Big metadata: when metadata is big data.  _Proc. VLDB Endow_ 14, 12 (2021), 3083–3095.
  * Fan et al. (2020) Zhiwei Fan, Rathijit Sen, Paraschos Koutris, and Aws Albarghouthi. 2020.  Automated tuning of query degree of parallelism via machine learning. In _Workshop on Exploiting Artificial Intelligence Techniques for Data Management (aiDM)_. 1–4.
  * Ferguson et al. (2012) Andrew D Ferguson, Peter Bodik, Srikanth Kandula, et al. 2012\.  Jockey: guaranteed job latency in data parallel clusters. In _ACM EuroSys’12_. 99–112.
  * Florescu and Kossmann (2009) Daniela Florescu and Donald Kossmann. 2009.  Rethinking cost and performance of database systems.  _ACM SIGMOD Record_ 38, 1 (2009), 43–48.
  * Ganapathi et al. (2009) Archana Ganapathi, Harumi Kuno, Umeshwar Dayal, et al. 2009\.  Predicting multiple metrics for queries: Better decisions enabled by machine learning. In _IEEE ICDE’09_. 592–603.
  * Graefe (1995) Goetz Graefe. 1995\.  The cascades framework for query optimization.  _IEEE Data Eng. Bull._ 18, 3 (1995), 19–29.
  * Karampaglis et al. (2014) Zisis Karampaglis, Anastasios Gounaris, and Yannis Manolopoulos. 2014.  A bi-objective cost model for database queries in a multi-cloud environment. In _MEDES’14_. 109–116.
  * Kllapi et al. (2011) Herald Kllapi, Eva Sitaridi, Manolis M Tsangaris, and Yannis Ioannidis. 2011.  Schedule optimization for data processing flows on the cloud. In _ACM SIGMOD’11_. 289–300.
  * Lamb et al. (2012) Andrew Lamb, Matt Fuller, et al. 2012\.  The vertica analytic database: C-store 7 years later.  _Proc. VLDB Endow_ 5, 12 (2012), 1790–1801.
  * Leis et al. (2014) Viktor Leis, Peter Boncz, Alfons Kemper, and Thomas Neumann. 2014\.  Morsel-driven parallelism: A NUMA-aware query evaluation framework for the many-core age. In _ACM SIGMOD’14_. 743–754.
  * Leis and Kuschewski (2021) Viktor Leis and Maximilian Kuschewski. 2021.  Towards cost-optimal query processing in the cloud.  _Proc. VLDB Endow_ 14, 9 (2021), 1606–1612.
  * Lyu et al. (2022) Chenghao Lyu, Qi Fan, Fei Song, et al. 2022\.  Fine-Grained Modeling and Optimization for Intelligent Resource Management in Big Data Processing.  _Proc. VLDB Endow_ 15 (2022).
  * Lyu et al. (2021) Zhenghua Lyu, Huan Hubert Zhang, Gang Xiong, et al. 2021\.  Greenplum: a hybrid database for transactional and analytical workloads. In _ACM SIGMOD’21_. 2530–2542.
  * Ma et al. (2018) Lin Ma, Dana Van Aken, Ahmed Hefny, et al. 2018\.  Query-based workload forecasting for self-driving database management systems. In _ACM SIGMOD’18_. 631–645.
  * Marcus and Papaemmanouil (2019) Ryan Marcus and Olga Papaemmanouil. 2019.  Plan-Structured Deep Neural Network Models for Query Performance Prediction.  _Proc. VLDB Endow_ 12, 11 (2019), 1733–1746.
  * Müller et al. (2020) Ingo Müller, Renato Marroquín, and Gustavo Alonso. 2020\.  Lambada: Interactive data analytics on cold data using serverless cloud infrastructure. In _ACM SIGMOD’20_. 115–130.
  * Narasayya and Chaudhuri (2021) Vivek R. Narasayya and Surajit Chaudhuri. 2021.  Cloud Data Services: Workloads, Architectures and Multi-Tenancy.  _Found. Trends Databases_ 10 (2021), 1–107.
  * Ortiz et al. (2015) Jennifer Ortiz, Victor Teixeira De Almeida, and Magdalena Balazinska. 2015.  Changing the Face of Database Cloud Services with Personalized Service Level Agreements.. In _CIDR’15_.
  * Pavlo et al. (2017) Andrew Pavlo, Gustavo Angulo, Joy Arulraj, et al. 2017\.  Self-Driving Database Management Systems. In _CIDR’17_ , Vol. 4. 1\.
  * Perron et al. (2020) Matthew Perron, Raul Castro Fernandez, David DeWitt, and Samuel Madden. 2020.  Starling: A scalable query engine on cloud functions. In _ACM SIGMOD’20_. 131–141.
  * Pimpley et al. (2022) Anish Pimpley, Shuo Li, Rathijit Sen, et al. 2022\.  Towards Optimal Resource Allocation for Big Data Analytics.. In _EDBT’22_. 2–338.
  * Rajan et al. (2016) Kaushik Rajan, Dharmesh Kakadia, Carlo Curino, and Subru Krishnan. 2016.  Perforator: eloquent performance models for resource optimization. In _ACM SOCC’16_. 415–427.
  * Siddiqui et al. (2020) Tarique Siddiqui, Alekh Jindal, et al. 2020\.  Cost models for big data query processing: Learning, retrofitting, and our findings. In _ACM SIGMOD’20_. 99–113.
  * Tan et al. (2019) Junjay Tan, Thanaa Ghanem, Matthew Perron, et al. 2019\.  Choosing a cloud DBMS: architectures and tradeoffs.  _Proc. VLDB Endow_ 12, 12 (2019), 2170–2182.
  * Tang et al. (2021) Chunxu Tang, Beinan Wang, Zhenxiao Luo, et al. 2021\.  Forecasting SQL query cost at Twitter. In _IEEE ICDE’21_. 154–160.
  * Thamsen et al. (2017) Lauritz Thamsen, Ilya Verbitskiy, Jossekin Beilharz, et al. 2017\.  Ellis: Dynamically scaling distributed dataflows to meet runtime targets. In _2017 IEEE International Conference on Cloud Computing Technology and Science_. IEEE, 146–153.
  * Trummer and Koch (2014) Immanuel Trummer and Christoph Koch. 2014.  Approximation schemes for many-objective query optimization. In _ACM SIGMOD’14_. 1299–1310.
  * Venkataraman et al. (2016) Shivaram Venkataraman, Zongheng Yang, Michael Franklin, Benjamin Recht, and Ion Stoica. 2016\.  Ernest: Efficient Performance Prediction for Large-Scale Advanced Analytics. In _USENIX NSDI’16_. 363–378.
  * Viswanathan et al. (2018) Lalitha Viswanathan, Alekh Jindal, and Konstantinos Karanasos. 2018\.  Query and resource optimization: Bridging the gap. In _IEEE ICDE’18_. 1384–1387.
  * Yint et al. (2018) Zhicheng Yint, Jin Sun, Ming Li, et al. 2018\.  Bubble execution: resource-aware reliable analytics at cloud scale.  _Proc. VLDB Endow_ 11, 7 (2018), 746–758.