# Ranked Enumeration of Join Queries with Projections

Shaleen Deep University of Wisconsin - Madison<EMAIL_ADDRESS>,  Xiao Hu
Duke University<EMAIL_ADDRESS>and  Paraschos Koutris University of
Wisconsin - Madison<EMAIL_ADDRESS>
###### Abstract.

Join query evaluation with ordering is a fundamental data processing task in
relational database management systems. SQL and custom graph query languages
such as Cypher offer this functionality by allowing users to specify the order
via the  ORDER BY clause. In many scenarios, the users also want to see the
first $k$ results quickly (expressed by the  LIMIT clause), but the value of
$k$ is not predetermined as user queries are arriving in an online fashion.
Recent work has made considerable progress in identifying optimal algorithms
for ranked enumeration of join queries that do _not_ contain any projections.
In this paper, we initiate the study of the problem of enumerating results in
ranked order for queries with projections. Our main result shows that for any
acyclic query, it is possible to obtain a near-linear (in the size of the
database) delay algorithm after only a linear time preprocessing step for two
important ranking functions: sum and lexicographic ordering. For a practical
subset of acyclic queries known as star queries, we show an even stronger
result that allows a user to obtain a smooth tradeoff between faster answering
time guarantees using more preprocessing time. Our results are also extensible
to queries containing cycles and unions. We also perform a comprehensive
experimental evaluation to demonstrate that our algorithms, which are simple
to implement, improve up to three orders of magnitude in the running time over
state-of-the-art algorithms implemented within open-source RDBMS and
specialized graph databases.

PVLDB Reference Format:
PVLDB, 15(5): XXX-XXX, 2022.
doi:10.14778/3510397.3510401 ††This work is licensed under the Creative
Commons BY-NC-ND 4.0 International License. Visit
https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this
license. For any use beyond those covered by this license, obtain permission
by emailing<EMAIL_ADDRESS>Copyright is held by the owner/author(s).
Publication rights licensed to the VLDB Endowment.
Proceedings of the VLDB Endowment, Vol. 15, No. 5 ISSN 2150-8097.
doi:10.14778/3510397.3510401

PVLDB Artifact Availability:
The source code, data, and/or other artifacts have been made available at
%leave␣empty␣if␣no␣availability␣url␣should␣be␣sethttps://github.com/shaleen/rankedenumprojections.

##  1\. Introduction

Join processing is one of the most fundamental problems in database research
with applications in many areas such as anomaly and community detection in
social media, fraud detection in finance, and health monitoring. In many data
analytics tasks, it is also required to rank the query results in a specific
order. This functionality is supported by the  ORDER BY clause in SQL, Cypher
and SPARQL. We demonstrate a practical example use-case.

###### Example 0.

Consider the DBLP dataset as a single relation $R(A,B)$, indicating that $A$
is an author of paper $B$. Given an author $a$, the function h-index$(a)$
returns the h-index of $a$. A popular analytical task asks to find all co-
authors who authored at least one paper together. Additionally, the pairs of
authors should be returned in decreasing order of the sum of their h-indexes,
since users are only interested in the top-100 results. The following SQL
query captures this task.

⬇

SELECT DISTINCT $R_{1}.A,R_{2}.A$ FROM $R$ AS $R_{1}$, $R$ AS $R_{2}$

WHERE $R_{1}.B=R_{2}.B$

ORDER BY h_index($R_{1}.A$) + h_index($R_{2}.A$) LIMIT 100;

The above task is an example of a join query with projections (join-project
queries) because attribute $B$ has been projected out (i.e. it is not present
in the selection clause). The  DISTINCT clause ensures that there are no
duplicate results.

Importance of joins with projections. Join queries containing projections
appear in several practical applications such as recommendation systems (Feng
et al., 2019; Li et al., 2019), similarity search (Yu et al., 2012), and
network reachability analysis (Elmacioglu and Lee, 2005; Biryukov, 2008). In
fact, as Manegold et al. (Manegold et al., 2009) remarked, joins in real-life
queries almost always come with projections over certain attributes. Matrix
multiplication (Amossen and Pagh, 2009), path queries (equivalent to sparse
matrix multiplication), and reachability queries (Green et al., 2013) are all
examples of join-project queries that have widespread applications in linear
and relational algebra. Other data models such as SPARQL (Pérez et al., 2009)
also support the projection operator and evaluation of join-project queries
has been a subject of research, both theoretically (Angles and Gutierrez,
2011) and practically (Corby and Faron-Zucker, 2007). In fact, as SPARQL
supports  ORDER BY/ LIMIT operator, ranked enumeration for queries (that
include projections) and top-k over knowledge bases in the SPARQL model has
also been explicitly studied recently (Leeka et al., 2016; Christmann et al.,
2021). As many practical SPARQL evaluation systems (Harris and Shadbolt, 2005;
Sequeda and Miranker, 2013) evaluate queries using RDBMS, it is important to
develop efficient algorithms for such queries in the relational model.
Similarly, (Xirogiannopoulos and Deshpande, 2017) argued that since a large
fraction of the data of interest resides in RDBMS, efficient execution of
graph queries (such as path and reachability queries that contain projections
and ranking) using RDBMS as the backend is valuable. In the relational
setting, join-project queries also appear in the context of probabilistic
databases (see Section 2.3 in (Dalvi and Suciu, 2007)). This motivates us to
develop efficient algorithms, both in theory and practice, that address the
challenge of incorporating the ranked enumeration paradigm for join-project
queries.

Prior Work. Efficient evaluation of join queries in the presence of ranking
functions has been a subject of intense research in the database community.
Recent work (Tziavelis et al., 2020a; Deep and Koutris, 2021; Yang et al.,
2018; Chang et al., 2015; Tziavelis et al., 2021) has made significant
progress in identifying optimal algorithms for enumerating query results in
ranked order. In each of these works, the key idea is to perform on-the-fly
sorting of the output via the use of priority queues by taking into account
the query structure. (Chang et al., 2015) considered the problem of top-k tree
matching in graphs and proposed optimal algorithms by combining Lawler’s
procedure (Lawler, 1972) with the ranking function. (Tziavelis et al., 2020a)
introduced multiple dynamic programming algorithms that lazily populate the
priority queues. (Yang et al., 2018) took a different approach where all
possible candidates were eagerly inserted into the priority queues and (Deep
and Koutris, 2021) generalized these ideas to present a unified theory of
ranked enumeration for full join queries. Very recently, (Tziavelis et al.,
2021) was able to extend some of these results to non equi-joins as well. The
performance metric for enumerating query results is the _delay_ (Bagan et al.,
2007), defined as the time difference between any two consecutive answers.
Prior work was able to obtain logarithmic delay guarantees, which were shown
to be optimal. However, all prior work in this space suffer from one
fundamental limitation: it assumes that the join query is full, i.e. there are
no non-trivial projections involved. In fact, (Tziavelis et al., 2021)
explicitly remarks that in presence of projections, the strong guarantees
obtained for full queries do not hold anymore. Their suggestion to handle this
limitation is to convert the query with projections into a projection-free
result, i.e. materialize the join query result, apply the projection filter,
and then rank the resulting output. However, this conversion requires an
expensive materialization step. An alternate approach is to modify the weights
of the tuples/attribute values to allow re-use of existing algorithms (we
describe this approach in Section 2). As we show later, this approach also
does not fare any better and requires enumerating the full output of the join
query, which can be polynomially slower than the optimal solution.

On the practical side, all RDBMS and graph processing engines evaluate join-
project queries in the presence of ranking functions by performing three
operations in serial order: $(i)$ materializing the result of the full join
query, $(ii)$ de-duplicating the query result (since the query has  DISTINCT
clause), and $(iii)$ sorting the de-duplicated result according to the ranking
function. The first step in this process is a show-stopper. Indeed, the size
of the full join query result can be orders of magnitude larger than the size
of the final output after applying projections and de-duplicating it. Thus,
the materialization and the de-duplication step introduces significant
overhead since they are blocking operators. Further, if the user is interested
in only a small fraction of the ordered output, the user still has to wait
until the entire query completes even to see the top-ranked result.

###  1.1. Our Contribution and Key Ideas

In this paper, we initiate the study of ranked enumeration over join-project
queries. We focus on two important ranking functions:  SUM ($f(x,z)=x+z$) and
LEXICOGRAPHIC ($f(x,z)=x,z$) for two reasons. First, both of these functions
are very useful in practice (Ilyas et al., 2008). Second, extending the
algorithmic ideas to other functions, such as  MIN,  MAX,  AVG and circuits
that use sum and products, is quite straightforward. More specifically, we
make three contributions.

1\. Enumeration with Formal Delay Guarantees. Our first main result shows that
for any acyclic query (the most common fragment of queries in practice
(Bonifati et al., 2020)) with arbitrary projection attributes, it is possible
to develop efficient enumeration algorithms (Section 3).

###### Theorem 2.

For an acyclic join-project query $Q$, an instance $D$, and a ranking function
$\mathsf{rank}\in\\{\text{{\color[rgb]{0.76953125,0.125,0.26171875}\definecolor[named]{pgfstrokecolor}{rgb}{0.76953125,0.125,0.26171875}
SUM}},\text{{\color[rgb]{0.76953125,0.125,0.26171875}\definecolor[named]{pgfstrokecolor}{rgb}{0.76953125,0.125,0.26171875}
LEXICOGRAPHIC}}\\}$, the query result $Q(D)$ can be enumerated according to
$\mathsf{rank}$ with worst-case delay $O(|D|\log|D|)$, after $O(|D|)$
preprocessing time.

This result implies that top-$k$ results in $Q(D)$ can be enumerated in
$O(k|D|\log|D|)$ time. Theorem 2 is able to recover the prior results for
ranked enumeration of full queries as well (Deep and Koutris, 2021). The key
idea of our algorithm is to develop multiway join plans (Ngo et al., 2012) by
exploiting the properties of join trees. Embedding the priority queues in the
join tree strategically allows us to generate the sorted output on-the-fly and
avoid the binary join plans that all state-of-the-art systems use. Further,
since we formulate the problem in terms of delay guarantees, it allows our
techniques to be limit-aware: for small $k$, the answering time is also small.

2\. Faster Enumeration with More Preprocessing. Our second contribution is an
algorithm that allows for a smooth tradeoff between preprocessing time and
delay guarantee for a subset of join-project queries known as star queries
over binary relations of the form $R_{i}(A_{i},B)$ (denoted as
$Q^{\star}_{m})$ (Section 4):

⬇

SELECT DISTINCT $A_{1},\dots,A_{m}$ FROM $R_{1},\dots,R_{m}$

WHERE $R_{1}.B=\dots=R_{m}.B$ ORDER BY $A_{1}+\dots+A_{m}$ LIMIT k;

###### Theorem 3.

For a star join-project query $Q^{\star}_{m}$, an instance $D$, and a ranking
function
$\mathsf{rank}\in\\{\text{{\color[rgb]{0.76953125,0.125,0.26171875}\definecolor[named]{pgfstrokecolor}{rgb}{0.76953125,0.125,0.26171875}
SUM}},\text{{\color[rgb]{0.76953125,0.125,0.26171875}\definecolor[named]{pgfstrokecolor}{rgb}{0.76953125,0.125,0.26171875}
LEXICOGRAPHIC}}\\}$, the query result $Q(D)$ can be enumerated according to
$\mathsf{rank}$ with worst-case delay $O\left(|D|^{1-\epsilon}\log|D|\right)$,
using $O\left(|D|^{1+(m-1)\epsilon}\right)$ preprocessing time and
$O\left(|D|^{m(1-\epsilon)}\right)$ space, for any $0\leq\epsilon\leq 1$.

Theorem 3 enables users to carefully control the space usage, preprocessing
time and delay. For both Theorem 2 and Theorem 3, we can show that the delay
guarantee is optimal subject to a conjecture about the running time of star
join-project queries in Subsection 4.2.

3\. Experimental Evaluation. Our final contribution is an extensive
experimental evaluation for practical join-project queries on real-world
datasets (Section 6). To the best of our knowledge, this is the first
comprehensive evaluation of how existing state-of-the-art relational and graph
engines execute join-project queries in the presence of ranking. We choose
MariaDB, PostgreSQL, two popular open-source RDBMS, and Neo4j as our
baselines. We highlight two key results. First, our experimental evaluation
demonstrates the bottleneck of serially performing materialization, de-
duplicating, and sorting. Even with  LIMIT 10 (i.e. return the top-$10$ ranked
results), the engines are orders of magnitude slower than our algorithm. For
some queries, they cannot finish the execution in a reasonable time since they
run out of main memory. On the other hand, our algorithm has orders of
magnitude smaller memory footprint that allows for faster execution. The
second key result is that all baseline engines are agnostic of the ranking
function. The execution time of the queries is identical for both the sum and
lexicographic ranking function. However, our algorithm uses the additional
structure of lexicographical ordering and can execute queries $2-3\times$
faster than the sum function. For queries with unions and cycles, our
algorithm maintains its performance improvement over the baselines.

##  2\. Problem Setting

In this section we present the basic notions and terminology, and then discuss
our framework. We focus on the class of join-project queries, which are
defined as

$Q=\pi_{\mathbf{A}}(R_{1}(\mathbf{A}_{1})\Join
R_{2}(\mathbf{A}_{2})\Join\ldots\Join R_{m}(\mathbf{A}_{m}))$

Here, each relation has schema $R_{i}(\mathbf{A}_{i})$, where $\mathbf{A}_{i}$
is an ordered set of attributes. Let
$\mathbb{A}=\mathbf{A}_{1}\cup\mathbf{A}_{2}\cup\cdots\cup\mathbf{A}_{m}$. The
projection operator $\pi_{\mathbf{A}}$ only keeps a subset of the attributes
from $\mathbb{A}$. The join we consider is natural join, where tuples from two
relations can be joined if they share the same value on the common attributes.
A join-project query is full if $\mathbf{A}=\mathbb{A}$. Unlike prior work on
ranked enumeration, in this paper we place no restriction on the set of
attributes in the projection operator. For simplicity of presentation, we do
not consider selections; these can be easily incorporated into our algorithms.
As an example, the SQL query in Example 1 corresponds to the following query:
$\pi_{A,B}(R_{1}(A,C)\Join R_{2}(B,C))$.

A database $D$ is a set of relations, whose size is defined as the total
number of tuples in all relations denoted as $|D|$. For tuple $t$, we will use
the shorthand $t[A]$ to denote $\pi_{A}(t)$. We use $\mathcal{E}$ to denote
the set of all relations in the database.

Acyclic Queries and Join Trees. A join-project query $Q$ is _acyclic_ if and
only if it admits a join tree $\mathcal{T}$. In a join tree, each relation is
a node, and for each attribute $A$, all nodes in the tree containing $A$ form
a connected subtree. For simplicity, we will use node $i$ to refer to the node
corresponding to relation $R_{i}$ in $\mathcal{T}$. Given a join tree
$\mathcal{T}$, pick any node to be the root, and then orient each edge towards
the root. Let $\mathcal{T}_{i}$ be the subtree rooted at node $R_{i}$. Let
$\texttt{parent}({R_{i}})$ be the (unique) parent of $R_{i}$, and
$\texttt{anchor}({R_{i}})=R_{i}\cap\texttt{parent}({R_{i}})$ to be the anchor
attributes between $R_{i}$ and its parent. Let $\texttt{child}({R_{i}})$ be
the set of children nodes of $R_{i}$. Finally, we fix the ordering of the
projection attributes in $\mathbf{A}$ to be the order of visiting them in the
in-order traversal of $\mathcal{T}$. Finally, we define $\mathbf{A}^{\pi}_{i}$
as the ordered set of projection attributes in subtree rooted at node $i$
(including projection attributes of node $i$). As a convention, we define
$\texttt{anchor}({r})=\emptyset,A^{\pi}_{r}=\emptyset$ for the root $r$ and
$\texttt{child}({R_{i}})=\emptyset$ for a leaf node $R_{i}$.

###### Example 0.

Consider a join-project query $Q=\pi_{A,E}(R_{1}(A,B)\Join R_{2}\\\ (B,C)\Join
R_{3}(C,D)\Join R_{4}(D,E))$ under the ranking function  SUM defined over
attributes $A,E$. In other words, for every output tuple $t$, the score of the
tuple is $t[A]+t[E]$. Figure 1 shows the join tree for the query. We fix
$R_{3}$ as the root with $R_{2}$ as the left child and $R_{4}$ (a leaf node)
as the right child. $R_{1}$, as a leaf node, is also the only child of
$R_{2}$.

Figure 1. Illustration of join tree for a join-project query
$Q=\pi_{A,E}(R_{1}(A,B)\Join R_{2}(B,C)\Join R_{3}(C,D)\Join R_{4}(D,E))$.
Figure 2. Examples of GHD and fhw. The leftmost is the minimal GHD of a cycle
join $Q=R_{1}(A_{1},A_{2})\Join R_{2}(A_{2},A_{3})\Join\cdots\Join
R_{n-1}(A_{n-1},A_{n})\Join R_{n}(A_{n},A_{1})$ with $\texttt{fhw}=2$. The
middle is the minimal GHD of a bi-clique join
$Q=\Join_{i\in[n],j\in[m]}R_{(i-1)m+j}(A_{i},B_{j})$ with $\texttt{fhw}=m$.
The rightmost is the minimal GHD of a butterfly join
$Q=R_{1}(A_{1},A_{2})\Join R_{2}(A_{2},A_{3})\Join R_{3}(A_{1},A_{4})\Join
R_{4}(A_{4},A_{3})$ with $\texttt{fhw}=2$.

