A Simple Algorithm for Worst Case Optimal Join and Sampling

A simple algorithm for joins

:::

Algorithm overview

Complexity analysis

Number of calls

Worst case value

Consider 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

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))

• For example, it has to compute Q_\Delta(\mathbb{D}) in time N^{1.5} where N is the largest relation in \mathbb{D}.
• Naive strategy (R(x,y) \bowtie S(y,z)) \bowtie T(x,z) may take N^2 >> N^{1.5}.

Existing WCOJ Algorithm

Rich literature:

• NPRR join (PODS 2012): usual join plans but with relations partitionned into high/low degree tuples.
• Leapfrog Triejoin
• Generic Join: both branch and bound algorithm as ours but more complex analysis or data structures.
• PANDA

Refining our previous analysis

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.

Problem

Given Q and \mathbb{D}, sample \tau \in Q(\mathbb{D}) with probability 1 \over |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)).

Let’s do a modular proof of this fact!

Revisiting the problem

Sampling leaves, the easy way

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:

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_{\tau \in \mathsf{dom}^X} \prod_{Y} R[\tau] | \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 {\mathsf{wc}(Q,\mathcal{C}_\Delta^N) \over 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 \mathsf{wc}(Q,\mathcal{C}) \over |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?