Acyclic Join Sampling Under Selections: Dichotomy, Union Sampling, and Enumeration

Fix a schema graph $𝒢=(𝒱,ℰ)$ whose size is assumed to be a constant, together with a subset $𝒵\subseteq 𝒱$. Let $𝒬$ be a join instance of $𝒢$. Given a tuple $𝒛$ over $𝒵$, define

namely, ${\sigma }_{𝒛}(\mathrm{𝐽𝑜𝑖𝑛}(𝒬))$ comprises the tuples $𝒖$ in the join result satisfying the conjunctive condition ${\bigwedge }_{Z\in 𝒵}𝒖(Z)=𝒛(Z)$. Given a tuple $𝒛$ over $𝒵$, a $(𝒢,𝒵)$-sampling operation returns a tuple chosen from ${\sigma }_{𝒛}(\mathrm{𝐽𝑜𝑖𝑛}(𝒬))$ uniformly at random, or returns nil if ${\sigma }_{𝒛}(\mathrm{𝐽𝑜𝑖𝑛}(𝒬))=\mathrm{\varnothing }$.

We call the above the $(𝒢,𝒵)$-sampling problem. A data structure is feasible if it uses $\tilde{O}(\text{IN})$ space and supports a sampling operation in $\tilde{O}(1)$ time where the notation $\tilde{O}(.)$ hides a factor polylogarithmic to IN.

Fix a schema graph $𝒢=(𝒱,ℰ)$ whose size is assumed to be a constant, as well as $m$ subsets ${𝒵}_1,$ ${𝒵}_2,\mathrm{\dots },{𝒵}_m$ of $𝒱$ for some $m\ge 1$. Let $𝒬$ be a join instance of $𝒢$. Given $m$ tuples ${𝒛}_1,{𝒛}_2,\mathrm{\dots },{𝒛}_m$ where ${𝒛}_i$ is over ${𝒵}_i$ for each $i\in [m]$, define

where ${\sigma }_{{𝒛}_i}(\mathrm{𝐽𝑜𝑖𝑛}(𝒬))$ is as defined in (2). In other words, ${\sigma }_{{𝒛}_1\vee \mathrm{\dots }\vee {𝒛}_m}(\mathrm{𝐽𝑜𝑖𝑛}(𝒬))$ includes all and only the tuples $𝒖$ in the join result that satisfy a condition given in a disjunctive normal form: ${\bigvee }_{i=1}^m\left({\bigwedge }_{X\in {𝒵}_i}𝒖(X)={𝒛}_i(X)\right)$. The value of $m$ is permitted to be arbitrarily greater than $2^{|V|}$, implying that ${𝒵}_1,$ ${𝒵}_2,\mathrm{\dots },{𝒵}_m$ need not be distinct¹¹1For example: SELECT * FROM Payment P, TaxPayer T WHERE P.ssn = T.ssn AND (T.job = “prof” OR T.job = “lawyer”). Here, both ${𝒵}_1$ and ${𝒵}_2$ are {job}..

Given $m$ tuples ${𝒛}_1,{𝒛}_2,\mathrm{\dots },{𝒛}_m$, a $(𝒢,{\bigvee }_{i=1}^m{𝒵}_i)$-sampling operation returns a tuple chosen from ${\sigma }_{{𝒛}_1\vee \mathrm{\dots }\vee {𝒛}_m}(\mathrm{𝐽𝑜𝑖𝑛}(𝒬))$ uniformly at random, or returns nil if ${\sigma }_{{𝒛}_1\vee \mathrm{\dots }\vee {𝒛}_m}(\mathrm{𝐽𝑜𝑖𝑛}(𝒬))=\mathrm{\varnothing }$.

We call the above the $(𝒢,{\bigvee }_{i=1}^m{𝒵}_i)$-sampling problem.

The following is a conjecture that has been extensively used in studying fine-grained complexities; see, e.g., [14, 18, 23, 24, 29, 30] and their references.

Strong Set Disjointness (SSD) Conjecture. Let $S_1,S_2,\mathrm{\dots },S_m$ be $m\ge 2$ sets whose elements are integers. Define $N={\sum }_{i=1}^m|S_i|$. In the set disjointness problem, we want to preprocess these sets into a data structure of $𝒮$ space such that, given any distinct integers $a,b\in [m]$, we can report in $𝒯=o(N)$ time whether $S_a\cap S_b=\mathrm{\varnothing }$. The SSD conjecture states that $𝒮$ must be $\mathrm{\Omega }(N^2/({𝒯}^{2}polylogN))$.