Generalized Hypertree Decompositions. A weight assignment
$\mathbf{u}=(u_{F})_{F\in\mathcal{E}}$ is said to be a fractional edge cover
if $(i)$ for every $F\in\mathcal{E}$, $u_{F}\geq 0$; and $(ii)$ for every
$X\in\mathbb{A},\sum_{F:X\in F}u_{F}\geq 1$. The fractional edge cover number
for $\mathbb{A}$, denoted $\rho^{*}(\mathbb{A})$ is the minimum of
$\sum_{F\in\mathcal{E}}u_{F}$ over all possible edge covers. A generalized
hypertree decomposition (GHD) of a query $Q$ is a tuple
$(\mathscr{T},(\mathscr{B}_{t})_{t\in V(\mathscr{T})})$ where $\mathscr{T}$ is
a tree and every $\mathscr{B}_{t}$ (called the bag of $t$) is a subset of
$\mathbb{A}$ for each node $t$ of the tree such that: $(i)$ each variables of
each $F\in\mathcal{E}$ is contained in some bag; and $(ii)$ for each
$A\in\mathbb{A}$, the set of nodes $\\{{t}\mid{A\in\mathscr{B}_{t}}\\}$ is
connected in $\mathscr{T}$. The fractional hypertree width of a decomposition
is defined as $\max_{t\in V(\mathscr{T})}\rho^{*}(\mathscr{B}_{t})$, where
$\rho^{*}(\mathscr{B}_{t})$ is the fractional edge cover number of the
attributes in $\mathscr{B}_{t}$. The fractional hypertree width of a query
$Q$, denoted $\texttt{fhw}(Q)$, is the minimum fractional hypertree width over
all possible GHDs of $Q$. Figure 2 gives examples of GHDs of popular queries
and their width. For an acyclic query, it holds that $\texttt{fhw}=1$ and any
join tree is a valid GHD.

Computational Model. To measure the running time of our algorithms, we use the
uniform-cost RAM model (Hopcroft et al., 1975), 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, where the query is
assumed fixed. It is important to note that we focus on the main memory
setting. We further assume existence of perfect hashing that allows constant
time lookups in hash tables.

###  2.1. Ranking Functions

The ordering of query results in $Q(D)$ can be specified by a ranking
function, or through the  ORDER BY clause of a SQL query in practice.
Formally, a total order $\succeq$ on the tuples in $Q(D)$ defined over the
attributes $\mathbf{A}$, is induced by a ranking function rank that maps each
tuple $t\in Q(D)$ to a real number $\mathsf{rank}(t)\in\mathbb{R}$. In
particular, for two tuples $t_{1},t_{2}$, we have $t_{1}\succeq t_{2}$ if and
only if $\mathsf{rank}(t_{1})\geq\mathsf{rank}(t_{2})$. We assume that
$\mathbf{dom}(A)$ for any $A\in\mathbf{A}$ is also equipped with a total order
$\succeq$. We present an example of a ranking function below.

###### Example 0.

Consider a function $w:\mathbf{dom}(A)\to\mathbb{R}$ for any attribute
$A\in\mathbf{A}$. For each query result $t$, we define its rank as
$\texttt{rank}(t)=\sum_{A\in\mathbf{A}}w(t[A])$, the total sum of the weights
over all attributes in $\mathbf{A}$.

We will focus on  SUM and  LEXICOGRAPHIC in this paper. We note that both
functions are instantiations of a more general class of _decomposable
functions_ (Deep and Koutris, 2021). The ideas introduced for  SUM and
LEXICOGRAPHIC are readily applicable to more complicated functions including
products, a combination of sum and products, etc.

###  2.2. Problem Parameters

Given a join-project query $Q$ and a database $D$, an enumeration query asks
to enumerate the tuples of $Q(D)$ according to some specific ordering defined
by rank. We study this problem in a similar framework as (Segoufin, 2015),
where an algorithm is decomposed into:

  * •

a preprocessing phase that takes time $T_{p}$ and computes a data structure of
size $S_{p}$, and

  * •

an enumeration phase (i.e. the online query phase) that outputs $Q(D)$ without
duplicates under the specified ordering whenever a user query is issued. This
phase has full access to any data structures constructed in the preprocessing
phase. The time between outputting any two consecutive tuples (and also the
time to output the first tuple, and the time to notify that the enumeration
has completed after the last tuple) is at most $\delta$.

Prior work (Deep and Koutris, 2021) has shown that for acyclic joins without
projections, there exists an algorithm with $T_{p}=S_{p}=O(|D|)$ that can
achieve $\delta=O(\log|D|)$ delay under ranking. However, the problem of
ranked enumeration when projections are involved is wide open.

Using Existing Algorithms. One possible solution to the problem is to set the
weights of non-projection attributes to $0$. This will ensure that for  SUM
function, only the projection attributes are considered in the ranking and
existing algorithms for full join queries could be used. However, this
proposal gives poor delay guarantees and is as expensive as enumerating the
full join result. For example, for the four path query in Example 1, the
output of the query could be constant in size but the full join can be as
large as $\Omega(|D|^{2})$ which is prohibitively expensive, but our algorithm
would only require $O(|D|)$ in this case. In general, a join with $\ell$
relations may require as much as $\Omega(|D|^{\ell-1})$ time to output the
smallest tuple. We describe more details and the formal proof in Appendix B.

##  3\. General acyclic queries

We first describe the main algorithm of enumerating acyclic join-project
queries for  SUM ordering in Subsection 3.1, followed by a specialized
algorithm for  LEXICOGRAPHIC ordering in Subsection 3.2. Before we describe
the algorithm, we introduce two key data structures that will be used: cell
and priority queues.

###### Definition 0.

A cell, denoted as $c=\langle t,[p_{1},\dots,p_{k}],q\rangle$, is a vector
consisting of three values: (i) a tuple $t\in R_{i}$ for node $i$ in the join
tree $\mathcal{T}$, (ii) an array of pointers $[p_{1},\dots,p_{k}]$ where the
$\ell^{th}$ pointer points to a cell defined for $\ell^{th}$ child of node $i$
in $\mathcal{T}$, (iii) a pointer $q$ that can only point to another cell
defined for node $i$.

Given a cell $c$ defined for node $i$, one can reconstruct the tuple over
$\mathbf{A}^{\pi}_{i}$in constant time (dependent only on the query size,
which is a constant) by traversing the pointers recursively. We will use
$\mathsf{output(c)}$ to denote the utility method that performs this task.
Note that the time and space complexity of creating a cell is $O(1)$ since the
size of the query and the database schema is assumed to be a constant. This
implies that we only need to insert/access a constant number of entries in the
vector representing a cell. Similarly, $\mathsf{output(c)}$ also takes $O(1)$
time since the join tree size is a constant.

Priority queue. A priority queue is a data structure for maintaining a set $S$
of elements, each with an associated value called a key. The space complexity
of a priority queue containing $|S|$ elements is $O(|S|)$. We will use an
implementation of a priority queue (e.g., a Fibonacci heap (Fredman and
Tarjan, 1987)) with the following properties: (i) an element can be inserted
in $O(1)$ time, (ii) the min element can be obtained in $O(1)$ time, and (iii)
the min element can be popped and deleted in $O(\log|D|)$ time. We will use
the priority queue in conjunction with a cell in the following way: for two
cells $c_{1}$ and $c_{2}$, the priority queue uses
$\texttt{rank}(\mathsf{output(c_{1})})$ and
$\texttt{rank}(\mathsf{output(c_{2})})$ in the comparator function to
determine the relative ordering of $c_{1}$ and $c_{2}$. If
$\texttt{rank}(\mathsf{output(c_{1})})=\texttt{rank}(\mathsf{output(c_{2})})$,
then we break ties according to the lexicographic order of
$\mathsf{output(c_{1})}$ and $\mathsf{output(c_{2})}$. The choice of
lexicographic ordering is not driven by any specific consideration; as long as
the ties are broken consistently, we can use other tie-breaking criteria too.
Once again, the comparator function only takes a $O(1)$ time to compare since
the ranking function $\texttt{rank}(\mathsf{output(c)})$ can be evaluated in
constant time.

###  3.1. General Algorithm

In this section, we present the algorithm for Theorem 2. At a high level, each
node $i$ in the join tree will materialize, in an incremental fashion, all
tuples over the attributes $\mathbf{A}^{\pi}_{i}\cup\texttt{anchor}({R_{i}})$
in sorted order. In order to efficiently store the materialized output, we
will use the cell data structure. Since we need to sort the materialized
output, each node in the join tree maintains a set of priority queues indexed
by $\pi_{\texttt{anchor}({R_{i}})}(u),u\in R_{i}$. The values of the priority
queue are the cells of node $i$. For example, given the join tree from Example
1, node $2$ containing $R_{2}$ will incrementally materialize the sorted
result of the subquery $\pi_{C,A}(R_{2}(B,C)\Join R_{1}(A,B))$ that is indexed
by the values $\pi_{C}(R_{2}(B,C))$ since $\mathbf{A}^{\pi}_{2}=\\{A\\}$ and
$\texttt{anchor}({R_{2}})=\\{C\\}$. Note that there may be multiple possible
join trees for a given acyclic query. Our algorithm is applicable to all join
trees. In fact, any node in the join tree can be chosen as the root without
any impact on the time and space complexity.

Preprocessing Phase. We begin by describing the algorithm for preprocessing in
Algorithm 1. We assume that a join tree has been fixed and the input instance
$D$ does not contain any dangling tuples, i.e., tuples that will not
contribute in the join; otherwise, we can invoke the Yannakakis algorithm
(Yannakakis, 1981) to remove all dangling tuples. We initialize a set of empty
priority queues for every node in the join tree. We proceed in a bottom up
fashion and perform the following steps. For each leaf relation
$R_{i}\in\mathcal{T}$, we create a cell $\langle t,[],\bot\rangle$ for each
tuple $t\in R_{i}$ and insert it into
$\textsf{PQ}_{i}[\pi_{\texttt{anchor}({R_{i}})}(t)]$. For each non-leaf
relation $R_{j}\in\mathcal{T}$, we create a cell for $t\in R_{j}$, which
points to the top of the priority queue in each child node of $R_{j}$ that can
be joined with $t$. This cell is then added to the priority queue
$\textsf{PQ}_{i}[\pi_{\texttt{anchor}({R_{i}})}(t)]$. Note that we only have
one priority queue for the root relation $r$ since
$\texttt{anchor}({r})=\emptyset$ by definition.

Input : Input query $Q$, database instance $D$; join tree $\mathcal{T}$;
ranking function $\mathsf{rank}$.

Output : Priority Queues $\mathsf{PQ}$

1

2foreach  _$R_{i}\in\mathcal{T}$ in post order traversal_ do

3 foreach  _$t\in R_{i}$_ do

4 $u\leftarrow\pi_{\texttt{anchor}({R_{i}})}(t);$

5 if  _$\textnormal{{$\mathsf{PQ}$}}_{i}[u]$ does not exist_ then

$\textnormal{{$\mathsf{PQ}$}}_{i}[u]\leftarrow\emptyset;$ /* Initialize a
priority queue */

6

7 $L\leftarrow\emptyset$;

8 foreach  _$R_{j}$ is the child of $R_{i}$ _ do

9
$L.\textnormal{{{insert}}}(\textnormal{{$\mathsf{PQ}$}}_{j}[\pi_{\texttt{anchor}({R_{j}})}(u)].\textnormal{{{top()}}})$;

10 $\textnormal{{$\mathsf{PQ}$}}_{i}[u].\textnormal{{{insert}}}(\langle
t,L,\bot\rangle)$;

Algorithm 1 PreprocessAcyclic

Input : Input query $Q$, database instance $D$; join tree $\mathcal{T}$;
ranking function rank; Priority queues $\mathsf{PQ}$

Output : $Q(D)$ in ranked order

1

2

3procedure  _Enum(__)_

4 $\textnormal{{{last}}}\leftarrow\emptyset$;

5 while  _$\textnormal{{$\mathsf{PQ}$}}_{r}[\emptyset]\neq\emptyset$_ do

6
$o\leftarrow\textnormal{{$\mathsf{PQ}$}}_{r}[\emptyset].\textnormal{{{top()}}}$;

7 if  _is_equal(_$o,\textnormal{{{last}}}$_) $=$ false _ then

print $\mathsf{output}(o),\textnormal{{{last}}}\leftarrow o$;

/* new output */

8

9 Topdown $(o,r)$;

10

11procedure  _Topdown(_$c,$ $j$_) /* $c=\langle
t,[p_{1},\dots,p_{k}],\textnormal{{{next}}}\rangle$ */ _

12 $u\leftarrow\pi_{\texttt{anchor}({R_{j}})}(c.t)$;

13 if  _$c.\textnormal{{{next}}}=\bot$_ then

14 while  _true_ do

15
$\textnormal{{{temp}}}\leftarrow\textnormal{{{pop}}}(\textnormal{{$\mathsf{PQ}$}}_{j}[u])$;

16 foreach  _$R_{i}$ is a child of $R_{j}$ _ do

17 $p^{\prime}_{i}\leftarrow\textnormal{{{Topdown}}}(c.p_{i},i)$ ;

18 if  _$p_{i}^{\prime}\neq\bot$ _ then

19 $\textnormal{{$\mathsf{PQ}$}}_{j}[u].\textnormal{{{insert}}}(\langle
t,[c.p_{1},\dots,p_{i}^{\prime},\dots c.p_{k}],\bot\rangle)$

20 if  _$R_{j}$ is not the root_ then

21
$c.\textnormal{{{next}}}\leftarrow{\mathsf{addressof}}(\textnormal{{$\mathsf{PQ}$}}_{j}[u].\textnormal{{{top()}}})$;

22 if
_is_equal(_$\textnormal{{{temp}}},\textnormal{{$\mathsf{PQ}$}}_{j}[u].\textnormal{{{top()}}}$_)
= false _ then break;

23

24 return _$c.\textnormal{{{next}}}$_ ;

25

26procedure  _is_equal(_$c_{1},c_{2}$_)_

27 if  _rank(_$\mathsf{output}(c_{1})$_)$\neq$
rank(_$\mathsf{output}(c_{2})$_)_ then return false

28 foreach  _$A\in\mathbf{A}$_ do

29 if  _$\mathsf{output}(c_{1})[A] <\mathsf{output}(c_{2})[A]$_ then return
false

30

31 return true;

Algorithm 2 EnumAcyclic

(a) Data structure state after the preprocessing phase. Each memory location
has a cell and the partial score of the partial answer

(b) Data structure after one iteration of procedure Enum()

Figure 3. Example to demonstrate the preprocessing and enumeration phase of
the general algorithm

###### Example 0.

Continuing with the 4-path query running example, consider the following
instance $D$ as shown below.

${A}$ |  ${B}$
---|---
1 |  1
2 |  1
1 |  2
3 |  2
|

$R_{1}$

${B}$ |  ${C}$
---|---
1 |  1
2 |  1
|

$R_{2}$

${C}$ |  ${D}$
---|---
1 |  1
1 |  2
|

$R_{3}$

${D}$ |  ${E}$
---|---
1 |  1
1 |  2
|

$R_{4}$

As we saw before, Figure 1 shows the join tree along with the anchor
attributes in each relation. 3(a) shows the state of priority queues after the
preprocessing step. After the full reducer pass, tuple $(1,2)$ is removed from
$R_{3}$ because there is no join tuple that can be formed using it. Then, we
start constructing the cells for each node starting with the leaf nodes. Since
$B$ is the anchor for relation $R_{1}$, we create two priority queues
$\textsf{PQ}_{1}[1]$ and $\textsf{PQ}_{1}[2]$. For $\textsf{PQ}_{1}[1]$, we
create the cells for tuples $(1,1)$ and $(2,1)$. For convenience, the cells
are followed by the partially aggregated score. Consider relation
$R_{2}(B,C)$. The cell for tuple $(1,1)$ in $\textsf{PQ}_{2}[1]$ points to the
top of $\textsf{PQ}_{1}[1]$ (shown as pointer with address $100$). The root
bag consists of a single tuple entry which points to the cells at locations
$300$ and $400$. The output tuple that can be formed by the root bag is
$(A=1,E=1)$.

Enumeration Phase. We describe the enumeration procedure in Algorithm 2. The
high-level idea is to output answers by repeatedly popping elements from the
root priority queue. It may be possible that multiple tuples of the root
priority queue output the same final result. In order to deduplicate answers,
we compare the answer at the current top of the priority queue with the
previous answer (Algorithm 2), and output it only if they are different. Then,
we invoke the procedure Topdown to insert new candidates into the priority
queue. This procedure will be recursively propagated over the join tree until
it reaches the leaf nodes. Observe that once the new candidates have been
inserted, the next pointer of a cell is updated by pointing to the topmost
element in the priority queue. This chaining materializes the answers for a
particular node that can be reused and is key to avoiding repeated
computation.

