Draft
The Order the Compiler Chose
Conversation 2.5 — Choosing a Plan and Testing Its Limits
The order the compiler chose
Let us test whether separate partners can always fit together. Bring back the two query shapes from 2.3, starting with the star:
shared_origin(a, b, c) :-
road(h, a),
road(h, b),
road(h, c).Number these body occurrences $E_1,E_2,E_3$, as before.
Let road contain just (0,1) and (1,0). What answers do we get?
For h=0, all three endpoints must be 1, giving (1,1,1). For h=1, they must all be 0, giving (0,0,0).
Each answer uses one common value of h across all three atoms.
Use the same two road tuples with the loop:
round_trip(a, b, c) :-
road(a, b),
road(b, c),
road(c, a).
Call the occurrences $E_1,E_2,E_3$. Start with (a=0,b=1) in $E_1$. Which $E_2$ tuple can join it?
(b=1,c=0). The first two atoms give the candidate (a=0,b=1,c=0).
What does $E_3$ demand of that candidate?
The road tuple (c=0,a=0). There is no (0,0) road, so the candidate fails.
Starting instead with (a=1,b=0) would require (1,1) at the end. That also fails. The answer is empty.
Before doing a full join, could we remove (a=0,b=1) from $E_1$ by semijoining with $E_2$? With $E_3$?
Neither removes it. It has a partner in each:
The two partners cannot be used together. One assigns c=0, the other c=1.
Check the other $E_1$ tuple, and then the tuples in $E_2$ and $E_3$. Would repeating all pairwise semijoins eventually remove something?
No. Swapping 0 and 1 gives the other tuple the same separate support, and the three atom positions are symmetric.
Every pairwise semijoin leaves its left relation unchanged. Another pass would have nothing new to use.
What made separate partners work for the star's tuple (h=0,a=1)?
shared_origin(a, b, c) :-
road(h, a),
road(h, b),
road(h, c).The partner in road(h,b) and the partner in road(h,c) both use h=0. Their other variables, b and c, are different query variables.
There is no additional agreement between those two choices waiting to fail.
Let us describe that structural difference. Arrange the star's three body occurrences in a tree:
Each rectangle below is a body occurrence. The links belong to the proposed tree; they are not the hyperedges in the previous picture.
Test this rule: for each variable, all atoms containing it must form a connected part of the tree. Does h pass? What about a,b,c?
h occurs in all three atoms, with no gap along either link. Each of a,b,c occurs in just one atom, so each passes too.
Try the same tree arrangement for the loop:
round_trip(a, b, c) :-
road(a, b),
road(b, c),
road(c, a).
Which variable fails the test?
a. It appears at the two ends, but the path between them passes through $E_2$, which has only b,c.
b and c each occur in two adjacent atoms, so they pass this particular arrangement.
That rejects one tree. Could a different middle atom repair it? Draw the two other choices before answering.
If $E_1$ is in the middle, c occurs at both ends and is missing in the middle. If $E_3$ is in the middle, b has that problem.
Every three-vertex tree has a middle vertex. Whichever atom we put there omits the variable shared by the endpoints. No tree passes.
What about a single three-variable atom?
stock_record(depot, item, day) :-
stocks_on(depot, item, day).
Call its occurrence $S$. Draw a join tree. Is the query acyclic?
Yes. Its join tree has one node.
All three variables occur in that one node.
Here is how to use a join tree for filtering. Choose a root. Going from leaves toward the root, filter each parent by its already processed child. Then, going outward from the root, filter each child by its parent.
Why would these two passes be enough? In the loop, separate partners still disagreed with each other.
If two branches share a variable, the join-tree rule puts that variable in every atom along the path between them. Matching along the path therefore carries the same value through both branches. The loop's disagreement crossed a gap that a join tree forbids.
Use the star tree with $E_2$ as root. Here the arrows point to the occurrence being filtered. Write the four semijoins in this order.
First filter the root by both leaves:
Then send its surviving choices back outward:
Each occurrence still has its own local schema, even though all three read road initially. Both leaves now use h values that survived at $E_2$.
Does the star's join tree tell us how many answers it has? Suppose the single origin 0 has roads to $m$ possible endpoints.
It can independently choose any endpoint for a, any for b, and any for c: $m^3$ answers.
An acyclic query can have a large output even after all unsupported tuples have been removed.
Acyclicity gives a filtering guarantee, but we still need to compare intermediate sizes. Consider the rule “Always start with two atoms sharing a variable.” How did that work in the first delivery instance of 2.1?
A connected first join produced four tuples, while the Cartesian first step produced sixteen.
Those counts came from the input, though, not from the drawing alone.
Test “always” on a different query:
answer(a, d) :-
R(a, b),
S(b, c),
T(c, d).
Use these complete inputs:
| $R$: a | b |
|---|---|
| A | 0 |
| $S$: b | c |
|---|---|
| 0 | 0 |
| 0 | 1 |
| 0 | 2 |
| 1 | 0 |
| 2 | 0 |
| $T$: c | d |
|---|---|
| 0 | D |
How many tuples does $R\bowtie S$ produce? How many does $S\bowtie T$?
Three each.
$R$ keeps the three $S$ tuples with b=0. $T$ keeps the three with c=0. Only (b=0,c=0) can survive both requirements, so the complete body has one tuple.
How many tuples does $R\times T$ produce? Then what does joining $S$ do?
The product contains just
| a | b | c | d |
|---|---|---|---|
| A | 0 | 0 | D |
$S$ checks the pair (b=0,c=0) and keeps it. It adds no columns.
Use the row-volume proxy $W_0$ from 2.1: add the tuple counts produced by the two binary combines. What are the totals?
A connected first join gives $3+1=4$. Product first gives $1+1=2$.
Product first gives a lower $W_0$ here. What happens to the number of columns it carries?
Check the columns. Apply our safe-projection rule after the first combine in each order.
After $R\bowtie S$, we can keep just a,c: two columns and three rows. After $S\bowtie T$, we can keep b,d: also two columns and three rows.
After $R\times T$, all four columns are needed: a,d for the head and b,c for $S$. Fewer rows can still mean more columns.
Can we always find some order that avoids a large wasted intermediate?
Let us test that with the loop query:
round_trip(a, b, c) :-
road(a, b),
road(b, c),
road(c, a).Call the occurrences $E_1,E_2,E_3$ in written order. Keep the same query hypergraph:
Enlarge the input road to
| from | to |
|---|---|
| 0 | 1 |
| 1 | 0 |
| 0 | 2 |
| 2 | 0 |
How many candidates come from $E_1\bowtie E_2$?
Six:
| a | b | c |
|---|---|---|
| 0 | 1 | 0 |
| 0 | 2 | 0 |
| 1 | 0 | 1 |
| 1 | 0 | 2 |
| 2 | 0 | 1 |
| 2 | 0 | 2 |
Which survive the final road(c,a) test?
None. The first two need the missing road (0,0). The other four need a road between two nonzero endpoints. Every stored road has 0 at one end, so those are missing too.
For a positive integer $k$, generalize that input to
Each atom has $2k$ tuples. Count the first join by separating b=0 from b being nonzero.
With b=0, there are $k$ choices for a and $k$ for c, making $k^2$ candidates.
With nonzero b, there are $k$ choices for b, and both a and c must be 0. That adds $k$.
The first join has $k^2+k$ tuples. The complete join is still empty.
Could choosing a different first pair avoid that intermediate? Could projection or pairwise semijoins rescue this instance?
Every pair of loop atoms has the same arrangement after renaming the variables. On this symmetric input, every first binary join has $k^2+k$ tuples.
All three variables are in the head, so projection cannot discard them. Every tuple still has a partner in each other atom, so pairwise semijoins remove nothing.
The tie uses both this query's symmetry and the chosen input. Different data can favor a different order even on the same graph.
But here every first pair builds candidates the third atom rejects. Could that third atom help reject them while we construct them?
That is the direction of multiway join algorithms, including worst-case optimal joins: use several constraints while constructing candidates. We still need an algorithm and a bound on its work to make that promise precise.
For this input, changing which pair goes first cannot solve the problem.
For now, make one justified choice with the tools we have. Return to
eligible(driver, job) :-
based_at(driver, depot),
stocks(depot, item),
needs(job, item).Use the first delivery instance from 2.1 and 2.4, and keep only answers with job=job1.
Start from $N'=\sigma_{job=job1}(N)$. Give the complete sequence, including safe projections.
Select the one job1 tuple; join it with $S$; keep job,depot; join $D$; then keep the head columns.
Explain the first projection without using the row counts.
After $S\bowtie N'$, the item agreement has been checked. The remaining $D$ uses depot, and the head uses job. Neither needs item.
That argument does not need the row counts.
Now use the row counts. Compare starting with $D\bowtie S$ instead.
Starting with $S\bowtie N'$ gives combine outputs of 1 and 2 tuples, so $W_0=3$.
Starting with $D\bowtie S$ gives 4 tuples and then 2 after joining $N'$, so $W_0=6$. Safe projection does not merge any of those tuples here.
The restriction makes starting near $N$ attractive on this instance.
The variable overlaps identify the matches; remaining uses justify the projections; row counts compare the intermediates. A join tree gives an additional guarantee when we use its semijoin passes.
Have we established the cheapest physical execution?
No. We have justified the same answers and a lower $W_0$ on this input. The cost of executing each operation still depends on storage, access methods, and tuple representation.