We investigate under the above conjecture the existence of feasible structures for Problem 1. It turns out that the answer depends on whether the schema graph $𝒢=(𝒱,ℰ)$ of $𝒬$ is “ext-$𝒵$-connex”, which is a notion introduced by Bagan, Durand and Grandjean [5]:

Our dichotomy result is:

Prior to our work, ext-$𝒵$-connexity has been used to prove dichotomies in several settings [5, 9, 10, 11, 12, 13, 21], all of which seem quite different from $(𝒢,𝒵)$-sampling. Interestingly, the dichotomy in Theorem 4 implies an approach to implement feasible $(𝒢,𝒵)$-sampling via “direct-access” queries. To explain, let $L$ be an ordering of the attributes in $𝒱$: $X_1,X_2,\mathrm{\dots },X_{|V|}$. This $L$ defines a lexicographic order $\prec$ on the tuples in $\mathrm{𝐽𝑜𝑖𝑛}(𝒬)$: ${𝒖}_{\mathrm{𝟏}}\prec {𝒖}_{\mathrm{𝟐}}$ if there is an $i\in [|V|]$ such that but ${𝒖}_{\mathrm{𝟏}}(X_j)={𝒖}_{\mathrm{𝟐}}(X_j)$ for all $1\le j\le i-1$. Given an integer $t$, a direct access (DA) query [6, 7, 12, 13] returns the $t$-th tuple of $\mathrm{𝐽𝑜𝑖𝑛}(𝒬)$ under $\prec$ if $t\in [|\mathrm{𝐽𝑜𝑖𝑛}(𝒬)|]$, or nil otherwise. As shown in [12], if $𝒢$ is ext-$𝒵$-connex, we can find an order $L$ such that

• $\mathrm{■}$

  the attributes of $𝒵$ form a prefix of $L$, i.e., $X_i\in 𝒵$ for every $i\in [|𝒵|]$;

• $\mathrm{■}$

  one can build a structure of $O(\text{IN})$ space that answers any DA query in $O(\log \text{IN})$ time.

Fix an arbitrary tuple $𝒛$ over $𝒵$. Crucially, the tuples in ${\sigma }_{𝒛}(\mathrm{𝐽𝑜𝑖𝑛}(𝒬))$ must be consecutive under $\prec$ (because $𝒵$ is a prefix of $L$). Thus, if ${\sigma }_{𝒛}(\mathrm{𝐽𝑜𝑖𝑛}(𝒬))\ne \mathrm{\varnothing }$, there exist integers $t_1$ and $t_2$ such that a tuple is in ${\sigma }_{𝒛}(\mathrm{𝐽𝑜𝑖𝑛}(𝒬))$ if and only if it is the $t$-th tuple under $\prec$ for some $t\in [t_1,t_2]$. With $O(\log \text{IN})$ DA queries, one can obtain the values of $t_1$ and $t_2$ (or certify their non-existence) via binary search. Then, a sample of ${\sigma }_{𝒛}(\mathrm{𝐽𝑜𝑖𝑛}(𝒬))$ can be drawn by generating a random $t\in [t_1,t_2]$ and issuing one more DA query. This supports a $(𝒢,𝒵)$-sampling operation in $O({\log }^2\text{IN})$ time.²²2We thank an anonymous reviewer for pointing out the connection to DA queries.

In this work, we show that the sample time can be reduced to constant:

Our core contribution to this problem is a new algorithm for a fundamental sampling problem:

Set Union Sampling: Let $S_1,S_2,\mathrm{\dots },S_m$ be $m\ge 2$ sets of elements drawn from a certain domain. Each $S_i$ ($i\in [m]$) supports three operations in constant time:

1. 1.

   (size) return $|S_i|$;

2. 2.

   (membership) check whether a given element is in $S_i$;

3. 3.

   (sampling) return an element of $S_i$ chosen uniformly at random.

The goal is to sample an element from ${\bigcup }_{i=1}^m{S}_i$ uniformly at random using only these operations. The sample obtained each time must be independent of all previous samples.

We will prove:

Currently the fastest expected sample time [13, 4] – as will be reviewed in Section 2 – is $O(\min \{m^2,m{\log }^{2}N\})$ where $N={\sum }_{i=1}^m|S_i|$, which we strictly improve. By combining Theorems 5 and 6 with additional ideas, we will prove:

The connexity requirement is necessary for $m\le {\text{IN}}^{0.49}$, as formally stated below:

Random enumeration of a query result produces a (uniformly) random permutation of the elements therein. An algorithm achieves a delay of $\mathrm{\Delta }$ if it can (i) output the first element or declare an empty result within $\mathrm{\Delta }$ time, and (ii) after the previous output, produce the next element or declare “no more” within an additional $\mathrm{\Delta }$ time. The algorithm ensures an expected delay $\mathrm{\Delta }$ if it satisfies the preceding requirement, except that the two “$\mathrm{\Delta }$ time” occurrences are replaced with “$\mathrm{\Delta }$ expected time”. By combining our sampling techniques with a new enumeration-to-sampling reduction, we prove:

Let us first prove the “if direction” ($\Leftarrow$). Consider an arbitrary tuple $𝒖\in {\sigma }_{𝒛}(\mathrm{𝐽𝑜𝑖𝑛}(𝒬))$. Clearly, $𝒖(A)=a$ and $𝒖(B)=b$. Since $A,X_1,X_2,\mathrm{\dots },X_{\mathrm{\ell }},B$ is a $𝒵$-path, there exist hyperedges $e_0,e_1,\mathrm{\dots },e_{\mathrm{\ell }}$ in $ℰ$ such that (i) $\{A,X_1\}\subseteq e_0$, (ii) $\{X_i,X_{i+1}\}\subseteq e_i$ for each $i\in [\mathrm{\ell }-1]$, and (iii) $\{X_{\mathrm{\ell }},B\}\subseteq e_{\mathrm{\ell }}$. We argue:

To see why, fix any $i\in [\mathrm{\ell }-1]$. As $𝒖\in {\sigma }_{𝒛}(\mathrm{𝐽𝑜𝑖𝑛}(𝒬))$, we know $𝒖[e_i]\in R_{e_i}$. As $X_i$ and $X_{i+1}$ are attributes outside $Z$, our construction of $𝒬$ ensures $𝒖(X_i)=𝒖(X_{i+1})$. The fact that this holds for every $i\in [\mathrm{\ell }-1]$ proves (6). By the construction of $𝒬$, $𝒖(X_1)$ is an element of $S_a$ and $𝒖(X_{\mathrm{\ell }})$ is an element of $S_b$. Therefore, (6) tells us $S_a\cap S_b\ne \mathrm{\varnothing }$.

Next, we prove the “only if direction” ($\Rightarrow$). Fix any $x\in S_a\cap S_b$. Construct a tuple $𝒖$ over $𝒱$ where $𝒖(A)=a,𝒖(B)=b,𝒖(Z)=\perp$ for every $Z\in 𝒵\setminus \{A,B\}$, and $𝒖(X)=x$ for every $X\in 𝒱\setminus 𝒵$. It suffices to prove that $𝒖\in {\sigma }_{𝒛}\mathrm{𝐽𝑜𝑖𝑛}(𝒬)$. Indeed, this is true because, for every $e\in ℰ$, our construction explicitly inserts tuple $𝒖[e]$ into $R_e$, noticing that $e$ cannot contain both $A$ and $B$. $◀$

The above lemma can be used to break the SSD-conjecture. Note that the input size of $𝒬$ satisfies $\text{IN}\le N\cdot |ℰ|=O(N)$, thus allowing us to build a structure of $\tilde{O}(\text{IN})=\tilde{O}(N)$ space on $𝒬$ to support a $(𝒢,𝒵)$-sampling operation in $\tilde{O}(1)$ time. A disjointness query parameterized by integers $a,b\in [m]$ can be answered as follows. First, create a tuple $𝒛$ over $𝒵$ such that $𝒛(A)=a$, $𝒛(B)=b$, and $𝒛(Z)=\perp$ for every $Z\in 𝒵\setminus \{A,B\}$. Then, issue a $(𝒢,𝒵)$-sampling operation and declare $S_a\cap S_b=\mathrm{\varnothing }$ if and only if the operation returns nothing. This correctly answers the query in $\tilde{O}(1)$ time.

We note that similar constructions were used in [5, 7] to prove dichotomies for settings different from ours. Our contribution lies in establishing connections to $(𝒢,𝒵)$-sampling.

By Definition 3.3, in this case there is a hyperedge $e^{\ast }\in ℰ$ satisfying $𝒵\subseteq e^{\ast }$. Now, root $𝒯$ at $e^{\ast }$, apply Lemma 3.2 to calculate the subjoin weights of all tuples in $R_{e^{\ast }}$ (the relation in $𝒬$ with schema $e^{\ast }$), and build a sampling structure of Lemma 3.2 by setting the symbol $e$ there to $e^{\ast }$. Given a tuple $𝒛$ over $𝒵$, define

