
\section{Reducing Materialization Space} 

A direct application of~\autoref{thm:main} can lead to cases where, if enumeration is carried to the end, almost all the tuples in the output are materialized. In this section, we show how to incorporate instance specific properties to reduce this space requirement. 

Before we state the main result, we introduce some notation. For a node $t$ of a tree decomposition, we denote by $\tOUT(\mB_t)$ the materialized output of its bag, and by $\tOUT(\subtree{t})$ the output of the subtree rooted at $t$. For a valuation $\theta$, we use $R \ltimes \theta$ to denote the restriction of the set $R$ on valuations that agree with $\theta$. 

\begin{theorem} 
	Let $Q$ be a natural join query with hypergraph $\mH = (\nodes, \edges)$. Let $\htree$ be a fixed tree decomposition with fractional hypertree-width \fhw, such that the root node $r$ has two children $b,c$.
	Then, for any input database $D$ and ranking function compatible with $\htree$, we can preprocess $D$ in time and space,
	$$
	T_p = {O}(\log |D| \cdot |D|^{\fhw}) \quad \quad S_p = {O}(|D|^{\fhw})
	$$
	such that for any $k$, we can enumerate the top-$k$ results of $Q(D)$ with delay $\text{delay } \delta = O(\log |D|)$ and space
	\begin{align*}
	\qquad \qquad \qquad \text{space } S_e &= O(\vert D \vert^\fhw + \min\{\mk, |\tOUT(\subtree{b})| + |\tOUT(\subtree{c})| + \\
	& \sum_{\theta \in \tOUT(\mB_r)} \min \{| \tOUT(\subtree{b}) \ltimes \theta|, | \tOUT(\subtree{c}) \ltimes \theta|  \}   \})
	\end{align*} \label{thm:main:2}
\end{theorem}

Next, we demonstrate how to apply~\autoref{thm:main:2} to different cases.

\begin{example} \label{ex:three:path}
	Consider the $3$-path query $Q(x,y,z) = R(x,y), S(y,z),$  $T(z,w)$. Fix the decomposition where $\{y,z\}$ is at the root with the one child $\mB_b =\{x,y\}$ and the other child $\mB_c = \{z,w\}$. For simplicity, we fix the size of each relation as $N$. This gives $|\tOUT(\subtree{b})| = |\tOUT(\subtree{c})| = N$.  Further, 
	$ \sum_{\theta \in \tOUT(\mB_r)} \min \{| \tOUT(\subtree{b}) \ltimes \theta|, | \tOUT(\subtree{c}) \ltimes \theta|  \}   \leq N^{1/2} |\tOUT|^{1/2}$.
	%
	Then,~\autoref{thm:main:2} gives space $S_e = O(N + \min\{\mk, \sqrt{N \cdot |\tOUT|}\})$.
	In the worst-case $|\tOUT| = N^2$ and $S_e = O(N^{3/2})$, while~\autoref{thm:main} requires $\Theta(N^2)$ space. 

\end{example} 

Generalizing the $3$-path example to $t$-path queries (each of fixed size $N$), we can achieve linear time preprocessing 
with $O(\log N)$ delay using space $S_e = O(N + \min\{\mk,N^{(\rho^*+1)/2}\})$.

If for a specific tree decomposition $\htree$ the root has more than two children, we can still apply the theorem by modifying the decomposition as follows: we partition the children into two subsets $S_b, S_c$, and create two new nodes $b,c$. The bag of node $b$  contains all the variables from $S_b$ that occur in the root, and similarly for $c$. Node $b$ is connected to all nodes in $S_b$, as well as the root node (similarly for $c$). Note that this transformation does not change the fractional hypertree width of the decomposition. 

\begin{example} \label{ex:cartesian}
	Consider the cartesian product query $Q(x,y,z,w) = R(x), S(y),$ $T(z), U(w)$. Let the decomposition for $Q$ have $\{x\}$ at the root and $\{y\}, \{z\}, \{w\}$ as its children. We create two nodes $b,c$, with empty bags, where $b$ is connected to $\{y\}, \{z\}, \{x\}$, and $c$ to $\{w\},\{x\}$.
	One can see that the resulting space guarantee during enumeration becomes $S_e = O(N^2)$, where $N$ is the size of each relation. 
\end{example}

The above idea can be generalized as follows.