###### Example 0.

Continuing our running example, 3(b) shows the state of the priority queues
after one complete iteration of procedure Enum(). We first pop the only
element in root priority queue and note that the output tuple $(A=1,E=1)$ is
enumerated. Then we call Topdown with cell at memory $500$ and root (node $3$)
as arguments (denoted as $\textsc{Topdown}(*500,3)$). The next for the cell is
$\bot$ so we pop the cell at $500$ from the priority queue (shown as greyed
out in the figure) and recursively call $\textsc{Topdown}(*300,2)$. The cell
at memory location $300$ has $\textsf{next}=\bot$. Therefore, we enter the
while loop, pop the cell and recursively call $\textsc{Topdown}(*100,1)$. We
have now reached the leaf node. The anchor attribute value for cell at $100$
is $u=1$, so we pop the current cell from $\textsf{PQ}_{1}[1]$ (greyed out
cell at $100$), find the next candidate at the top of $\textsf{PQ}_{1}[1]$
(which is cell at $101$), chain it to the cell at $100$ by assigning
$\textsf{next}=101$ and return the cell at $101$ to the parent. When the
program control returns from the recursive call back to node $2$, we create a
new cell (at memory address $302$) that points to $101$ and insert it into the
priority queue. However, observe that the cell at memory location $301$ also
generates $A=1$, a duplicate since cell at $300$ also generated it. This is
where the equality check at Algorithm 2 comes in. Since both cells at $300$
and $301$ generate the same value, we also pop off the cell at $301$ in the
subsequent while loop iteration, find its next candidate and create the cell
at $303$, and insert into the priority queue. This ensures that all elements
in $\textsf{PQ}_{2}[1]$ generating the same $A$ value are removed, ensuring no
duplicates at the root level. Finally, the control returns to the root level
Topdown call. The recursive call to the right child (node $4$) create a new
cell $401$ and we insert two cells at the root priority queue, cell $501$ and
$502$ that correspond to output tuple $(A=2,E=1)$ and $(A=1,E=2)$
respectively.

We are now ready to formally prove Theorem 2.

###### Lemma 0.

The delay guarantee of EnumAcyclic is at most $O(|D|\log|D|)$.

###### Lemma 0.

PreprocessAcyclic running in $O(|D|\log|D|)$ time, generates a data structure
of size $O(|D|)$.

###### Lemma 0.

EnumAcyclic enumerates the query result $Q(D)$ in ranked order correctly.

Together, the above lemmas establish Theorem 2. We defer the full proofs to
Appendix C. We also show how we can recover logarithmic delay guarantee for
full queries from (Tziavelis et al., 2020a; Deep and Koutris, 2021).

###  3.2. Improvement for Lexicographic Ranking

The algorithm from last section is also applicable to  LEXICOGRAPHIC ranking
function. In fact, we can transform  LEXICOGRAPHIC with an attribute ordering
of $A_{1},A_{2},\cdots,A_{m}$, into  SUM by defining a ranking function
$\textnormal{{{rank}}}(t)=\sum_{i=1}^{m}10^{m-i}\cdot w(\pi_{A_{i}}(t))$ for
tuple $t$, while preserving the  LEXICOGRAPHIC ordering. In this section, we
present an alternative algorithm by exploiting the special structural
properties of  LEXICOGRAPHIC, that the global ranking also implies local
ranking over every output attribute. Moreover, it admits to enumerate query
results not only in lexicographic order as given by  ORDER BY
$A_{1},A_{2},\cdots,A_{m}$ but also arbitrary ordering on each attribute (for
instance,  ORDER BY $A_{1}$ ASC, $A_{2}$ DESC $\dots$).

Preprocessing Phase. In this phase, we perform the full reducer pass to remove
all dangling tuples and create hash indexes for the base relations in sorted
order. We also sort $\mathbf{dom}(A_{i})$.

Enumeration Phase. Given an attribute order of output attributes
$\mathbf{A}=\\{A_{1},A_{2},\cdots,A_{m}\\}$, we start by fixing the minimum
value in $\mathbf{dom}(A_{1})$ as $a_{1}$. Then, we perform the two-phase
semi-joins to remove tuples that cannot be joined with value $a_{1}$, and find
the values in $\mathbf{dom}(A_{2})$ that survive after semi-joins, denoted as
$\mathcal{L}_{A_{2}}(a_{1})$. Similarly, we fix the minimum value in
$\mathcal{L}_{A_{2}}(a_{1})$ as $a_{2}$, and perform the two-phase semi-joins
for finding the values in $\mathbf{dom}(A_{3})$ that can be joined with both
$a_{1},a_{2}$. We continue this process until all attributes in $\mathbf{A}$
have been fixed, and end up with enumerating such a query result (with fixed
values). Then, we backtrack and continue the process until all values in
attribute $A_{1}$ are exhausted.

Input : Input query $Q$, database $D$

Output : $Q(D)\ltimes t$ in lexicographic order of $A_{i},\cdots,A_{m}$

1

2if  _$i=m$_ then output $t$ and return;

3 foreach  _$a\in\mathcal{L}$_ do

$\mathcal{L}^{\prime}\leftarrow\pi_{A_{i+1}}(\sigma_{A_{i}=a}(R_{i+1}\ltimes
t))$ ;

/* by semi-joins */

$t^{\prime}\leftarrow(t,a)$;

/* create new tuple */

4 EnumAcyclicLexi($t^{\prime},\mathcal{L}^{\prime},i+1$);

5

Algorithm 3 EnumAcyclicLexi($t$, $\mathcal{L}$, $i$)

Algorithm 3 takes as input an acyclic query $Q$, an database $D$, an integer
$i\in\\{1,\cdots,m\\}$, a tuple $t$ defined over attributes
$A_{1},\cdots,A_{i-1}$, and a set of values
$\mathcal{L}\subseteq\mathbf{dom}(A_{i})$ that can be joined with $t$ in $D$.
The original problem can be solved by invoking
$\textsc{EnumAcyclicLexi}(\emptyset,\mathbf{dom}(A_{1}),1)$ for sorted
$\mathbf{dom}(A_{1})$.

###### Lemma 0.

EnumAcyclicLexi enumerates $Q(D)$ correctly in lexicographic order with delay
guarantee $O(|D|)$ after preprocessing time $T_{p}=O(|D|\log|D|)$ and space
complexity $O(|D|)$.

##  4\. Star Queries

In this section, we present a specialized data structure for the star query,
which is represented as: $Q^{\star}_{m}=\pi_{\mathbf{A}}(R_{1}(A_{1},B)\Join
R(A_{2},B)\Join\dots\Join R_{m}(A_{m},B)).$ where
$\mathbf{A}=\\{A_{1},\cdots,A_{m}\\}$. All relations in a star query join on
exactly the same attribute(s). In this following, we present a specialized
data structure on ranked enumeration for $Q^{\star}_{m}$ in Section 4.1, and
prove the optimality in Section 4.2.

###  4.1. The Algorithm

Consider the star query $Q^{\star}_{m}$, a database $D$ and a ranking function
rank. Now we present a data structure for Theorem 3.

Input : Input star query $Q^{\star}_{m}$, ranking function $\mathsf{rank}$ and
database $D$; degree threshold $\delta\geq 1$

Output : Heavy output $\mathcal{O}^{H}$ and priority queue $\mathsf{PQ}$

1

2 foreach  _$i\in\\{1,2,\cdots,m\\}$_ do

3 $R^{H}_{i}\leftarrow\\{t\in
R_{i}:|\sigma_{A_{i}=\pi_{A_{i}}(t)}|\geq\delta\\}$;

4 $R^{L}_{i}\leftarrow\\{t\in
R_{i}:|\sigma_{A_{i}=\pi_{A_{i}}(t)}|<\delta\\}$;

5

6Compute
$\mathcal{O}^{H}\leftarrow\pi_{\mathbf{A}}\left(R^{H}_{1}\Join\dots\Join
R^{H}_{m}\right)$;

7 Sort $\mathcal{O}^{H}$ by rank;

8 for  _$i\in\\{0,1,\dots,m-1\\}$_ do

9 $Q_{i}\leftarrow R^{H}_{1}\Join\dots\Join R^{H}_{m-1}\Join R^{L}_{i}\Join
R_{i+1}\Join\dots\Join R_{m}$;

10 $\mathcal{T}_{i}\leftarrow$ a join tree for $Q$ with $R_{i}$ as root and
all other relations as children of $R_{i}$;

11 PreprocessAcyclic$(Q_{i},\mathcal{T}_{i})$;

12 $\textnormal{{{next}}}\leftarrow$EnumAcyclic$(Q_{i},\mathcal{T}_{i})$;

$\textnormal{{$\mathsf{PQ}$}}.\textnormal{{{insert}}}(\textnormal{{{next}}})$;
/* insert the smallest tuple into $\mathsf{PQ}$ */

13

Algorithm 4 PreprocessStar

Preprocessing Phase. Without loss of generality, assume that there is no
dangling tuples in $D$. Moreover, if $\mathbf{A}$ does not include an
attribute $A$, we can remove efficiently $R_{i}$ using a semi-join. We first
fix a degree threshold $\delta\geq 1$ (whose value will be determined later).
For each $i\in\\{1,2,\cdots,m\\}$, a value $a_{i}\in\mathbf{dom}(A)$ is
_heavy_ if it has degree larger than $\delta$ in $R_{i}$, i.e.,
$|\sigma_{A=a_{i}}(R_{i})|\geq\delta$, and _light_ otherwise. A tuple
$t=(a_{i},b)\in R_{i}$ is heavy if $a_{i}$ is heavy. For $R_{i}$, let
$R^{H}_{i},R^{L}_{i}$ be the set of heavy and light tuples in $R_{i}$. An
output $t=(a_{1},a_{2},\dots,a_{m})\in Q^{\star}_{m}(D)$ is _heavy_ if $a_{i}$
is heavy in $R_{i}$ for each $i\in\\{1,2,\cdots,m\\}$, and _light_ otherwise.
In this way, we can divide the output $Q^{\star}_{m}(D)$ into
$\mathcal{O}^{H}$ and $\mathcal{O}^{L}$, containing all heavy and light output
tuples separately. In the preprocessing phase, our goal is to materialize all
heavy output tuples ($\mathcal{O}^{H}$) ordered by rank. Details are described
in Algorithm 4. We compute
$\mathcal{O}^{H}=\pi_{\mathbf{A}}\left(R^{H}_{1}\Join
R^{H}_{2}\Join\cdots\Join R^{H}_{m}\right)$ by invoking the Yannakakis
algorithm (Yannakakis, 1981), and then sort $\mathcal{O}^{H}$ by rank. Next,
we insert the smallest query result from $\mathcal{O}^{H}$ into the priority
queue. Then, we define $m$ different subqueries as
$Q_{i}=\pi_{\mathbf{A}}\left(R^{H}_{1}\Join\dots\Join R^{H}_{i-1}\Join
R^{L}_{i}\Join R_{i+1}\Join\dots\Join R_{m}\right)$ where tuples in relation
$R_{j}$ are heavy for any $j<i$ and tuples in relation $R_{i}$ are light. For
such $Q_{i}$, we consider a join tree $\mathcal{T}_{i}$ in which $R_{i}$ is
the root and all other relations are children of $R_{i}$. We preprocess a data
structure for $Q_{i}$ with $\mathcal{T}_{i}$, by invoking Algorithm 1.

Enumeration Phase. As described in Algorithm 5, the high-level idea in the
enumeration is to perform a ($m+1$)-way merge over $\mathcal{O}^{H}$ and
$Q_{i}$’s. Specifically, we maintain a priority queue PQ with one entry for
each subquery $Q_{i}$ and one entry for $\mathcal{O}^{H}$. Once the smallest
element is extracted from PQ (say $t$ generated by $Q_{i}$), we extract the
next smallest candidate from $Q_{i}$ (if there is any) and insert it into PQ.
Moreover, finding the smallest candidate output result from $\mathcal{O}^{H}$
is trivial since $\mathcal{O}^{H}$ have been materialized in a sorted way in
the preprocessing phase. We conclude this subsection with the formal statement
of the result.

Input : Star query $Q^{\star}_{m}$, ranking function $\mathsf{rank}$ and
database $D$; Output of $\mathcal{O}^{H}$ and priority queue $\mathsf{PQ}$

Output : $Q^{\star}_{m}(D)$ in ranked order

1

2

3while  _$\textnormal{{$\mathsf{PQ}$}}\neq\emptyset$_ do

4 $t\leftarrow\textnormal{{$\mathsf{PQ}$}}.\textnormal{{{pop()}}}$;

output $t$;

/* enumerate the result */

5 if  _$t\notin\mathcal{O}^{H}$_ then

6 $i\leftarrow$ smallest positive index such that $\pi_{A_{j}}(t)$ is heavy
for all $j<i$ and $\pi_{A_{i}}(t)$ is light;

7 $\textnormal{{{next}}}\leftarrow$
$\textsc{EnumAcyclic}(Q_{i},\mathcal{T}_{i})$;

8
$\textnormal{{$\mathsf{PQ}$}}.\textnormal{{{insert}}}(\textnormal{{{next}}})$;

9

10 else
$\textnormal{{$\mathsf{PQ}$}}.\textnormal{{{insert}}}(\mathcal{O}^{H}.\textnormal{{{pop()}}})$;

11

Algorithm 5 EnumStar

###### Lemma 0.

Algorithm 4 runs in time $T=O(|D|\cdot(|D|/\delta)^{m-1})$ and requires space
$S=O((|D|/\delta)^{m})$. Algorithm 5 correctly enumerates the result of the
query in ranked order with delay $O(|D|\log|D|/\delta)$.

###  4.2. Tradeoff Optimality

We next present conditional optimality for our tradeoff achieved in Theorem 3.
Before showing the proof, we first revisit a result on unranked evaluation for
$Q^{\star}_{m}$ in (Amossen and Pagh, 2009):

###### Lemma 0 ((Amossen and Pagh, 2009)).

There exists a combinatorial111An algorithm is called combinatorial if it does
not use algebraic techniques such as fast matrix multiplication. algorithm
that can evaluate $Q^{\star}_{m}$ on any database $D$ in time
$O\left(|D|\cdot{|Q^{\star}_{m}(D)|}^{1-\frac{1}{m}}\right)$.

This result was presented over a decade ago without any improvement since
then. Thus, it is not unreasonable to conjecture that Lemma 2 is optimal.
Based on its conjectured optimality, we can show the following result for
unranked enumeration.

###### Lemma 0.

Consider star query $Q^{\star}_{m}$, database $D$ and some constant
$\epsilon\in[0,1]$. If there exists an algorithm that supports
$O(|D|^{1-\epsilon}\log|D|)$-delay enumeration after
$O(|D|^{1+(m-1)\epsilon-\epsilon^{\prime}})$ preprocessing time for some
constant $\epsilon^{\prime}>0$, the optimality of Lemma 2 will be broken.

The lower bound holds for any ranking function. Lemma 3 implies that for star
queries, both Theorem 2 and Theorem 3 are optimal. Before concluding this
section, we also remark on the question of whether the logarithmic factor that
we obtain in the delay guarantee is removable. Prior work (Deep and Koutris,
2021) showed that for the following simple join query $Q=R(x)\Join S(y)$ over
SUM, there exists no algorithm supporting constant-delay enumeration after
linear preprocessing time. Note that this does not rule out a sub-logarithmic
delay guarantee, which remains an open problem.

##  5\. General queries

In this section, we will describe how to extend the algorithm for acyclic
queries to handle cyclic queries. The key idea is to transform the cyclic
query into an acyclic one, by constructing a GHD as defined in Section 2. A
GHD automatically implies an algorithm for cyclic joins. After materializing
the results of the subquery induced by each node in the decomposition, the
residual query becomes acyclic. Hence, we can apply our algorithm for acyclic
queries directly obtaining the following:

###### Theorem 1.

For a join-project query $Q$, a database instance $D$ and a ranking function
$\textnormal{{{rank}}}\in\\{\textrm{{\color[rgb]{0.76953125,0.125,0.26171875}\definecolor[named]{pgfstrokecolor}{rgb}{0.76953125,0.125,0.26171875}
SUM}},\textrm{{\color[rgb]{0.76953125,0.125,0.26171875}\definecolor[named]{pgfstrokecolor}{rgb}{0.76953125,0.125,0.26171875}
LEXICOGRAPHIC}}\\}$, the query results $Q(D)$ can be enumerated according to
rank with $O(|D|^{\texttt{fhw}}\log|D|)$ delay, after
$O(|D|^{\texttt{fhw}}\log|D|)$ preprocessing time.

We now go one step further and extend our algorithm to queries that are unions
of join-project queries (UCQs) using an idea introduced by (Deep and Koutris,
2021; Tziavelis et al., 2020a). A UCQ query is of the form $Q=Q_{1}\cup
Q_{2}\cup\cdots\cup Q_{m}$, where each $Q_{i}$ is a join-project query defined
over the same projection attributes $\mathbf{A}$. Semantically,
$Q(D)=\bigcup_{i}Q_{i}(D)$. Recent work by Abo Khamis et al. (Abo Khamis et
al., 2017) presents an improved algorithm (called PANDA) that constructs
multiple GHDs by partitioning the input database into disjoint pieces and
build a GHD for each piece. In this way, the size of materialized subquery can
be bounded by $O(|D|^{\texttt{subw}})$, where subw is the _submodular width_
(Marx, 2013) of input query $Q$. Moreover, $\texttt{subw}\leq\texttt{fhw}$
holds generally for query $Q$, thus improving the previous result on fhw. By
using Theorem 2 in conjunction with data-dependent decompositions from PANDA
we can immediately obtain the following result:

###### Theorem 2.

For a join-project query $Q$, a database instance $D$ and a ranking function
$\textnormal{{{rank}}}\in\\{\textrm{{\color[rgb]{0.76953125,0.125,0.26171875}\definecolor[named]{pgfstrokecolor}{rgb}{0.76953125,0.125,0.26171875}
SUM}},\textrm{{\color[rgb]{0.76953125,0.125,0.26171875}\definecolor[named]{pgfstrokecolor}{rgb}{0.76953125,0.125,0.26171875}
LEXICOGRAPHIC}}\\}$, the query results $Q(D)$ can be enumerated according to
rank with $O(|D|^{\texttt{subw}}\log|D|)$ delay, after
$O(|D|^{\texttt{subw}}\log|D|)$ preprocessing time.

###### Example 0.

Consider the 4-cycle (butterfly) query $\pi_{A,C}(R_{1}(A,B)\Join
R_{2}(B,C)\Join R_{3}(C,D)\Join R_{4}(D,A))$ with ranking function
$\textnormal{{{rank}}}(t)=\pi_{A}(t)+\pi_{C}(t)$. With $\texttt{fhw}=2$,
Theorem 2 implies that the query results can be enumerated according to rank
with $O(|D|^{2}\log|D|)$ delay, after $O(|D|^{2})$ preprocessing time. With
$\texttt{subw}=\frac{3}{2}$, Theorem 2 implies that query results can be
enumerated according to rank with delay $O(|D|^{3/2}\log|D|)$, after
$O(|D|^{3/2}\log|D|)$ preprocessing time.

A note on optimality. The reader may wonder whether the exponent of fhw and
subw in Theorem 1 and Theorem 2 are truly necessary. For the triangle query
$Q_{\triangle}(x,y)=R(x,y)\Join S(y,z)\Join T(z,x)$ which is the simplest
cyclic query, $\texttt{fhw}=\texttt{subw}=3/2$ and even after $30$ years, the
original AYZ algorithm (Alon et al., 1994) that detects the existence of a
triangle in $O(|D|^{3/2})$ time still remains the best known combinatorial
algorithm. It is widely conjectured (Marx, 2021; Abboud and Williams, 2014;
Abboud et al., 2018b; Kopelowitz et al., 2016) that there exists no better
algorithm. As noted in (Abo Khamis et al., 2017), the notion of submodular
width was suggested as the yardstick for optimality. Indeed, the
groundbreaking results by Marx (Marx, 2013) rules out algorithms with better
dependence than subw in the exponent for a small of class of queries but a
general unconditional lower bound still remains out of reach. Thus, any
improvement in the exponent would automatically imply a better algorithm for
cycle detection since ranked enumeration is at least as hard. In Appendix F,
we formally show that the exponential dependence of subw in Theorem 2 is
unavoidable subject to popular conjectures.

##  6\. Experimental Evaluation

⬇

$\mathsf{DBLP}_{2\mathsf{hop}}$ = SELECT DISTINCT
$\mathsf{A}_{1}.\mathsf{name},\mathsf{A}_{2}.\mathsf{name}$ FROM
$\mathsf{Author}$ AS $\mathsf{A_{1}}$, $\mathsf{Author}$ AS $\mathsf{A_{2}}$,
$\mathsf{AuthorPapers}$ AS $\mathsf{AP}_{1}$, $\mathsf{AuthorPapers}$ as
$\mathsf{AP_{2}}$, $\mathsf{Paper}$ AS $\mathsf{P}$ WHERE
$\mathsf{AP_{1}.pid}=\mathsf{AP_{2}.pid}$ AND
$\mathsf{AP_{1}.aid}=\mathsf{A_{1}.aid}$ AND
$\mathsf{AP_{2}.aid}=\mathsf{A_{2}.aid}$ AND $\mathsf{P.is\\_research}=$true
ORDER BY $\mathsf{A}_{1}.\mathsf{weight}+\mathsf{A}_{2}.\mathsf{weight}$ LIMIT
k;

$\mathsf{DBLP}_{3\mathsf{hop}}$ = SELECT DISTINCT
$\mathsf{A}.\mathsf{name},\mathsf{P}.\mathsf{name}$ FROM $\mathsf{Author}$ AS
$\mathsf{A}$, $\mathsf{Paper}$ AS $\mathsf{P}$, $\mathsf{AuthorPapers}$ AS
$\mathsf{AP}_{1}$, $\mathsf{AuthorPapers}$ as $\mathsf{AP_{2}}$,
$\mathsf{AuthorPapers}$ as $\mathsf{AP_{3}}$ WHERE
$\mathsf{AP_{1}.pid}=\mathsf{AP_{2}.pid}$ AND
$\mathsf{AP_{2}.aid}=\mathsf{AP_{3}.aid}$ AND
$\mathsf{AP_{1}.aid}=\mathsf{A.aid}$ AND $\mathsf{AP_{3}.pid}=\mathsf{P.pid}$
AND $\mathsf{P.is\\_research}=$true ORDER BY
$\mathsf{A}.\mathsf{weight}+\mathsf{P}.\mathsf{weight}$ LIMIT k;

$\mathsf{DBLP}_{4\mathsf{hop}}$ = SELECT DISTINCT
$\mathsf{A}_{1}.\mathsf{name},\mathsf{A}_{2}.\mathsf{name}$ FROM
$\mathsf{Author}$ AS $\mathsf{A_{1}}$, $\mathsf{Author}$ AS $\mathsf{A_{2}}$,
$\mathsf{AuthorPapers}$ AS $\mathsf{AP}_{1}$, $\mathsf{AuthorPapers}$ as
$\mathsf{AP_{2}}$, $\mathsf{AuthorPapers}$ as $\mathsf{AP_{3}}$,
$\mathsf{AuthorPapers}$ as $\mathsf{AP_{4}}$, $\mathsf{Paper}$ AS
$\mathsf{P_{1}}$, $\mathsf{Paper}$ AS $\mathsf{P_{2}}$ WHERE
$\mathsf{AP_{1}.pid}=\mathsf{AP_{2}.pid}$ AND
$\mathsf{AP_{2}.aid}=\mathsf{AP_{3}.aid}$ AND
$\mathsf{AP_{3}.pid}=\mathsf{AP_{4}.pid}$ AND
$\mathsf{AP_{3}.pid}=\mathsf{P_{2}.pid}$ AND
$\mathsf{AP_{1}.pid}=\mathsf{P_{1}.pid}$ AND
$\mathsf{AP_{1}.aid}=\mathsf{A_{1}.aid}$ AND
$\mathsf{AP_{4}.aid}=\mathsf{A_{2}.aid}$ AND
$\mathsf{P_{1}.is\\_research}=$true AND $\mathsf{P_{2}.is\\_research}=$true
ORDER BY $\mathsf{A}_{1}.\mathsf{weight}+\mathsf{A}2.\mathsf{weight}$ LIMIT k;

$\mathsf{DBLP}_{3\mathsf{star}}$ = SELECT DISTINCT
$\mathsf{A}_{1}.\mathsf{name},\mathsf{A}_{2}.\mathsf{name},\mathsf{A}_{3}.\mathsf{name}$
FROM $\mathsf{Author}$ AS $\mathsf{A_{1}}$, $\mathsf{Author}$ AS
$\mathsf{A_{2}}$, $\mathsf{Author}$ AS $\mathsf{A_{3}}$,
$\mathsf{AuthorPapers}$ AS $\mathsf{AP}_{1}$, $\mathsf{AuthorPapers}$ as
$\mathsf{AP_{2}}$, $\mathsf{AuthorPapers}$ as $\mathsf{AP_{3}}$,
$\mathsf{Paper}$ AS $\mathsf{P}$ WHERE
$\mathsf{AP_{1}.pid}=\mathsf{AP_{2}.pid}=\mathsf{AP_{3}.pid}$ AND
$\mathsf{AP_{1}.aid}=\mathsf{A_{1}.aid}$ AND
$\mathsf{AP_{2}.aid}=\mathsf{A_{2}.aid}$ AND
$\mathsf{AP_{3}.aid}=\mathsf{A_{3}.aid}$ AND
$\mathsf{AP_{3}.pid}=\mathsf{P.pid}$ AND $\mathsf{P.is\\_research}=$true ORDER
BY
$\mathsf{A}_{1}.\mathsf{weight}+\mathsf{A}_{2}.\mathsf{weight}+\mathsf{A}_{3}.\mathsf{weight}$
LIMIT k;

Figure 4. Network analysis queries for DBLP. Queries for IMDB are defined
similarly (see (Deep et al., 2022)).

In this section, we perform an extensive evaluation of our proposed algorithm.
Our goal is to evaluate three aspects: $(a)$ how fast our algorithm is
compared to state-of-the-art implementations for both  SUM and  LEXICOGRAPHIC
ranking functions on various queries and datasets, $(b)$ test the empirical
performance of the space-time tradeoff in Theorem 3, $(c)$ investigate the
performance of our algorithm on various cyclic queries based on different
shapes and $(d)$ test the scalability behavior of our algorithm.

###  6.1. Experimental Setup

We use Neo4j $4.2.3$ community edition, MariaDB $10.1.47$222Compared with
MySQL, MariaDB performed better in our experiments, hence we report the
results for MariaDB and PostgreSQL $11.12$ for our experiments. All
experiments are performed on a Cloudlab machine (Duplyakin et al., 2019)
running Ubuntu $18.04$ equipped with two Intel E5-2630 v3 8-core<EMAIL_ADDRESS>GHz and $128$ GB RAM. We focus only on the main memory setting and all
experiments run on a single core. Since the join queries are memory intensive,
we take special care to ensure that only one DBMS engine is running at a time,
restart the session for each query to ensure temp tables in main memory are
flushed out to avoid any interference, and also monitor that no temp tables
are created on the disk. We only keep one database containing a single
relation when performing experiments. We switch off all logging to avoid any
performance impact. For PostgreSQL and MariaDB, we allow the engines to use
the full main memory to ensure all temp tables are resident in the RAM and
sorting (if any) happens without any disk IOs by increasing the sort buffer
limit. For Neo4j, we allow the JVM heap to use the full main memory at the
time of start up. We also build bidirectional B-tree indexes for each relation
ahead of time and create named indexes in Neo4j. All of our algorithms are
implemented in C++ and compiled using the GNU C++ $7.5.0$ compiler that ships
with Ubuntu $18.04$. Each experiment is run $5$ times and we report the median
after removing the slowest and the fastest run.

####  6.1.1. Small-Scale Datasets

We use two real world small scale datasets for our experiments: the DBLP
dataset, containing relationship between authors and papers, and the IMDB
dataset, containing relationship between actors, directors, and movies. We use
these datasets for two reasons: $(i)$ both datasets have been found to be
useful and studied extensively in practical problems such as similarity search
(Yu et al., 2012), citation graph analysis (Rahm and Thor, 2005), and network
analysis (Elmacioglu and Lee, 2005; Biryukov, 2008). $(ii)$ small-scale
datasets allow experiments to finish for all systems allowing us to make a
fair comparison and develop a fine-grained understanding. In line with prior
work (Kargar et al., 2020), for each tuple we assign the weight attribute (and
add it to the table schema) in two ways: first, we assign a randomly chosen
value, and second, logarithmic weights in which the weight of the entity
(author and paper in DBLP) $v$ is $\log_{2}(1+deg_{v})$, where $deg_{v}$
denotes its degree in the relation. The schema for both datasets is as shown
below (underlined attributes are primary keys for the relation):

DBLP: AuthorPapers$(aid,pid)$, Author$(\underline{aid},name,weight)$,

Paper$(\underline{aid},title,venue,year,weight,is\\_research)$.

IMDB: PersonMovie$(pid,mid)$, Company$(\underline{cid},name,nation)$,

Person$(\underline{pid},name,role,weight)$,

Movie$(\underline{mid},name,year,genre,cid,weight)$

Queries. We consider $4$ acyclic join queries as shown in Figure 4 for the
small-scale datasets, which are commonly seen in practice (Sun and Han, 2013;
Bonifati et al., 2020). Intuitively, the first three queries find all the
top-k weighted 2-hops, 3-hops and 4-hops reachable attribute pairs within the
DBLP network. As remarked by in (Sun and Han, 2013; Chen et al., 2018;
Küçüktunç et al., 2012), these queries are of immense practical interest
(e.g., see Table 4 in (Sun and Han, 2013)). Queries for IMDB dataset are
defined similarly in Appendix G. In Subsection 6.2.2, we also investigate the
performance for cyclic queries.

####  6.1.2. Large-Scale Datasets

We also perform experiments on two real-world large scale relational datasets
and one relational benchmark. The first dataset is from the Friendster
(Leskovec and Krevl, 2014) online social network that contains $1.8B$ tuples.
In the social network each, user is associated with multiple groups. The
second dataset is the Memetracker (Leskovec and Krevl, 2014) dataset which
describes user generated memes and which users have interacted with the meme.
The dataset contains $418M$ tuples. For both Friendster and Memetracker, we
use weights for users as the number of groups they belong to and the number of
memes they create respectively. Finally, we also use the queries containing a
ranking function from the LDBC Social Network Benchmark (Erling et al., 2015)
with scale factor $\mathsf{SF=10}$, a publicly available benchmark, to perform
scalability experiments.

Queries. For Friendster and Memetracker, we use two popular queries that are
used in network analysis. Similar to the DBLP queries, we identify the ranked
user pairs in the two hop and three hop neighborhoods for all users. The
ranking is the sum of weights of the user pair. These queries have widespread
application in understanding information flow in a network (Myers et al.,
2014) and are used in recommendation systems (Feng et al., 2019; Li et al.,
2019). For LDBC benchmark, we use the multi-source version of Q3, Q10 and Q11.
Each of these queries are variants of the neighborhood analysis and contains
UNION.

###  6.2. Small Scale Experiments

In this section, we compare the empirical performance of the algorithm given
by Theorem 2 (labeled as LinDelay in all figures) against the baselines for
each query. In order to perform a fair comparison, we materialize the top-$k$
answers in-memory since other engines also do it. However, a strength of our
system is that if a downstream task only requires the output as a stream, we
are able to enumerate the result instead of materializing it, which is not
possible with other engines.

Sum ordering. Figure 5 shows the main results for the DBLP and IMDB datasets
when the ranking function is the sum function and the weights are chosen
randomly. Let us first review the results for the DBLP dataset. 5(a) shows the
running time for different values of $k$ in the limit clause. The first
observation is that all engines materialize the join result, followed by
deduplicating and sorting according to the ranking function which leads to
poor performance for all baselines. This is because all engines treat sorting
and distinct clause as blocking operators, verified by examining the query
plan. On the other hand, our approach is limit-aware. For small values of $k$,
we are up to two orders of magnitude faster and as the value of $k$ increases,
the total running time of our algorithm increases linearly. Even when our
algorithm has to enumerate and materialize the entire result, it is still
faster than asking the engines for the top-$10$ results. This is a direct
benefit of generating the output in deduplicated and ranked order. As the path
length increases from two to three and four path (5(b) and 5(c)), the
performance gap between existing engines and our approach also becomes larger.
We also point out that all engines require a large amount of main memory for
query execution. For example, MariaDB requires about $40$GB of memory for
executing $\mathsf{DBLP}_{4\mathsf{hop}}$. In contrast, the space overhead of
our algorithm is dominated by the size of the priority queue. For DBLP
dataset, our approach requires a measly $1.3$GB, $4$GB, $3$GB and $2.7$GB
total space for
$\mathsf{DBLP}_{2\mathsf{hop}},\mathsf{DBLP}_{3\mathsf{hop}},\mathsf{DBLP}_{4\mathsf{hop}}$
and $\mathsf{DBLP}_{3\mathsf{star}}$ respectively. For
$\mathsf{DBLP}_{3\mathsf{hop}},\mathsf{DBLP}_{4\mathsf{hop}}$ and
$\mathsf{DBLP}_{3\mathsf{star}}$, we also implement breadth first search (BFS)
followed by a sorting step using the idea of Algorithm 3. As it can be seen
from the figures, BFS and sort provides an intermediate strategy which is
faster than our algorithm for large values of $k$ but at the cost of expensive
materialization of the entire result, which may not be always possible (and is
the case for IMDB dataset). However, deciding to use BFS and sort requires
knowledge of the output result size, which is unknown apriori and difficult to
estimate. For the IMDB dataset, we observe a similar trend of our algorithm
displaying superior performance compared to all other baselines. In this case,
BFS and sorting even for $\mathsf{DBLP}_{4\mathsf{hop}}$ is not possible since
the result is almost $0.5$ trillion items. For
$\mathsf{DBLP}_{3\mathsf{star}}$, none of the engines were able to compute the
result after running for $5$ hours when main memory ran out. BFS and sort also
failed due to the size being larger than the main memory limit. Lastly, Neo4j
was consistently the best performing (albeit marginally) engine among all
baselines. While there is little scope for rewriting the SQL queries to try to
obtain better performance, Neo4j has graph-specific operators such as variable
length expansion. We tested multiple rewritings of the query to obtain the
best performance (although this is the job of the query optimizer), which is
finally reported in the figures. Regardless of the rewritings, Neo4j still
treats materializing and sorting as a blocking operator which is a fundamental
bottleneck.