It is easy to verify

Random sampling from ${\sigma }_{𝒛}(\mathrm{𝐽𝑜𝑖𝑛}(𝒬))$ can be done in a two-step approach similar to what was described at the end of Section 3.2. First, obtain a random tuple $𝑿\in R_{e^{\ast }}(𝒛)$ such that, for each $𝒖\in R_{e^{\ast }}(𝒛)$, we have

where $\mathrm{𝑠𝑢𝑏𝑗}\text{-}{w}_{e^{\ast }}(𝒖)$ is the subjoin weight of $𝒖$ (with respect to the rooted $𝒯$); see (5). As $|{\sigma }_{𝒛}(\mathrm{𝐽𝑜𝑖𝑛}(𝒬))|={\sum }_{𝒖\in R_{e^{\ast }}(𝒛)}|𝒖\bowtie \mathrm{𝐽𝑜𝑖𝑛}({𝒬}_{e^{\ast }})|={\sum }_{𝒖\in R_{e^{\ast }}(𝒛)}\mathrm{𝑠𝑢𝑏𝑗}\text{-}{w}_{e^{\ast }}(𝒖)$, this is an instance of weighted sampling since the $\mathrm{𝑠𝑢𝑏𝑗}\text{-}{w}_{e^{\ast }}(𝒖)$ value of every $𝒖\in R_{e^{\ast }}(𝒛)$ is already available. Hence, an alias structure on $R_{e^{\ast }}(𝒛)$ allows us to obtain $𝑿$ in constant time. Second, apply Lemma 3.2 to draw a uniformly random tuple from $𝑿\bowtie \mathrm{𝐽𝑜𝑖𝑛}({𝒬}_{e^{\ast }})$ in constant time.

The alias structure on $R_{e^{\ast }}(𝒛)$ occupies $O(|R_{e^{\ast }}(𝒛)|)$ space and can be built in $O(|R_{e^{\ast }}(𝒛)|)$ time, as explained in Section 3.1. We do this for every $𝒛\in {\mathrm{\Pi }}_{𝒵}(R_{e^{\ast }})$, where $\mathrm{\Pi }$ is projection in relational algebra. For distinct $𝒛,{𝒛}^{\prime }\in {\mathrm{\Pi }}_{𝒵}(R_{e^{\ast }})$, the sets $R_{e^{\ast }}(𝒛)$ and $R_{e^{\ast }}({𝒛}^{\prime })$ are disjoint. Hence, in total, all the alias structures occupy $O(|R_{e^{\ast }}|)=O(\text{IN})$ space and can be built in $O(\text{IN})$ expected time (the time is expected because hashing is required to obtain the sets $R_{e^{\ast }}(𝒛)$ of each $𝒛\in {\mathrm{\Pi }}_{𝒵}(R_{e^{\ast }})$).

Let $𝒯$ be an arbitrary join tree of $𝒢$. As $𝒢$ is ext-$𝒵$-connex, by Lemma 3.3, $𝒯$ defines a number $s\ge 1$ of $(𝒵,𝒯)$-components of $𝒢$ – denoted as ${𝒢}_1=({𝒱}_1,{ℰ}_1),\mathrm{\dots },{𝒢}_s=({𝒱}_s,{ℰ}_s)$, respectively – such that ${𝒢}_i$ is $({𝒱}_i\cap 𝒵)$-canonical for every $i\in [s]$. For each $i\in [s]$, define ${𝒵}_i={𝒱}_i\cap 𝒵$ and ${𝒬}_i=\{R_e\in 𝒬\mid e\in {ℰ}_i\}$. Note that ${𝒬}_i$ is a join instance of the schema graph ${𝒢}_i$, which is ${𝒵}_i$-canonical. Denote by ${\text{IN}}_i$ the input size of ${𝒬}_i$; we have ${\sum }_{i=1}^s{\text{IN}}_i=\text{IN}$ because every relation of $𝒬$ appears in exactly one of ${𝒬}_1,\mathrm{\dots },{𝒬}_s$. For each $i\in [s]$, we build a $({𝒢}_i,{𝒵}_i)$-sampling structure on ${𝒬}_i$ in the way explained for Case 1. All the $s$ structures occupy $O(\text{IN})$ space in total and can be built in $O(\text{IN})$ expected time.