\begin{proposition}
	Consider a cartesian product query $Q(x_1, \dots, x_t) = R_1(x_1), \dots, R_t(x_t)$. For any totally decomposable ranking function, we can enumerate the top-$k$ tuples after linear time preprocessing with ${O}(\log N)$ delay using space 
	$S_e = O(N + \min \{ k, O(N^{\lceil \frac{t}{2} \rceil})\}$
\end{proposition}

In the case where the root node of the decomposition has only one child (say $t$), we can again transform it accordingly.
Indeed, we can create a new decomposition $\htree'$ (with the same width) where $\mbroot \cap \mB_{t}$ is the new root, $\mB_r$ is the left child and $\mB_t$ is the right child. By doing this transformation,~\autoref{thm:main:2} implies that the space guarantee reduces from $|\tOUT|$ to $|\tOUT(\subtree{t})|$, which can be much smaller.  

\begin{example}
	Consider the $2$-path query $Q(x,y,z) = R(x,y), S(y,z)$. For any totally decomposable ranking function, we can enumerate the top-$k$ tuples after linear time preprocessing with ${O}(\log N)$ delay using only $O(N)$ space in the worst case.
\end{example}

It is an interesting question to find the best instance-specific decomposition according to the data, query structure and ranking function; we leave this as an open problem.

\subsection{Proof of~\autoref{thm:main:2}}

Before we describe the main algorithm, we present some intuition. \autoref{fig:decomposition} shows the conceptual difference between~\autoref{thm:main} and the modified algorithm. For a fixed root valuation, algorithm from previous section would generate next candidates by incrementally enumerating the cartesian product. This is inefficient as it inevitably takes $|\tOUT_b| \cdot |\tOUT_c|$ space in the worst-case. The proposed change in this section enumerates the next candidates by keeping $|\tOUT_b|$ pointers to $\tOUT_c$ which is enough to get space savings. We now describe the modifications. To simplify the description, we assume that for each $\theta \in \tOUT(\mB_r)$, $d^{+}(\subtree{b}, \theta) = |\tOUT(\subtree{{b}}) \ltimes \theta|$ (and similarly for $c$) is already computed. Further, we will create a modified cell structure only for use by node $b$ and $c$, $\psi(v) = \llangle v, [p_1, \dots p_i],$ $\mnext  \rrangle$. $[p_1, \dots p_i]$ are pointers to cells of children nodes of $b$ and $c$. Additionally, it also includes a pointer $\mnext$ that will only point to an object of type modified cell. We will modify our algorithm in the following way:

\begin{enumerate}
	
	\item {\em Initialization of $\qQ_{r}[()]$} : The preprocessing phase remains exactly the same as~\autoref{algo:preprocessing} for all bags except the root and its children. Once all other nodes have been processed, for each root node valuation $\theta$, we create modified cells for nodes $b$ and $c$ (if they don't already exist). Let $\theta(e) = \theta[\key{\mB_e}]$ for some node $e$.
	%
	\begin{align*}
		\theta_c(1)  &= \llangle \theta(c), [q_1, \dots q_\ell], \bot \rrangle \\
		\theta_b(1)  &= \llangle \theta(b), [p_1, \dots p_m],\addressof \theta_c(1) \rrangle
	\end{align*}
	
	where $p_i = \addressof \qQ_s[\theta(s)].\mathsf{top()}, i \in [m]$ for each child $s$ of $\mB_b$ and $q_i = \addressof \qQ_s[\theta(s)].\mathsf{top()}, i \in [\ell]$ for each child $s$ of $\mB_c$ and$\addressof$ operator returns the address of memory location of its argument. Intuitively, $\theta_b(1)$ and $\theta_c(1)$ are the smallest ranked valuation over subtree rooted at node $b$ and $c$. We insert them into priority queue $\qQ_{b}[\theta(b)]$ and $\qQ_{c}[\theta(c)]$ respectively. Finally, we push $\psi(\theta) = \llangle \theta, [\addressof \theta_b(1)], \bot \rrangle$ into $\qQ_{r}$.~\autoref{algo:preprocessing:modified} describes the detailed algorithm.
	
	\item {\em Enumeration phase} : Suppose that output valuation $\psi(\theta)$ is popped from $\qQ_{r}[()]$ pointing to modified cell $\theta_b(i)$ that in turn points to $\theta_c(j)$.
	Then, we will push two new cells into root priority queue. First, 
	
	\begin{itemize}
		\item find the next ranked valuation after $\theta_c(j)$ (say $\theta_c(j+1)$)
		\item set $\theta_b(i).\mnext = \addressof \theta_c(j+1)$
		\item chain $\theta_c(j).\mnext = \addressof \theta_c(j+1)$
		\item insert $\psi''(\theta) = \llangle \theta, [\addressof \theta_b(i)], $ $\bot \rrangle$ into root priority queue.
	\end{itemize}
	
	We will discuss in a bit how to find $\theta_c(j+1)$. Second, if $\pi_{\mB_b}(\theta)$ is not the last valuation in $\tOUT(\subtree{b}) \ltimes \theta$,
	
	\begin{itemize}
		\item  find next ranked valuation after $\theta_b(i)$ (say $\theta_b(i+1)$)
		\item set $\theta_b(i+1).\mnext = \addressof \theta_c(1)$
		\item insert $\psi'(\theta) = \llangle \theta, [\addressof \theta_b(i+1)], \bot \rrangle$.
	\end{itemize}

	~\autoref{algo:enumeration:modified} describes the detailed algorithm for enumeration.
	
\end{enumerate}

\begin{figure} 
	\centering
	\vspace{-1em}
	
	\begin{minipage}{0.45\linewidth}
		\centering
		\scalebox{.99}{\begin{tikzpicture} 
			\tikzset{edge/.style = {->,> = latex'},
				vertex/.style={circle, thick, minimum size=7mm}}
			\def0.25{0.25}
			\def-1{-0.5}		
			
			\begin{scope}[fill opacity=1]
			
			\tikzset{root/.style = {rectangle split, rectangle split parts=1,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=8em, align=center}}
			
			\node[root] (t1)  at (0,0) {
				\nodepart{one} {\mystrut \small root valuation $t$}
			};
			
			\node[root] (t21)  at (-1.75,-1.5) {
				\nodepart{one} {\mystrut \small child valuation $b_1$}
			};
			
			\node[root] (t22)  at (-1.75,-2.75) {
				\nodepart{one} {\mystrut \small child valuation $b_2$}
			};
			
			\node[root] (t31)  at (1.75,-1.5) {
				\nodepart{one} {\mystrut \small child valuation $c_1$}
			};
			
			\node[root] (t32)  at (1.75,-2.75) {
				\nodepart{one} {\mystrut \small child valuation $c_2$}
			};
			
			\node[vertex]  at (-1.75, -3.3) {$\boldsymbol{\vdots}$};
			\node[vertex]  at (1.75, -3.3) {$\boldsymbol{\vdots}$};
			\node[vertex]  at (0, -2.1) {$\boldsymbol{\times}$};
			\node[vertex]  at (-2.5, -0.5) {$\tOUT_b$};
			\node[vertex]  at (2.5, -0.5) {$\tOUT_c$};
			\draw[edge] [fill=black!5,text opacity=1] (-0.15, -1) -> (-0.15,-3.5);	
			\draw[edge] [fill=black!5,text opacity=1] (0.15, -1) -> (0.15,-3.5);
			
			\draw[*->] (t1.one south) to[out=-90,in=90] (t21.one north);
			\draw[*->] (t21.one west) to[out=-180,in=-180] (t22.one west);
			
			\draw[*->] (t1.one south) to[out=-90,in=90] (t31.one north);
			\draw[*->] (t31.one east) to[out=0,in=-0] (t32.one east);
			\end{scope}
			\end{tikzpicture}
		}
	\end{minipage} \hfill
	\begin{minipage}{0.45\linewidth}
		\centering
		\scalebox{.99}{\begin{tikzpicture} 
			\tikzset{edge/.style = {->,> = latex'},
				vertex/.style={circle, thick, minimum size=7mm}}
			\def0.25{0.25}
			\def-1{-0.5}		
			
			\begin{scope}[fill opacity=1]
			
			\tikzset{root/.style = {rectangle split, rectangle split parts=1,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=8em, align=center}}
			
			\node[root] (t1)  at (0,0) {
				\nodepart{one} {\mystrut \small root valuation $t$}
			};
			
			\node[root] (t21)  at (-1.75,-1.5) {
				\nodepart{one} {\mystrut \small child valuation $b_1$}
			};
			
			\node[root] (t22)  at (-1.75,-2.75) {
				\nodepart{one} {\mystrut \small child valuation $b_2$}
			};
			
			\node[root] (t31)  at (1.75,-1.5) {
				\nodepart{one} {\mystrut \small child valuation $c_1$}
			};
			
			\node[root] (t32)  at (1.75,-2.75) {
				\nodepart{one} {\mystrut \small child valuation $c_2$}
			};
			
			\node[vertex]  at (-1.75, -3.3) {$\boldsymbol{\vdots}$};
			\node[vertex]  at (1.75, -3.3) {$\boldsymbol{\vdots}$};
			\node[vertex]  at (0, -2.1) {$\boldsymbol{\times}$};
			\node[vertex]  at (-2.5, -0.5) {$\tOUT_b$};
			\node[vertex]  at (2.5, -0.5) {$\tOUT_c$};
			\draw[edge] [fill=black!5,text opacity=1] (4, -1.4) -> (4,-3);
			
			\draw[*->] (t1.one south) to[out=-90,in=90] (t21.one north);
			\draw[*->] (t21.one east) to[out=0,in=-180] (t31.one west);
			\draw[*->] (t22.one east) to[out=0,in=-180] (t31.one west);
			\draw[*->] (t31.one east) to[out=0,in=-0] (t32.one east);
			\end{scope}
			\end{tikzpicture}
		}
	\end{minipage}
	\caption{(left)~\autoref{thm:main} enumerates result by cartesian product; (right) modified algorithm that enumerates result via $|\tOUT_b|$ pointers } \label{fig:decomposition}
\end{figure}

In other words, in the worst-case, for each valuation $\theta \in \tOUT(\mB_r)$ there will be at most $d^{+}(\subtree{b}, \theta)$ pointers from each valuation in $\tOUT(\subtree{b}) \ltimes \theta$ to $\tOUT(\subtree{c}) \ltimes \theta$. The first observation is that we can use procedure $\FuncSty{\texttt{topdown}}$ from~\autoref{thm:main} to enumerate $\tOUT(\subtree{b})$ and $\tOUT(\subtree{c})$ for a given key valuation in ranked order. This is possible because any compatible ranking function over the decomposition $\htree$ is also compatible for any subtree of the decomposition. Thus, we can use $\FuncSty{\texttt{topdown}}$ from~\autoref{algo:enumeration} to find $\theta_b(i+1)$ and $\theta_c(j+1)$.

\begin{figure*} 
	\begin{subfigure}{0.45\linewidth}
		
		\hspace{-3em}
		\scalebox{.6}{
			\begin{tikzpicture} 
			\tikzset{edge/.style = {->,> = latex'},
				vertex/.style={circle, thick, minimum size=7mm}}
			\def0.25{0.25}
			\def-1{-0.5}		
			
			\begin{scope}[fill opacity=1]
			\draw[fill=black!5] (0, 0) ellipse (1cm and 0.33cm) node {\small ${\color{black} \vec{y}, \underline{x}}$};
			\draw[fill=black!5] (-4.2, -1+-1) ellipse (1cm and 0.33cm) node {\small ${\color{black} \underline{x}, \vec{z}_1}$};
			\draw[fill=black!5] (-1.2, -1+-1) ellipse (1cm and 0.33cm) node {\small ${\color{black} \underline{x}, \vec{z}_p}$};
			\draw[fill=black!5] (1.2, -1+-1) ellipse (1cm and 0.33cm) node {\small ${\color{black} \underline{x}, \vec{z}_{p+1}}$};				
			\draw[fill=black!5] (4.2, -1+-1) ellipse (1cm and 0.33cm) node {\small ${\color{black} \underline{x}, \vec{z}_{\ell}}$};						
		
		
			
			
			\draw[edge] [fill=black!5,opacity=0,text opacity=1] (1, 0) -- (1.9,-1+0.2);						
			\draw[edge] [fill=black!5,text opacity=1] (-1, 0) -- (-1.9,-1+0.2);	
			\draw[edge] [fill=black!5,text opacity=1] (1, 0) -- (1.9,-1+0.2);								
			\draw[edge] [fill=black!5,text opacity=1] (-2, -0.7) -- (-1,-1.2);	
			\draw[edge] [fill=black!5,text opacity=1] (2, -0.7) -- (1,-1.2);
			\draw[edge] [fill=black!5,text opacity=1] (-2.5, -0.5) -- (-4,-1.2);
			\draw[edge] [fill=black!5,text opacity=1] (2.5, -0.5) -- (4,-1.2);	
			\draw[fill=black!5] (2.5, -0.5) ellipse (0.75cm and 0.33cm) node {\small ${\color{black} \underline{x}}$};
			\draw[fill=black!5] (-2.5, -0.5) ellipse (0.75cm and 0.33cm) node {\small ${\color{black} \underline{x}}$};
			
			\node[vertex]  at (-3.5, -0.5) {$\mB_b$};
			\node[vertex]  at (3.5, -0.5) {$\mB_c$};
			\node[vertex]  at (-2.7, -1+-1) {$\boldsymbol{\dots}$};		
			\node[vertex]  at (2.7, -1+-1) {$\boldsymbol{\dots}$};				
			\node[vertex]  at (4.5, -2+-1) {$\tOUT(\mB_c, s_1)$};		
			\node[vertex]  at (-4.5, -2+-1) {$\tOUT(\mB_b,s_1)$};				
			
			\matrix [nodes={fill=blue!10,minimum size=6mm, scale=1,text depth=.5ex,text height=2ex,text width=1em},ampersand replacement=\&, font=\tt \small ] at (-4.5,0.5)
			{
				\& \node {$y$}; \&  \node {$\underline{x}$}; \\
				\node {$(s_1)$}; \& \node {3}; \&  \node (t1) {7}; \\
			};
			
			\tikzset{root/.style = {rectangle split, rectangle split parts=1,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6.5em, align=center}}
			
			\node[root] (b1)  at (-2, 0.5) {
				\nodepart{one} {\mystrut \small $\langle s_1, [\tikz\draw[blue,fill=blue] circle (.5ex);], \bot \rangle$ \quad {$5$}}
			};	
			
			\matrix (m1) [nodes={fill=blue!10,minimum size=6mm, scale=1,text depth=.5ex,text height=2ex,text width=1em},ampersand replacement=\&, font=\tt \small ] at (-4.5,-4)
			{
				\& \node (t2) {$\underline{x}$}; \&  \node {$z_1$}; \& \node {$\dots$}; \& \node {$z_p$}; \\
				\node {$(t_1)$}; \& \node {7}; \& \node {1}; \& \node {$\dots$}; \& \node (n1) {4}; \\
				\node {$(t_2)$}; \& \node {7}; \& \node {3}; \& \node {$\dots$}; \& \node (n2) {6}; \\
				\& \node {$\vdots$}; \& \node {$\vdots$}; \& \node {$\vdots$}; \& \node {$\vdots$}; \\				
			};
			
			\tikzset{left1/.style = {rectangle split, rectangle split parts=1,
					draw=green!150, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=7em, align=center, rectangle split part fill={blue!20}}}
			
			\node[left1] (b21)  at (-1.5, -3) {
				\nodepart{one} {\mystrut \small $\langle t_1, [\dots], \tikz\draw[orange,fill=orange] circle (.5ex); \rangle$ \quad {$3$}}
			};
			
			\tikzset{left2/.style = {rectangle split, rectangle split parts=1,
					draw=green!150, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=7em, align=center, rectangle split part fill={magenta!40}}}
			
			\node[left2] (b22)  at (-1.5, -4) {
				\nodepart{one} {\mystrut \small $\langle t_2, [\dots], \tikz\draw[orange,fill=orange] circle (.5ex); \rangle$ \quad {$4$}}
			};
			
			
			\matrix (m2) [nodes={fill=blue!10,minimum size=6mm, scale=1,text depth=.5ex,text height=2ex,text width=1em},ampersand replacement=\&, font=\tt \small ] at (5, -4)
			{
				\node (t3) {$\underline{x}$}; \&  \node {$z_1$}; \& \node {$\dots$}; \& \node {$z_p$}; \& \\
				\node (n4) {7}; \& \node {7}; \& \node {$\dots$}; \& \node {3}; \& \node {$(u_1)$};\\
				\node (n5) {7}; \& \node {2}; \& \node {$\dots$}; \& \node {2}; \& \node {$(u_2)$};\\
				\node {$\vdots$}; \& \node {$\vdots$}; \& \node {$\vdots$}; \& \node {$\vdots$}; \\			
			};
			
			\tikzset{right1/.style = {rectangle split, rectangle split parts=1,
					draw=green!150, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=7em, align=center,rectangle split part fill={orange!60}}}
			
			\node[right1] (b31)  at (2, -3) {
				\nodepart{one} {\mystrut \small $\langle u_1, [\dots], \tikz\draw[brown,fill=brown] circle (.5ex); \rangle$ \quad {$3$}}
			};
			
			\tikzset{right2/.style = {rectangle split, rectangle split parts=1,
					draw=green!150, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=7em, align=center, rectangle split part fill={brown!30}}}
			
			\node[right2] (b32)  at (2, -4) {
				\nodepart{one} {\mystrut \small $\langle u_2, [\dots], \bot \rangle$ \quad {$4$}}
			};
			
			\draw[*->, color=brown, dashed] (b31.one south) to[out=-90,in=90] (b32.one north);
			\draw[*->, color=orange] (b21.one east) to[out=0,in=180] (b31.one west);
			\draw[*->, color=brown, dashed] (b21.one east) to[out=0,in=180] (b32.one west);
			\draw[*->, color=orange, dashed] (b22.one east) to[out=0,in=180] (b31.one west);
			
			\draw[*->, color=blue] (b1.one east) to[out=0,in=90] (b21.one north);
			\draw[*->, color=magenta, dashed] (b1.one east) to[out=0,in=-180] (b22.one west);
			
			\end{scope}	
			\end{tikzpicture}}
		\caption{Pointers from $\tOUT(\mB_b)$ to $\tOUT(\mB_c)$} \label{fig:decomposition:left}
	\end{subfigure}	
	\begin{subfigure}{0.45\linewidth}
		\hspace{1em}
		\scalebox{.6}{
			\begin{tikzpicture} 
			\tikzset{edge/.style = {->,> = latex'},
				vertex/.style={circle, thick, minimum size=7mm}}
			\def0.25{0.25}
			\def-1{-0.5}		
			
			
			\begin{scope}[fill opacity=1]
			\draw[fill=black!5] (0, 0) ellipse (1cm and 0.33cm) node {\small ${\color{black} \vec{y}, \underline{x}}$};
			\draw[fill=black!5] (-4.2, -1+-1) ellipse (1cm and 0.33cm) node {\small ${\color{black} \underline{x}, \vec{z}_1}$};
			\draw[fill=black!5] (-1.2, -1+-1) ellipse (1cm and 0.33cm) node {\small ${\color{black} \underline{x}, \vec{z}_p}$};
			\draw[fill=black!5] (1.2, -1+-1) ellipse (1cm and 0.33cm) node {\small ${\color{black} \underline{x}, \vec{z}_{p+1}}$};				
			\draw[fill=black!5] (4.2, -1+-1) ellipse (1cm and 0.33cm) node {\small ${\color{black} \underline{x}, \vec{z}_{\ell}}$};						
		
		
			
			
			\draw[edge] [fill=black!5,opacity=0,text opacity=1] (1, 0) -- (1.9,-1+0.2);						
			\draw[edge] [fill=black!5,text opacity=1] (-1, 0) -- (-1.9,-1+0.2);	
			\draw[edge] [fill=black!5,text opacity=1] (1, 0) -- (1.9,-1+0.2);								
			\draw[edge] [fill=black!5,text opacity=1] (-2, -0.7) -- (-1,-1.2);	
			\draw[edge] [fill=black!5,text opacity=1] (2, -0.7) -- (1,-1.2);
			\draw[edge] [fill=black!5,text opacity=1] (-2.5, -0.5) -- (-4,-1.2);
			\draw[edge] [fill=black!5,text opacity=1] (2.5, -0.5) -- (4,-1.2);	
			\draw[fill=black!5] (2.5, -0.5) ellipse (0.75cm and 0.33cm) node {\small ${\color{black} \underline{x}}$};
			\draw[fill=black!5] (-2.5, -0.5) ellipse (0.75cm and 0.33cm) node {\small ${\color{black} \underline{x}}$};
			
			\node[vertex]  at (-3.5, -0.5) {$\mB_b$};
			\node[vertex]  at (3.5, -0.5) {$\mB_c$};
			\node[vertex]  at (-2.7, -1+-1) {$\boldsymbol{\dots}$};		
			\node[vertex]  at (2.7, -1+-1) {$\boldsymbol{\dots}$};				
			\node[vertex]  at (4.5, -2+-1) {$\tOUT(\mB_c, s_1)$};		
			\node[vertex]  at (-4.5, -2+-1) {$\tOUT(\mB_b,s_1)$};				
			
			\matrix [nodes={fill=blue!10,minimum size=6mm, scale=1,text depth=.5ex,text height=2ex,text width=1em},ampersand replacement=\&, font=\tt \small ] at (-4.5,0.5)
			{
				\& \node {$y$}; \&  \node {$\underline{x}$}; \\
				\node {$(s_1)$}; \& \node {3}; \&  \node (t1) {7}; \\
			};
			
			\tikzset{root/.style = {rectangle split, rectangle split parts=1,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6.5em, align=center}}
			
			\node[root] (b1)  at (-2, 0.5) {
				\nodepart{one} {\mystrut \small $\langle s_1, [\tikz\draw[orange,fill=orange] circle (.5ex);], \bot \rangle$ \quad {$5$}}
			};	
			
			\matrix (m1) [nodes={fill=blue!10,minimum size=6mm, scale=1,text depth=.5ex,text height=2ex,text width=1em},ampersand replacement=\&, font=\tt \small ] at (-4.5,-4)
			{
				\& \node (t2) {$\underline{x}$}; \&  \node {$z_1$}; \& \node {$\dots$}; \& \node {$z_p$}; \\
				\node {$(t_1)$}; \& \node {7}; \& \node {1}; \& \node {$\dots$}; \& \node (n1) {4}; \\
				\node {$(t_2)$}; \& \node {7}; \& \node {3}; \& \node {$\dots$}; \& \node (n2) {6}; \\
				\& \node {$\vdots$}; \& \node {$\vdots$}; \& \node {$\vdots$}; \& \node {$\vdots$}; \\				
			};
			
			\tikzset{left1/.style = {rectangle split, rectangle split parts=1,
					draw=green!150, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=7em, align=center, rectangle split part fill={blue!20}}}
			
			\node[left1] (b21)  at (-1.5, -3) {
				\nodepart{one} {\mystrut \small $\langle t_1, [\dots], \tikz\draw[magenta,fill=magenta] circle (.5ex); \rangle$ \quad {$3$}}
			};
			
			\tikzset{left2/.style = {rectangle split, rectangle split parts=1,
					draw=green!150, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=7em, align=center, rectangle split part fill={magenta!40}}}
			
			\node[left2] (b22)  at (-1.5, -4) {
				\nodepart{one} {\mystrut \small $\langle t_2, [\dots], \bot \rangle$ \quad {$4$}}
			};
			
			
			\matrix (m2) [nodes={fill=blue!10,minimum size=6mm, scale=1,text depth=.5ex,text height=2ex,text width=1em},ampersand replacement=\&, font=\tt \small ] at (5, -4)
			{
				\node (t3) {$\underline{x}$}; \&  \node {$z_1$}; \& \node {$\dots$}; \& \node {$z_p$}; \& \\
				\node (n4) {7}; \& \node {7}; \& \node {$\dots$}; \& \node {3}; \& \node {$(u_1)$};\\
				\node (n5) {7}; \& \node {2}; \& \node {$\dots$}; \& \node {2}; \& \node {$(u_2)$};\\
				\node {$\vdots$}; \& \node {$\vdots$}; \& \node {$\vdots$}; \& \node {$\vdots$}; \\			
			};
			
			\tikzset{right1/.style = {rectangle split, rectangle split parts=1,
					draw=green!150, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=7em, align=center,rectangle split part fill={orange!60}}}
			
			\node[right1] (b31)  at (2, -3) {
				\nodepart{one} {\mystrut \small $\langle u_1, [\dots], \tikz\draw[blue,fill=blue] circle (.5ex); \rangle$ \quad {$3$}}
			};
			
			\tikzset{right2/.style = {rectangle split, rectangle split parts=1,
					draw=green!150, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=7em, align=center, rectangle split part fill={brown!30}}}
			
			\node[right2] (b32)  at (2, -4) {
				\nodepart{one} {\mystrut \small $\langle u_2, [\dots], \tikz\draw[blue,fill=blue] circle (.5ex); \rangle$ \quad {$4$}}
			};
			
			\draw[*->, color=magenta, dashed] (b21.one south) to[out=-90,in=90] (b22.one north);
			\draw[*->, color=blue!50] (b31.one west) to[out=180,in=0] (b21.one east);
			\draw[*->, color=magenta, dashed] (b31.one west) to[out=180,in=0] (b22.one east);
			\draw[*->, color=blue!50, dashed] (b32.one west) to[out=180,in=0] (b21.one east);
			
			\draw[*->, color=orange] (b1.one east) to[out=0,in=90] (b31.one north);
			\draw[*->, color=brown, dashed] (b1.one east) to[out=0,in=0] (b32.one east);
			
			\end{scope}	
			\end{tikzpicture}}
		\caption{Pointers from $\tOUT(\mB_c)$ to $\tOUT(\mB_b)$} \label{fig:decomposition:right}
	\end{subfigure}	
	\caption{Modified algorithm example} \label{fig:pointers}
\end{figure*}

\begin{algorithm}
	\SetCommentSty{textsf}
	\DontPrintSemicolon 
	\SetKwFunction{fullreducer}{\textsc{Materialize}}
	\SetKwFunction{initializepq}{\textsc{InitializePQ}}
	\SetKwFunction{recurse}{\textsc{Recurse}}
	\SetKwFunction{proc}{\textsf{eval}}
	\SetKwFunction{ins}{\textsc{insert}}
	\SetKwFunction{app}{\textsc{insert}}
	\SetKwFunction{top}{\textsc{top()}}
	\SetKwFunction{pop}{\textsc{pop()}}
	\SetKwData{pointer}{\textsf{pointer}}
	\SetKwData{temp}{\textsf{temp}}
	\SetKwData{red}{\textsf{ref}}
	\SetKwFunction{fillout}{\textsc{FillOUT}}
	\SetKwInOut{Input}{\textsc{input}}
	\SetKwInOut{Global}{\textsc{global variables}}
	\SetKwInOut{Output}{\textsc{output}}
	\SetKwProg{myproc}{\textsc{procedure}}{}{}
	%



	\BlankLine
	
	\ForEach{$t \in V(\htree)$}{
		\textit{materialize the bag} $\mB_t$ \;
	}
	\textit{perform full reducer pass on materialized bags in} $\htree$ \;
	
	\BlankLine
	\ForAll{$t \in V(\htree)$ in post-order traversal except root}{
		\ForEach{valuation $v$ in bag $\mB_t$}{
			$u \gets v[\key{\mB_t}]$\;
			\If{$\qQ_t[u]$ is $\texttt{NULL}$}{ $\qQ_t[u] \gets$ new priority queue \;}
			$\ell \gets []$ \;
			\ForEach{child $s$ of $t$}{ 
				$\ell.\app(\& \qQ_s[v[\key{\mB_{s}}]].\top)$ \;
			}
			$\qQ_t[u].\ins(\langle v, \ell, \bot \rangle)$ \;
		}
	}
	$\qQ_r \gets$ new priority queue \;
	\ForEach{valuation $\theta$ in bag $\mB_r$}{
		$\theta(b) \gets v[\key{\mB_b}]$, $\theta(c) \gets v[\key{\mB_c}]$ \;
		\If{$\qQ_{b}[\theta_b]$ is $\texttt{NULL}$}{ $\qQ_{b}[\theta_b] \gets$ new priority queue \;}
		\If{$\qQ_{c}[\theta_c]$ is $\texttt{NULL}$}{ $\qQ_{c}[\theta_c] \gets$ new priority queue \;}
		
		$\ell \gets [], w \gets \emptyset$ \;
		\ForEach{child bag $s$ of $c$}{
			$\ell.\app(\addressof \qQ_s[\theta(s)].\top)$ \;
			/* $\circ$ operator joins tuples */ \;
			$w \gets w \circ \qQ_s[\theta(s)].\top.v$ \;
		}
		$\qQ_{c}[\theta(c)].\ins(\langle w, \ell, \bot \rangle)$ \;	
		$\theta_c(1) \gets \addressof \qQ_{c}[\theta(c)].\top$ \;
		$\ell \gets [], w \gets \emptyset$ \;
		\ForEach{child bag $s$ of $b$}{
			$\ell.\app(\addressof \qQ_s[\theta(s)].\top)$ \;
			/* $\circ$ operator joins tuples */ \;
			$w \gets w \circ \qQ_s[\theta(s)].\top.v$ \;
		}
		$\qQ_{b}[\theta(b)].\ins(\langle w, \ell, \bot \rangle)$ \;	
		$\qQ_{r}[()].\ins(\langle v, [\addressof \qQ_{b}[\theta(b)].\top], \bot \rangle)$ \;
	}
	
	\caption{Preprocessing Phase}
	\label{algo:preprocessing:modified}
\end{algorithm}


\begin{example}
	~\autoref{fig:decomposition:left} shows an example instance to illustrate the idea. Green bordered cells are instances of modified cells $S(v)$, i.e the cells that store valuations over subtree $\mB_b$ or $\mB_c$. After the preprocessing stage, cell with $s_1$ points to $b(s_1, 1)$ (modified cell $t_1$) shown in blue arrow. $b(s_1, 1)$ in turn points to $c(s_1, 1)$ (modified cell $u_1$). The first answer is formed by $s_1 \rightarrow t_1 \rightarrow u_1$. The next smallest valuation after $u_1$ is $u_2$. We update $u_1.next = u_2$ and insert $s_1 \rightarrow t_1 \rightarrow u_2$ (shown by dashed brown arrow from $t_1$ to $u_2$). Additionally, we insert $s_1 \rightarrow t_2 \rightarrow u_1$ (dashed magenta and orange arrow) into $\qQ_r$. $t_1, t_2$ and $u_1, u_2$ are constructed using \FuncSty{\texttt{topdown}} procedure from~\autoref{algo:enumeration}.
\end{example}

Let us now analyze the space requirement of this algorithm,
$$
S_1 = \vert \tOUT(\subtree{c}) \vert + \sum_{\theta \in \tOUT(\mB_r)} d^+(\subtree{b}, \theta) 
$$
However, we could have also chosen to have pointers from $\tOUT(\subtree{c}) \ltimes \theta$ to $\tOUT(\subtree{b}) \ltimes \theta$ as shown in~\autoref{fig:decomposition:right}. In this case, the space requirement would be,
$$
S_2 = \vert \tOUT(\subtree{b}) \vert + \sum_{\theta \in \tOUT(\mB_r)} d^+(\subtree{c}, \theta) 
$$
Our second key observation is that we can use the power of two choices. In particular, for each root valuation $t$, we can choose which side we keep pointers from based on the smaller of $d^+(\subtree{b}, \theta)$ and $d^+(\subtree{c}, t)$. This will lead to the following space bound,

$$
S = \sum_{e \in \{b,c\}}\vert \tOUT(\subtree{e}) \vert + \sum_{\theta \in \tOUT(\mB_r)} \min\{d^+(\subtree{c}, \theta),  d^+(\subtree{b}, \theta)\}
$$

We conclude this section by removing the assumption about $d^+(\subtree{e}, \theta)$. The key observation is that once the dangling tuples have been removed in the preprocessing phase, $d^+(\subtree{e}, \theta)$ can be computed in bottom-up fashion by counting the number of tuples for a particular valuation of $t[\key{\mB'}]$ in the children bags $\mB'$ and taking their product. For the base case of leaf nodes, this can simply be done by counting $|\tOUT({\mB}) \ltimes \theta[\key{\mB}]|$ in a linear pass.~\autoref{sec:modified:algorithm} shows how the idea of~\autoref{thm:main:2} can be applied to more general queries as well.



\section{Extending~\autoref{thm:main:2}} \label{sec:modified:algorithm}

The core idea of \autoref{thm:main:2} can be useful for other acyclic queries as well depending on $k$. To illustrate how the idea can be extended, we will review the following example with four relations.

Let $Q(x,y,z,w,p,q,r) = R(x,y,z,w), S(p,x,y), T(q,y,z), U(r,z,w)$. Consider the decomposition that places $\{x,y,z,w\}$ at the root and $\{p,x,y\}, \{q,y,z\}, \{r,z,w\}$ as its children. For each tuple $s \in R$, we can choose to keep pointers from $t \in S$ to on-the-fly materialized output of $OUT_1 = T(q,y,z) \Join U(r,z,w)$ or pointers from $t \in T$ to on-the-fly materialized output of $OUT_2 = S(p,x,y) \Join U(q,z,w)$ or pointers from $t \in U$ to on-the-fly materialized output of $OUT_3 = S(p,x,y) \Join T(q,y,z)$. Choosing the minimum of three gives us the space requirement as,

\begin{align*}
S &= \min \big\{ k, \sum_{s \in R} \min \{d_p, d_q, d_r\} + \max\{|OUT_1|, |OUT_2|, |OUT_3|\} \big\}\\
	& \leq \min \big\{k, \sum_{s \in R} (1)^{2/3} \cdot (d_pd_qd_r)^{1/3} + N^2 \big\} \\
	& \leq \min \big\{k, N^{2/3}|\tOUT|^{1/3} + N^2 \big\}
\end{align*}

Here, $d_p(d_q, d_r)$ denotes the degree of some valuation for variable $p(q,r)$ in relation $S(T, U)$ for a fixed tuple of $R$. If $\mk \leq O(N^2)$,~\autoref{thm:main} and~\autoref{thm:main:2} give the same bound. For $\mk = \Omega(N^2)$,~\autoref{thm:main:2} gives a better bound.

\begin{algorithm}[htp!]


	\SetCommentSty{textsf}
	\DontPrintSemicolon 
	\SetKwFunction{fullreducer}{\textsc{Materialize}}
	\SetKwFunction{initializepq}{\textsc{InitializePQ}}
	\SetKwFunction{fillout}{\textsc{modifiedtopdown}}
	\SetKwFunction{oldfillout}{\textsc{topdown}}	
	\SetKwFunction{ins}{\textsc{insert}}
	\SetKwFunction{app}{\textsc{insert}}
	\SetKwFunction{top}{\textsc{top()}}
	\SetKwFunction{pop}{\textsc{pop()}}
	\SetKwFunction{enum}{\textsc{enum}}	
	\SetKwFunction{eoe}{\textsc{eoe}}	
	\SetKwData{pointer}{\textsf{pointer}}
	\SetKwData{temp}{\textsf{temp}}
	\SetKwData{ref}{\textsf{ref}}
	\SetKwData{retval}{\textsf{retval}}
	\SetKwData{popvalue}{\textsf{popvalue}}
	\SetKwInOut{Input}{\textsc{input}}\SetKwInOut{Output}{\textsc{output}}
	\SetKwProg{myproc}{\textsc{procedure}}{}{}
	%
	\myproc{\enum{} \label{func:enum}}{
		\While{$\qQ_{r}[()]$ is not empty}{
			\textbf{output} $\qQ_{r}[()].\top$ \;
			\fillout{$\qQ_{r}[()].\top, r$} \;
		}
	}
	\BlankLine
	\myproc{\fillout{$c, t$}}{
		/* $c = \langle \theta,  [l], \bot \rangle$ for root node */ \;
		$\theta(b) \gets \theta[\key{\mB_b}]$, $\theta(c) \gets \theta[\key{\mB_c}]$ \;
		\If{$*(*l.\mnext).\mnext = \bot$}{
			$\qQ_{c}[\theta(c)].\pop$ \;
			/* {$ *l= \langle \phi,  [c_{1}, \dots, c_{\ell}], \mnext \rangle$} */ \;
			\FuncSty{\texttt{topdown}($*(*l.\mnext), c$)} \;
		}
		\If{$*(*l.\mnext).\mnext \neq \bot$}{
			$*l.\mnext = *(*l.\mnext).\mnext$ \;
			$\qQ_r[()].\ins(\langle \theta,  [l], \bot \rangle)$
		}
		\If{tuples left in $\tOUT(\subtree{b})$}{
			$\qQ_{b}[\theta(b)].\pop$ \;
			\ForEach{child bag $t_i$ of $b$}{
				\FuncSty{\texttt{topdown}($*l, b$)} \;
			}
			\If{$\qQ_{b}[\theta(b)]$ is not empty}{
				$\ref \gets \qQ_{b}[\theta(b)].\top$ \;
				$\ref.\mnext \gets \theta_c(1)$ \;
				$\qQ_r[()].\ins(\langle \theta,  [\addressof \ref], \bot \rangle)$ \;
			}
		}	
	}
	\caption{Enumeration Phase} \label{algo:enumeration:modified}
\end{algorithm}}

\section{Algorithm for~\autoref{sec:extension}} \label{appendix:sec:extension}

In this section, we describe the formal algorithm for~\autoref{thm:main:subw}. \autoref{algo:subw} shows the enumeration algorithm. It outputs one output tuple $t$ in every iteration and~\autoref{line:one}-\autoref{line:two} pop out all duplicates of $t$ in the queue. Recall that since $Q = Q_1 \cup \dots Q_\ell$, there can be at most $\ell$ duplicates where $\ell$ is a constant.

\begin{algorithm}[H]


	\SetCommentSty{textsf}
	\DontPrintSemicolon 
	\SetKwFunction{fullreducer}{\textsc{Materialize}}
	\SetKwFunction{initializepq}{\textsc{InitializePQ}}
	\SetKwFunction{fillout}{\textsc{topdown}}
	\SetKwFunction{ins}{\textsc{insert}}
	\SetKwFunction{app}{\textsc{insert}}
	\SetKwFunction{top}{\textsc{top()}}
	\SetKwFunction{pop}{\textsc{pop()}}
	\SetKwFunction{push}{\textsc{pop}}
	
	\SetKwFunction{enum}{\textsc{enum}}	
	\SetKwFunction{eoe}{\textsc{eoe}}	
	\SetKwFunction{queue}{\textsc{Queue}}	
	\SetKwData{pointer}{\textsf{pointer}}
	\SetKwData{temp}{\textsf{temp}}
	\SetKwData{retval}{\textsf{retval}}
	\SetKwData{popvalue}{\textsf{popvalue}}
	\SetKwInOut{Input}{\textsc{input}}\SetKwInOut{Output}{\textsc{output}}
	\SetKwProg{myproc}{\textsc{procedure}}{}{}
	%
	\myproc{\enum{} \label{func:enum}}{
		\While{$\queue$ is not empty}{
			$t \gets \queue.\pop$ \;
			\textbf{output} $t$ \;
			$\queue.\push(\enum_i)$ \tcc*{Assume duplicate $t$ came from subquery $i$}
			\While{$\queue.\top = t$}{
				$\queue.\pop$ \label{line:one} \tcc*{drain the queue of duplicate $t$}
				$\queue.\push(\enum_i())$ \label{line:two} \tcc*{Assume duplicate $t$ came from subquery $i$}
			}
		}
	}
	\caption{Enumeration Phase} \label{algo:subw}
\end{algorithm}

The comparison function for priority queues in~\autoref{algo:enumeration} for each subquery $Q_i$ of $Q$ is modified in the following way. Consider two tuples $t_1$ and $t_2$ with schema $(x_1, x_2, \dots, x_n)$ and scores $\rank{t_1}$ and $\rank{t_2}$ respectively.

\begin{algorithm}[H]


	\SetCommentSty{textsf}
	\DontPrintSemicolon 
	\SetKwFunction{fullreducer}{\textsc{Materialize}}
	\SetKwFunction{initializepq}{\textsc{InitializePQ}}
	\SetKwFunction{fillout}{\textsc{topdown}}
	\SetKwFunction{ins}{\textsc{insert}}
	\SetKwFunction{app}{\textsc{insert}}
	\SetKwFunction{top}{\textsc{top()}}
	\SetKwFunction{pop}{\textsc{pop()}}
	\SetKwFunction{push}{\textsc{pop}}
	
	\SetKwFunction{compare}{\textsc{compare}}	
	\SetKwFunction{eoe}{\textsc{eoe}}	
	\SetKwFunction{queue}{\textsc{Queue}}	
	\SetKwData{pointer}{\textsf{pointer}}
	\SetKwData{temp}{\textsf{temp}}
	\SetKwData{retval}{\textsf{retval}}
	\SetKwData{popvalue}{\textsf{popvalue}}
	\SetKwInOut{Input}{\textsc{input}}\SetKwInOut{Output}{\textsc{output}}
	\SetKwProg{myproc}{\textsc{procedure}}{}{}
	%
	\tcc{Returns the smaller ranked tuple of $t_1$ and $t_2$}
	\myproc{\compare$(t_1, t_2)$}{
		\If{$\rank{t_1} < \rank{t_2}$}{
			\texttt{return} $t_1$ \;
		}
		\If{$\rank{t_2} < \rank{t_1}$}{
			\texttt{return} $t_2$ \;
		}
		\ForEach{$i \in \{n, n-1, \dots, 1\}$}{
			\If{$\pi_{x_i}(t_1) < \pi_{x_i}(t_2)$}{\texttt{return} $t_1$}
			\If{$\pi_{x_i}(t_2) < \pi_{x_i}(t_1)$}{\texttt{return} $t_2$}
		}
	}
	\caption{Comparison function for priority queues} \label{comparison}
\end{algorithm}

Comparison function in~\autoref{comparison} compares $t_1$ and $t_2$ based on the ranking function and tie breaks by using the lexicographic ordering of the two tuples. This ensures that all tuples with the same score arrive in a fixed from $\textsc{Enum}_i()$ procedure of each subquery $Q_i$.

\section{Proofs for~\autoref{sec:lowerbound}}


\begin{proof}[Proof of~\autoref{lem:lowerbound}]
	We construct an instance $D$ as follows. For every variable we use the domain
	$\{a_1, \dots, a_N\}$, which we equip with the order $a_1 < a_2 < \dots < a_N$.
	Then, every tuple in $R$ and $S$ is of the form $(a_i, a_{N-i+1})$ for $i = 1, \dots, N$.
	Similarly, every tuple in $S$ is of the form $(a_i, a_{N-i+1})$.
	The result of the query $Q$ on $D$ has size $N^2$.
	
	To construct a family of coordinate decomposable ranking functions, we consider all ranking functions
	that are monotone w.r.t. the order of the domain $\{a_1, \dots, a_N\}$ for every variable.
	

	
	We will show that any two tuples in $Q(D)$ are incomparable, in the sense that neither tuple dominates the other in all
	variables. Indeed, consider two distinct tuples $t_1 = ( a_i, a_{N-i+1}, a_j, a_{N-j+1} )$, and $t_2 = ( a_k, a_{N-k+1}, a_\ell, a_{N-\ell+1} )$.
	For the sake of contradiction, suppose $t_1$ dominates $t_2$. Then, we must have $i \geq k$ and $N-i+1 \geq N-k+1$, giving $i=k$. Similarly, $j = \ell$.  But this contradicts our assumption that $t_1 \neq t_2$. 
	
	Therefore, a ranking function from our family can assign to any of the $N^2$ tuples the smallest score, which implies that any algorithm that does not examine all $N^2$  tuples can miss the smallest.
\end{proof}

\begin{figure}[!tp]
	\centering
	\scalebox{1}{\begin{tikzpicture}
		\tikzset{edge/.style = {->,> = latex'},
			vertex/.style={circle, thick, minimum size=7mm}}
		\def0.25{0.25}
		
		\begin{scope}[fill opacity=1]
		\draw[fill=black!5] (0, 0) ellipse (1cm and 0.33cm) node {\small ${\color{black} x_1, \dots, x_n}$};
		\draw[fill=black!5] (-0.5, -1) ellipse (1cm and 0.33cm) node {\small ${\color{black} y_1, \dots, y_m}$};
		\draw[fill=black!5] (-1, -2) ellipse (1cm and 0.33cm) node {\small ${\color{black} z_1, \dots, z_k}$};
		\draw[fill=black!5] (2, -1) ellipse (1cm and 0.33cm) node {\small ${\color{black} w_1, \dots, w_\ell}$};
		\draw[edge] (0, -0.33) -- (-0.25,-.65);
		\draw[dotted] (0, -0.33) -- (-2,-0.65);
		\draw[dotted] (0, -0.33) -- (4,-0.65);
		\draw[edge] (-0.5, -1.33) -- (-0.75, -1.65);
		\draw[edge] (0, -0.33) -- (2, -0.65);
		
		\node[vertex]  at (-2, 0) {\small $\mB_{\texttt{root}} = \mB_1$};
		\node[vertex]  at (-2, -1) {\small $\mB_{2}$};				
		\node[vertex]  at (-2.5, -2) {\small $\mB_{3}$};				
		\node[vertex]  at (2, -1.66) {\small $\mB_{4}$};												
		\end{scope}	
		\end{tikzpicture}
	}
	\caption{Query decomposition example with depth $2$}
	\label{ex:decomposition:two}
\end{figure}

\begin{figure}
	\centering
	\scalebox{1}{
		\begin{tikzpicture}
		\tikzset{vertex/.style={circle, fill=black!25, minimum size=8pt}}
		
		\node[color=red] at (-5, 1) {$R(x,y)$};
		\node[color=blue] at (-3, 1) {$S(y,z)$};
		\node[color=orange] at (0, 1) {$T(p,q)$};
		\node[color=violet] at (2, 1) {$U(q,r)$};
		
		\node[vertex] (X-1) at (-6,-1) {$a_1$};
		\node[vertex] (Y-1) at (-4,-1) {$b_1$};
		\node[vertex] (Z-1) at (-2,-1) {$c_1$};
		\node[vertex] (X-2) at (-6,0) {$a_2$};
		\node[vertex] (Y-2) at (-4,0) {$b_2$};			
		\node[vertex] (Z-2) at (-2,0) {$c_2$};
		\node[draw=none] at (-4,-1.5) {$\boldsymbol{\vdots}$};
		\node[vertex] (X-n) at (-6,-2.5) {$a_n$};
		\node[vertex] (Y-n) at (-4,-2.5) {$b_n$};		
		\node[vertex] (Z-n) at (-2,-2.5) {$c_n$};		
		
		
		
		\node[vertex] (W-1) at (1,0) {$e_1$};
		\node[vertex] (U-1) at (3,0) {$f_1$};
		\node[vertex] (V-1) at (-1,0) {$d_1$};
		\node[vertex] (W-2) at (1,-1) {$e_2$};
		\node[vertex] (U-2) at (3,-1) {$f_2$};			
		\node[vertex] (V-2) at (-1,-1) {$d_1$};
		\node[draw=none] at (2,-1.5) {$\boldsymbol{\vdots}$};
		\node[vertex] (W-n) at (1,-2.5) {$e_n$};
		\node[vertex] (U-n) at (3,-2.5) {$f_n$};		
		\node[vertex] (V-n) at (-1,-2.5) {$d_n$};
		
		\draw[color=red, line width=0.2mm] (X-1) -- node [above, color=black] {$2$} (Y-1);
		\draw[color=red, line width=0.2mm] (X-2) -- node [above, color=black] {$1$} (Y-2);
		\draw[color=red, line width=0.2mm] (X-n) -- node [above, color=black] {$n$} (Y-n);
		\draw[color=violet, line width=0.2mm] (W-1) -- node [above, color=black] {$1$} (U-1);
		\draw[color=violet, line width=0.2mm] (W-2) -- node [above, color=black] {$2$} (U-2);
		\draw[color=violet, line width=0.2mm] (W-n) -- node [above, color=black] {$n$} (U-n);		
		\draw[color=blue, line width=0.2mm] (Y-1) -- node [above, color=black] {$n-1$}  (Z-1);
		\draw[color=blue, line width=0.2mm] (Y-2) -- node [above, color=black] {$n$}  (Z-2);
		\draw[color=blue, line width=0.2mm] (Y-n) -- node [above, color=black] {$1$}  (Z-n);
		\draw[color=orange, line width=0.2mm] (W-1) -- node [above, color=black] {$n$}  (V-1);
		\draw[color=orange, line width=0.2mm] (W-2) -- node [above, color=black] {$n-1$}  (V-2);
		\draw[color=orange, line width=0.2mm] (W-n) -- node [above, color=black] {$1$}  (V-n);
		\end{tikzpicture}
	}
	\caption{Database instance $D$ for~\autoref{ex:cartesian:edge}. Each edge is color coded by the relation it belongs to. Values over edge denote the weight assigned to the edge.}	\label{fig:cartesian:edge}
\end{figure}

\begin{example} \label{ex:cartesian:edge}
	Consider $Q = R(x,y), S(y,z), T(p,q), U(q,r)$. Then, there exists a database and edge decomposable function such that finding the smallest tuple in $Q(D)$ requires $\Omega(|D|^2)$ time.
	\autoref{fig:cartesian:edge} shows the instance and ranking for each tuple. It is easy to see that no two vectors dominate each other. Since $Q(D) = \Theta(|D|^2)$, we require at least that much time to examine all output tuples.
\end{example}


\begin{proof}[Proof of~\autoref{thm:dichotomy:vertex}]
	Suppose that $Q$ does not satisfy the condition of the theorem. Then, there are atoms 
	$R$ and $S$ in $Q$ with $\vars{R} \setminus \vars{S} \geq 2$ and $\vars{S} \setminus \vars{R} \geq 2$.
	This means that we can apply the same construction as~\autoref{lem:lowerbound} to show that the preprocessing time
	must be $\Omega(|D|^2)$ in order to achieve $O(\log |D|)$ delay.
	
	For the other direction, we will construct a compatible decomposition $\htree$ for a $Q$ that satisfies the condition.
	Pick the relation with largest number of variables as the root of  decomposition. Each remaining relation forms a single bag that is connected to the root. 
	
	The main observation is that each child bag of the root contains at most one variable that is not in the root.
	Indeed, suppose that there exists one child bag with at least two variables not present in the root. But the root bag must also contains at least two variables in addition to the common variables. This would violate the condition of the theorem, which is a contradiction.
	
	Equipped with this observation, we can see that the constructed tree is indeed a valid decomposition of $\fhw = 1$.
	Additionally, we can show the compatibility of $\htree$.  The root bag is $\mbroot$-decomposable by definition since $\key{\mbroot} = \{\}$. Let $u_i$ be the unique variable in bag $\mB_i$. Then, $\htree$ is $u_i$-decomposable conditioned on $\key{\mB_i}$. This follows from the definition of coordinate decomposable. Thus,~\autoref{thm:main} is applicable.
\end{proof}

\begin{proof}[Proof of~\autoref{thm:edge:dichotomy}]
	To prove the hardness result, suppose that $\dia(Q) \geq 4$.
	We construct a database instance $D$ and a family of edge decomposable ranking functions such that any algorithm must make $\Omega(|D|^2)$ calls to the ranking function to output the first tuple in $Q(D)$.
	Indeed, since $\dia(Q) \geq 4$, there exists a path $x_1 R_1 y_1 S_1 z S_2 y_2 R_2 x_2$ in the hypergraph of $Q$.
	Since this path cannot be made shorter, this implies that $x_1 \notin S_1, S_2, R_2$, $y_1 \notin S_2, R_2$, $z \notin R_1, R_2$, $y_2 \notin R_1, S_1$ and $x_2 \notin R_1, S_1, S_2$.
	
	\autoref{fig:lowerbound} shows how the construction for the database instance $D$; 
	all variables not depicted take the same constant value. 
	For the family of ranking functions, we consider all functions that are monotone with respect to the order of the tuples as depicted in~\autoref{fig:lowerbound}. Using the same argument as in~\autoref{lem:lowerbound}, it is easy to see that any correct algorithm must examine the rank of $\Omega(n^2)$ tuples in order to find the smallest one.
	
	\smallskip
	For the other direction, we	 first show that if $\dia(Q) \leq 3$, then we can construct a tree decomposition with $\fhw=1$ and depth at most one. Indeed, any such decomposition is compatible with any edge decomposable function, and hence~\autoref{thm:main} is applicable with $\fhw=1$. In the remainder of the proof, we will show how to find such a decomposition.
	
	Among all tree decompositions with $\fhw=1$ (there exists at least one), let $\htree$ be the one with the smallest depth. We will show that it has depth one. Suppose not; then, there is at least one bag that is not a child of the root bag. \autoref{ex:decomposition:two} shows an example of a query decomposition where bag $\mB_3$ is not a neighbor of $\mB_1$.
	Note that $\mB_3  \not \subseteq \mB_2, \mB_2  \not \subseteq \mB_3, \mB_2  \not \subseteq \mB_1, \mB_1  \not \subseteq \mB_2, \mB_4  \not \subseteq \mB_1, \mB_1  \not \subseteq \mB_4$ (otherwise, bags can be merged without changing the $\fhw$ and there will be a decomposition of depth one, a contradiction). Thus, there must exist at least one variable in $\mB_3$ (say $u$) 
	that does not exist in $\mB_2$, and hence not in any of $\mB_1, \mB_4$ since this is a valid decomposition; similarly there exists one variable in $\mB_4$ (say $v$) that is unique to it. This implies that the distance between $u$ and $v$ is at least $4$, which is a contradiction to the fact that $\dia(Q) \leq 3$. 
\end{proof}


\begin{figure}
	\centering
	\scalebox{1}{
		\begin{tikzpicture}
		\tikzset{vertex/.style={circle, fill=black!25, minimum size=8pt}}
		
		\node[color=red] at (-4, 1) {$R_1(x_1,y_1,\dots)$};
		\node[color=blue] at (-1.8, 1) {$S_1(y_1,z,\dots)$};
		\node[color=orange] at (0.2, 1) {$S_2(y_2,z,\dots)$};
		\node[color=violet] at (2.4, 1) {$R_2(x_2,y_2,\dots)$};
		
		\node[vertex] (X-1) at (-5,0) {$a_1$};
		\node[vertex] (Y-1) at (-3,0) {$b_1$};
		\node[vertex] (X-2) at (-5,-1) {$a_2$};
		\node[vertex] (Y-2) at (-3,-1) {$b_2$};			
		\node[draw=none] at (-4,-1.5) {$\boldsymbol{\vdots}$};
		\node[vertex] (X-n) at (-5,-2.5) {$a_n$};
		\node[vertex] (Y-n) at (-3,-2.5) {$b_n$};		
		
		\node[vertex] (Z) at (-1,-1.25) {$c$};		
		
		\node[vertex] (W-1) at (1,0) {$d_1$};
		\node[vertex] (U-1) at (3,0) {$e_1$};
		\node[vertex] (W-2) at (1,-1) {$d_2$};
		\node[vertex] (U-2) at (3,-1) {$e_2$};			
		\node[draw=none] at (2,-1.5) {$\boldsymbol{\vdots}$};
		\node[vertex] (W-n) at (1,-2.5) {$d_n$};
		\node[vertex] (U-n) at (3,-2.5) {$e_n$};		
		
		\draw[color=red, line width=0.2mm] (X-1) -- node [above, color=black, xshift=0em, yshift=0em] {$1$} (Y-1);
		\draw[color=red, line width=0.2mm] (X-2) -- node [above, color=black, xshift=0em, yshift=0em] {$2$} (Y-2);
		\draw[color=red, line width=0.2mm] (X-n) -- node [above, color=black, xshift=0em, yshift=0em] {$n$} (Y-n);
		\draw[color=violet, line width=0.2mm] (W-1) -- node [above, color=black,  xshift=0em, yshift=0em] {$1$} (U-1);
		\draw[color=violet, line width=0.2mm] (W-2) -- node [above, color=black,  xshift=0em, yshift=0em] {$2$} (U-2);
		\draw[color=violet, line width=0.2mm] (W-n) -- node [above, color=black,  xshift=0em, yshift=0em] {$n$} (U-n);		
		\draw[color=blue, line width=0.2mm] (Y-1) -- node [above, color=black,  xshift=0em, yshift=0em] {$n$}  (Z);
		\draw[color=blue, line width=0.2mm] (Y-2) -- node [above, color=black,  xshift=0em, yshift=0em] {$n-1$}  (Z);
		\draw[color=blue, line width=0.2mm] (Y-n) -- node [above, color=black,  xshift=0em, yshift=0em] {$1$}  (Z);
		\draw[color=orange, line width=0.2mm] (W-1) -- node [above, color=black,  xshift=0em, yshift=0em] {$n$}  (Z);
		\draw[color=orange, line width=0.2mm] (W-2) -- node [above, color=black,  xshift=0em, yshift=0em] {$n-1$}  (Z);
		\draw[color=orange, line width=0.2mm] (W-n) -- node [above, color=black,  xshift=0em, yshift=0em] {$1$}  (Z);
		\end{tikzpicture}
	}
	\caption{Database instance $D$ for~\autoref{thm:edge:dichotomy}. Each edge is color coded by the relation it belongs to. Values over the edges denote the weight assigned to each tuple.}	\label{fig:lowerbound}
\end{figure}




\section{Proofs}
\label{sec:proofs}

\subsection{Proofs for Section~\ref{sec:app}}

\begin{proof}[Proof of~\autoref{lem:conditioned}]
We need to show that for every valuation $\pi$ over $S$, $\rf(\pi \circ \Phi \circ \theta)$ is $T$-decomposable where $\Phi$ is defined over $U = \nodes \setminus (S \cup T)$ and $\theta$ is defined over $T$.  We use the same total order for $\theta$ as used for $T$-decomposability. Let $\theta_1 \succeq \theta_2$, and consider any valuation $\Phi$ over $U$. 
Define the valuation $\varphi$ over $\nodes \setminus T$ such that $\varphi[S] = \pi$ and $\varphi[U] = \Phi$. Then,
	%
	\begin{align*} 
		\theta_1 \succeq \theta_2 & \Rightarrow \rf(\varphi \circ \theta_1) \geq \rf(\varphi \circ \theta_2) \\
		& \Leftrightarrow \rf(\varphi[S] \circ \varphi[U] \circ \theta_1) \geq \rf(\varphi[S] \circ \varphi[U] \circ \theta_2) \\
		& \Leftrightarrow \rf(\pi \circ \Phi \circ \theta_1) \geq \rf(\pi \circ \Phi \circ \theta_2)
	\end{align*}
	%
Step $1$ follows from the definition of $T$-decomposable. Step $2$ and $3$ compute the restriction of $\varphi$ to $S$ and $U$.
\end{proof}


\begin{proof}[Proof of~\autoref{lem:vb}]
Pick any set $S \subseteq \nodes$ and let
$\theta^\star$ be the valuation over $\nodes \setminus S$ such that for every $x$, $f_x(\theta^\star(x)) = e$,
where $e$ is the identity element of the monoid. 
Suppose that $ \rank{\theta^\star \circ \theta_1} \geq  \rank{\theta^\star \circ \theta_2}$ for
valuations $\theta_1, \theta_2$ over $S$ establishing a total order $\theta_1 \succeq \theta_2$.
This implies that  
$$\oplus_{x \in S} f_x(\theta_1(x)) \geq \oplus_{x \in S} f_x(\theta_2(x)).$$

Then, for any valuation $\theta$ over $\nodes \setminus S$ we have:
\begin{align*}
\rank{\theta \circ \theta_1} & =  \oplus_{x \in \nodes \setminus S} f_x(\theta(x))  \bigoplus  \oplus_{x \in S} f_x(\theta_1(x))  \\
& \geq \oplus_{x \in \nodes \setminus S} f_x(\theta(x))  \bigoplus  \oplus_{x \in S} f_x(\theta_2(x))  \\
& = \rank{\theta \circ \theta_2}
\end{align*} 
The inequality holds because of the monotonicity of the binary operator.
\end{proof}

\begin{proof}[Proof of~\autoref{lem:tb}]
Pick some node $t$ in the decomposition, and fix a valuation $\theta_0$ over $\key{t}$.
Let $E \subseteq \edges$ be the hyperedges that correspond to bags in the subtree rooted at $t$,
and $\bar{E}$ the remaining hyperedges.
Let $\theta^\star$ be the valuation over $\nodes \setminus \subtree{t}$ such that for every $F \in \bar{E}$
we have $w_F((\theta_0 \circ \theta^\star)[x_F]) =e$, where $e$ is the identity element. Notice that the
latter is well-defined, since the hyperedges in $\bar{E}$ can not contain any variables in $\subtree{t} \setminus \key{t}$.

Suppose now that $ \rank{\theta_0 \circ \theta^\star \circ \theta_1} \geq  \rank{\theta_0 \circ \theta^\star \circ \theta_2}$ for
valuations $\theta_1, \theta_2$ over $\subtree{t} \setminus \key{t}$ establishing total ordering $\theta_1 \succeq \theta_2$. This implies that  
$$\oplus_{F \in E} w_F((\theta_0 \circ \theta_1)[x_F]) \geq \oplus_{F \in E} w_F((\theta_0 \circ \theta_2)[x_F]).$$
Then, for any valuation $\theta$ over $\nodes \setminus \subtree{t}$  we have:
\begin{align*}
\rf(\theta_0 & \circ \theta \circ \theta_1) = \\
& =  \oplus_{F \in E} w_F((\theta_0 \circ \theta_1)[x_F])  \bigoplus  \oplus_{F \in \bar{E}} w_F((\theta \circ \theta_0)[x_F])   \\
& \geq \oplus_{F \in E} w_F((\theta_0 \circ \theta_2)[x_F])  \bigoplus  \oplus_{F \in \bar{E}} w_F((\theta \circ \theta_0)[x_F])   \\
& = \rf(\theta_0  \circ \theta \circ \theta_2) 
\end{align*} 
The inequality holds because of the monotonicity of the binary operator.
\end{proof}

\begin{proof}[Proof of~\autoref{prop:c}]
	Let $\htree$ by the optimal decomposition of $Q$ with fractional hypertree-width $\fhw$. We create a new decomposition $\htree'$ by simply adding the variables $S$ that determine the ranking functions in all the bags of $\htree$. By doing this, the width of the decomposition will grow by at most an additive factor of $c$. To complete the proof, we need to show that $\rf$ is compatible with the new decomposition. 
	
	Indeed, for any node in $\htree'$ (with the exception of the root node) we have that $S \subseteq \key{t}$. Hence, if we fix a valuation over $\key{t}$, the ranking function will output exactly the same score, independent of what values the other variables take. 
\end{proof}

\begin{proof} [Proof of~\autoref{lem:time:space}]
	It is known that the materialization of each bag can be done in time $O(|D|^\fhw)$, and the full reducer pass is linear in the size of the bags. For the second step of the preprocessing algorithm, observe that for each valuation in a bag, the algorithm performs only a constant number of operations (the number of children in the tree plus one), where each operation takes a constant time (since insert and top can be done in $O(1)$ time for the priority queue). Hence, the second step needs $O(|D|^\fhw)$ time as well.
	
	Regarding the space requirements, it is easy to see that the data structure uses only constant space for every valuation in each bag, hence the space is bounded by $O(|D|^\fhw)$.
\end{proof}




\subsection{Proof of Main Theorem}
\label{sec:proof:main}

We analyze the behavior of the algorithm in terms of delay, space and correctness.

\begin{lemma} \label{lem:time:space}
	The runtime of~\autoref{algo:preprocessing} is ${O}(|D|^\fhw)$. Moreover, at the end of the algorithm, the resulting
	data structure has size $O(|D|^\fhw)$.
\end{lemma}

\begin{lemma}
	\autoref{algo:enumeration} enumerates $Q(D)$ with delay $\delta = {O}(\log |D|)$.
\end{lemma}

\begin{proof}
	In order to show the delay guarantee, it suffices to prove that procedure \FuncSty{\textsc{topdown}} takes ${O}(\log |D|)$ time when called from the root node, since getting the top element from the priority queue at the root node takes only $O(1)$ time. 
	
	Indeed, \FuncSty{\textsc{topdown}} traverses the tree decomposition recursively. The key observation is that it visits each node in $\htree$ exactly once. For each node, if $next$ is not $\bot$, the processing takes time $O(1)$. If $next = \bot$, it will perform one pop -- with cost $O(\log |D|)$ -- and a number of inserts equal to the number of children.  Thus, in either case the total time per node is $O(\log |D|)$. Summing up over all nodes in the tree, the total time until the next element is output will be  
	${O}(\log |D|) \cdot |V(\htree)| = {O}(\log |D|)$.	
\end{proof}

We next bound the space $S_e$ needed by the algorithm during the enumeration phase.

\begin{lemma}
	After~\autoref{algo:enumeration} has enumerated $k$ tuples, the additional space used by the algorithm is  
	$S_e = O(\min \{ k, \vert Q(D) \vert \})$.
\end{lemma}

\begin{proof}
	The space requirement of the algorithm during enumeration comes from the size of the priority queues at every bag in the decomposition. Since we have performed a full reducer pass over all bags during the preprocessing phase, and each bag $t$ stores in its priority queues all valuations over $\subtree{t}$, it is straightforward to see that the sum of the sizes of the priorities queues in each bag is bounded by $|Q(D)|$.~\footnote{Here we must make sure that the priority queue is implemented such that any duplicate valuations are rejected.} 
	
	To obtain the bound of $O(k)$, we observe that for each tuple that we output, the \FuncSty{\textsc{topdown}}  procedure 
	adds at every node in the decomposition a constant number of new tuples in one of the priority queues in this node (equal to the number of children). Hence, at most $O(1)$ amount of data will be added in the data structure between two consecutive tuples are output. Thus, if we enumerate $k$ tuples from $Q(D)$, the increase in space will be $k \cdot O(1) = O(k)$.
\end{proof}


Finally, we show that the algorithm correctly enumerates all tuples in $Q(D)$ in increasing order according to the ranking function.

\begin{lemma} \label{enum:correctness}
	\autoref{algo:enumeration} enumerates $Q(D)$ in order according to $\rf$.
\end{lemma}
\begin{proof}[Proof of~\autoref{enum:correctness}]
	We will prove our claim by induction on post-order traversal of the decomposition. We will show that the priority queue for each node $s$ gives the output in correct order which in turn populates $\tOUT(\subtree{s})$ correctly. Here, $\tOUT(\subtree{s})$ is the ranked materialized output of subtree rooted at $\mB_s$.
	
	\smallskip
	\noindent \introparagraph{Base Case} Correctness for ranked output of $\tOUT(\mB_s)$ for leaf node $s$ is trivial as the leaf node tuples are popped from priority queues in order. Let $\phi^\star$ be the valuation over $\nodes \setminus \mB_s$ according to definition of decomposability. We insert each valuation $\theta$ over node $s$ with score $\rf(\phi^\star \circ \theta )$. Since $\rf$ is compatible with the decomposition, it follows that if $\rf(\phi^\star \circ \theta_2 ) \geq \rf(\phi^\star \circ\theta_1)$ such that $\theta_1[\key{\mS_s}] = \theta_1[\key{\mS_s}]$, then $\theta_2 \succeq \theta_1$, thus recovering the correct ordering for tuple in $s$.
	
	\smallskip
	\noindent Let $s$ be a non-leaf node whose children are leaf nodes $s_1, \dots s_m$. Suppose $\theta$ is a valuation over $\subtree{s}$ popped at~\autoref{tuple:pop}. Let $u = \theta[\key{\mB_s}]$ and $u_i = \theta[\key{\mB_{s_i}}]$. From \autoref{for:1}-\ref{push:queue}, one may observe that a new candidate is pushed into priority queue for key  by incrementing pointers to materialized output one at a time for each child bag $\mB$, while keeping the remainder of tuple (including $\key{\mB}$) fixed (\autoref{push:queue}). Let the notation $\phi^{\succ}$ denotes the smallest tuple in a bag that has rank greater than tuple $\phi$ such that $\phi^{\succ}[\key{\mB}]  = \phi[\key{\mB}]$. Then, $\theta = \theta_1 \circ \theta_2 \circ \dots \circ \theta_m$ will {\em generate} the following candidates: 
	%
	\begin{align*}
	\qquad \qquad \qquad \qquad \qquad \qquad \mathcal{L} = &\ w \circ \theta^{\succ}_1 \circ \theta_2 \circ \dots \circ \theta_m, \\
	&\ w \circ \theta_1 \circ \theta^{\succ}_2 \circ \dots \circ \theta_m, \\
	&\ \dots \\
	&\ w \circ \theta_1 \circ \theta_2 \circ \dots \circ \theta^{\succ}_m
	\end{align*}
	%
	Here $w$ is the projection of $\theta$ over variables in $\mB_s$ but not in any child node. However, we also need to argue that the next smallest valuation after $\theta$ that agrees with $\theta[{\mB_s}]$ is one of the tuples in $\mathcal{L}$. Suppose there is a tuple $\theta' = \theta'_1 \circ \theta'_2 \circ \dots \circ \theta'_m$ such that $\theta'[\mB_s] = \theta[\mB_s]$ \footnote{If $\theta'[\mB_s] \neq \theta[\mB_s]$, then smallest candidates of $\theta'[\mB_s]$ will be compared with that of $\theta[\mB_s]$ in $\qQ_s$}. For the sake of contradiction, suppose $\theta'$ has strictly smaller score than any tuple in $\mathcal{L}$ or $\theta$ but has not been enumerated yet. In other words, $\rf(\phi \circ \theta') < \rf(\phi \circ \theta)$ for any valuation $\phi$ over $\nodes \setminus \subtree{s}$. Clearly, since $\theta'$ has smaller rank than $\theta$ but has not been enumerated, it follows that $\theta'$ has not been inserted into the priority queue. We will show that such a scenario will violate compatibility of ranking function. Recall that $\theta_1$ is said to dominate $\theta_2$ whenever $\theta_1(x) \succeq \theta_2(x)$ for every variable $x \in S$ implies $\rf(\theta_1) \geq \rf(\theta_2)$. There are three possible scenarios regarding the tuples $\theta$ and $\theta'$:
	
	\smallskip
	\begin{enumerate}
		
		\item 	$\theta$ dominates $\theta'$ over each variable in $S_i = \subtree{{s_i}} \setminus \key{\mB_{s_i}},$ $i\in [m]$. Note that this scenario would mean that $\theta'$ was generated before $\theta$ given our candidate generation logic~\autoref{for:1}-\ref{tuple:pop}, violating our assumption that $\theta'$ has not been generated yet. \\
		
		\item $\theta'$ dominates $\theta$ over each variable in $S_i$. This scenario implies that $\rf(\phi \circ \theta) < \rf(\phi \circ \theta')$. Indeed, since $\rf$ is compatible with decomposition for each bag $\mB_{s_i}$, it holds that $\rf(\phi' \circ \theta[S_i]) \leq \rf(\phi' \circ \theta'[S_i])$ which is implied from the leaf node ordering correctness. More formally,
		
		\begin{align*}
		 \qquad  \qquad  \qquad \rf(\phi \circ w \circ \theta_1 \circ  \dots  \theta_m) &\leq  \rf(\phi \circ w \circ \theta'_1 \circ \theta_2 \ \dots  \theta_m) \\ 
		&\leq  \rf(\phi \circ w \circ \theta'_1 \circ \theta'_2 \dots \theta_m) \\
		& \dots \\
		&\leq  \rf(\phi \circ w \circ \theta'_1 \circ \theta'_2 \dots \theta'_m) \\
		\end{align*}
		%
		Each inequality is a successive application of $(\subtree{s_i} \setminus \key{s_i})$-decomposability since $\theta'_i \succeq \theta_i$ by domination assumption of $\theta'$ over $\theta$.  \\
		
		\item $\theta'$ and $\theta$ are incomparable. It is easy to see that all candidates in $\mathcal{L}$ dominate $\theta$ but are incomparable to each other. Also, the only way to generate new candidate tuples is~\autoref{for:1}-\ref{push:queue}. Thus, if $\theta'$ is not in the priority queue, there are two possibilities. Either there is some tuple $\theta''$ in the priority queue that is dominated by $\theta'$ and thus, $\rf(\theta'') \leq \rf(\theta')$. $\theta''$ will eventually generate $\theta'$ via a chain of tuples that successively dominate each other. As $\theta$ was popped before $\theta''$, it follows that $\rf(\theta) \leq \rf(\theta'') \leq \rf(\theta')$. The second possibility is that there is no such $\theta''$, which will mean that $\theta$ and $\theta'$ are generated in the same for loop~\autoref{for:1}. But this would again mean that $\theta'$ is in the priority queue. Both these cases violate our assumption that $\rf(\theta') < \rf(\theta)$.
		
	\end{enumerate}	
	
	Therefore, it cannot be the case that $\rf(\phi \circ \theta') < \rf(\phi \circ \theta)$ which proves the ordering correctness for node $s$. Since the output $\tOUT(\subtree{s})$ is populated using this ordering form priority queue, it is also materialized (chaining of cells at~\autoref{chaining}) in ranked order.
	
	\smallskip
	\noindent \introparagraph{Inductive Case} Consider some node $s$ in post-order traversal with children $s_1, \dots s_m$. By induction hypothesis, the ordering of $\tOUT(\mB_{s_i})$ and correctness of $\qQ_{s_i}$ is guaranteed. Applying the same argument as in the base case, it is straightforward to show the correctness for bag $s$. This completes the proof.
	
	It is easy to see that the algorithm indeed enumerates all tuples in $Q(D)$ since the full reducer pass removes all dangling tuples. 
	
\end{proof}	
\section{Conclusion}
\label{sec:conclusion}

In this paper, we study the problem of CQ result enumeration in ranked order. We combine the notion of query decompositions with certain desirable properties of ranking functions to enable logarithmic delay enumeration with small preprocessing time. We view this as a fundamental building block to answer several more interesting questions of both theoretical and practical relevance. The most natural open problem is to prove space lower bounds. An intriguing question is to explore the full continuum of time-space tradeoffs. For instance, for any compatible ranking function with the $4$-path query and $T_P = O(N)$, we can achieve $\delta = O(N^{3/2})$ with space $S_e = O(N)$ and $\delta = O(\log N)$ with space $S_e = O(N^2)$. The precise tradeoff between these two points and its generalization to arbitrary CQs is unknown. 
There also remain several open question regarding how the structure of ranking functions influences the efficiency of the algorithms. It would be interesting to find fine-grained classes of ranking functions which are more expressive than totally decomposable, but less expressive than coordinate decomposable. For instance, the ranking function $f(x,y) = \vert x - y \vert$ is not coordinate decomposable, but it is {\em piecewise} coordinate decomposable on either side of the global minimum critical point for each $x$ valuation. 

\section{Problem Setting}
\label{sec:framework}

In this section we present the basic notions and terminology, and then discuss our framework.

\subsection{Conjunctive Queries}
\label{subsec:cq}

In this paper we will focus on the class of {\em Conjunctive Queries (CQs)}, which are expressed as
$ \label{eq:q}
Q(\by) = R_1(\bx_1), R_2(\bx_2), \ldots, R_n(\bx_n) 
$
Here, the symbols $\by,\bx_1, \dots, \bx_n$ are vectors that contain {\em variables} 
or {\em constants}, the atom $Q(\by)$ is the {\em head} of the query, and the atoms
$R_1(\bx_1), R_2(\bx_2), \ldots, R_n(\bx_n)$ form the {\em body}. 
The variables in the head are a subset of the variables that appear in the body. A CQ  is 
{\em full} if every variable in the body appears also in the head, and it is {\em boolean} 
if the head contains no variables, {\em i.e.}\xspace it is of the form $Q()$. We will typically use the symbols 
$x,y,z,\dots$ to denote variables, and $a,b,c,\dots$ to denote constants.
We use $Q(D)$ to denote the result of the query $Q$ over input database $D$.
A {\em valuation} $\theta$ over a set $V$ of variables is a total function that maps
each variable $x \in V$ to a value $\theta(x) \in \domain$, where $\domain$ is a domain
of constants. We will often use $\domain(x)$ to denote the constants that the valuations
over variable $x$ can take. 
It is implicitly understood that a valuation is the identity function on constants.
If $U \subseteq V$, then $\theta[U]$ denotes the restriction of $\theta$ to $U$. A \emph{Union of Conjunctive Queries} $\varphi = \bigcup_{i \in \{1, \dots, \ell\}} \varphi_i$ is a set of CQs where head$(\varphi_{i_1}) = $ head$(\varphi_{i_2})$ for all $1 \leq i_1, i_2 \leq \ell$. Semantically, $\varphi(D) = \bigcup_{i \in \{1, \dots, \ell\}} \varphi_i(D)$. A UCQ is said to be full if each $\varphi_i$ is full.

\smallskip
\introparagraph{Natural Joins}
If a CQ is full, has no constants and no repeated variables in the same atom, then we
say it is a {\em natural join query}. For instance, the 3-path query
$Q(x,y,z,w) = R(x,y), S(y,z), T(z,w)$ is a natural join query.
A natural join can be represented equivalently as a {\em hypergraph} 
$\mathcal{H}_Q = (\nodes_Q, \edges_Q)$, where $\nodes_Q$ is the set of variables, and
for each hyperedge $F \in \edges_Q$ there exists a relation $R_F$ with variables $F$. 
We will write the join as $\Join_{F \in \edges_Q} R_F$.
We denote the size of relation $R_F$  by $|R_F|$. Given two tuples $t_1$ and $t_2$ over a set of variables $\nodes_1$ and $\nodes_2$ where $\nodes_1 \cap \nodes_2 = \emptyset$, we will use $t_1 \circ t_2$ to denote the tuple formed over the variables $\nodes_1 \cup \nodes_2$. If $\nodes_1 \cap \nodes_2 \neq \emptyset$, then $t_1 \circ t_2$ will perform a join over the common variables.


\smallskip
\introparagraph{Join Size Bounds}
Let $\mathcal{H} = (\nodes, \edges)$ be a hypergraph, and $S \subseteq \nodes$.
A weight assignment $\bu = (u_F)_{F \in \edges}$ 
is called a {\em fractional edge cover} of $S$ if 
$(i)$ for every $F \in \edges, u_F \geq 0$  and $(ii)$ for every
$x \in S, \sum_{F:x \in F} u_F \geq 1$. 
The {\em fractional edge cover number} of $S$, denoted by
$\rho^*_{\mathcal{H}}(S)$ is the minimum of
$\sum_{F \in \edges} u_F$ over all fractional edge covers of $S$. 
We write $\rho^*(\mathcal{H}) = \rho^*_{\mathcal{H}}(\nodes)$.

In a celebrated result, Atserias, Grohe and Marx~\cite{AGM} proved that
for every fractional edge cover $\bu$ of $\nodes$,  the size 
of a natural join is bounded using the {\em AGM inequality}: $\label{eq:agm}
|\Join_{F \in \edges} R_F| \leq \prod_{F \in \edges} |R_F|^{u_F}
$
The above bound is constructive~\cite{skewstrikesback,ngo2012worst}: 
there exist worst-case algorithms that compute the join $\Join_{F \in \edges} R_F$ in 
time $O(\prod_{F \in \edges} |R_F|^{u_F})$ for every fractional edge cover $\bu$ of $\nodes$.

\smallskip
\introparagraph{Tree Decompositions}
Let $\mathcal{H} = (\nodes, \edges)$ be a hypergraph of a natural join query $Q$.
A {\em tree decomposition} of $\mathcal{H}$ is  a tuple 
$(\htree, (\bag_t)_{t \in V(\htree)})$ where $\htree$ is a tree, and 
every $\bag_t$ is a subset of $\nodes$, called the {\em bag} of $t$, such that 
	%
	\begin{packed_enum}
		\item  
		each edge in $\edges$ is contained in some bag; and
		\item 
		for each variable $x \in \nodes$, the set of nodes $\{t \mid x \in \bag_t\}$ is connected in $\htree$.
	\end{packed_enum}

Given a rooted tree decomposition, we use $\prnt{t}$ to denote the (unique) parent of node $t \in V(\htree)$. 
Then, we define $\key{t} = \mB_t \cap \mB_{\prnt{t}}$ to be the common variables that occur in the bag $\mB_t$ and
its parent, and $\val{t} = \mB_t \setminus \key{t} $ the remaining variables of the bag.
We also use $\subtree{t}$ to denote the union of all bags in the subtree rooted at $t$ (including $\mB_t$). 


 

The {\em fractional hypertree width} of a decomposition is 
defined as $\max_{t \in V(\htree)} \rho^*(\bag_t)$, where
$\rho^*(\bag_t)$ is the minimum fractional edge cover of the vertices in $\bag_t$.
The  fractional hypertree width of a query $Q$, denoted $\fhw(Q)$, is the minimum 
fractional hypertree width among all tree decompositions of its hypergraph.
We say that a query is {\em acyclic} if $\fhw(Q)=1$.
The {\em depth} of a rooted tree decomposition is  the largest distance over all root to leaf paths in $\htree$.




\smallskip
\introparagraph{Computational Model}
To measure the running time of our algorithms, we use the uniform-cost RAM 
model~\cite{hopcroft1975design}, where data values as well as pointers to
databases are of constant size. Throughout the paper, all complexity results are 
with respect to data complexity (unless explicitly mentioned), where the query is assumed fixed. 


\subsection{Ranking Functions}

Consider a natural join query $Q$ and a database $D$. Our goal is to enumerate all
the tuples of $Q(D)$ according to an order that is specified by a {\em ranking function}.
In practice, this ordering could be specified, for instance, 
in the \oldtt{ORDER BY} clause of a \oldtt{SQL} query. 

Formally, we assume a total order $\succeq$ of the valuations $\theta$ over the variables
 of $Q$. The total order is induced by a ranking function $\rf$ that maps each valuation $\theta$ 
to a number $\rank{\theta} \in \mathbb{R}$. In particular, for two valuations $\theta_1, \theta_2$, 
we have $\theta_1 \succeq \theta_2$ if and only if $\rank{\theta_1} \geq \rank{\theta_2}$. Throughout the paper, we will assume that $\rf$ is a computable function that takes times linear in the input size to the function . We present below two concrete examples of ranking functions.



\begin{example} \label{ex:vertex}
For every constant $c \in \domain$, we associate a weight $w(c) \in \mathbb{R}$. 
Then, for each valuation $\theta$, we can define
$\rf(\theta) := \sum_{x \in \nodes} w(\theta(x)).$
This ranking function sums the weights of each value in the tuple. 
 \end{example}

\begin{example} \label{ex:edge}
For every input tuple $t \in R_F$, we associate a weight $w_F(t) \in \mathbb{R}$.
Then, for each valuation $\theta$, we can define
$\rank{\theta} = \sum_{F \in \edges} w_F(\theta[x_F])$
where $x_F$ is the set of variables in $F$. In this case, the ranking function sums the
weights of each contributing input tuple to the output tuple $t$ (we can extend the ranking function to all valuations
by associating a weight of 0 to tuples that are not contained in a relation).
\end{example}

\smallskip
\introparagraph{Decomposable Rankings}
As we will see later, not all ranking functions are amenable to efficient evaluation. Intuitively, an arbitrary ranking
function will require that we look across all tuples to even find the smallest or largest element. We next
present several restrictions which are satisfied by ranking functions seen in practical settings.

\begin{definition}[Decomposable Ranking]
Let $\rf$ be a ranking function over $\nodes$ and $S \subseteq \nodes$.
We say that $\rf$ is {\em $S$-decomposable} 
if there exists a total order for all valuations over $S$, such that for every valuation $\varphi$
over $\nodes \setminus S$, and any two valuations $\theta_1, \theta_2$ over $S$ we have:
$$ \theta_1 \succeq \theta_2 \Rightarrow \rank{\varphi \circ \theta_1} \geq  \rank{\varphi \circ \theta_2}. $$
\end{definition}


We say that a ranking function is {\em totally decomposable} if it is $S$-decomposable for every
subset $S \subseteq \nodes$, and that it is {\em coordinate decomposable} if it is $S$-decomposable
for any singleton set. Additionally, we say that it is {\em edge decomposable} for a query $Q$ if it is
$S$-decomposable for every set $S$ that is a hyperedge in the query hypergraph.
We point out here that totally decomposable functions are equivalent to monotonic orders as defined in~\cite{kimelfeld2006incrementally}.

\begin{example}
The ranking function $\rank{\theta} = \sum_{x \in \nodes} w(\theta(x))$ defined in~\autoref{ex:vertex} is 
totally decomposable, and hence also coordinate decomposable. Indeed, pick any set $S \subseteq \nodes$. 
We construct a total order on valuations $\theta$ over $S$ by using the value $\sum_{x \in S} w(\theta(x))$.
Now, consider valuations $\theta_1, \theta_2$ over $S$ such that
 $\sum_{x \in S} w(\theta_1(x)) \geq \sum_{x \in S} w(\theta_2(x))$.
Then, for any valuation $\varphi$ over $\nodes \setminus S$ we have:
\begin{align*}
\rank{\varphi \circ \theta_1}  = \sum_{x \in \nodes \setminus S} w(\varphi(x)) + \sum_{x \in S} w(\theta_1(x)) 
 \geq \sum_{x \in \nodes \setminus S} w(\varphi(x)) + \sum_{x \in S} w(\theta_2(x)) 
 = \rank{\varphi \circ \theta_2} 
\end{align*} 
Next, we construct a function that is coordinate-decomposable but it is not totally decomposable. Consider the query 
$$Q(x_1 \dots, x_d, y_1, \dots, y_d) = R(x_1, \dots, x_d), S(y_1, \dots, y_d)$$ 
where $\domain = \{-1,1\}$, and define  $\rf(\theta) := \sum_{i=1}^d \theta(x_i) \cdot \theta(y_i)$. This ranking function corresponds to taking the inner product of the input tuples if viewed as binary vectors. The total order for $\domain$ is $-1 \prec 1$. It can be shown that for $d=2$, the function is not $\{x_1,x_2\}$-decomposable. For instance, if we define $(1,1) \succeq (1,-1)$, then inner product ranking function over $x_1,x_2,y_1,y_2$ for $\varphi = (1,-1)$ is $\rf(1,1,1,-1) < \rf(1,-1,1,-1)$ but if we define $(1,-1) \succeq (1,1)$, then for $\varphi = (-1,-1)$ we get $\rf(1,-1,-1,-1) < \rf(1,1,-1,-1)$. This shows that there exists no total ordering over the valuations of variables $\{x_1,x_2\}$.

\end{example} 

\begin{definition}
Let $\rf$ be a ranking function over a set of variables $\nodes$, and $S,T \subseteq \nodes$
such that $S \cap T = \emptyset$.
We say that $\rf$ is {\em $T$-decomposable conditioned on $S$} 
if for every valuation $\theta$ over $S$, the function
$\rf_{\theta}(\varphi) := \rank{\theta \circ \varphi}$ defined over $\nodes \setminus S$ is $T$-decomposable.
\end{definition}

The next lemma connects the notion of conditioned decomposability with decomposability.

\begin{lemma} \label{lem:conditioned}
Let $\rf$ be a ranking function over a set of variables $\nodes$, and $T \subseteq \nodes$.
If $\rf$ is $T$-decomposable, then it is also $T$-decomposable conditioned on $S$ for any $S \subseteq \nodes \setminus T$.
\end{lemma}

It is also easy to check that if a function is $(S\cup T)$-decomposable, then it is also $T$-decomposable
conditioned on $S$. 

\begin{definition}[Compatible Ranking]
Let $\htree$ be a rooted tree decomposition of hypergraph $\mathcal{H}$ of a natural join query. We say that a ranking function is {\em compatible
with $\htree$} if for every node $t$ it is $(\subtree{t} \setminus \key{t})$-decomposable conditioned on $\key{t}$.
\end{definition}

\begin{example} \label{ex:decomposable}
Consider the join query $Q(x,y,z) = R(x,y), S(y,z)$, and the ranking function from~\autoref{ex:edge},
 $\rf(\theta) = w_R(\theta(x),\theta(y)) + w_S(\theta(y), \theta(z))$. This function is not $\{z\}$-decomposable,
 but it is $\{z\}$-decomposable conditioned on $\{y\}$.
 
 Consider a decomposition of the hypergraph of $Q$ that has two nodes: the root node $r$ with $\mB_r = \{x,y\}$,
 and its child $t$ with $\mB_t = \{y,z\}$. Since $\subtree{t} = \{y,z\}$ and $\key{t} = \{y\}$, the condition of
 compatibility holds for node $t$. Similarly, for the root node $\subtree{t} = \{x,y,z\}$ and $\key{t} = \{\}$, hence the
 condition is trivially true as well. Thus, the ranking function is compatible with the decomposition.
\end{example}



\subsection{Problem Parameters}
\label{subsec:cq}

Given a natural join query $Q$  and a database $D$, we want to enumerate
the tuples of $Q(D)$ according to the order  specified by $\rf$.
We will study this problem in the enumeration framework similar to that of~\cite{Segoufin15}, 
where an algorithm can be decomposed into two phases:

\begin{itemize}
	\item a {\bf preprocessing phase} that takes time $T_p$ and computes a data structure of size $S_p$,
	\item an {\bf enumeration phase} that outputs $Q(D)$ with no repetitions. The enumeration phase has full access to any data structures constructed in the preprocessing phase and can also use additional space of size $S_e$.
	The {\em delay} $\delta$ is defined as the maximum time to output any two consecutive tuples (and also the time to output the first tuple, and the time to notify that the enumeration has completed).  
\end{itemize}

It is straightforward to perform ranked enumeration for any ranking function by computing $Q(D)$, storing the tuples in an ordered list, and finally enumerating by scanning the ordered list with constant delay. This simple strategy implies the following result.

\begin{proposition}\label{prop:simple:enum}
Let $Q$ be a natural join query with hypergraph $\mH = (\nodes, \edges)$. Let $\htree$ be a tree decomposition with fractional hypertree-width \fhw, and $\rf$ be a ranking function. Then, for any input database $D$, we can preprocess $D$ in time $ T_p = {O}(\log{D} \cdot |D|^{\fhw} + |Q(D)|)$ and space $S_p = O(|Q(D)|)$,
	such that for any $k$, we can enumerate the top-$k$ results of $Q(D)$ with
	$\text{delay } \delta = {O}(1)$ and $\text{space } S_e = O(1)$
\end{proposition}

The drawback of~\autoref{prop:simple:enum} is that the user will have to wait ${\Omega}(|Q(D)| \cdot \log |Q(D)|)$ time to even obtain the first tuple in the output. Moreover, even when we are interested in a few tuples, the whole output result will have to be materialized. Instead, we want to design algorithms that minimize the preprocessing time and space, while guaranteeing a small delay $\delta$. Interestingly, as we will see in~\autoref{sec:lowerbound}, the above result is essentially the best we can do if the ranking function is completely arbitrary; thus, we need to consider reasonable restrictions of $\rf$. 

To see what it is possible to achieve in this framework, it will be useful to keep in mind what we can do in the case where there is no ordering of the output.

\begin{theorem}[due to \cite{DBLP:journals/tods/OlteanuZ15}]\label{thm:no:rank}
	Let $Q$ be a natural join query with hypergraph $\mH = (\nodes, \edges)$. Let $\htree$ be a tree decomposition with fractional hypertree-width \fhw. Then, for any input database $D$, we can pre-process $D$ in time $T_p = O(|D|^{\fhw})$ and space $ S_p = O(|D|^{\fhw})$
	such that we can enumerate the results of $Q(D)$ with $\text{delay } \delta = {O}(1) $ and $\text{space } S_e = O(1)$
\end{theorem}

For acyclic queries, $\fhw = 1$, and hence the preprocessing phase takes only linear time and space in the size of the input. 

\section{Introduction}
\label{sec:intro}

For many data processing applications, enumerating query results according to an order given by a ranking function is a fundamental task. For example, \cite{yang2018any, chang2015optimal} consider a setting where users want to extract the top patterns from an edge-weighted graph, where the rank of each pattern is the sum of the weights of the edges in the pattern. Ranked enumeration also occurs in \oldtt{SQL} queries with an \oldtt{ORDER BY} clause~\cite{qi2007sum, ilyas2004rank}.
In the above scenarios, the user often wants to see the first $k$ results in the query as quickly as possible, but the value of $k$ may not be predetermined. Hence, it is critical to construct algorithms that can output the first tuple of the result as fast as possible, and then output the next tuple in the order with a very small {\em delay}.
In this paper, we study the algorithmic problem of enumerating the result of a Conjunctive Query (CQ, for short) against a relational database where the tuples must be output in order given by a ranking function.

The simplest way to enumerate the output is to materialize the result $\tOUT$ and sort the tuples based on the score of each tuple. Although this approach is conceptually simple, it requires that $\vert \tOUT \vert$ tuples are materialized; moreover, the time from when the user submits the query to when she receives the first output tuples is $\Omega (\vert \tOUT \vert \cdot \log \vert \tOUT \vert)$. Further, the space and delay guarantees do not depend on the number of tuples that the user wants to actually see. 
 More sophisticated approaches to this problem construct optimizers that exploit properties such as the monotonicity of the ranking function, allowing for join evaluation on a subset of the input relations (see~\cite{ilyas2008survey} and references within). In spite of the significant progress, all of the known techniques suffer from large worst-case space requirements, no dependence on $k$, and provide no formal guarantees on the delay during enumeration, {with the exception of a few cases where the ranking function is of a special form}. Fagin et al.~\cite{fagin2003optimal} initiated a long line of study related to aggregation over {\em sorted lists}. However,~\cite{fagin2003optimal} and subsequent works also suffer from the above mentioned limitations as we do not have the materialized output $Q(D)$ that can be used as sorted lists.

In this paper, we construct algorithms that remedy some of these issues. Our algorithms are divided into two phases: the {\em preprocessing phase}, where the system constructs a data structure that can be used later and the {\em enumeration phase}, when the results are generated. All of our algorithms aim to minimize the time of the preprocessing 
phase, and guarantee a {\em logarithmic delay} ${O}(\log |D|)$ during enumeration. Although we cannot hope to
perform efficient ranked enumeration for an arbitrary ranking function, we show that our techniques apply for most ranking 
functions of practical interest, including lexicographic ordering, and sum (also product or max) of weights of input tuples among others.

\begin{example}\label{ex:intro}
Consider a weighted graph $G$, where an edge $(a,b)$ with weight $w$ is represented by the relation $R(a,b,w)$.
Suppose that the user is interested in finding the (directed) paths of length 3 in the graph with the lowest score, where
the score is a (weighted) sum of the weights of the edges. The user query in this case can be specified as:
$ Q(x,y,z,u, w_1, w_2, w_3, ) = R(x,y,w_1), R(y,z, w_2), R(z,u,w_3)$
where the ranking of the output tuples is specified for example by the score $5w_1 + 2w_2 + 4w_3$. 
If the graph has $N$ edges, the na\"ive algorithm that computes and ranks all tuples needs $\Omega(N^2 \log N)$ preprocessing time. We show that it is possible to design an algorithm with $O(N)$ preprocessing time, such that
the delay during enumeration is ${O}(\log N)$. This algorithm outputs the first $k$ tuples by
materializing $O(N+k)$ data, even if the full output is much larger.
\end{example}


The problem of ranked enumeration for CQs has been studied both theoretically~\cite{kimelfeld2006incrementally, cohen2007incremental, DBLP:journals/tods/OlteanuZ15} and practically~\cite{yang2018any, chang2015optimal, bakibayev2012fdb}. 
Theoretically,~\cite{kimelfeld2006incrementally} establishes the tractability of enumerating answers in sorted order with polynomial delay (combined complexity), albeit with suboptimal space and delay factors for two classes of ranking functions. 
\cite{yang2018any} presents an anytime enumeration algorithm restricted to acyclic queries on graphs that uses $\Theta(|\tOUT| + |D|)$ space in the worst case, has a $\Theta(|D|)$ delay guarantee, and supports only simple ranking functions.
As we will see, both of these guarantees are suboptimal and can be improved upon. 


Ranked enumeration has also been studied for the class of lexicographic orderings. In~\cite{bagan2007acyclic}, the authors show that {\em free-connex acyclic CQs} can be enumerated in constant delay after only linear time preprocessing. Here, the lexicographic order is chosen by the algorithm and not the user. 
Factorized databases~\cite{bakibayev2012fdb, DBLP:journals/tods/OlteanuZ15} can also support constant delay ranked enumeration, but only when the lexicographic ordering agrees with the order of the query decomposition. In contrast, our results imply that we can achieve a logarithmic delay with the same preprocessing time for {\em any} lexicographic order.


\smallskip
\introparagraph{Our Contribution} In this work, we show how to obtain logarithmic delay guarantees with small preprocessing time  for ranking results of full (projection free) CQs. We summarize our technical contributions below:

\begin{enumerate}

\item Our main contribution (\autoref{thm:main}) is a novel algorithm that uses query decomposition techniques in conjunction with structure of the ranking function. The preprocessing phase sets up priority queues that maintain partial tuples at each node of the decomposition. During the enumeration phase, the algorithm materializes the output of the subquery formed by the subtree rooted at each node of the decomposition {\em on-the-fly}, in sorted order according to the ranking function. In order to define the rank of the partial tuples, we require that the ranking function can be \emph{decomposed} with respect to the particular decomposition at hand.~\autoref{thm:main} then shows that with $O(|D|^\fhw)$ preprocessing time, where \fhw\ is the {\em fractional hypertree width} of the decomposition, we can enumerate with delay ${O}(\log |D|)$. We then discuss how to apply our main result to  commonly used classes of ranking functions. Our work thoroughly resolves an open problem stated at the Dagstuhl Seminar 19211~\cite{boros_et_al} on ranked enumeration (see Question $4.6$).

\item We propose two extensions of \autoref{thm:main} that improve the preprocessing time to $O(|D|^\subw)$, polynomial improvement over \autoref{thm:main} where \subw\ is the {\em submodular width} of the query $Q$. The result is based on a simple but powerful corollary of the main result that can be applied to any full UCQ $Q$ combined with the \panda\ algorithm proposed by Abo Khamis et al.~\cite{abo2017shannon}.

\item Finally, we show lower bounds (conditional and unconditional) for our algorithmic results.
In particular, we show that subject to a popular conjecture, the logarithmic factor in delay cannot be removed. Additionally, we show that for two particular classes of ranking functions, we can characterize for which acyclic queries it is possible to achieve logarithmic delay with linear preprocessing time, and for which it is not. 
\end{enumerate}


\section{Lower Bounds}
\label{sec:lowerbound}

In this section, we provide evidence for the near optimality of our results. 

\subsection{The Choice of Ranking Function}
We first consider the impact of the ranking function on the performance of ranked enumeration. 
We start with a simple observation that deals with the case where $\rf$ has no structure,
and can be accessed only through a blackbox that, given a tuple/valuation, returns its score: we call this 
a {\em blackbox} \footnote{Blackbox implies that the score $\rf(\theta)$ is revealed only upon querying the function.} ranking function. Note that all of our algorithms work under the blackbox assumption.

\begin{proposition}
Let $Q$ be a natural join query, and $\rf$ a blackbox ranking function. Then, any enumeration algorithm
on a database $D$ needs $\Omega(\vert Q(D) \vert)$ calls to $\rf$-- and worst case $\Omega(|D|^{\rho^*})$ calls 
--  in order to output the smallest tuple.
\end{proposition}

Indeed, if the algorithm does not examine the rank of an output tuple, then we can always assign a value to the ranking
function such that the tuple is the smallest one. Hence, in the case where there is no restriction on the ranking function,
the simple result in~\autoref{prop:simple:enum} that materializes and sorts the output is essentially optimal.
Thus, it is necessary to exploit properties of the ranking function in order to construct better algorithms. Unfortunately, even for natural restrictions of ranking functions, it is not possible to do much better than the
$|D|^{\rho^*}$ bound for certain queries. 

Such a natural restriction is that of coordinate decomposable functions, 
where we can show the following lower bound result:


\begin{lemma} \label{lem:lowerbound}
Consider the query $Q (x_1,y_1, x_2, y_2) = \ R(x_1,y_1), S(x_2, y_2)$
and let $\rf$ be a blackbox coordinate decomposable ranking function. Then, there exists an instance of size $N$
such that the time required to find the smallest  tuple is $\Omega(N^2)$.
\end{lemma}

~\autoref{lem:lowerbound} shows that for coordinate decomposable functions, there exist queries where  obtaining constant (or almost constant) delay requires the algorithm to spend superlinear time during the preprocessing step. 
Given this result, the immediate question is to see whether we can extend the lower bound to other CQs. 

\smallskip
\introparagraph{Dichotomy for coordinate decomposable}
We first show a dichotomy result for coordinate decomposable functions.

\begin{theorem} \label{thm:dichotomy:vertex}
Consider a full acyclic query $Q$ and a coordinate decomposable blackbox ranking function. There exists an algorithm that enumerates the result of $Q$ in ranked order with $O(\log |D|)$ delay guarantee and $T_p = O(|D|)$ preprocessing time if and only if 
there are no atoms $R$ and $S$ in $Q$ such that $\vars{R} \setminus \vars{S} \geq 2$ and $\vars{S} \setminus \vars{R} \geq 2$.
 \end{theorem}
 
For example, the query $Q(x,y,z) = R(x,y), S(y,z)$ satisfies the condition of~\autoref{thm:dichotomy:vertex}, while the
Cartesian product query defined in~\autoref{lem:lowerbound} does not.
 
\smallskip
\introparagraph{Dichotomy for edge decomposable} 
We will show a dichotomy result for edge decomposable ranking functions: these are functions that
 are $S$-decomposable for any $S$ that is a hyperedge in the query hypergraph. 
Before we present the result, we need to formally define the notion of path and diameter in a hypergraph.

\begin{definition}
	Given a connected hypergraph $\mH = (\nodes, \edges)$, a path $P$ in $\mH$ from vertex $x_1$ to $x_{s+1}$ is a vertex-edge alternate set $x_1E_1x_2E_2 \dots x_s E_s x_{s+1}$ such that $\{x_i, x_{i+1}\} \subseteq E_i (i \in [s])$ and $x_i \neq x_{j}, E_i \neq E_j$ for $i \neq j$. Here, $s$ is the length of the path $P$. The distance between any two vertices $u$ and $v$, denoted $d(u,v)$, is the length of the shortest path connecting $u$ and $v$. The {\em diameter} of a hypergraph, $\dia(\mH)$, is the maximum distance between all pairs of vertices.
\end{definition}

\begin{theorem} \label{thm:edge:dichotomy}
Consider a full connected acyclic join query $Q$ and a blackbox edge decomposable ranking function. Then, there exists an algorithm that enumerates the result of $Q$ in ranked order with $O(\log |D|)$ delay and $T_p = O(|D|)$ preprocessing time if and only if $\dia(Q) \leq 3$.
\end{theorem}

For example, $Q(x,y,z,w) = R(x,y),S(y,z),T(z,w)$ has diameter $3$, and thus we can enumerate the result with linear preprocessing time and logarithmic delay for any edge decomposable ranking function. On the other hand, for the 4-path query $Q(x,y,z,w,t) = R(x,y),S(y,z),T(z,w),U(w,t)$, it is not possible to achieve this.


When the query is not connected, the characterization must be slightly modified:
an acyclic query can be enumerated with  $O(\log |D|)$ delay and $T_p = O(|D|)$
if and only if each connected subquery has diameter at most $3$.




\subsection{Beyond Logarithmic Delay} 
Next, we examine whether  the logarithmic factor that we obtain in the delay of~\autoref{thm:main} can be removed for ranked enumeration. In other words, is it possible to achieve constant delay enumeration while keeping the preprocessing time small, even for simple ranking functions? To reason about this, we need to describe the {\em $X+Y$ sorting} problem.

Given two lists of $n$ numbers, $X = \langle x_1, x_2, \dots, x_{n} \rangle$ and $Y = \langle y_1, y_2, \dots, y_{n} \rangle$, we want to enumerate all $n^2$ pairs $(x_i, y_j)$ in ascending order of their sum $x_i + y_j$. This classic problem has a trivial $O(n^2 \log n)$ algorithm that materializes all $n^2$ pairs and sorts them. However, it remains an open problem whether the pairs can be enumerated faster in the RAM model. Fredman~\cite{fredman1976good}  showed that $O(n^2)$ comparisons suffice in the nonuniform linear decision tree model, but it remains open whether this can be converted into an $O(n^2)$-time algorithm in the real RAM model. Steiger and Streinu~\cite{steiger1995pseudo} gave a simple algorithm that takes $O(n^2 \log n)$ time while using only $O(n^2)$ comparisons. 
\begin{mdframed}
\vspace{-0.7em}
\begin{conjecture} [\cite{bremner2006necklaces, open}]
 {\em $X+Y$ sorting} does not admit an $O(n^2)$ time algorithm. \label{conjecture:sort:x+y}
\end{conjecture}
\end{mdframed}

In our setting, $X+Y$ sorting can be expressed as enumerating the output of the cartesian product $Q(x, y) = R(x), S(y)$, where relations $R$ and $S$ correspond to the sets $X$ and $Y$ respectively. The ranking function is $\rf(x,y) = x + y$. ~\autoref{conjecture:sort:x+y} implies that it is not possible to achieve constant delay for the cartesian product query and the sum ranking function; otherwise, a full enumeration would produce a sorted order in time $O(n^2)$.

\section{Main Result}
\label{sec:proof}

In this section, we present our first main result. 


\begin{theorem}[Main Theorem] \label{thm:main}
Let $Q$ be a natural join query with hypergraph $\mH = (\nodes, \edges)$. Let $\htree$ be a fixed tree decomposition with fractional hypertree-width \fhw, and $\rf$ be a ranking function that is compatible with $\htree$.
Then, for any database $D$, we can preprocess $D$ with
	$$
		 T_p = {O}(|D|^{\fhw}) \quad \quad S_p = {O}(|D|^{\fhw})
	$$
	such that for any $k$, we can enumerate the top-$k$ tuples of $Q(D)$ with
	$$
		 \text{delay } \delta = {O}(\log |D|) \quad \quad
		\text{space } S_e = O(\min \{k, \vert Q(D) \vert\})
	$$
	\end{theorem}

In the above theorem, the preprocessing step is independent of the value of $k$: we perform exactly the same preprocessing if the user only wants to obtain the first tuple, or all tuples in the result. However, if the user decides to stop after having obtained the first $k$ results, the space used during enumeration will be bound by $O(k)$.
We should also note that all of our algorithms work in the case where the ordering of the tuples/valuations is instead expressed through a \texttt{comparable} function that, given two valuations, returns the largest one.

It is instructive to compare~\autoref{thm:main} with~\autoref{thm:no:rank}, where no ranking is used when enumerating the results. There are two major differences. First, the delay $\delta$ has an additional logarithmic factor. As we will discuss later in ~\autoref{sec:lowerbound}, this logarithmic factor is a result of doing ranked enumeration, and it is most likely unavoidable. The second difference is that the space $S_e$ used during enumeration blows up from constant $O(1)$ to $O(|Q(D)|)$ in the worst case (when all results are enumerated).

In the remainder of this section, we will present a few applications of~\autoref{thm:main}, and then sketch the construction for the proof of the theorem.



\subsection{Applications}
\label{sec:app}

We show here how to apply~\autoref{thm:main} to obtain algorithms for different ranking functions.

\smallskip
\introparagraph{Vertex-Based Ranking} A vertex-based ranking function over $\nodes$ is of the form: $ \rf(\theta) := \bigoplus_{x \in \nodes} f_x(\theta(x)) $
where $f_x$ maps values from $\domain$ to some set $U \subseteq \mathbb{R}$, and 
$\langle U, \oplus \rangle$ forms a {\em commutative monoid}. Recall that this means that 
$\oplus$ is a binary operator that is commutative, associative, and has an identity element in $U$. 
We say that the function is monotone if $a \geq b$ implies that $a \oplus c \geq b \oplus c$ for every $c$.
Such examples are $\langle \mathbb{R}, + \rangle$, $\langle \mathbb{R}, * \rangle$, and
$\langle U, max \rangle$, where $U$ is bounded.

\begin{lemma}\label{lem:vb}
Let $\rf$ be a monotone vertex-based ranking function over $\nodes$. Then, $\rf$ is totally decomposable,
and hence compatible with any tree decomposition of a hypergraph with vertices $\nodes$.
\end{lemma}


\introparagraph{Tuple-Based Ranking} 
Given a query hypergraph $\mH$, a tuple-based ranking function assigns for every valuation $\theta$ over
the variables $x_F$ of relation $R_F$ a weight $w_F(\theta) \in U \subseteq \mathbb{R}$. Then, it takes the 
following form: $ \rf(\theta) := \bigoplus_{F \in \edges} w_F(\theta[x_F]) $
where $\langle U, \oplus \rangle$ forms a {\em commutative monoid}. In other words, a tuple-based ranking function
assigns a weight to each input tuple, and then combines the weights through $\oplus$.

\begin{lemma} \label{lem:tb}
Let $\rf$ be a monotone tuple-based ranking function over $\nodes$. Then, $\rf$
is compatible with any tree decomposition of a hypergraph with vertices $\nodes$.
\end{lemma}

Since both monotone tuple-based and vertex-based ranking functions are compatible with any tree decomposition
we choose, the following result is immediate.

\begin{proposition} \label{prop:rankings}
Let $Q$ be a natural join query with optimal fractional hypertree-width $\fhw$. Let $\rf$ be a ranking function that can be 
either $(i)$ monotone vertex-based, $(ii)$ monotone tuple-based.
Then, for any input $D$, we can pre-process $D$ in time $ T_p = {O}(|D|^{\fhw})$ and space $ S_p = {O}(|D|^{\fhw})$	such that for any $k$, we can enumerate the top-$k$ results of $Q(D)$ with $ \delta = O(\log|D|) $ and  $ S_e = O(\min \{k, \vert Q(D) \vert\})$
\end{proposition}

For instance, if the query is acyclic, hence $\fhw=1$, the above theorem gives an algorithm with linear preprocessing time $O(|D|)$ and $O(\log |D|)$ delay.

\smallskip
\introparagraph{Lexicographic Ranking} A typical ordering of the output valuations is according to a {\em lexicographic order}.
In this case, each $\domain(x)$ is equipped with a total order. If $\nodes = \{x_1, \dots, x_k\}$, a lexicographic order
$\langle x_{i_1}, \dots, x_{i_\ell} \rangle$ for $\ell \leq k$ means that two valuations $\theta_1, \theta_2$ are first ranked on $x_{i_1}$, and if they have the same rank on $x_{i_1}$, then they are ranked on $x_{i_2}$, and so on. This ordering can be naturally encoded by first taking a function $f_x: \domain(x) \rightarrow \mathbb{R}$ that captures the total order for variable $x$, and then defining $\rf(\theta) := \sum_x w_x f_x(\theta(x))$, where $w_x$ are appropriately chosen constants. Since this ranking function is a monotone vertex-based ranking,~\autoref{prop:rankings} applies here as well. 

We should note here that lexicographic ordering has been previously considered in the context of factorized databases.

\begin{proposition}[due to ~\cite{DBLP:journals/tods/OlteanuZ15, bakibayev2012fdb}] \label{thm:factorized:lexicographic}
Let $Q$ be a natural join query with hypergraph $\mH = (\nodes, \edges)$, and 
$\langle x_{i_1}, \dots, x_{i_\ell} \rangle$  a lexicographic ordering of the variables in $\nodes$.

Let $\htree$ be a tree decomposition with fractional hypertree-width \fhwob\ such that 
$\langle x_{i_1}, \dots, x_{i_\ell} \rangle$ forms a prefix in the topological ordering of the variables in the decomposition. 
Then, for any input database $D$, we can pre-process $D$ with $T_p = O(|D|^{\fhwob})$ and  $S_p = O(|D|^{\fhwob})$
such that results of $Q(D)$ can be enumerated with delay $\delta = {O}(1)$ and space $S_e = O(1)$.	
\end{proposition}

In other words, if the lexicographic order "agrees" with the tree decomposition (in the sense that whenever $x_{i}$ is before $x_j$ in the lexicographic order, $x_j$ can never be in a bag higher than the bag where $x_i$ is), then it is possible to get an even better result than~\autoref{thm:main}, by achieving constant delay $O(1)$, and constant space $S_e$.
However, given a tree decomposition,~\autoref{thm:main} applies for any lexicographic ordering - in contrast to~\autoref{thm:factorized:lexicographic}. 
As an example, consider the join query $Q(x,y,z) = R(x,y),S(y,z)$ and the lexicographic ordering $\langle z, x, y \rangle$. 
Since $\fhw = 1$, our result implies that we can achieve $O(|D|)$ time preprocessing with delay ${O}(\log |D|)$.
On the other hand, the optimal width of a tree decomposition that agrees with $\langle z, x, y \rangle$ is $\fhwob = 2$; 
hence,~\autoref{thm:factorized:lexicographic} implies $O(|D|^2)$ preprocessing time and space. 
Thus, variable orderings in a decomposition fail to capture the additional challenge of user chosen lexicographic orderings. It is also not clear whether further restrictions on variable orderings in~\autoref{thm:factorized:lexicographic} are sufficient to capture ordered enumeration for other ranking functions (such as sum).





\smallskip
\introparagraph{Bounded Ranking} A ranking function is {\em $c$-bounded} if there exists a subset $S \subseteq \nodes$ of
size $|S| =c$, such that the value of $\rf$ depends only on the variables from $S$. A $c$-bounded ranking is related to $c$-determined ranking functions~\cite{kimelfeld2006incrementally}: $c$-determined implies $c$-bounded, but not vice versa.
For $c$-bounded ranking functions, we can show the following result:

\begin{proposition}  \label{prop:c}
Let $Q$ be a natural join query with optimal fractional hypertree-width $\fhw$. If $\rf$ is a $c$-bounded ranking function,
then for any input $D$, we can pre-process $D$ in time $ T_p = {O}(|D|^{\fhw+c})$ and space $ S_p = {O}(|D|^{\fhw+c})	$ such that for any $k$, we can enumerate the top-$k$ results of $Q(D)$ with	$\delta = O(\log |D|)$ and $ S_e = O(\min \{k, \vert Q(D) \vert\})$
\end{proposition}


\subsection{The Algorithm for the Main Theorem}

At a high level, each node $t$ in the tree decomposition will materialize in an incremental fashion all valuations over
$\subtree{t}$ that satisfy the query that corresponds to the subtree rooted at $t$. 
We do not store explicitly each valuation $\theta$ over $\subtree{t}$ at every node $t$, but instead we use a simple 
recursive structure $C(v)$ that we call a {\em cell}.
If $t$ is a leaf, then $C(\theta) = \langle \theta, [], \bot \rangle$, where $\bot$ is used to denote a null pointer.
Otherwise, suppose that $t$ has $n$ children $t_1, \dots, t_n$.
Then, $C(\theta) = \langle \theta[\mB_t], [p_1, \dots, p_n], q \rangle$, where 
$p_i$ is a pointer to the cell $C(\theta[\subtree{t_i}])$ stored at node $t_i$,
and $q$ is a pointer to a cell stored at node $t$ (intuitively representing the "next" valuation in the order).
It is easy to see that, given a cell $C(\theta)$, one can reconstruct $\theta$ in constant time (dependent only on the query).
Additionally, each node $t$ maintains one hash map $\qQ_t$, which
maps each valuation $u$ over $\key{\mB_t}$ to a {\em priority queue} $\qQ_t[u]$.
The elements of $\qQ_t$ are cells $C(\theta)$, where $\theta$ is a valuation over $\subtree{t}$
such that $u = \theta[\key{\mB_t}]$. The priority queues will be the data structure that performs the
comparison and ordering between different tuples. We will use an implementation of a priority queue (e.g., a Fibonacci heap~\cite{CLRS}) with the following properties: $(i)$ we can insert an element in constant time $O(1)$, $(ii)$ we can obtain the min element (top) in time $O(1)$, and $(iii)$ we can delete the min element (pop) in time $O(\log n)$. 

Notice that it is not straightforward to rank the cells according to the valuations, since the ranking function is
defined over all variables $\nodes$. However, here we can use the fact that the ranking function is compatible
with the decomposition at hand. Indeed, given a fixed valuation $u$ over $\key{\mB_t}$, we will order the valuations $\theta$ 
over $\subtree{t}$ that agree with $u$ according to the score:
$ \rank{v_{t}^{\star} \circ \theta}$
where $v_{t}^\star$ is a valuation over $\nodes \setminus \subtree{t}$ chosen according to the definition of decomposability. The key intuition is that the compatibility of the ranking function with the decomposition implies that the ordering of the tuples in the priority queue $\qQ_t[u]$ will not change if we replace $v_{t}^\star$ with any other valuation. Thus, the comparator can use $v_{t}^\star$ to calculate the score which is used by the priority queue internally.
We next discuss the {\em preprocessing} and {\em enumeration} phase of the algorithm.

\begin{minipage}{0.48\linewidth}
	\hspace{-2em}
	\scalebox{0.9}{
		\begin{algorithm}[H]
			\SetCommentSty{textsf}
			\DontPrintSemicolon 
			\SetKwFunction{fullreducer}{\textsc{Materialize}}
			\SetKwFunction{initializepq}{\textsc{InitializePQ}}
			\SetKwFunction{recurse}{\textsc{Recurse}}
			\SetKwFunction{proc}{\textsf{eval}}
			\SetKwFunction{ins}{\textsc{insert}}
			\SetKwFunction{app}{\textsc{insert}}
			\SetKwFunction{top}{\textsc{top()}}
			\SetKwFunction{pop}{\textsc{pop()}}
			\SetKwData{pointer}{\textsf{pointer}}
			\SetKwFunction{preprocess}{\textsc{preprocess}}	
			\SetKwData{temp}{\textsf{temp}}
			\SetKwFunction{fillout}{\textsc{FillOUT}}
			\SetKwInOut{Input}{\textsc{input}}
			\SetKwInOut{Global}{\textsc{global variables}}
			\SetKwInOut{Output}{\textsc{output}}
			\SetKwProg{myproc}{\textsc{procedure}}{}{}
			
				\ForEach{$t \in V(\htree)$}{
					\textit{materialize the bag} $\mB_t$ \;
				}
				\textit{full reducer pass on materialized bags in} $\htree$ \;
				
				\BlankLine
				\ForAll{$t \in V(\htree)$ in post-order traversal}{
					\ForEach{valuation $\theta$ in bag $\mB_t$}{
						$u \gets \theta[\key{\mB_t}]$\;
						\If{$\qQ_t[u]$ is $\texttt{NULL}$}{ $\qQ_t[u] \gets$ new priority queue}
						$\ell \gets []$ \;
						\tcc{$\ell$ is a list of pointers}
						\ForEach{child $s$ of $t$}{ \label{line:loop}
							\label{line:topq} $\ell.\app( \qQ_s[\theta[\key{\mB_{s}}]].\top)$ 
						}
						$\qQ_t[u].\ins(\langle \theta, \ell, \bot \rangle)$
						\tcc{ranking function uses $\theta, \ell, v_{t}^\star$ to calculate score used by priority queue}
					}
				}
			
			\caption{Preprocessing Phase}
			\label{algo:preprocessing}
	\end{algorithm}}
\end{minipage}
\begin{minipage}{0.48\linewidth}
	\hspace{-2em}
	\scalebox{0.9}{
		\begin{algorithm}[H]
			\SetCommentSty{textsf}
			\DontPrintSemicolon 
			\SetKwFunction{fullreducer}{\textsc{Materialize}}
			\SetKwFunction{initializepq}{\textsc{InitializePQ}}
			\SetKwFunction{fillout}{\textsc{topdown}}
			\SetKwFunction{ins}{\textsc{insert}}
			\SetKwFunction{app}{\textsc{insert}}
			\SetKwFunction{top}{\textsc{top()}}
			\SetKwFunction{pop}{\textsc{pop()}}
			\SetKwFunction{enum}{\textsc{enum}}	
			\SetKwFunction{eoe}{\textsc{eoe}}	
			\SetKwData{pointer}{\textsf{pointer}}
			\SetKwData{temp}{\textsf{temp}}
			\SetKwData{retval}{\textsf{retval}}
			\SetKwData{popvalue}{\textsf{popvalue}}
			\SetKwInOut{Input}{\textsc{input}}\SetKwInOut{Output}{\textsc{output}}
			\SetKwProg{myproc}{\textsc{procedure}}{}{}
			%
			\myproc{\enum{} \label{func:enum}}{
				\While{$\qQ_{r}[()]$ is not empty}{
					\textbf{output} $\qQ_{r}[()].\top$ \;
					\fillout{$\qQ_{r}[()].\top, r$} \;
				}
			}
			\BlankLine
			\myproc{\fillout{$c, t$}}{
				/* $c = \langle \theta,  [p_1, \dots, p_k], \mnext \rangle$ */ \;
				$u \gets \theta[\key{\mB_t}]$ \;
				\If{$\mnext = \bot$ \label{line:if}}{
					$\qQ_t[u].\pop$ \label{tuple:pop}\;
					\ForEach{child $t_i$ of $t$ \label{for:1}}{
						$p_i' \gets \fillout{$*p_i, t_i$}$\;
						\If{$p_i' \neq \bot$}{ \label{push:queue}
							$\qQ_t[u].\ins(\langle \theta,  [p_1, \dots, p_i', \dots p_k], \bot \rangle)$ 
							\tcc{insert new candidate(s)}
						}
					}
					\If {$t$ is not the root}{
						$\mnext \gets \qQ_t[u].\top$ \label{chaining}}
				}
				\KwRet{$\mnext$} \;
			}
			\caption{Enumeration Phase} \label{algo:enumeration}
	\end{algorithm}}
\end{minipage}


\begin{figure}[htp!]
	\begin{subfigure}[t]{0.99\linewidth}
		\centering
	
		\scalebox{.99}{\begin{tikzpicture}
			\tikzset{edge/.style = {->,> = latex'},
				vertex/.style={circle, thick, minimum size=7mm}}
			\def0.25{0.25}
			\def-1{-1}
			\begin{scope}[fill opacity=0.5, draw opacity = 0.5]
			\draw[fill=black!5] (0, 1) ellipse (1cm and 0.33cm) node {\small ${\color{black} x, y}$};
			\draw[fill=black!5] (0, -1) ellipse (1cm and 0.33cm) node {\small ${\color{black} y, z}$};
			\draw[fill=black!5] (-3, -2.25) ellipse (1cm and 0.33cm) node {\small ${\color{black} z, w}$};
			\draw[fill=black!5] (3, -2.25) ellipse (1cm and 0.33cm) node {\small ${\color{black} z, u}$};
			\draw[edge] (0, 0.66) -- (0,-.65);
			\draw[edge] (0, -1.33) -- (-3, -1.9);
			\draw[edge] (0, -1.33) -- (3, -1.9);
			
		
		
		
		
			\end{scope}	
			\tikzset{pblock/.style = {rectangle split, rectangle split parts=2,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6em, align=center, rectangle split part fill = {white, white}}}
			
			\tikzset{qblock/.style = {rectangle split, rectangle split parts=1,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6em, align=center}}	
			
			\tikzset{rblock/.style = {rectangle split, rectangle split parts=2,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6em, align=center}}		
			
			\tikzset{b4block/.style = {rectangle split, rectangle split parts=2,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6em, align=center, rectangle split part fill={olive!30,teal!30}}}		
			
			\tikzset{b3block/.style = {rectangle split, rectangle split parts=2,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6em, align=center, rectangle split part fill={magenta!30,orange!60}}}
			
			\tikzset{b2block/.style = {rectangle split, rectangle split parts=1,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6em, align=center, rectangle split part fill={blue!30}}}	
			
			\node[b4block] (b4) at (3, -3.5) {
				\nodepart{one} {\mystrut $\mathtt{\langle 1, [], \bot \rangle}$ \quad {$1$}}
				\nodepart{two} {\mystrut $\langle 2, [], \bot \rangle$ \quad {$5$}}};
			
			\node[b3block] (b3)  at (-3, -3.5) {
				\nodepart{one} {\mystrut $\mathtt{\langle 1, [], \bot \rangle}$ \quad {$1$}}
				\nodepart{two} {\mystrut $\langle 2, [], \bot \rangle$ \quad {$4$}}};										
			
		
			\node[b2block] (b2) at (4+-1, -1) {
				\nodepart{one} {\mystrut $\langle 1, [\tikz\draw[magenta,fill=magenta] circle (.5ex); \tikz\draw[olive,fill=olive] circle (.5ex);], \bot \rangle$ \enskip {$3$}}};
			
			\draw[*->, color=olive] (b2.one west)++(0,-0.1) to[out=-180,in=-180] (b4.one west);
			\draw[*->, color=magenta] (b2.one west)++(0,-0.1) to[out=-180,in=0] (b3.one east);
			
		
			\node[rblock] (b1)  at (4+-1, 1) {
				\nodepart{one} {\mystrut $\mathtt{\langle 1, [\tikz\draw[blue!40,fill=blue!40] circle (.5ex);], \bot \rangle}$ \quad {$4$}}
				\nodepart{two} {\mystrut $\langle 2, [\tikz\draw[blue!40,fill=blue!40] circle (.5ex);], \bot \rangle$ \quad {$5$}}};		
			
			\draw[*->, color=blue!40] (b1.one west)++(0,0) to[out=-180,in=-180] (b2.one west);
			\draw[*->, color=blue!40] (b1.two west)++(0,0) to[out=-180,in=-180] (b2.one west);
			
			\node[left, align=left] at (b4.west) {$\qQ_{\mB_4}[1]$};
			\node[left, align=left] at (b3.west) {$\qQ_{\mB_3}[1]$};
			\node[right, align=right] at (b2.east) {$\qQ_{\mB_2}[1]$};			
			\node[right, align=right] at (b1.east) {$\qQ_{\mB_1}[()]$};
			
			\end{tikzpicture}
		}
		\caption{Priority queue state (mirroring the decomposition) after preprocessing phase.} \label{fig:preprocessing}
	\end{subfigure}	\hfill 
	\begin{subfigure}[t]{0.99\linewidth}
	
		\centering
		\scalebox{.99}{\begin{tikzpicture}
			\tikzset{edge/.style = {->,> = latex'},
				vertex/.style={circle, thick, minimum size=7mm}}
			\def0.25{0.25}
			\def-1{-1}
			
			\tikzset{pblock/.style = {rectangle split, rectangle split parts=2,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6em, align=center}}
			
			\tikzset{qblock/.style = {rectangle split, rectangle split parts=1,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6em, align=center, rectangle split part fill={lightgray}}}	
			
			\tikzset{b4block/.style = {rectangle split, rectangle split parts=2,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6em, align=center, rectangle split part fill={olive!30,teal!30}}}		
			
			\tikzset{b3block/.style = {rectangle split, rectangle split parts=2,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6em, align=center, rectangle split part fill={magenta!30,orange!60}}}
			
			\tikzset{b2block/.style = {rectangle split, rectangle split parts=2,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6em, align=center, rectangle split part fill={brown!50,lime!60}}}	
			
			\tikzset{b2pblock/.style = {rectangle split, rectangle split parts=1,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6em, align=center, rectangle split part fill={blue!30}}}	
			
			\scalebox{.7}{
				
				\node[draw, rectangle, minimum width=8em, minimum height=12.5em, line width=0.1mm, label=above:{\texttt{first popped tuple}}] at (-3.5,-1.1) {};
				
				\node[b2pblock] (b2p) at (-3.5, -1+0.25-1.75) {
					\nodepart{one} {\mystrut $\mathtt{\langle 1, [\tikz\draw[magenta,fill=magenta] circle (.5ex);\tikz\draw[olive,fill=olive] circle (.5ex);], \tikz\draw[brown,fill=brown] circle (.5ex); \rangle}$ \enskip {$3$}}};
				
				\node[qblock] (b1p) at (-3.5, 1+-1+0.25) {
					\nodepart[text opacity=0.5, fill opacity=0.5]{one} {\mystrut $\mathtt{\langle 1, [\tikz\draw[blue,fill=blue] circle (.5ex);], \bot \rangle}$ \quad {$4$}}};
				
				\draw[*->, color=blue!60] (b1p.one south)++(0,-0.15) to[out=-270,in=90] (b2p.one north);
			}	
			
			
		
			\node[b4block] (b4) at (4.5, -3.5+-1) {
				\nodepart{one} {\mystrut $\mathtt{\langle 1, [], \tikz\draw[cyan,fill=cyan] circle (.5ex); \rangle}$ \quad {$1$}}
				\nodepart{two} {\mystrut $\langle 2, [], \bot \rangle$ \quad {$5$}}};
			
		
			\node[b3block] (b3)  at (-3, -3.5+-1) {
				\nodepart{one} {\mystrut $\mathtt{\langle 1, [], \tikz\draw[orange,fill=orange] circle (.5ex); \rangle}$ \quad {$1$}}
				\nodepart{two} {\mystrut $\langle 2, [], \bot \rangle$ \quad {$4$}}};							
			
			\draw[*->, color=magenta] (b2p.one south)++(1,0.85) to[out=-90,in=90] (b3.one north);
			\draw[*->, color=olive] (b2p.one south)++(1.15,0.85) to[out=-90,in=180] (b4.one west);			
			
		
			\node[b2block] (b2) at (1, -1+-1) {
				\nodepart{one} {\mystrut $\langle 1, [\tikz\draw[orange,fill=orange] circle (.5ex); \tikz\draw[olive,fill=olive] circle (.5ex);], \bot \rangle$ \enskip {$6$}}
				\nodepart{two} {\mystrut $\langle 1, [\tikz\draw[magenta,fill=magenta] circle (.5ex); \tikz\draw[cyan,fill=cyan] circle (.5ex);], \bot \rangle$ \enskip {$7$}}};
			
			\draw[*->, color=olive] (b2.one east) to[out=0,in=-180] (b4.one west);
			\draw[*->, color=orange] (b2.one west)++(0,-0.1) to[out=-180,in=0] (b3.two east);
			\draw[*->, color=magenta] (b2.two west) to[out=-180,in=0] (b3.one east);
			\draw[*->, color=cyan] (b2.two east)++(0,-0.1) to[out=0,in=-180] (b4.two west);
			
			\draw[*->, color=brown] (b2p.one west)++(3.08,0.7) to[out=0,in=180] (b2.one west);			
			
		
			\node[pblock] (b1)  at (1, 1+-1) {
				\nodepart{one} {\mystrut $\langle 2, [\tikz\draw[blue!30,fill=blue!30] circle (.5ex);], \bot \rangle$ \quad {$5$}}
				\nodepart{two} {\mystrut $\mathtt{\langle 1, [\tikz\draw[brown,fill=brown] circle (.5ex);], \bot \rangle}$ \quad {$7$}}};		
			
			\draw[*->, color=blue!60] (b1.one west) to[out=-180,in=0] ([xshift=0.7cm, yshift=0.9cm]b2p.one east);
			\draw[*->, color=brown] (b1.two west)++(0,0) to[out=-180,in=-180] (b2.one west);
			
			\node[left, align=right] at (b4.west) {$\qQ_{\mB_4}[1]$};
			\node[left, align=left] at (b3.west) {$\qQ_{\mB_3}[1]$};
			\node[right, align=right] at (b2.east) {$\qQ_{\mB_2}[1]$};			
			\node[right, align=right] at (b1.east) {$\qQ_{\mB_1}[()]$};
			
			\end{tikzpicture}
		}
		\caption{Priority queue state after one iteration of loop in procedure \FuncSty{\texttt{ENUM}()}.} \label{fig:firstenum}
	\end{subfigure}
	%
	\begin{subfigure}[t]{\linewidth}
		\vspace{1em}
		\centering
		\scalebox{.99}{\begin{tikzpicture}
			\tikzset{edge/.style = {->,> = latex'},
				vertex/.style={circle, thick, minimum size=7mm}}
			\def0.25{0.25}
			\def-1{-1}
			
			\tikzset{pblock/.style = {rectangle split, rectangle split parts=2,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6em, align=center}}
			
			\tikzset{qblock/.style = {rectangle split, rectangle split parts=1,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6em, align=center, rectangle split part fill={lightgray}}}	
			
			\tikzset{b4block/.style = {rectangle split, rectangle split parts=2,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6em, align=center, rectangle split part fill={olive!30,teal!30}}}		
			
			\tikzset{b3block/.style = {rectangle split, rectangle split parts=2,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6em, align=center, rectangle split part fill={magenta!30,orange!60}}}
			
			\tikzset{b2block/.style = {rectangle split, rectangle split parts=2,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6em, align=center, rectangle split part fill={brown!50,lime!60}}}	
			
			\tikzset{b2oneblock/.style = {rectangle split, rectangle split parts=1,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6em, align=center, rectangle split part fill={blue!30}}}	
			
			\tikzset{b2twoblock/.style = {rectangle split, rectangle split parts=1,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6em, align=center, rectangle split part fill={brown!50}}}
			
			\tikzset{b2threeblock/.style = {rectangle split, rectangle split parts=1,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6em, align=center, rectangle split part fill={lime!50}}}		
			
			\tikzset{b2fourblock/.style = {rectangle split, rectangle split parts=1,
					draw, rectangle split horizontal=false,inner ysep=0pt, line width=0.15em, text width=6.5em, align=center, rectangle split part fill={violet!50}}}	
			
			
			\node[b2oneblock] (b21) at (-5, -2) {
				\nodepart{one} {\mystrut $\mathtt{\langle 1, [\tikz\draw[magenta,fill=magenta] circle (.5ex);\tikz\draw[olive,fill=olive] circle (.5ex);], \tikz\draw[brown,fill=brown] circle (.5ex); \rangle}$ \enskip {$3$}}};
			
			\node[b2twoblock] (b22) at (-1.5, -2) {
				\nodepart{one} {\mystrut $\mathtt{\langle 1, [\tikz\draw[orange,fill=orange] circle (.5ex);\tikz\draw[olive,fill=olive] circle (.5ex);], \tikz\draw[lime,fill=lime] circle (.5ex); \rangle}$ \enskip {$6$}}};
			
			\node[b2threeblock] (b23) at (1.5, -2) {
				\nodepart{one} {\mystrut $\langle 1, [\tikz\draw[magenta,fill=magenta] circle (.5ex); \tikz\draw[cyan,fill=cyan] circle (.5ex);], \tikz\draw[violet,fill=violet] circle (.5ex); \rangle$ \enskip {$7$}}};
			
			\node[b2fourblock] (b24) at (5, -2) {
				\nodepart{one} {\mystrut $\langle 1, [\tikz\draw[orange,fill=orange] circle (.5ex); \tikz\draw[cyan,fill=cyan] circle (.5ex);], \bot \rangle$ \enskip {$10$}}};
			
		
			\node[b4block] (b4) at (6, -3.5+-1) {
				\nodepart{one} {\mystrut $\mathtt{\langle 1, [], \tikz\draw[cyan,fill=cyan] circle (.5ex); \rangle}$ \quad {$1$}}
				\nodepart{two} {\mystrut $\langle 2, [], \bot \rangle$ \quad {$5$}}};
			
		
			\node[b3block] (b3)  at (-6, -3.5+-1) {
				\nodepart{one} {\mystrut $\mathtt{\langle 1, [], \tikz\draw[orange,fill=orange] circle (.5ex); \rangle}$ \quad {$1$}}
				\nodepart{two} {\mystrut $\langle 2, [], \bot \rangle$ \quad {$4$}}};							
			
			\draw[*->, color=magenta] (b21.one south)++(-0.1,0) to[out=-90,in=90] (b3.one north);
			\draw[*->, color=olive] (b21.one south)++(0.1,0) to[out=-90,in=180] (b4.one west);	
			
			\draw[*->, color=brown] (b21.one east)++(0,0) to[out=0,in=180] (b22.one west);
			\draw[*->, color=lime] (b22.one east)++(0,0) to[out=0,in=180] (b23.one west);		
			\draw[*->, color=violet] (b23.one east)++(0,0) to[out=0,in=180] (b24.one west);
			
			
			\draw[*->, color=olive] (b22.one south)++(0.1,0) to[out=-90,in=180] (b4.one west);
			\draw[*->, color=orange] (b22.one south)++(-0.1,0) to[out=-90,in=0] (b3.two east);
			\draw[*->, color=magenta] (b23.one south)++(-0.1,0) to[out=-90,in=-0] (b3.one east);
			\draw[*->, color=cyan] (b23.one south)++(0.1,0) to[out=-90,in=180] (b4.two west);
			\draw[*->, color=orange] (b24.one south)++(-0.1,0) to[out=-90,in=-0] (b3.two east);
			\draw[*->, color=cyan] (b24.one south)++(0.1,0) to[out=-90,in=180] (b4.two west);
			\end{tikzpicture}}
		\caption{The materialized output stored at subtree rooted at $\mB_2$  after enumeration is complete} \label{fig:materialized}
	\end{subfigure}
	\caption{Preprocessing and enumeration phase for~\autoref{ex:intro}. Each memory location is shown with a different color. Pointers in cells are denoted using \mytikzdot\ which means that the it points to a memory location with the corresponding color (shown using pointed arrows). Root bag priority queue cells are not color coded as nobody points to them.}
\end{figure}


\smallskip
\introparagraph{Preprocessing}
\autoref{algo:preprocessing} consists of two steps.
The first step works exactly as in the case where there is no ranking function: each bag $\mB_t$ is computed and materialized, and then we apply a full reducer pass to remove all tuples from the materialized bags that will not join in the final result.
The second step initializes the hash map with the priority queues for every bag in the tree. We traverse the decomposition in a bottom up fashion (post-order traversal), and do the following. For a leaf node $t$, notice that the algorithm does not enter the loop in line~\ref{line:loop}, so each valuation $\theta$ over $\mB_t$ is added to the corresponding queue as the triple $\langle \theta, [], \bot \rangle$. For each non-leaf node $t$, we take each valuation $v$ over $\mB_t$ and form a valuation (in the form of a cell) over $\subtree{t}$ by using the valuations with the largest rank from its children (we do this by accessing the top of the corresponding queues in line~\ref{line:topq}). The cell is then added to the corresponding priority queue of the bag. Observe that the root node $r$ has only one priority queue, since $\key{r} = \{\}$.


\begin{example}
	As a running example, we consider the  natural join query $Q(x,y,z,w) =  R_1(x,y), R_2(y,z), R_3(z,w), R_4(z,u)$ where the ranking function is the sum of the weights of each input tuple. Consider the following instance $D$ and decomposition $\htree$ for our running example.
	
	\begin{minipage}[t]{0.3\linewidth}
		\centering
		\begin{tabular}[t]{ !{\vrule width1pt} c| c|c|c  !{\vrule width1pt} } 
			\Xhline{1pt}
			$id$ & $\mathbf{w_1}$ & $\mathbf{x}$ & $\mathbf{y}$ \\ 
			\Xhline{1pt}
			1 & 1 & 1 & 1 \\ 
			2& 2 & 2 & 1 \\
			\Xhline{1pt}
		\end{tabular}		
		\vspace{1em}
		$R_1$
	\end{minipage}
	\begin{minipage}[t]{0.3\linewidth}
		\centering
		\begin{tabular}[t]{ !{\vrule width1pt} c| c|c|c !{\vrule width1pt} } 
			\Xhline{1pt}
			$id$& $\mathbf{w_2}$ & $\mathbf{y}$ & $\mathbf{z}$ \\ 
			\Xhline{1pt}
			1 & 1 & 1 & 1 \\ 
			2 & 1 & 3 & 1 \\
			\Xhline{1pt}
		\end{tabular}		
		\vspace{1em}	
		$R_2$
	\end{minipage}
	\begin{minipage}[t]{0.3\linewidth}
		\centering
		\begin{tabular}[t]{ !{\vrule width1pt} c|c|c|c !{\vrule width1pt} } 
			\Xhline{1pt}
			$id$ & $\mathbf{w_3}$ & $\mathbf{z}$ & $\mathbf{w}$ \\ 
			\Xhline{1pt}
			1 & 1 & 1 & 1 \\ 
			2 & 4 & 1 & 2 \\
			\Xhline{1pt}
		\end{tabular}		
		\vspace{1em}
		$R_3$
	\end{minipage}
	\newline
	\begin{minipage}[t]{0.45\linewidth}
		\centering
		\begin{tabular}[t]{ !{\vrule width1pt} c|c|c|c !{\vrule width1pt} } 
			\Xhline{1pt}
			$id$ & $\mathbf{w_3}$ & $\mathbf{z}$ & $\mathbf{u}$ \\ 
			\Xhline{1pt}
			1 & 1 & 1 & 1 \\ 
			2 & 5 & 1 & 2 \\
			\Xhline{1pt}
		\end{tabular}		
		\vspace{1em}
		$R_4$
	\end{minipage}
	\begin{minipage}[t]{0.45\linewidth}
		\centering
		\vspace{-1.5em}
		\scalebox{.8}{\begin{tikzpicture}
			\tikzset{edge/.style = {->,> = latex'},
				vertex/.style={circle, thick, minimum size=7mm}}
			\def0.25{0.25}
			
			\begin{scope}[fill opacity=1]
			\draw[fill=black!5] (0, 0) ellipse (1cm and 0.33cm) node {\small ${\color{black} x, y}$};
			\draw[fill=black!5] (0, -1) ellipse (1cm and 0.33cm) node {\small ${\color{black} y, z}$};
			\draw[fill=black!5] (-1.5, -2) ellipse (1cm and 0.33cm) node {\small ${\color{black} z, w}$};
			\draw[fill=black!5] (1.5, -2) ellipse (1cm and 0.33cm) node {\small ${\color{black} z, u}$};
			\draw[edge] (0, -0.33) -- (0,-.65);
			\draw[edge] (0, -1.33) -- (-1.5, -1.65);
			\draw[edge] (0, -1.33) -- (1.5, -1.65);
			
			\node[vertex]  at (-2, 0) {\small $\mB_{\texttt{root}} = \mB_1$};
			\node[vertex]  at (-1.5, -1) {\small $\mB_{2}$};				
			\node[vertex]  at (-1.5, -2.66) {\small $\mB_{3}$};				
			\node[vertex]  at (1.5, -2.66) {\small $\mB_{4}$};												
			\end{scope}	
			\end{tikzpicture}
		}
	
	\end{minipage}


	
	
For the instance shown above and the query decomposition that we have fixed, relation $R_i$ covers bag $\mB_i, i \in [4]$. Each relation has size $N = 2$. Since the relations are already materialized, we only need to perform a full reducer pass, which can be done in linear time. This step removes tuple $(3,1)$ from relation $R_2$ as it does not join with any tuple in $R_1$. 
	
	\autoref{fig:preprocessing} shows the state of priority queues after the pre-processing step. For convenience, $\theta$ in each cell $\langle \theta,  [p_1, \dots, p_k], \mnext \rangle$ is shown using the primary key of the tuple and pointers $p_i$ and $\mnext$ are shown using colored dots \mytikzdot\ representing the memory location it points to. The cell in a memory location is followed by the partial aggregated score of the tuple formed by creating the tuple from the pointers in the cell recursively. For instance, the score of the tuple formed by joining $(y=1,z=1) \in R_2$ with $(z=1,w=1)$ from $R_3$ and $(z=1,u=1)$ in $R_4$ is $1+1+1=3$  (shown as \mytikzcell\ in the figure). Each cell in every priority queue points to the top element of the priority queue of child nodes that are joinable. Note that since both tuples in $R_1$ join with the sole tuple from $R_2$, they point to the same cell.
\end{example}







\introparagraph{Enumeration}
\autoref{algo:enumeration} presents the algorithm for the enumeration phase. The heart of the algorithm is the procedure \texttt{TOPDOWN(}$c,t$\texttt{)}.
The key idea of the procedure is that whenever we want to output a new tuple, we can simply obtain it from the top of the priority queue in the root node (node $r$ is the root node of the tree decomposition). Once we do that, we need to update the priority queue by popping the top, and inserting (if necessary) new valuations in the priority queue. This will be recursively propagated in the tree until it reaches the leaf nodes. Observe that once the new candidates have been inserted, the \textsf{next} pointer of cell $c$ is updated by pointing to the topmost element in the priority queue. This chaining materializes the answers for the particular bag that can be reused.


\begin{example}
	\autoref{fig:firstenum} shows the state of the data structure after one iteration in \FuncSty{\texttt{ENUM}()}. The first answer returned to the user is the topmost tuple from $\qQ_{\mB_1}[()]$ (shown in top left of the figure). Cell \myrootcell\ is popped from $\qQ_{\mB_1}[()]$ (after satisfying if condition on~\autoref{line:if} as $\mnext$ is $\bot$). Since nothing is pointing to this cell, it is garbage collected (denoted by greying out the cell). We recursively call \FuncSty{\texttt{TOPDOWN}} for child node $\mB_2$ and cell \mytikzcell\ . The \textsf{next} for this cell is also $\bot$ and we pop it from $\qQ_{\mB_2}[1]$. At this point, $\qQ_{\mB_2}[1]$ is empty. The next recursive call is for $\mB_3$ with \mybthreecell\ . The least ranked tuple but larger than \mybthreecell\ in $\qQ_{\mB_3}[1]$ is the cell at address \mytikzdot\ . Thus, \textsf{next} for \mybthreecell\ is updated to \mytikzdot\ and cell at \mytikzdot\ is returned which leads to creation and insertion of \hspace{0.1em} \mybtwocell\ cell in $\qQ_{\mB_2}[1]$. Similarly, we get the other cell in $\qQ_{\mB_2}[1]$ by recursive call for $\mB_4$. After both the calls are over for node $\mB_2$, the topmost cell at $\qQ_{\mB_2}[1]$ is \mytikzbrowndot\ ,which is set as the $\mnext$ for \mytikzcell\ (changing into \mytikzcellcopy\ ), terminating one full iteration. \mytikzcellcopy\ is not garbage collected as \mybonecell\ is pointing to it. 
	
	Let us now look at the second iteration of \FuncSty{\texttt{ENUM}()}. The tuple returned is top element of $Q_{\mB_1}[()]$ which is \mybonecell\ . However, the function \FuncSty{\texttt{TOPDOWN}()} with \mybonecell\ does not recursively go all the way down to leaf nodes. Since \mytikzcellcopy\ already has \textsf{next} populated, we insert \mybonecellcopy\ in $Q_{\mB_1}[()]$ completing the iteration. This demonstrates the benefit of materializing ranked answers at each node in the tree. As the enumeration continues, we are materializing the output of each subtree on-the-fly that can be reused by other tuples in the root bag.~\autoref{fig:materialized} shows the eventual sequence of pointers at node $\mB_2$ which is the ranked materialized output of the subtree rooted at $\mB_2$. \mybonecell\ is garbage collected. 
\end{example}



\section{Extensions} \label{sec:extension}

In this section, we describe two extensions of~\autoref{thm:main} and how it can be used to further improve the main result. 

\subsection{Ranked Enumeration of UCQs}

We begin by discussing how ranked enumeration of full UCQs can be done. The first observation is that given a full UCQ $\varphi = \varphi_1 \cup \dots \varphi_\ell$, if the ranked enumeration of each $\varphi_i$ can be performed efficiently, then we can perform ranked enumeration for the union of query results. This can be achieved by applying~\autoref{thm:main} to each $\varphi_i$ and introducing another priority queue that compares the score of the answer tuples of each $\varphi_i$, pops the smallest result, and fetches the next smallest tuple from the data structure of $\varphi_i$ accordingly. Although each $\varphi_i(D)$ does not contain duplicates, it may be the case that the same tuple is generated by multiple $\varphi_i$. Thus, we need to introduce a mechanism to ensure that all tuples with the same weight are enumerated in a specific order. Fortunately, this is easy to accomplish by modifying~\autoref{algo:enumeration} to enumerate all tuples with the same score in lexicographic increasing order. This ensures that tuples from each $\varphi_i$ also arrive in the same order. Since each $\varphi_i$ is enumerable in ranked order with delay $O(\log|D|)$ and the overhead of the priority queue is $O(\ell)$ (priority queue contains at most one tuple from each $\varphi_i$), the total delay guarantee is bounded by $O(\ell \cdot \log|D|) = O(\log|D|)$ as the query size is a constant.  The space usage is determined by the largest fractional hypertree-width across all decompositions of subqueries in $\varphi$. This immediately leads to the following corollary of the main result.

\begin{corollary} \label{cor:ucq}
	Let $\varphi = \varphi_1 \cup \dots \varphi_\ell$ be a full UCQ. Let \fhw\ denote the fractional hypertree-width of all decompositions across all CQs $\varphi_i$, and $\rf$ be a ranking function that is compatible with the decomposition of each $\varphi_i$. Then, for any input database $D$, we can pre-process $D$ in time and space,
	$$
	T_p = {O}(|D|^{\fhw}) \quad \quad S_p = {O}(|D|^{\fhw})
	$$
	such that for any $k$, we can enumerate the top-$k$ tuples of $\varphi(D)$ with
	$$
	\text{delay } \delta = {O}(\log |D|)  \quad \quad
	\text{space } S_e = O(\min \{k, \vert \varphi(D) \vert\})
	$$
	
\end{corollary}

\subsection{Improving The Main Result}

Although~\autoref{cor:ucq} is a straightforward extension of~\autoref{thm:main}, it is powerful enough to improve the pre-processing time and space of~\autoref{thm:main} by using~\autoref{cor:ucq} in conjunction with \emph{data-dependent} tree decompositions. It is well known that the query result for any CQ can be answered in time ${O}(|D|^\fhw + |Q(D)|)$ time and this is asymptotically tight~\cite{AGM}. However, there exists another notion of width known as the \emph{submodular width} (denoted \subw)~\cite{marx2013tractable}. It is also known that for any CQ, it holds that $\subw \leq \fhw$. Recent work by Abo Khamis et al.~\cite{abo2017shannon} presented an elegant algorithm called \panda\ that constructs multiple decompositions by partitioning the input database to minimize the intermediate join size result. \panda\ computes the output of any full CQ in time ${O}(|D|^\subw \cdot \log|D| + |\tOUT|)$. In other words, \panda\ takes a CQ query $Q$ and a database $D$ as input and produces multiple tree decompositions in time ${O}(|D|^\subw\cdot\log|D|)$ such that each answer tuple is generated by at least one decomposition. The number of decompositions depends only on size of the query and not on $D$. Thus, when the query size is a constant, the number of decompositions constructed is also a constant. We can now apply~\autoref{cor:ucq} by setting $\varphi_i$ as the tree decompositions produced by \panda\ to get the following result.~\autoref{appendix:sec:extension} describes the details of the enumeration algorithm and the tie-breaking comparison function.

\begin{theorem} \label{thm:main:subw}
	Let $\varphi$ be a natural join query with hypergraph $\mH = (\nodes, \edges)$, submodular width \subw, and $\rf$ be a ranking function that is compatible with each tree decomposition of $\varphi$.
	Then, for any input database $D$, we can pre-process $D$ in time and space,
	$$
	T_p = {O}(|D|^{\subw} \cdot \log |D|) \quad \quad S_p = {O}(|D|^{\subw})
	$$
	such that for any $k$, we can enumerate the top-$k$ tuples of $\varphi(D)$ with
	$$
	\text{delay } \delta = {O}(\log |D|)  \quad \quad
	\text{space } S_e = O(\min \{k, \vert \varphi(D) \vert\})
	$$
\end{theorem}


\section{Related Work}
\label{sec:related}

Top-k ranked enumeration of join queries has been studied extensively by the database community for both certain~\cite{li2005ranksql, qi2007sum, ilyas2004rank, li2005ranksql2} and uncertain databases~\cite{re2007efficient, zou2010finding}. Most of these works exploit the monotonicity property of scoring functions, building offline indexes and integrate the function into the cost model of the query optimizer in order to bound the number of operations required per answer tuple. We refer the reader to~\cite{ilyas2008survey} for a comprehensive survey of top-k processing techniques. More recent work~\cite{chang2015optimal, gupta2014top} has focused on enumerating \emph{twig-pattern} queries over graphs. Our work departs from this line of work in two aspects: {\itshape(i)} use of novel techniques that use query decompositions and clever tricks to achieve strictly better space requirement and formal delay guarantees; {\itshape(ii)} our algorithms are applicable to arbitrary hypergraphs as compared to simple graph patterns over binary relations. Most closely related to our setting are~\cite{kimelfeld2006incrementally} and~\cite{ yang2018any}. Algorithm in~\cite{kimelfeld2006incrementally} is fundamentally different from ours. It uses an adaptation of Lawler-Murty's procedure to generate candidate output tuples which is also a source of inefficiency given that it ignores query structure.~\cite{yang2018any} presented a novel anytime algorithm for enumerating {\em homomorphic tree patterns} with worst case delay and space guarantees where the ranking function is sum of weights of input tuples that contribute to an output tuple. Their algorithm also generates candidate output tuples with different scores and sorts them via a priority queue. However, the candidate generation phase is expensive and can be improved substantially, as we show in this paper. Our algorithm also generalizes the approach of prior work that showed how to find $k$ shortest paths in a graph~\cite{eppstein1998finding}  and may be useful to other problems in DP~\cite{roy2020crypt} and DGM~\cite{chowdhury2020data} where ranked enumeration is useful.

\smallskip
\noindent \introparagraph{Rank aggregation algorithms} 	Top-k processing over ranked lists of objects has a rich history. The problem was first studied by Fagin et al.~\cite{fagin2002combining, fagin2003optimal} where the database consists of $N$ objects and $m$ ranked streams, each containing a ranking of the $N$ objects with the goal of finding the top-$\mk$ results for coordinate monotone functions. The authors proposed Fagin's algorithm (\textsc{FA}) and Threshold algorithm (\textsc{TA}), both of which were shown to be instance optimal for database access cost under  sorted list access and random access model. This model would be applicable to our setting only if $Q(D)$ is already computed and materialized.  More importantly, \textsc{TA} can only give $O(N)$ delay guarantee using $O(N)$ space.~\cite{natsev2001supporting} extended the problem setting to the case where we want to enumerate top-$\mk$ answers for $t$-path query. The first proposed algorithm $J^*$ uses an iterative deepening mechanism that pushes the most promising candidates into a priority queue. Unfortunately, even though the algorithm is instance optimal with respect to number of sorted access over each list, the delay guarantee is $\Omega(\vert \tOUT \vert)$ with space requirement $S = \Omega(\vert \tOUT \vert)$. A second proposed algorithm $J^*_{PA}$ allows random access over each sorted list. $J^*_{PA}$ uses a dynamic threshold to decide when to use random access over other lists to find joining tuples versus sorted access but does not improve formal guarantees. 

\smallskip
\noindent \introparagraph{Query enumeration} The notion of constant delay query enumeration was introduced by Bagan, Durand and Grandjean in~\cite{bagan2007acyclic}. In this setting, preprocessing time is supposed to be much smaller than the time needed to evaluate the query (usually, linear in the size of the database), and the delay between two output tuples may depend on the query, but not on the database. This notion captures the {\em intrinsic hardness} of query structure. For an introduction to this topic and an overview of the state-of-the-art we refer the reader to the survey~\cite{segoufin2013enumerating, segoufin2015constant}. Most of the results in existing works focus only on lexicographic enumeration of query results where the ordering of variables cannot be arbitrarily chosen. Transferring the static setting enumeration results to under updates has also been a subject of recent interest~\cite{berkholz2018answering, berkholz2017answering}.

\smallskip
\noindent \introparagraph{Factorized databases} Following the landmark result of~\cite{DBLP:journals/tods/OlteanuZ15} which introduced the notion of using the logical structure of the query for efficient join evaluation, a long line of research has benefited from its application to learning problems and broader classes of queries~\cite{bakibayev2012fdb, bakibayev2013aggregation, olteanu2016factorized, deep2018compressed, kara2020trade, deep2020fast, deep2021enumeration}. The core idea of factorized databases is to convert an arbitrary query into an acyclic query by finding a query decomposition of small width. This width parameter controls the space and pre-processing time required in order to build indexes allowing for constant delay enumeration. We build on top of factorized representations and integrate ranking functions in the framework to enable enumeration beyond lexicographic orders. 

