Joining like a pro

$$Q \coloneq R(x_1, x_2) \wedge S(x_1, x_3) \wedge T(x_2, x_3)$$

Joining like a brute

$$Q \coloneq R(x_1, x_2) \wedge S(x_1, x_3) \wedge T(x_2, x_3)$$

Disruptive poll

In theory, is it better to join like:

1. A pro
2. A brute

No confidence vote

1. Go home, you are not qualified to talk about joins after saying dumb things like that.
2. We are all theorist here, please tell us the whole story

What is wrong with joining like a pro

$$Q \coloneq R(x_1, x_2) \wedge S(x_1, x_3) \wedge T(x_2, x_3)$$

• It is known that if $|R^\mathbb{D}|, |S^\mathbb{D}|, |T^\mathbb{D}| \leq N$, then $|Q(\mathbb{D})| \leq N^{1.5}$.
• $R \bowtie S$ may have $N^2$ answers!

Worst scenario for query plans

Consider $\mathbb{D}$ on domain $D = D_1 \uplus D_2 \uplus D_3$ with:

• $0 \notin D$
• $|D_1|=|D_2|=|D_3|=N$.

• $|R^\mathbb{D}\bowtie S^\mathbb{D}| \geq N^2$, $|R^\mathbb{D}\bowtie T^\mathbb{D}| \geq N^2$, $|S^\mathbb{D}\bowtie T^\mathbb{D}| \geq N^2$
• $|Q(\mathbb{D})| = 0$.

And the brute?

Domain $D = D_1 \uplus D_2 \uplus D_3$ with $0 \notin D$ and $|D_1|=|D_2|=|D_3|=N$.

Worst-case optimal join

$$Q \coloneq R(x_1, x_2) \wedge S(x_1, x_3) \wedge T(x_2, x_3)$$

… unlikely to be possible.

$f(|Q|)$: data complexity, ie, $Q$ is considered constant. Ideally, $f$ is a reasonable polynomial though.

Worst case value

Consider a join query $Q$ and all databases for $Q$ with a bound $N$ on the table size: $$\mathcal{D}_{Q}^{\leqslant N}= \{\mathbb{D}\mid \forall R \in Q, |R^\mathbb{D}| \leqslant N\}$$ and let: $$\mathsf{wc}(Q, N) = \mathsf{sup}_{\mathbb{D}\in\mathcal{D}_{Q}^{\leqslant N}}~|Q(\mathbb{D})|$$

Worst case examples

• Cartesian product: $Q_2 = R_1(x_1) \wedge R_2(x_2)$ has $\mathsf{wc}(Q_2,N) = N^2$.
• Similarly: $Q_k = R_1(x_1) \wedge \dots \wedge R_k(x_k)$ has $\mathsf{wc}(Q_2,N) = N^k$.
• Square query: $Q_\square = R(x_1,x_2) \wedge R(x_2,x_3) \wedge R(x_3,x_4) \wedge R(x_4,x_1)$ has $\mathsf{wc}(Q_\square,N)=N^2$.
• Triangle query: $Q_\Delta = R(x, y) \wedge S(x, z) \wedge T(y, z)$, $\mathsf{wc}(Q_\Delta, N) = N^{1.5}$.
• The n-cycle: $Q_{C_n}(x_1,\dots,x_n) = R_1(x_1,x_2) \wedge R_2(x_2,x_3) \wedge \dots \wedge R_n(x_{n},x_1)$: $\mathsf{wc}(Q_{C_n})=N^\frac{n}{2}$.

Worst case optimal join (WCOJ) algorithms

A join algorithm is worst case optimal (wrt $\mathcal{D}_{Q}^{\leqslant N}$) if for every $Q$, $N \in \mathbb{N}$ and $\mathbb{D}\in \mathcal{D}_{Q}^{\leqslant N}$, it computes $Q(\mathbb{D})$ in time $$\tilde{O}(f(|Q|) \cdot \mathsf{wc}(Q,N))$$

• Data complexity model: $Q$ considered constant hence $f(|Q|)$ also.
• In this talk, $f$ will be a reasonable polynomial!

Existing WCOJ Algorithm

Rich literature:

• NPRR join (Ngo, Porat, Ré, Rudra, PODS12): usual join plans but with relations partitionned into high/low degree tuples.
• Leapfrog Triejoin (Veldhuizen, ICDT14)
• Generic Join (Ngo, PODS18): both branch and bound algorithms as ours but more complex analysis/data structures.
• PANDA (PODS17): handle complex database constraints, very complex, long analysis.

Algorithm reminder

Complexity analysis

Number of calls: example

Number of calls in general

Toward worst case optimality

Branch and bound complexity

$$|Q_i(\mathbb{D})| \leq wc(Q,N)$$

The complexity of the branch and bound algorithm is

Make the domain binary!

• $Q$ ⇝ $\tilde{Q}^b$ has $bn$ variables
• $\mathbb{D}$ ⇝ $\tilde{\mathbb{D}}^b$ for $b = \log |\mathsf{dom}|$. Database has roughly the same bitsize but size $2$ domain!

WCOJ finally

• To compute $Q(\mathbb{D})$ run simple branch and bound algorithm on $(\tilde{Q}^b, \tilde{\mathbb{D}}^b)$:
  • runs in time $\tilde{O}(m \cdot (n\log |\mathsf{dom}|) \cdot {\color{red}2} \mathsf{wc}(\tilde{Q}^{b}, N, 2))$
  • where $\mathsf{wc}(\tilde{Q}^{b}, N, 2)$ is the worst case for $\tilde{Q}^b$ on relations of size $\leq N$ and domain $2$.
  • $\mathsf{wc}(\tilde{Q}^{b}, N, 2) \leq \mathsf{wc}(Q,N)$ by reconverting back to larger domain.

More on Binarization

• Explicit binarization is not necessary: fix one bit of the variables at a time and filter $\mathbb{D}$.
• Using bigger bases (bytes, words etc.):
  • depth/width tradeoff
  • may be interesting in practice
  • Interesting base: $\log |\mathsf{dom}|$.

Problem statement

Given $Q$ and $\mathbb{D}$, sample $\tau \in Q(\mathbb{D})$ with probability $\frac{1}{|Q(\mathbb{D})|}$ or fail if $Q(\mathbb{D}) = \emptyset$.

Naive algorithm:

• materialize $Q(\mathbb{D})$ in a table
• sample $i \leq |Q(\mathbb{D})|$ uniformly
• output $Q(\mathbb{D})[i]$.

Complexity using WCOJ: $\tilde{O}(\mathsf{wc}(Q,N) poly(|Q|))$.

Let’s do a modular proof of this fact!

Revisiting the problem

Sampling leaves, the easy way

In our case, we do not know $\ell(t)$…

Sampling leaves with a nice oracle

Upper bound oracles for conjunctive queries

Wrapping up sampling

Given a super-additive function upperbounding the number of -leaves in a tree at each node, we have:

Las Vegas uniform sampling algorithm:

• each leaf /answer is output with probability $\frac{1}{ubp(t)}$ $=\frac{1}{wc(Q,N)}$
• fails with proba $1 - \frac{\ell(t)}{upb(t)}$$=1-\frac{|Q(\mathbb{D})|}{wc(Q,N)}$

Repeat until output: $O(\frac{upb(r)}{\ell(r)})$$=\frac{\mathsf{wc}(Q,N)}{1+|Q(\mathbb{D})|}$ expected calls.

Worst case and constraints

So far we have considered worst case wrt this class:

• $\mathcal{D}_{Q}^{\leqslant N}= \{\mathbb{D}\mid \forall R \in Q, |R^\mathbb{D}| \leqslant N\}$
• $\mathsf{wc}(Q,N) = \sup_{\mathbb{D}\in \mathcal{D}_{Q}^{\leqslant N}} |Q(\mathbb{D})|$

Each relation is subject to a cardinality constraint of size $N$.

What if we know that our instance has some extra properties (e.g., a functional dependency)

• We know $\mathbb{D}\in \mathcal{C}\subseteq \mathcal{D}_{Q}^{\leqslant N}$
• We want the join to run in $\tilde{O}(f(|Q|) \cdot \mathsf{wc}(Q,\mathcal{C}))$ where $\mathsf{wc}(Q, \mathcal{C}) := \sup_{\mathbb{D}\in \mathcal{C}} |Q(\mathbb{D})|$.

Finer constraints can help

$Q = R(x_1,x_2) \wedge S(x_2,x_3)$.

We have: $\mathsf{wc}(Q,N) = N^2$.