Consider now a $(𝒢,𝒵)$-sampling operation, which is given a tuple $𝒛$ over $𝒵$. For each $i\in [s]$, defining ${𝒛}_i=𝒛[{𝒱}_i]$, we perform a $({𝒢}_i,{𝒵}_i)$-sampling operation using ${𝒛}_i$; let us assume that this operation returns ${𝒖}_i$. If ${𝒖}_i$ is nil for any $i$, we return nil for the original $(𝒢,𝒵)$-sampling operation. Otherwise, return ${𝒖}_1\bowtie {𝒖}_2\bowtie \mathrm{\dots }\bowtie {𝒖}_s$, which, as explained in Appendix B, must be a uniformly random tuple of ${\sigma }_{𝒛}(\mathrm{𝐽𝑜𝑖𝑛}(𝒬))$. The $(𝒢,𝒵)$-sampling operation takes $O(s)=O(1)$ time overall. This concludes the proof of Theorem 5.

Draw a random value $X\in [m]$ such that $\mathrm{𝐏𝐫}[X=i]=|S_i|/N$ for each $i\in [m]$. Then, use the sampling operation to draw an element $Y$ from $S_X$. Finally, carry out an acceptance step:

Acceptance Step: Accept $Y$ with probability $1/\mathrm{deg}(Y)$.

If accepted, $Y$ is returned; otherwise, the algorithm repeats from scratch.

The algorithm correctly returns a uniform sample of ${\bigcup }_{i=1}^m{S}_i$. To see why, fix an arbitrary element $y\in {\bigcup }_{i=1}^m{S}_i$. This element is returned if and only if three conditions are satisfied: (i) $X\in \text{InvS}(y)$, which occurs with probability $|S_X|/N$ for each $X\in \text{InvS}(y)$, (ii) $Y=y$, which occurs with probability $1/|S_X|$ conditioned on $X$, and (iii) $y$ is accepted, which occurs with probability $1/\mathrm{deg}(y)$ conditioned on $y$. Hence, the algorithm outputs $y$ with probability

which is identical for all $y\in {\bigcup }_{i=1}^m{S}_i$. As a corollary, in each repeat, the algorithm succeeds in returning a sample with probability $n/N$. Thus, $N/n$ repeats are needed in expectation.

The random value $X$ can be easily obtained in $O(m)$ time. One (logically simple) way to do so is to build an alias structure (see Section 3.2) on $|S_1|,|S_2|,\mathrm{\dots },|S_m|$ – namely, the $m$ set sizes – on the fly in $O(m)$ time (using the size operation), after which $X$ can be extracted from the structure in $O(1)$ time. The time to obtain $Y$ is $O(1)$ (using the sampling operation). The troublemaker, however, is the acceptance step. The standard approach [4, 13] is to query the membership of $Y$ in each $S_i$ ($i\in [m]$), which costs $O(m)$ time. This renders the overall sample time $O(mN/n)$ in expectation.

Our objective is to implement the acceptance step in $O(mn/N)$ expected time – note that this is faster than $O(m)$ by a factor of $N/n$, which eventually allows us to bring the expected sample time from $O(mN/n)$ down to $O(m)$.

Let us start with a fundamental fact:

The proposition is the total law of expectation in disguise; see Appendix C for a proof. Equipped with the above, implementing the acceptance step boils down to:

Given $x\in [m]$ and $y\in S_x$, generate a rand. var. $\mathrm{\Gamma }\in [m]$ with $𝐄[\mathrm{\Gamma }]=m/\mathrm{deg}(y)$.

Later, we will explain how to achieve the above purpose in $O(m/\mathrm{deg}(y))$ expected time. Once done, we can perform the acceptance step as follows (recall that, prior to this, the baseline method has obtained the values of two random variables $X$ and $Y$): (i) generate a uniformly random variable $U$ over $[m]$ in constant time; (ii) generate the aforementioned random variable $\mathrm{\Gamma }$ (setting $x$ and $y$ to the values of $X$ and $Y$, respectively) in $O(m/\mathrm{deg}(Y))$ expected time; (iii) accept if $U\le \mathrm{\Gamma }$.

Correctness follows from Proposition 5.1 (the acceptance probability is $\frac{1}{m}𝐄[\mathrm{\Gamma }]=1/\mathrm{deg}(Y)$, as desired). For a particular $x\in [m]$ and a particular $y\in S_x$, we have $\mathrm{𝐏𝐫}[X=x,Y=y]=\frac{|S_x|}{N}\frac{1}{|S_x|}=1/N.$ Thus, the expected cost of the acceptance step will be at the order of