Lexicographic ordering. Figures 6(a),6(b),6(c) and 6(d) show the running time
for different values of $k$ in the limit clause for lexicographic ranking
function on DBLP (i.e. we replace
$\mathsf{A}_{1}.\mathsf{weight}+\mathsf{A}_{2}.\mathsf{weight}$ with
$\mathsf{A}_{1}.\mathsf{weight},\mathsf{A}_{2}.\mathsf{weight}$ in the  ORDER
BY clause) for random weights. The first striking observation here is that the
running time for all baseline engines is identical to that of sum function.
This demonstrates that existing engines are also agnostic to the ranking
function in the query and fail to take advantage of the additional structure.
However, lexicographic functions are easier to handle in practice than sum
because we can avoid the use of a priority queue altogether. This in turn
leads to faster running time since push and pops from the priority queue are
expensive due to the logarithmic overhead and need for re-balancing of the
tree structure. Thus, we obtain a $2\times$ improvement for lexicographic
ordering as compared to the sum function.

Join ordering. At this point, the reader may wonder what is the impact of
different join orderings on the query execution time for DBMS engines in the
presence of  ORDER BY. To investigate this, we supply join order hints to each
of the engines. We run the queries on all possible join order hints to find
the best possible running time. We found that the join order hints had
virtually no impact on execution time. For instance,
$\mathsf{DBLP}_{4\mathsf{hop}}$ on Neo4J takes $5521.61s$ without any join
hints and the best possible join ordering reduces the time to $5418.23s$, a
mere $1.8\%$ reduction. This is not surprising since the bottleneck for all
engines is the materialization of the unsorted output, which is orders of
magnitude larger than the final output and ends up being the dominant cost. In
fact, for queries containing only self-joins, join order hints do not have any
impact on the query plan because all relations are identical. Further, the
number of possible join orderings that may need to be explored is exponential
in the number of relations. On the other hand, our algorithm has the advantage
of bypassing the materialization due to the delay based problem formulation
and use of multi-way joins.

Logarithmic weights. Instead of choosing the weights randomly, we also
investigate the behavior when the weights scale logarithmically w.r.t. to the
degree. We observed that all systems as well as our algorithm had identical
execution times. This is not surprising considering that no algorithm takes
into account the actual distribution of the weights. This observation points
to an additional opportunity for optimization where one could use the weight
distribution to allow for fine-grained, data-dependent processing. We leave
the study of this problem for future work.

(a) $\mathsf{DBLP}_{2\mathsf{hop}}$

(b) $\mathsf{DBLP}_{3\mathsf{hop}}$

(c) $\mathsf{DBLP}_{4\mathsf{hop}}$

(d) $\mathsf{DBLP}_{3\mathsf{star}}$

(e) $\mathsf{IMDB}_{2\mathsf{hop}}$

(f) $\mathsf{IMDB}_{3\mathsf{hop}}$

(g) $\mathsf{IMDB}_{4\mathsf{hop}}$

(h) $\mathsf{IMDB}_{3\mathsf{star}}$

Figure 5. Comparing our algorithm with state-of-the-art engines for sum
function

(a) $\mathsf{DBLP}_{2\mathsf{hop}}$

(b) $\mathsf{DBLP}_{3\mathsf{hop}}$

(c) $\mathsf{DBLP}_{4\mathsf{hop}}$

(d) $\mathsf{DBLP}_{3\mathsf{star}}$

Figure 6. Comparing our linear delay algorithm with state-of-the-art engines
for lexicographic function.

####  6.2.1. Enumeration with Preprocessing

We next investigate the empirical performance of the preprocessing step and
its impact on the result enumeration as described by Theorem 3. For all
experiments in this section, we fix $k$ to be large enough to enumerate the
entire result (which is equivalent to having no limit clause at all).

Sum ordering. 7(a) and 7(b) show the tradeoff between space used by the data
structure constructed in the preprocessing phase and running time of the
enumeration algorithm for $\mathsf{DBLP}_{2\mathsf{hop}}$ and
$\mathsf{IMDB}_{2\mathsf{hop}}$ repectively. We show the tradeoff for $6$
different space budgets but the user is free to choose any space budget in the
entire spectrum. As expected, the time required to enumerate the result is
large when there is no preprocessing and it gradually drops as more and more
results are materialized in the preprocessing phase. The sum of preprocessing
time and enumeration time is not a flat line: this is because as an
optimization, we do not use priority queues in the preprocessing phase.
Instead, we can simply use the BFS and sort algorithm for all chosen nodes
which need to be materialized. This is a faster approach in practice as we
avoid use of priority queues but priority queues cannot be avoided for
enumeration phase. We observe similar trend for
$\mathsf{DBLP}_{3\mathsf{star}},\mathsf{IMDB}_{3\mathsf{star}}$ on both
datasets as well.

(a) $\mathsf{DBLP}_{2\mathsf{hop}}$

(b) $\mathsf{IMDB}_{2\mathsf{hop}}$

(c) $\mathsf{DBLP}_{3\mathsf{star}}$

(d) $\mathsf{IMDB}_{3\mathsf{star}}$

Figure 7. Comparing the preprocessing and enumeration tradeoff for sum
function when enumerating the entire result

####  6.2.2. Cyclic Queries

We also compare the performance of our algorithm to other systems for cyclic
queries. We choose four cyclic queries found commonly in practice inspired by
(Tziavelis et al., 2020a): four cycle, six cycle, eight cycle and bowtie query
(two four cycles joined at a common attribute). Figure 10 shows the
performance of our algorithm on the DBLP dataset for the sum function. As the
table shows, our algorithm is able to process all queries within $200$
seconds, with the bowtie query being the most computationally intensive. In
contrast, for $k=10$ the fastest performing engine Neo4J required 240s (450s)
for four cycle (six cycle). It did not finish execution for eight cycle and
bowtie query due to an out of memory error. For the IMDB dataset, our
algorithm was able to process all queries, while Neo4J was not able to process
any query (except four cycle) due to its large memory requirement. We defer
those experiments to Appendix G.

###  6.3. Large Scale Experiments and Scalability

In this section, we investigate the performance of our techniques on the large
scale datasets. 8(a) and 8(b) shows the time to find the top-$k$ answers for
the Memetracker dataset on two neighborhood and three neighborhood queries.
Compared to the small scale datasets, the execution time increases rapidly
even for low values of $k$. This is attributed to the high duplication of
answers, which leads to a rapidly increasing priority queue size. None of
MariaDB, Postgres and Neo4J were able to finish, or even to find the top-$10$
answers, within $5$ hours in our experiments. The same trend is also observed
for the Friendster dataset as shown in 8(d) and 8(c). Similar to the small-
scale datasets, lexicographic functions were faster than the sum function for
our algorithm but DBMS engines were unable to finish query execution. We also
conduct scalability experiments on LDBC benchmark queries that contain the
ORDER BY clause. Figure 9 shows the scalability of our algorithm for finding
answers of queries Q3, Q10, Q11. As the scale factor increases, the execution
time also increases linearly. For each of these queries, all engines require
more than $3$ hours to compute the result even for SF $=10$ and $k=10$. This
is because of the serial execution plan generated by the engines, forcing the
materialization of the unsorted result before sorting and filtering for
top-$k$.

(a) Memetracker 2-neighborhood

(b) Memetracker 3-neighborhood

(c) Friendster 2-neighborhood

(d) Friendster 3-neighborhood

Figure 8. LinDelay performance on large-scale datasets

| $\mathsf{SF}=10$ | $\mathsf{SF}=20$ | $\mathsf{SF}=30$ | $\mathsf{SF}=40$ | $\mathsf{SF}=40$
---|---|---|---|---|---
Q3 | 5.91s | 9.63s | 13.47s | 18.23s | 22.18s
Q10 | 2.82s | 3.47s | 4.65s | 5.23s | 6.46s
Q11 | 0.78s | 1.07s | 1.56s | 1.82s | 2.36s

Figure 9. Scalability for different scale factors (SF) in LDBC

| $\mathsf{k}=10$ | $\mathsf{k}=10^{2}$ | $\mathsf{k}=10^{3}$ | $\mathsf{k}=10^{4}$
---|---|---|---|---
four cycle | 0.85s | 0.95s | 1.2s | 1.8s
six cycle | 13.1s | 17.7s | 25.6s | 38.2s
eight cycle | 33.4s | 48.7s | 63.9s | 77.8s
bowtie | 112s | 125s | 156s | 192s

Figure 10. Cyclic query performance on the DBLP dataset for different values
of $k$ in the  LIMIT clause.

##  7\. Related Work

Top-$k$. Top-k ranked enumeration of full join queries has been studied
extensively by the database community for both certain (Li et al., 2005a; Qi
et al., 2007; Ilyas et al., 2004; Li et al., 2005b; Akbarinia et al., 2011;
Ilyas et al., 2008; Bast et al., 2006; Tsaparas et al., 2003) and uncertain
databases (Re et al., 2007; Zou et al., 2010). 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 (Ilyas et al., 2008) for a comprehensive survey. We note that none of these
works consider non-trivial join-project queries (see Appendix A for more
discussion). Ours is the first work to consider the ranked enumeration of
arbitrary join-project queries.

Rank aggregation algorithms. Top-k processing over ranked lists of objects has
a rich history. The problem was first studied by Fagin et al. (Fagin, 2002;
Fagin et al., 2003) 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-$k$ results for coordinate monotone functions. The authors proposed
Fagin’s algorithm (FA) and Threshold algorithm (TA), both of which were shown
to be instance optimal for database access cost under sorted list access and
random access model. A key limitation of these works is that it expects the
input to be materialized, i.e., $Q(D)$ must already be computed and stored for
the algorithm to perform random access.

Unranked enumeration of query results. Recent work by Kara et al. (Kara et
al., 2020) showed that for a small but important fragment of CQs known as
hierarchical queries, it is possible to obtain a tradeoff between
preprocessing and delay guarantees. Importantly, this result is applicable
even in the presence of arbitrary projection. However, the authors did not
investigate how to add ranking because adding priority queues at different
location in the join tree leads to different complexities. In fact, follow up
work (Deep et al., 2021) showed that the same unranked enumeration could be
performed with better delay guarantees under certain settings. Our work
considers the class of CQs with arbitrary projections and we are also able to
extend the main result to UCQs, an even broader class of queries. Naturally,
our algorithm automatically recovers the existing results for full CQs as well
(Deep and Koutris, 2021; Tziavelis et al., 2020a), in addition to the first
extensive empirical evidence on how ranked enumeration can be performed for
CQs containing projections beyond free-connex queries.

Factorization and Aggregation. Factorized databases (Bakibayev et al., 2012;
Olteanu and Závodnỳ, 2015; Ciucanu and Olteanu, 2015) exploit the
distributivity of product over union to represent query results compactly and
generalize the results on bounded fhwto the non-Boolean case (Olteanu and
Závodnỳ, 2015). (Abo Khamis et al., 2016) captures a wide range of aggregation
problems over semirings. Factorized representations can also enumerate the
query results with constant delay according to lexicographic orders of the
variables (Bakibayev et al., 2013). For that to work, the lexicographic order
must ”agree” with the factorization order. However, it was shown in (Deep and
Koutris, 2021) that the algorithm for lexicographic ordering is not optimal.
Further, since all prior work in this space using the concept of variable
ordering, adding projections to the query forces the building of a GHD that
can materialize the entire join query result, which is expensive and an
unavoidable drawback.

Ranked enumeration. Both Chang et al. (Chang et al., 2015) and Yang et al.
(Yang et al., 2018) provide any-$k$ algorithms for _graph queries_ instead of
the more general CQs; Kimelfeld and Sagiv (Kimelfeld and Sagiv, 2006) give an
any-$k$ algorithm for acyclic queries with polynomial delay. Recent work on
ranked enumeration of MSO logic over words is also of particular interest
(Bourhis et al., 2021). None of these existing works give any non-trivial
guarantees for CQs with projections. Ours is the first work in this space that
provides non-trivial guarantees.

##  8\. Conclusion

In this paper, we study the problem of ranked enumeration for CQs with
projections. We present a general algorithm that can enumerate query results
according to two commonly-used ranking functions ( SUM,  LEXICOGRAPHIC) with
near-linear delay after near-linear preprocessing time. We also show how to
extend our results to a broader class of queries known as UCQs. For star
queries, an important and practical fragment of CQs, we further show how to
achieve a smooth tradeoff between the delay, preprocessing time and space used
for data structure. Extensive experiments demonstrate that our methods are up
to three orders of magnitude better when compared to popular open-source RDBMS
and specialized graph engines. This work opens up several exciting future work
challenges. The first important problem is to extend our results from main
memory setting to the distributed setting. Since the cost of I/O must also be
taken into account, it becomes important to identify the optimal priority
queue storage layout to ensure that access cost is low. It would also be
interesting to develop output balanced algorithms. The second exciting
challenge is to incorporate approximation into the ranking. For some
applications, it may be sufficient to get an approximately ordered output
which could lead to improved running time guarantees. Finally, it would be
useful to re-rank the query results when the ranking function is changed by
the user and extend our ideas to non-monotone ranking functions.

Acknowledgments. This research was supported in part by National Science
Foundation grants CRII-1850348 and III-1910014. We would like to thank the
anonymous reviewers for their careful reading and valuable comments that
contributed greatly in improving the manuscript. We also thank Wim Martens for
the reference (Bonifati et al., 2020) that motivates the study of star
queries.