Prefix closed classes

Recall the complexity of our algorithm: $\tilde{O}(m |\mathsf{dom}| \sum_{i=1}^n |Q_i(\mathbb{D})|))$ where $Q_i = \bigwedge_{R \in Q} \prod_{x_1,\dots, x_i} R$

A class of database $\mathcal{C}$ for $Q$ is prefix closed for order $\pi = (x_1,\dots,x_n)$ if for each $i$ and $\mathbb{D}\in \mathcal{C}$:

$$|Q_i(\mathbb{D})| \leq \mathsf{wc}(\mathcal{C})$$

Our algorithm is (almost) worst case optimal as long as we use an order for which $\mathcal{C}$ is prefix closed!

Acyclic functional dependencies

$F = (X_1 \rightarrow Y_1, \dots, X_k \rightarrow Y_k)$ is a set of functional dependencies:

• $G(F)$: vertices are the variables and $x \rightarrow y$ if $x \in X_i$ and $y \in Y_i$ for some $i$.
• If $G(F)$ is acyclic, then let $\pi = x_1,\dots,x_n$ be a topological sort of $G(F)$. Then

$$\mathcal{C}_F^N = \{\mathbb{D}\mid \mathbb{D}\text{ respects $F$} \} \cap \mathcal{D}_{Q}^{\leqslant N}$$

is prefix closed for order $\pi$ (exactly the same proof as for cardinality constraints).

Hence our algorithm is worst case optimal wrt $\mathcal{C}_F^N$ (as long as we follow $\pi$).

We need to show that this functional dependencies transfer in the binarised setting but it is almost immediate.

Degree constraints

A degree constraint is a constraint $(X,Y,N_{Y|X})$ where $X \subseteq Y$. A relation $R$ verifies the constraint if

$$\max \{ |\prod_{Y} R[\tau]|, \tau \in \mathsf{dom}^X\} \leq N_{Y|X}$$

• Cardinality constraint = degree constraint with $X = \emptyset$.
• Functional dependency = degree constraint with $N_{Y|X} = 1$.

Acyclic degree constraints

$\Delta = \{(X_1, Y_1, N_{1}) \dots, (X_k, Y_k, N_k)\}$ set of degree constraints.

• $G(\Delta)$: vertices are the variables and $x \rightarrow y$ if $x \in X_i$ and $y \in Y_i$ for some $i$.
• If $G(\Delta)$ is acyclic, then let $\pi = x_1,\dots,x_n$ be a topological sort of $G(\Delta)$. Then

$$\mathcal{C}_\Delta^N = \{\mathbb{D}\mid \mathbb{D}\text{ respects $\Delta$} \} \cap \mathcal{D}_{Q}^{\leqslant N}$$

is prefix closed for order $\pi$ (exactly the same proof as for cardinality constraints).

Hence our algorithm is worst case optimal wrt $\mathcal{C}_\Delta^N$ (as long as we follow $\pi$).

We need to show that this functional dependencies transfer in the binarised setting but it is almost immediate.

Bonus: sampling acyclic degree constraints

We can find $(\lambda_R)$ such that $\prod_{R \in Q} |R^\mathbb{D}|^{\lambda_R} \leq \tilde{O}(\mathsf{wc}(Q, \mathcal{C}_\Delta^N))$ for any $\mathbb{D}\in \mathcal{C}_\Delta^N$ (polymatroid bound).

Define $upb(t) := \prod_{R \in Q} |R^\mathbb{D}[\tau_t]|^{\lambda_R}$:

• upperbound of $Q(\mathbb{D})[\tau_t]$ for any $\mathbb{D}\in \mathcal{C}_\Delta^N$,
• superadditive.

We have sampling with complexity $\tilde{O}(nm \cdot \frac{\mathsf{wc}(Q,\mathcal{C}_\Delta^N)}{1+|Q(\mathbb{D})|})$

Conclusion

• Simple algorithms and analysis
• Modular:
  • join is worst-case optimal as soon as the class is prefix closed
  • sampling is in $\frac{\mathsf{wc}(Q,\mathcal{C})}{|Q(\mathbb{D})|}$ as long as one can provide a super additive upper bound

Future work:

• Other classes such as:
  • cyclic FD,
  • general system of degree constraints (as PANDA)
• Explore dynamic ordering: can we capture more classes?