## References

  * (1)
  * Abboud et al. (2018a) Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. 2018a.  If the current clique algorithms are optimal, so is Valiant’s parser.  _SIAM J. Comput._ 47, 6 (2018), 2527–2555.
  * Abboud and Williams (2014) Amir Abboud and Virginia Vassilevska Williams. 2014\.  Popular conjectures imply strong lower bounds for dynamic problems. In _2014 IEEE 55th Annual Symposium on Foundations of Computer Science_. IEEE, 434–443.
  * Abboud et al. (2018b) Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. 2018b.  Matching triangles and basing hardness on an extremely popular conjecture.  _SIAM J. Comput._ 47, 3 (2018), 1098–1122.
  * Abo Khamis et al. (2016) Mahmoud Abo Khamis, Hung Q Ngo, and Atri Rudra. 2016.  FAQ: questions asked frequently. In _Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems_. 13–28.
  * Abo Khamis et al. (2017) Mahmoud Abo Khamis, Hung Q Ngo, and Dan Suciu. 2017.  What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?. In _Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems_. 429–444.
  * Akbarinia et al. (2011) Reza Akbarinia, Esther Pacitti, and Patrick Valduriez. 2011\.  Best position algorithms for efficient top-k query processing.  _Information Systems_ 36, 6 (2011), 973–989.
  * Alon et al. (1994) Noga Alon, Raphael Yuster, and Uri Zwick. 1994.  Finding and counting given length cycles. In _European Symposium on Algorithms_. Springer, 354–364.
  * Amossen and Pagh (2009) Rasmus Resen Amossen and Rasmus Pagh. 2009.  Faster join-projects and sparse matrix multiplications. In _Proceedings of the 12th International Conference on Database Theory_. ACM, 121–126.
  * Angles and Gutierrez (2011) Renzo Angles and Claudio Gutierrez. 2011.  Subqueries in SPARQL.  _AMW_ 749 (2011), 12.
  * Bagan et al. (2007) Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. 2007\.  On acyclic conjunctive queries and constant delay enumeration. In _International Workshop on Computer Science Logic_. Springer, 208–222.
  * Bakibayev et al. (2013) Nurzhan Bakibayev, Tomáš Kočiskỳ, Dan Olteanu, and Jakub Závodnỳ. 2013\.  Aggregation and ordering in factorised databases.  _Proceedings of the VLDB Endowment_ 6, 14 (2013), 1990–2001.
  * Bakibayev et al. (2012) Nurzhan Bakibayev, Dan Olteanu, and Jakub Závodnỳ. 2012\.  FDB: A query engine for factorised relational databases.  _Proceedings of the VLDB Endowment_ 5, 11 (2012), 1232–1243.
  * Bast et al. (2006) Holger Bast, Debapriyo Majumdar, Ralf Schenkel, Christian Theobalt, and Gerhard Weikum. 2006\.  Io-top-k: Index-access optimized top-k query processing.  (2006).
  * Biryukov (2008) Maria Biryukov. 2008\.  Co-author network analysis in DBLP: Classifying personal names. In _International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences_. Springer, 399–408.
  * Bonifati et al. (2020) Angela Bonifati, Wim Martens, and Thomas Timm. 2020\.  An analytical study of large SPARQL query logs.  _The VLDB Journal_ 29, 2 (2020), 655–679.
  * Bourhis et al. (2021) Pierre Bourhis, Alejandro Grez, Louis Jachiet, and Cristian Riveros. 2021.  Ranked enumeration of MSO logic on words.  _ICDT_ (2021).
  * Carmeli and Kröll (2019) Nofar Carmeli and Markus Kröll. 2019.  On the enumeration complexity of unions of conjunctive queries. In _Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems_. 134–148.
  * Chang et al. (2015) Lijun Chang, Xuemin Lin, Wenjie Zhang, Jeffrey Xu Yu, Ying Zhang, and Lu Qin. 2015\.  Optimal enumeration: Efficient top-k tree matching.  _Proceedings of the VLDB Endowment_ 8, 5 (2015), 533–544.
  * Chen et al. (2018) Jinpeng Chen, Yu Liu, Guang Yang, and Ming Zou. 2018\.  Inferring tag co-occurrence relationship across heterogeneous social networks.  _Applied Soft Computing_ 66 (2018), 512–524.
  * Christmann et al. (2021) Philipp Christmann, Rishiraj Saha Roy, and Gerhard Weikum. 2021\.  Efficient Contextualization using Top-k Operators for Question Answering over Knowledge Graphs.  _arXiv preprint arXiv:2108.08597_ (2021).
  * Ciucanu and Olteanu (2015) Radu Ciucanu and Dan Olteanu. 2015.  _Worst-case optimal join at a time_.  Technical Report. Technical report, Oxford.
  * Corby and Faron-Zucker (2007) Olivier Corby and Catherine Faron-Zucker. 2007.  Implementation of SPARQL query language based on graph homomorphism. In _International Conference on Conceptual Structures_. Springer, 472–475.
  * Dalvi and Suciu (2007) Nilesh Dalvi and Dan Suciu. 2007.  Efficient query evaluation on probabilistic databases.  _The VLDB Journal_ 16, 4 (2007), 523–544.
  * Deep et al. (2021) Shaleen Deep, Xiao Hu, and Paraschos Koutris. 2021.  Enumeration Algorithms for Conjunctive Queries with Projection. In _24th International Conference on Database Theory (ICDT 2021)_. Schloss Dagstuhl-Leibniz-Zentrum für Informatik.
  * Deep et al. (2022) Shaleen Deep, Xiao Hu, and Paraschos Koutris. 2022.  Ranked Enumeration of Join Queries with Projections.  _arXiv preprint arXiv:2201.05566_ (2022).
  * Deep and Koutris (2021) Shaleen Deep and Paraschos Koutris. 2021.  Ranked Enumeration of Conjunctive Query Results. In _24th International Conference on Database Theory_.
  * Duplyakin et al. (2019) Dmitry Duplyakin, Robert Ricci, Aleksander Maricq, Gary Wong, Jonathon Duerig, Eric Eide, Leigh Stoller, Mike Hibler, David Johnson, Kirk Webb, et al. 2019\.  The design and operation of CloudLab. In _2019 $\\{$USENIX$\\}$ Annual Technical Conference ($\\{$USENIX$\\}$$\\{$ATC$\\}$ 19)_. 1–14.
  * Elmacioglu and Lee (2005) Ergin Elmacioglu and Dongwon Lee. 2005.  On six degrees of separation in DBLP-DB and more.  _ACM SIGMOD Record_ 34, 2 (2005), 33–40.
  * Erling et al. (2015) Orri Erling, Alex Averbuch, Josep Larriba-Pey, Hassan Chafi, Andrey Gubichev, Arnau Prat, Minh-Duc Pham, and Peter Boncz. 2015\.  The LDBC social network benchmark: Interactive workload. In _Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data_. 619–630.
  * Fagin (2002) Ronald Fagin. 2002\.  Combining fuzzy information: an overview.  _ACM SIGMOD Record_ 31, 2 (2002), 109–118.
  * Fagin et al. (2003) Ronald Fagin, Amnon Lotem, and Moni Naor. 2003.  Optimal aggregation algorithms for middleware.  _Journal of computer and system sciences_ 66, 4 (2003), 614–656.
  * Feng et al. (2019) Chenyuan Feng, Zuozhu Liu, Shaowei Lin, and Tony QS Quek. 2019\.  Attention-based graph convolutional network for recommendation system. In _ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 7560–7564.
  * Fredman and Tarjan (1987) Michael L Fredman and Robert Endre Tarjan. 1987.  Fibonacci heaps and their uses in improved network optimization algorithms.  _Journal of the ACM (JACM)_ 34, 3 (1987), 596–615.
  * Green et al. (2013) Todd J Green, Shan Shan Huang, Boon Thau Loo, Wenchao Zhou, et al. 2013\.  _Datalog and recursive query processing_.  Now Publishers.
  * Harris and Shadbolt (2005) Stephen Harris and Nigel Shadbolt. 2005.  SPARQL query processing with conventional relational database systems. In _International Conference on Web Information Systems Engineering_. Springer, 235–244.
  * Hopcroft et al. (1975) John E Hopcroft, Jeffrey D Ullman, and AV Aho. 1975.  The design and analysis of computer algorithms.
  * Ilyas et al. (2008) Ihab F Ilyas, George Beskales, and Mohamed A Soliman. 2008\.  A survey of top-k query processing techniques in relational database systems.  _ACM Computing Surveys (CSUR)_ 40, 4 (2008), 11\.
  * Ilyas et al. (2004) Ihab F Ilyas, Rahul Shah, Walid G Aref, Jeffrey Scott Vitter, and Ahmed K Elmagarmid. 2004.  Rank-aware query optimization. In _Proceedings of the 2004 ACM SIGMOD international conference on Management of data_. ACM, 203–214.
  * Kara et al. (2020) Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. 2020.  Trade-offs in static and dynamic evaluation of hierarchical queries. In _Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems_. 375–392.
  * Kargar et al. (2020) Mehdi Kargar, Lukasz Golab, Divesh Srivastava, Jaroslaw Szlichta, and Morteza Zihayat. 2020\.  Effective Keyword Search over Weighted Graphs.  _IEEE Transactions on Knowledge and Data Engineering_ (2020).
  * Kimelfeld and Sagiv (2006) Benny Kimelfeld and Yehoshua Sagiv. 2006.  Incrementally computing ordered answers of acyclic conjunctive queries. In _International Workshop on Next Generation Information Technologies and Systems_. Springer, 141–152.
  * Kopelowitz et al. (2016) Tsvi Kopelowitz, Seth Pettie, and Ely Porat. 2016.  Higher lower bounds from the 3SUM conjecture. In _Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms_. SIAM, 1272–1287.
  * Küçüktunç et al. (2012) Onur Küçüktunç, Erik Saule, Kamer Kaya, and Ümit V Çatalyürek. 2012\.  Recommendation on academic networks using direction aware citation analysis.  _arXiv preprint arXiv:1205.1143_ (2012).
  * Lawler (1972) Eugene L Lawler. 1972\.  A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem.  _Management science_ 18, 7 (1972), 401–405.
  * Leeka et al. (2016) Jyoti Leeka, Srikanta Bedathur, Debajyoti Bera, and Medha Atre. 2016.  Quark-X: An efficient top-k processing framework for RDF quad stores. In _Proceedings of the 25th ACM International on Conference on Information and Knowledge Management_. 831–840.
  * Leskovec and Krevl (2014) Jure Leskovec and Andrej Krevl. 2014.  SNAP Datasets: Stanford Large Network Dataset Collection.  http://snap.stanford.edu/data.
  * Li et al. (2005a) Chengkai Li, Kevin Chen-Chuan Chang, Ihab F Ilyas, and Sumin Song. 2005a.  RankSQL: query algebra and optimization for relational top-k queries. In _Proceedings of the 2005 ACM SIGMOD international conference on Management of data_. ACM, 131–142.
  * Li et al. (2005b) Chengkai Li, Mohamed A Soliman, Kevin Chen-Chuan Chang, and Ihab F Ilyas. 2005b.  RankSQL: supporting ranking queries in relational database management systems. In _Proceedings of the 31st international conference on Very large data bases_. VLDB Endowment, 1342–1345.
  * Li et al. (2019) Xiaoming Li, Hui Fang, and Jie Zhang. 2019.  Supervised user ranking in signed social networks. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 33. 184–191.
  * Lincoln et al. (2018) Andrea Lincoln, Virginia Vassilevska Williams, and Ryan Williams. 2018.  Tight hardness for shortest cycles and paths in sparse graphs. In _Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms_. SIAM, 1236–1252.
  * Manegold et al. (2009) Stefan Manegold, Martin L Kersten, and Peter Boncz. 2009\.  Database architecture evolution: Mammals flourished long before dinosaurs became extinct.  _Proceedings of the VLDB Endowment_ 2, 2 (2009), 1648–1653.
  * Marx (2013) Dániel Marx. 2013\.  Tractable hypergraph properties for constraint satisfaction and conjunctive queries.  _Journal of the ACM (JACM)_ 60, 6 (2013), 1–51.
  * Marx (2021) Dániel Marx. 2021\.  Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction. In _Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems_. 19–29.
  * Myers et al. (2014) Seth A Myers, Aneesh Sharma, Pankaj Gupta, and Jimmy Lin. 2014\.  Information network or social network? The structure of the Twitter follow graph. In _Proceedings of the 23rd International Conference on World Wide Web_. 493–498.
  * Ngo et al. (2012) Hung Q Ngo, Ely Porat, Christopher Ré, and Atri Rudra. 2012\.  Worst-case optimal join algorithms. In _Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems_. ACM, 37–48.
  * Olteanu and Závodnỳ (2015) Dan Olteanu and Jakub Závodnỳ. 2015.  Size bounds for factorised representations of query results.  _ACM Transactions on Database Systems (TODS)_ 40, 1 (2015), 1–44.
  * Pérez et al. (2009) Jorge Pérez, Marcelo Arenas, and Claudio Gutierrez. 2009\.  Semantics and complexity of SPARQL.  _ACM Transactions on Database Systems (TODS)_ 34, 3 (2009), 1–45.
  * Qi et al. (2007) Yan Qi, K Selçuk Candan, and Maria Luisa Sapino. 2007\.  Sum-max monotonic ranked joins for evaluating top-k twig queries on weighted data graphs. In _Proceedings of the 33rd international conference on Very large data bases_. VLDB Endowment, 507–518.
  * Rahm and Thor (2005) Erhard Rahm and Andreas Thor. 2005.  Citation analysis of database publications.  _ACM Sigmod Record_ 34, 4 (2005), 48–53.
  * Re et al. (2007) Christopher Re, Nilesh Dalvi, and Dan Suciu. 2007.  Efficient top-k query evaluation on probabilistic data. In _Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on_. IEEE, 886–895.
  * Segoufin (2015) Luc Segoufin. 2015\.  Constant Delay Enumeration for Conjunctive Queries.  _SIGMOD Record_ 44, 1 (2015), 10–17.  https://doi.org/10.1145/2783888.2783894
  * Sequeda and Miranker (2013) Juan F Sequeda and Daniel P Miranker. 2013.  Ultrawrap: SPARQL execution on relational data.  _Journal of Web Semantics_ 22 (2013), 19–39.
  * Sun and Han (2013) Yizhou Sun and Jiawei Han. 2013.  Mining heterogeneous information networks: a structural analysis approach.  _Acm Sigkdd Explorations Newsletter_ 14, 2 (2013), 20–28.
  * Tsaparas et al. (2003) Panayiotis Tsaparas, Themistoklis Palpanas, Yannis Kotidis, Nick Koudas, and Divesh Srivastava. 2003\.  Ranked join indices. In _Proceedings 19th International Conference on Data Engineering (Cat. No. 03CH37405)_. IEEE, 277–288.
  * Tziavelis et al. (2020a) Nikolaos Tziavelis, Deepak Ajwani, Wolfgang Gatterbauer, Mirek Riedewald, and Xiaofeng Yang. 2020a.  Optimal algorithms for ranked enumeration of answers to full conjunctive queries. In _Proceedings of the VLDB Endowment. International Conference on Very Large Data Bases_ , Vol. 13. NIH Public Access, 1582.
  * Tziavelis et al. (2020b) Nikolaos Tziavelis, Deepak Ajwani, Wolfgang Gatterbauer, Mirek Riedewald, and Xiaofeng Yang. 2020b.  Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries.  arXiv:1911.05582v3 [cs.DB]
  * Tziavelis et al. (2021) Nikolaos Tziavelis, Wolfgang Gatterbauer, and Mirek Riedewald. 2021.  Beyond Equi-joins: Ranking, Enumeration and Factorization. In _Proceedings of the VLDB Endowment. International Conference on Very Large Data Bases_ , Vol. 14. 2599–2612.
  * Xirogiannopoulos and Deshpande (2017) Konstantinos Xirogiannopoulos and Amol Deshpande. 2017.  Extracting and Analyzing Hidden Graphs from Relational Databases. In _Proceedings of the 2017 ACM International Conference on Management of Data_. ACM, 897–912.
  * Yang et al. (2018) Xiaofeng Yang, Deepak Ajwani, Wolfgang Gatterbauer, Patrick K Nicholson, Mirek Riedewald, and Alessandra Sala. 2018.  Any-k: Anytime Top-k Tree Pattern Retrieval in Labeled Graphs. In _Proceedings of the 2018 World Wide Web Conference on World Wide Web_. International World Wide Web Conferences Steering Committee, 489–498.
  * Yannakakis (1981) Mihalis Yannakakis. 1981\.  Algorithms for acyclic database schemes. In _VLDB_ , Vol. 81. 82–94.
  * Yu et al. (2012) Xiao Yu, Yizhou Sun, Brandon Norick, Tiancheng Mao, and Jiawei Han. 2012.  User guided entity similarity search using meta-path selection in heterogeneous information networks. In _Proceedings of the 21st ACM international conference on Information and knowledge management_. 2025–2029.
  * Zou et al. (2010) Zhaonian Zou, Jianzhong Li, Hong Gao, and Shuo Zhang. 2010\.  Finding top-k maximal cliques in an uncertain graph.  (2010).

##  Appendix A Other Enumeration Semantics

(Tziavelis et al., 2020b) discussed a more fine-grained approach to ranked
enumeration over joins queries with projections. The goal is to enumerate the
ranked output $Q(D)$ where $Q$ contains projections and the ranking function
is defined over all the attributes ($\mathbb{A}$). Since the weights are
placed on the attributes/relations and the output tuple $t$ does not contain
all the attributes, each answer could have multiple weights associated with
it. In this case, one option is to return $t$ with the list of all the
weights. Our algorithm for ranked enumeration can be extended to handle this
trivially. The second semantics identified is the min-weight-projection
semantics. In this case, $t$ is returned with the smallest possible weight.
(Tziavelis et al., 2020b) showed how their algorithm for full join can be
extended to incorporate min-weight-projection semantics. We note here that the
results for projection queries in (Tziavelis et al., 2020b) can only handle
acyclic free-connex queries, a restricted subclass of acyclic CQs (see
Appendix E for the definition). Further, in our problem formulation, the
ranking function depends only on the projection attributes and not all the
attributes.

##  Appendix B Using Existing Algorithms

Input : Join-project query $Q$, ranking function  SUM and database $D$

Output : $Q(D)$ in ranked order

1

2

3$Q^{\prime}\leftarrow\text{ full query obtained by dropping the projection
operator from }Q$

4 Provide $Q^{\prime}$, ranking function  SUM that assigns weight zero to all
values of attributes $\mathbb{A}\setminus\mathbf{A}$, and $D$ to $\mathcal{A}$
for pre-processing;

5 $\textnormal{{{last}}}\leftarrow\emptyset$

6 while  _$\mathcal{A}.\textnormal{{{hasNext}}}()$_ do

$o\leftarrow\mathcal{A}.\textnormal{{{getNext}}}()$

/* enumerate the answer from $\mathcal{A}$ */

7 if  _$\textnormal{{{last}}}\neq o[\mathbf{A}]$_ then

8 output $o[\mathbf{A}]$, $\textnormal{{{last}}}\leftarrow o[\mathbf{A}]$

9

return

/* Enumeration complete */

Algorithm 6 UseExistingAlgorithm

Given a blackbox algorithm $\mathcal{A}$ for ranked enumeration of full join
queries, we can obtain an algorithm for ranked enumeration of join-project
queries. Algorithm 6 shows how $\mathcal{A}$ can be used for enumeration of
join-project queries. The key idea here is that $\mathcal{A}$ can assign a
weight of zero to all values of non-projection attributes. This will guarantee
that tuples enumerated by $\mathcal{A}$ will be sorted only over the sum of
attribute values of $\mathbf{A}$. The while loop contains a variable that
stores the last tuple output $\mathbf{A}$. This helps in ensuring that no
duplicates are output for the join-project query. Intuitively, Algorithm 6 is
performing a ranked group by over the attributes $\mathbf{A}$ and outputs an
answer when the grouping value changes. We now show that there exist queries
where the dealy for this algorithm could be large. Consider the query

$Q=\pi_{X_{1}}(\Join_{i\in[\ell]}R_{i}(X_{i},Y))$

.

Suppose that each relation $R_{i}$ has $N$ attribute value for $X_{i}$ that is
connected one $Y$ attribute value $y^{\star}$ for each
$i\in\\{1,\dots,\ell\\}$. Then, the smallest answer of $QD)$ will be output
$N^{\ell-1}$ times by $\mathcal{A}$ on Algorithm 6. This is because the join
of $R_{2}\Join\dots\Join R_{\ell}$ has a size of $N^{\ell-1}$. This directly
implies that the delay guarantee is $\Omega(N^{\ell-1})$.

##  Appendix C Missing Proofs

See 4

###### Proof.

In order to prove the delay guarantee, we analyze the worst-case running time
that can happen in each iteration. Without loss of generality, we assume that
there exists at least one non-anchor projection attribute in all leaf nodes
(otherwise, we can simply remove the node from the join tree after the full
reducer pass).

Let us first analyze the procedure Enum. The root priority queue (denoted
$\textsc{PQ}_{r}$) can contain at most $|D|$ entries for each output result.
Indeed, in the worst-case, the output tuple emitted to the user on Algorithm 2
may join with every tuple in the root node relation. Therefore, in the worst-
case, for every tuple outputted to the user, we invoke the Topdown procedure
$|D|$ times.

We now argue that Topdown takes at most $O(|D|\log|D|)$ time. There are two
key observations to be made. First, Topdown takes $O(1)$ time if
$c.\textsf{next}$ is already populated. Intuitively, this means that in a
previous iteration, there was a recursive call made to Topdown that populated
the next and we are now simply reusing the computation. Thus, for every tuple
output to the user, it suffices to count how many times Topdown is invoked in
total, such that next is not empty. We say that such invocations of Topdown
are _non-trivial_. Our claim is that the number of non-trivial Topdown calls
is at most $O(|D|)$. Consider the set of all anchor attribute values for some
node $j$ (denoted $\mathcal{L}_{R_{j}}$). We fix some
$u\in\mathcal{L}_{R_{j}}$. In the worst-case, Topdown$(c,j)$ such that
$u=\pi_{\texttt{anchor}({R_{j}})}(c.t)$ is invoked by all tuples $t^{\prime}$
in the parent relation of node $j$ such that
$\pi_{\texttt{anchor}({R_{j}})}(t^{\prime})=u$ but only the first call will be
non-trivial since the first call populates the $c.\textsf{next}$. Therefore,
it follows that for each $u\in\mathcal{L}_{R_{j}}$, there is at most one non-
trivial call to Topdown$(c,R_{j})$ for a fixed node $R_{j}$. Since the size of
the join tree is at most $O(1)$, the total number of non-trivial calls over
all nodes in the join tree is
$\sum_{j}\sum_{u\in\mathcal{L}_{R_{j}}}1=\sum_{j}|D|=O(|D|)$. Finally, we
perform one pop operation and a constant number of inserts into the priority
queue in every non-trivial invocation which adds another $\log|D|$ factor in
the running time, giving us the claimed delay guarantee of $O(|D|\log|D|)$. ∎

See 5

###### Proof.

For a node $R_{i}\in\mathcal{T}$, we initialize an empty priority queue for
each possible value in $\texttt{anchor}({R_{i}})$. The for loop on Algorithm 1
takes $O(1)$ time as each node has $O(1)$ children in the decomposition and
all operations on line 8-12 also take $O(\log|D|)$ time. Overall, since each
node has at most $O(|D|)$ tuples, the claim readily follows. ∎

See 6

###### Proof.

We will prove our claim by induction on height of the tree. We will show that
at each relation $R$, the priority queue $\textsf{PQ}_{R}[u]$ correctly
computes the answers over all projection attributes in the subtree rooted at
$R$ (denoted $\mathbf{A}^{\pi}_{R}$) in ranked order.

Base Case. Correctness for ranked output of leaf relations is trivial. For all
tuples $t$ in the relation at a leaf node with the same anchor attribute value
$u$, $\textsf{PQ}_{R}[u]$ contains all tuples $t$ and the priority queue
(whose implementation is assumed to be correct) will pop out
$t[\mathbf{A}^{\pi}_{R}]$ in the correct order since the score
$\textnormal{{{rank}}}(t[\mathbf{A}^{\pi}_{R}])$ is used as the priority queue
comparator function and all projection attributes $\mathbf{A}^{\pi}_{R}$ are
present in $t$ already. It also follows that $R[\mathbf{A}^{\pi}_{R}]$ will be
materialized by chaining the cells popped from the priority queue since the
leaf relation already contains all the attributes in $\mathbf{A}^{\pi}_{R}$.

Inductive Case. Consider a relation $R$ with children relations $R_{1},\dots
R_{s}$. Let $c$ be the cell that was the input to the TopDown procedure call
under consideration. Let $u=c.t[\texttt{anchor}({R})]$ and
$u_{i}=c.t[\texttt{anchor}({R_{i}})]$. Let
$t_{\pi}=\mathsf{output}(c_{\mathsf{next}})$ be the next tuple and let
$c_{\mathsf{next}}$ be the cell that is to be returned to the parent of $R$ by
the recursive call to $R$ (i.e. $c_{\mathsf{next}}$ follows $c$ in the ranked
output of the subtree rooted at $R$). Our goal is to show that $t_{\pi}$ is
generated correctly and $c_{\mathsf{next}}$ is inserted in
$\textsf{PQ}_{R}[u]$. This will guarantee the correct ordering of the tuples
over attribute set $\mathbf{A}^{\pi}_{R}$. From the induction hypothesis, we
have that the ranked output, over the attributes $\mathbf{A}^{\pi}_{i}$, from
each $R_{i}$ is generated correctly. For the sake of contradiction, suppose
that $t^{\prime}_{\pi}$ is the next smallest candidate, i.e.
$\textnormal{{{rank}}}(t^{\prime}_{\pi})<\textnormal{{{rank}}}(t_{\pi})$.

Lines 2-2 in Algorithm 2 generates $s$ possible candidate cells (and is the
only way to generate new candidates) that could generate $t_{\pi}$. Let
$\hat{c}_{i}$ be the cell returned from the recursive call to TopDown for
relation $R_{i}$. Then, there are $s$ possible cells that are generated by
TopDown for relation $R$ whose array of pointers will be one of:

$\displaystyle\hat{c}_{1},c_{2},c_{3},\dots,c_{s},$ $\displaystyle
c_{1},\hat{c}_{2},c_{3},\dots,c_{s},$ $\displaystyle\dots,$ $\displaystyle
c_{1},c_{2},c_{3},\dots,\hat{c}_{s}$

Here, $c_{i}$ is $i^{\text{th}}$ pointer in the pointer array of $c$ and
$\textnormal{{{rank}}}(\mathsf{output}(\hat{c}_{i}))\geq\textnormal{{{rank}}}(\mathsf{output}(c_{i}))$
since the priority queue of the $R_{i}$ will generate answers in increasing
order (from the induction hypothesis). Assume for the sake of contradiction
that $c^{\prime}_{\mathsf{next}}=\langle
c.t,[c^{\prime}_{1},c^{\prime}_{2},\dots,c^{\prime}_{s}],\bot\rangle$ is the
cell such that $t^{\prime}_{\pi}=\mathsf{output}(c^{\prime}_{\mathsf{next}})$
and is not one of the $s$ candidate cells generated above. Since
$t^{\prime}_{\pi}$ has a smaller score than $t_{\pi}$, it follows that
$c^{\prime}_{\mathsf{next}}$ has not been inserted in the priority queue yet
(otherwise the priority queue will return $c^{\prime}_{\mathsf{next}}$
correctly). We will show that such a scenario will violate the monotonicity
property of the sum ranking function.

Case 1.
$\textnormal{{{rank}}}(\mathsf{output}(c_{i}))\geq\textnormal{{{rank}}}(\mathsf{output}(c^{\prime}_{i}))$
for $i\in[s]$. This scenario implies that $t^{\prime}_{\pi}$ has been
generated before $t_{\pi}$, which would violate our assumption that
$t^{\prime}_{\pi}$ has not been inserted in the priority queue. Indeed, since
$\textnormal{{{rank}}}(\mathsf{output}(c_{i}))\geq\textnormal{{{rank}}}(\mathsf{output}(c^{\prime}_{i}))$
and lines 2-2 in Algorithm 2 generate cells that are monotonically increasing,
there exists a sequence of generations that generate $c_{\mathsf{next}}$ from
$c^{\prime}_{\mathsf{next}}$ which would mean that
$c^{\prime}_{\mathsf{next}}$ was present in the priority queue at some point.

Case 2.
$\textnormal{{{rank}}}(\mathsf{output}(c_{i}))<\textnormal{{{rank}}}(\mathsf{output}(c^{\prime}_{i}))$
for $i\in[s]$. This scenario implies that
$\sum_{i}\textnormal{{{rank}}}(\mathsf{output}(c_{i}))=\textnormal{{{rank}}}(t_{\pi})<\sum_{i}\textnormal{{{rank}}}(\mathsf{output}(c^{\prime}_{i}))=\textnormal{{{rank}}}(t^{\prime}_{\pi})$
which contradicts our assumption that $t^{\prime}_{\pi}$ has a smaller score
than $t_{\pi}$.

Case 3. $\textnormal{{{rank}}}(\mathsf{output}(c_{i}))$ and
$\textnormal{{{rank}}}(\mathsf{output}(c^{\prime}_{i}))$ are incomparable. If
$c^{\prime}_{\mathsf{next}}$ has not been inserted in the priority queue yet,
there are two possible scenarios. Either $c^{\prime}_{\mathsf{next}}$ will be
generated by some cell $c^{\prime\prime}_{\mathsf{next}}$ that is already in
the priority queue. Clearly,
$\textnormal{{{rank}}}(\mathsf{output}(c^{\prime}_{\mathsf{next}}))>\textnormal{{{rank}}}(\mathsf{output}(c^{\prime\prime}_{\mathsf{next}}))>\textnormal{{{rank}}}(\mathsf{output}(c_{\mathsf{next}}))$
using the same reasoning as Case 1 which contradicts our assumption. The
second possibility is that $c^{\prime}_{\mathsf{next}}$ and
$c_{\mathsf{next}}$ are generated in the same loop. But this would again imply
that $c^{\prime}_{\mathsf{next}}$ is in the priority queue, a contradiction to
our assumption.

Therefore, it cannot be the case that
$\textnormal{{{rank}}}(t^{\prime}_{\pi})<\textnormal{{{rank}}}(t_{\pi})$ which
proves that for relation $R$, all tuples generated over the attributes
$\mathbf{A}^{\pi}_{R}$ are in the correct order and consequently, the claim
holds for all relations in the join tree, including the root.

In the second part of the proof, we will show that every result enumerated
must belong to $Q(D)$. This is a direct consequence of the properties of the
join tree. Indeed, if some tuple $t\not\in Q(D)$ is enumerated, that would
violate the join condition on some attribute $X\in\mathbf{A}$. Next, we will
show that every query result in $Q(D)$ will be enumerated using induction on
the join tree. In the base case, for some leaf node $R$ in $\mathcal{T}$,
every query result over attributes $\mathbf{A}^{\pi}_{R}$ will be enumerated
from Topdown because the relation is materialized. By the induction
hypothesis, for each $i\in[s]$,

$Q_{i}=(\Join_{j\in\text{ nodes in subtree rooted at
}i}R_{j})[\mathbf{A}^{\pi}_{i}]$

is enumerated completely generated. For each tuple $t$ in $R$, lines 2-2
guarantees that,

$((\times_{i\in[s]}Q_{i})\Join t)[\mathbf{A}^{\pi}_{R}]$

must be inserted into $\textsf{PQ}[\pi_{\texttt{anchor}({R})}(t)]$, and thus
enumerated. In other words, the projection of cartesian product between each
subquery rooted at $R_{i}$ (i.e. $Q_{i}$ as defined above) and $t$ over
$\mathbf{A}^{\pi}_{R}$ is generated. This implies that the subquery induced by
the subtree rooted at $R$ enumerates all join result over
$\mathbf{A}^{\pi}_{R}$. In the preprocessing phase, all tuples in $R$ are put
into the entries of $\textsf{PQ}[\pi_{\texttt{anchor}({R})}(t)]$, thus every
query result in $Q(D)$ will necessarily be enumerated. ∎

See 7

###### Proof.

We will prove that the algorithm enumerates the query result in the correct
lexicographic order using induction on the parameter $i$ in Algorithm 3.

Base case. $i=1$. Note that since $\mathbf{dom}(A_{1})$ is sorted
$t^{\prime}$, will be initialized with $a\in\mathbf{dom}(A_{1})$ in sorted
order which guarantees that all output tuples with $a$ as the attribute value
for $A_{1}$ will be enumerated before tuples with $a^{\prime}$ as the
attribute value for $A_{1}$ if $a\leq a^{\prime}$, thus respecting the
lexicographic order for $A_{1}$.

Inductive case. $i=k$. From the induction hypothesis, we get that the
algorithm will enumerate correctly for the first $k-1$ attributes including
$A_{k-1}$. From the previous iteration, $\mathcal{L}^{\prime}$ is set to be
the sorted list of attribute values for $A_{k}$ that join with
$R_{k}(A_{k},A_{k+1})$. Therefore, it follows that for the recursive call
where $i=k$, $t^{\prime}$ will have a attribute values set in sorted order for
$A_{k}$, ensuring that all answers containing $a=\pi_{A_{k}}(t^{\prime})$ will
be enumerated before answers containing $a^{\prime}$ as attribute value for
$A_{k}$ for all $a\leq a^{\prime}$. Thus, the argument holds for $i=m$ as
well, concluding the proof.

Next, we analyze the time complexity. The preprocessing phase takes
$O(|D|\log|D|)$ time in total for sorting and building hashing tables for each
relation. Observe that after fixing a value in $\mathbf{dom}(A_{i})$, it takes
at most $O(|D|)$ time to perform the semi-joins and find the set of candidate
values in $\mathbf{dom}(A_{i+1})$. Whenever $i$ reaches $m$, a valid query
result will be enumerated. As the query size as well as $m$ is a constant, the
delay between two consecutive query results is at most $O(|D|)$, which
improves Lemma 4 by a log factor. ∎

See 1

###### Proof.

Time and Space complexity. First, we analyze its time complexity. Computing
data statistics for each relation $R_{i}$ takes $O(|D|)$ time. As the degree
threshold is $\delta$, there are at most $O(\frac{|D|}{\delta})$ heavy values
for each $A_{i}$. The size of $\mathcal{O}^{H}$ can be bounded by
$O(|D|\cdot(\frac{|D|}{\delta})^{m-1})$, as well as the time cost for
computing $\mathcal{O}^{H}$ by the Yannakakis algorithm. At last, initializing
data structures for each $Q_{i}$ takes linear time in terms of $O(|D|)$. As
the number of such queries is $O(m)$, the time cost for line 3-6 is
$O(|D|\cdot m)$. Overall, the time complexity of Algorithm 4 is
$O(|D|\cdot(\frac{|D|}{\delta})^{m-1})$. For the space usage, storing
$\mathcal{O}^{H}$ takes $O((\frac{|D|}{\delta})^{m})$ space since its size can
be bounded by $O((\frac{|D|}{\delta})^{m})$ using the AGM bound.

Delay guarantee. Note that min-extraction and update of the priority queue
takes $O(\log|D|)$ time. The expensive part is the invocation of EnumAcyclic
for each $Q_{i}$. In the join tree $\mathcal{T}_{i}$, each node contains at
least one projection attribute. Plugging in Lemma 4 and the observations in
Appendix D, the delay of enumerating query result from $Q_{i}$ is at most the
degree of values of attribute $A_{i}$, i.e., $\delta$, since tuples in $R_{i}$
are light in this case, by construction of $Q_{i}$. Together, the delay of
Algorithm 5 is $O(\delta\log|D|)$. By setting $\delta=|D|^{1-\epsilon}$ for
arbitrary constant $0<\epsilon<1$, we can achieve the result in Theorem 3.

Correctness. Recall that $O^{H}$ is already materialized and sorted order and
since the enumeration of each subquery $Q_{i}$ is performed using EnumAcyclic
(which enumerated the query result correctly), the output of each $Q_{i}$ is
enumerated in the correct order. It remains to be shown that EnumStar can also
combine the answers from $O^{H}$ and $Q_{i}$ correctly. Suppose that $t$ was
the last answer output to the user. If $t$ was generated by some $Q_{i}$
(which can be checked in constant time), then we find the next smallest
candidate from $Q_{i}$ and insert it into PQ. Otherwise, if $t\in O^{H}$, we
find the next tuple in the materialized output and insert it into PQ. Thus,
since the smallest candidates for each $Q_{i}$ and $O^{H}$ are present in the
PQ, the smallest answer that must be output to the user necessarily has to be
from the priority queue. Thus, the priority queue performs the $m+1$-way merge
correctly. This concludes the proof. ∎

See 3

###### Proof.

For a star query $Q^{\star}_{m}$ and database $D$, assume there is an
algorithm that supports $O(|D|^{1-\epsilon}\log|D|)$-delay enumeration after
$O(|D|^{1+(m-1)\epsilon-\epsilon^{\prime}})$ preprocessing time. Then, there
is an algorithm evaluating $Q^{\star}_{m}(D)$ in (big-Oh of)

$|D|^{1+(m-1)\epsilon-\epsilon^{\prime}}+|D|^{1-\epsilon}\log|D|\cdot|Q^{\star}_{m}(D)|$

time. Let $\alpha=m\epsilon-\epsilon^{\prime}$ for some constant
$\epsilon^{\prime}<\epsilon$. Consider an instance $D^{\prime}$ for
$Q^{\star}_{m}$ with output size $N^{\alpha}/\log N$. The running time of the
algorithm is (big-Oh of)

$\displaystyle|D^{\prime}|^{1+(m-1)\epsilon-\epsilon^{\prime}}+|Q^{\star}_{m}(D^{\prime})|\cdot(|D^{\prime}|^{1-\epsilon}\log|D^{\prime}|)$
$\displaystyle=$
$\displaystyle|D^{\prime}|^{1-\frac{\epsilon^{\prime}}{m}}\cdot|Q^{\star}_{m}(D^{\prime})|^{(1-\frac{1}{m})}$

which breaks the optimality of Lemma 2. ∎

###### Lemma 0.

The delay guarantee of Lemma 4 is optimal up to polylogarithmic factors
subject to the combinatorial BMM conjecture.

##  Appendix D More fine grained results

In this section, we show tighter delay guarantees for Theorem 2 under certain
settings. Consider a query where each relation contains at least one
projection attribute (for instance, $Q^{\star}_{m}$). Let’s fix a relation $R$
and let the projection attributes in $R$ be $\mathbf{B}$. Denote
$\Delta_{R}=\max_{u\in\mathbf{dom}(\mathbf{B})}|\sigma_{\mathbf{B}=u}R|$ and
$\Delta=\max_{\text{non-leaf relations }R}\Delta_{R}$. Then, the delay
guarantee obtained by Theorem 2 is at most $O(\Delta\log|D|)$. A trivial upper
bound for $\Delta=|D|$ since the size of all relations is $|D|$. However, if
there are constraints known about the degree of the tuples in the relations,
we can improve our results. We give two concrete scenarios below.

Bounded Degree Database. For each relation, if every attribute value is
present in at most $\delta$ tuples, it implies that the degree is at most
$\delta$. In this case, it can be shown that $\Delta=\delta$ and we get
improved delay guarantees since the duplication is bounded when each relation
has projection attributes.

Bounded Degree By Preprocessing. Consider the star query $Q^{\star}_{m}$.
Recall that in Algorithm 4, we preprocess to reduce the degree of all $a_{i}$
from $|D|$ to $\delta=|D|^{1-\epsilon}$. Thus, the discussion above applies
and we can achieve $O(|D|^{1-\epsilon}\log|D|)$ delay.

Improved delay guarantee is obtained in Algorithm 2 only when the while loop
can terminate in $o(|D|)$ time. For any anchor attribute value $u$ for some
relation $R$ in the join-tree, this can only happen when the tuples generated
over $\mathbf{A}_{R}$ are not duplicated more than a certain number of times.
Since every relation contains a projection attribute and has bounded degree
$\Delta$, it means that $\textsf{PQ}_{R}[u]$ can have at most $\Delta$
duplicates which gives the better bound.

##  Appendix E Recovering results for full queries

Next, we outline how Algorithm 2 achieves delay $O(\log|D|)$ after $O(|D|)$
preprocessing for full acyclic queries. The key observation is that when the
query is full, the while loop always terminates after a constant number of
operations. This is because no two answer tuples over $\mathbf{A}^{\pi}_{R}$
are the same, i.e, the attribute values for any two answer tuples cannot be
identical. Further, any answer tuple at $R$ is inserted at most a constant
number of times. This guarantees that is_equal procedure will return false
after popping an answer constant number of times and the while loop
terminates. Thus, in the worst-case, TopDown visits each relation of the join
tree at most once and each iteration takes only $O(\log|D|)$ time due to the
priority queue operations.

Free-connex queries. A join query $Q$ is said to be free-connex if $Q$ is
acyclic and the hypergraph containing edges of $Q$ and a new edge containing
only the projection variables is also acyclic. Free-connex is an interesting
class of queries which allows constant delay enumeration for a variety of
problems (Bagan et al., 2007; Carmeli and Kröll, 2019). If a join-project
query is free-connex, then our actually algorithm achieves $O(\log|D|)$ delay
enumeration (instead of the general $O(|D|\log|D|)$ bound) after linear time
preprocessing. It can be shown that for free-connex queries, all projection
attributes are connected and must be at the top of the tree and all non-
projection attributes are connected and at the bottom of the tree. This
observation allows us to remove all relations that do not contain any
projection attributes or relation where only anchor attributes are projection
attributes, transforming the free-connex query into a full join query.

##  Appendix F Submodular width lower bound

Abboud, Backurs and, Vassilevska Williams present the Combinatorial $k-$Clique
Hypothesis (Abboud et al., 2018a).

###### Definition 0.

Let $C$ be the smallest constant such that a combinatorial algorithm running
in $O(n^{Ck/3})$ time exists for detecting a $k-$clique in a $n$ node
$O(n^{2})$ edge graph, for all sufficiently large constants $k$. The
Combinatorial $k-$Clique Hypothesis states that $C=3$.

Next, we recall a cycle detection hypothesis from (Lincoln et al., 2018) that
depends on the combinatorial $k-$clique hypothesis.

###### Theorem 2 (Combinatorial Sparse k-Cycle Lower Bound).

Detecting a directed odd $k-$cycle in a graph with $n$ nodes and
$m=n^{(k+1)/(k-1)}$ in time $O(m^{(1-\epsilon)2k/(k+1)})$ for any constant
$\epsilon>0$ violates the Combinatorial $k-$Clique Hypothesis.

Consider an odd $k-$ cycle CQ over binary relations of the form
$Q^{\circlearrowright}(x_{1},x_{2})=R_{1}(x_{1},x_{2})\Join
R_{2}(x_{2},x_{3})\Join\dots\Join R_{k}(x_{k},x_{1})$. Then, we can show the
following straightforward result.

###### Lemma 0.

For some odd $k$ cycle query $Q^{\circlearrowright}$ with $k>3$, an algorithm
that enumerates the query result with delay $O(|D|^{2k/k+1}-\epsilon)$ after
$O(|D|^{2k/(k+1)}-\epsilon)$ preprocessing violates the Combinatorial Sparse
$k-$Cycle Lower Bound.

###### Proof.

If the algorithm has delay guarantee $\delta=O(|D|^{2k/k+1}-\epsilon)$, then
in $\delta$ time, we can decide whether there exists a cycle or not since the
preprocessing time is also $O(|D|^{2k/k+1}-\epsilon)$, a contradiction. ∎

Note that the submodular width for the odd $k-$cycle query is
$\texttt{subw}=2-2/(k+1)=2k/(k+1)$. Thus, there exist queries for which the
exponential dependence of subw in Theorem 2 cannot be avoided assuming the
Combinatorial $k-$Clique Hypothesis.

##  Appendix G Deferred Experiments

In this section, we present the experimental results for settings that were
not covered in the main paper due to lack of space.

###  G.1. Small Scale Experiments

⬇

$\mathsf{IMDB}_{2\mathsf{hop}}$ = SELECT DISTINCT
$\mathsf{P}_{1}.\mathsf{name},\mathsf{P}_{2}.\mathsf{name}$ FROM
$\mathsf{Person}$ AS $\mathsf{P_{1}}$, $\mathsf{Person}$ AS $\mathsf{P_{1}}$,
$\mathsf{PersonMovie}$ AS $\mathsf{PM}_{1}$, $\mathsf{PersonMovie}$ as
$\mathsf{PM}_{2}$ WHERE $\mathsf{PM_{1}.pid}=\mathsf{PM_{2}.pid}$ AND
$\mathsf{PM_{1}.aid}=\mathsf{P_{1}.aid}$ AND
$\mathsf{PM_{2}.aid}=\mathsf{P_{2}.aid}$ AND $\mathsf{P_{1}.role}$ = 'ACTOR'
AND $\mathsf{P_{2}.role}$ = 'ACTOR' ORDER BY
$\mathsf{A}_{1}.\mathsf{weight}+\mathsf{A}_{2}.\mathsf{weight}$ LIMIT k;

$\mathsf{IMDB}_{3\mathsf{hop}}$ = SELECT DISTINCT
$\mathsf{P}.\mathsf{name},\mathsf{M}.\mathsf{name}$ FROM $\mathsf{Person}$ AS
$\mathsf{P}$, $\mathsf{Person}$ AS $\mathsf{P^{\prime}}$, $\mathsf{Movie}$ AS
$\mathsf{M}$, $\mathsf{PersonMovie}$ AS $\mathsf{PM}_{1}$,
$\mathsf{PersonMovie}$ as $\mathsf{PM_{2}}$, $\mathsf{PersonMovie}$ as
$\mathsf{PM_{3}}$ WHERE $\mathsf{PM_{1}.mid}=\mathsf{PM_{2}.mid}$ AND
$\mathsf{PM_{2}.pid}=\mathsf{PM_{3}.pid}$ AND
$\mathsf{PM_{2}.pid}=\mathsf{P^{\prime}.pid}$ AND
$\mathsf{PM_{1}.pid}=\mathsf{P.pid}$ AND $\mathsf{PM_{3}.mid}=\mathsf{M.mid}$
AND $\mathsf{P.role}$ = 'ACTOR' AND $\mathsf{P^{\prime}.role}$ = 'ACTOR' ORDER
BY $\mathsf{P}.\mathsf{weight}+\mathsf{M}.\mathsf{weight}$ LIMIT k;

$\mathsf{IMDB}_{4\mathsf{hop}}$ = SELECT DISTINCT
$\mathsf{P}_{1}.\mathsf{name},\mathsf{P}_{2}.\mathsf{name}$ FROM
$\mathsf{Person}$ AS $\mathsf{P_{1}}$, $\mathsf{Person}$ AS $\mathsf{P_{2}}$,
$\mathsf{Person}$ AS $\mathsf{P_{3}}$, $\mathsf{PersonMovie}$ AS
$\mathsf{PM}_{1}$, $\mathsf{PersonMovie}$ as $\mathsf{PM_{2}}$,
$\mathsf{PersonMovie}$ as $\mathsf{PM_{3}}$, $\mathsf{PersonMovie}$ as
$\mathsf{PM_{4}}$ WHERE $\mathsf{PM_{1}.mid}=\mathsf{PM_{2}.mid}$ AND
$\mathsf{PM_{2}.pid}=\mathsf{PM_{3}.pid}$ AND
$\mathsf{PM_{3}.mid}=\mathsf{PM_{4}.mid}$ AND
$\mathsf{PM_{1}.pid}=\mathsf{P_{2}.pid}$ AND $\mathsf{P_{3}.role}$ = 'ACTOR'
AND $\mathsf{PM_{2}.pid}=\mathsf{P_{3}.pid}$ AND $\mathsf{P_{1}.role}$ =
'ACTOR' AND $\mathsf{PM_{4}.pid}=\mathsf{P_{2}.aid}$ AND $\mathsf{P_{2}.role}$
= 'ACTOR' ORDER BY
$\mathsf{P}_{1}.\mathsf{weight}+\mathsf{P}_{2}.\mathsf{weight}$ LIMIT k;

$\mathsf{IMDB}_{3\mathsf{star}}$ = SELECT DISTINCT
$\mathsf{P}_{1}.\mathsf{name},\mathsf{P}_{2}.\mathsf{name},\mathsf{P}_{3}.\mathsf{name}$
FROM FROM $\mathsf{Person}$ AS $\mathsf{P_{1}}$, $\mathsf{Person}$ AS
$\mathsf{P_{2}}$, $\mathsf{Person}$ AS $\mathsf{P_{3}}$,
$\mathsf{PersonMovie}$ AS $\mathsf{AP}_{1}$, $\mathsf{PersonMovie}$ as
$\mathsf{AP_{2}}$, $\mathsf{PersonMovie}$ as $\mathsf{AP_{3}}$ WHERE
$\mathsf{PM_{1}.mid}=\mathsf{PM_{2}.mid}=\mathsf{PM_{3}.mid}$ AND
$\mathsf{PM_{1}.pid}=\mathsf{P_{1}.pid}$ AND
$\mathsf{PM_{2}.pid}=\mathsf{P_{2}.pid}$ AND
$\mathsf{PM_{3}.pid}=\mathsf{P_{3}.pid}$ AND $\mathsf{P_{1}.role}$ = 'ACTOR'
AND $\mathsf{P_{2}.role}$ = 'ACTOR' AND $\mathsf{P_{3}.role}$ = 'ACTOR' ORDER
BY
$\mathsf{P}_{1}.\mathsf{weight}+\mathsf{P}_{2}.\mathsf{weight}+\mathsf{P}_{3}.\mathsf{weight}$
LIMIT k;

Figure 11. Network analysis queries for IMDB.

Lexicographic ordering. Figures 12(a), 12(a), 12(c), 12(d) show the running
time for different values of $k$ in the limit clause for lexicographic
function for IMDB dataset. Our conclusions remain the same as they were for
DBLP dataset.

Choice of different root of the join tree. For the DBLP dataset, we test the
choice of different root nodes for $\mathsf{DBLP}_{\mathsf{3hop}}$ and
$\mathsf{DBLP}_{\mathsf{4hop}}$ queries since these queries have a large
choice of root nodes to pick from. We observed that for any choice of root
node in the join tree, the difference in total execution time for $k$ ranging
from $10$ to $10^{4}$ was less than $3\%$. This demonstrates that as long as
the join tree or GHD is of the minimal width, the actual orientation of the
GHD has no meaningful impact on the execution times.

(a) $\mathsf{IMDB}_{2\mathsf{hop}}$

(b) $\mathsf{IMDB}_{3\mathsf{hop}}$

(c) $\mathsf{IMDB}_{4\mathsf{hop}}$

(d) $\mathsf{IMDB}_{3\mathsf{star}}$

(e) $\mathsf{Friendster}_{2\mathsf{hop}}$

(f) $\mathsf{Friendster}_{3\mathsf{hop}}$

(g) $\mathsf{Memetracker}_{2\mathsf{hop}}$

(h) $\mathsf{Memetracker}_{3\mathsf{hop}}$

Figure 12. Comparing our linear delay algorithm with state-of-the-art engines
for lexicographic function.

(a) Four cycle query for DBLP (left) and Six cycle query for DBLP (right)

(b) Eight cycle query for DBLP

Figure 13. Hypergraphs for cyclic queries

Measuring the delay. Our final experiment in this subsection evaluates how
many priority queue operations are required for each answer tuple. Recall that
for each answer, our algorithm performs $O(|D|)$ priority queue operations in
the worst-case (Theorem 2). Thus, the number of priority queue operations is a
proxy for the delay between any two answers. 14(a) plots the fraction of
answers that require a certain number of PQ operations for
$\mathsf{DBLP}_{2\mathsf{hop}}$. Nearly $70\%$ of answers require only one PQ
push and pop operation and $99\%$ of the output requires at most $22$ push and
pop operations. However, there are some outliers as well. The largest number
of push and pops over all answers is $306$. This is not particularly
surprising given the fact that DBLP is a sparse dataset but dense matrix
datasets can easily have a large duplication in practice. For the IMDB
dataset, we found that $95\%$ of answers require one priority queue operation
and $99\%$ of answers needed at most three operations.

(a) $\mathsf{DBLP}_{2\mathsf{hop}}$PQ operations per answer

| $\mathsf{k}=10$ | $\mathsf{k}=10^{2}$ | $\mathsf{k}=10^{3}$ | $\mathsf{k}=10^{4}$
---|---|---|---|---
four cycle | 25.2s | 26.8s | 29.6s | 37.4s
six cycle | 323.8s | 325.7s | 339.2s | 360.4s
eight cycle | 595.6s | 605.3s | 609.4s | 620.8s
bowtie | 598.2s | 604.7s | 610.89s | 625.8

(b) Cyclic query performance on IMDB dataset for different values of $k$ in
LIMIT clause. Ranking function is sum.

Figure 14. (left) DBLP empirical delay; (right) cyclic query performance on
IMDB

###  G.2. Large Scale Experiments

Lexicographic ordering. 12(e), 12(f), 12(g), 12(h) show the execution time of
the ranked two and three hop queries on Friendster and Memetracker datasets.
Similar to the small-scale datasets, lexicographic function is faster to
evaluate than sum function but all baselines engines were unable to complete
execution in the cutoff time.

###  G.3. Cyclic Query Description

In this subsection, we describe the cyclic queries used in the experimental
evaluation. Figure 13 shows the hypergraphs for the cyclic queries on DBLP
dataset. The queries are defined in a very similar way for all other real-
world datasets as well.

Four cycle. Find all co-author pairs who have been on at least two research
papers together ranked by sum of weights/lexicographic ordering.

Six cycle. For every author, find all research paper such that the there exist
at least two co-authors and the research paper contains both the co-authors.
Rank all the output author, research paper pairs by sum of
weights/lexicographic ordering.

Eight cycle. Find all co-author of co-author pairs who have been on at least
two different research papers together ranked by sum of weights/lexicographic
ordering.

Bowtie. Consider the materialized view $V(a_{1},a_{2})$ for the eight cycle
query. The bowtie query enumerates $Q=\pi_{a_{1},a_{3}}(V(a_{1},a_{2})\Join
V(a_{2},a_{3}))$ ranked by sum of weights/lexicographic ordering.