The Order Logic Did Not Choose
Conversation 2.1 — From Equivalent Plans to Intermediate Work
The order logic did not choose
Before choosing an algebraic tree, consider a delivery service. These are its recorded facts:
A driver is eligible for a job when the driver's depot stocks the item that the job needs. Is Lin eligible for job1?
Yes. Lin reports to north, north stocks bolt, and job1 needs bolt. Those three facts connect Lin to job1.
Is Lin eligible for job3?
No. job3 needs nut, but Lin's depot stocks bolt.
Now find every eligible driver–job pair. If you begin with the drivers, how would you organize the reasoning?
For each driver, find the driver's depot, then the item stocked there, and finally the jobs needing that item. Lin and Moe reach job1 and job2 through north and bolt; Nia and Omar reach job3 and job4 through south and nut.
How would you organize the reasoning starting from the jobs?
Yes. For each job, find its required item, then the depot stocking that item, and finally the drivers based at that depot. The reasoning runs in the opposite direction but produces the same eight driver–job pairs.
Consider a third correct method: first pair every driver with every job, and only afterward check whether the driver's depot stocks the required item. How many pairs exist before that check?
There are four drivers and four jobs, so it begins with sixteen pairs. Eight survive after the depot and item facts are checked.
Write the eligibility condition as a conjunctive query.
eligible(driver, job) :-
based_at(driver, depot),
stocks(depot, item),
needs(job, item).Let \(D,S,N\) be the local atom expressions for based_at, stocks, and needs. Their schemas are
D = {driver, depot}
S = {depot, item}
N = {job, item}.Throughout this conversation, each displayed body-join tree is followed by the query's common head projection. We compare the body-join trees because that projection is identical for both orders.
Translate the driver-first reasoning into relational algebra. How many tuples does each join produce on this instance?
The expression is
The first join produces four (driver, depot, item) tuples: one stocked item for each driver. Joining needs produces eight complete valuations. Its join-output sizes are 4, 8.
And the job-first reasoning?
It is
The first join produces four (depot, item, job) tuples: one supplying depot for each job. Joining based_at produces the same eight complete valuations. Its join-output sizes are also 4, 8.
Before translating the third method, which shared variable could the natural join of D and N require agreement on?
None. D contains {driver, depot}, while N contains {job, item}. The stocks atom S is the only atom connecting depot to item.
With no shared variable, what does the natural join of D and N produce on this instance?
It produces their Cartesian product: every one of the four D tuples combines with every one of the four N tuples, giving sixteen tuples.
Now write the complete expression.
It is
The final join removes the unsupported pairs and leaves the same eight complete valuations. Its join-output sizes are 16, 8.
What information did those extra product tuples lack?
They had a driver, that driver's depot, a job, and that job's item, but no fact yet established that the depot stocked the item. The product carried all sixteen possibilities until stocks could reject eight of them.
The output of a nonfinal expression is called an intermediate relation. After the common head projection, all three body-join trees return the same eight answers. Why should we care that this one first produced sixteen tuples?
Because the final join must receive and check all sixteen candidates against stocks. Eight were constructed and carried forward only to be rejected.
In \((D\bowtie S)\bowtie N\), stocks is checked earlier. Only four supported (driver, depot, item) tuples reach the final join, which extends them into eight complete valuations.
Compute the proxy for the three plans.
The two shared-variable plans each give
while the Cartesian-first plan gives
Return to eligible, but change only its input instance. Suppose D, S, and N each contain three tuples. Both possible first joins share a variable and add an attribute. Must their first outputs therefore have the same cardinality?
I would expect so. With three tuples on each side, perhaps each first join also produces three tuples.
Here is the instance:
based_at stocks needs
(Lin, north) (north, bolt) (job1, bolt)
(Moe, north) (north, screw) (job2, bolt)
(Nia, south) (south, nut) (job3, nut)Trace D joined with S one shared depot value at a time.
For north, two drivers agree with two stocked items, producing four tuples. For south, one driver agrees with one stocked item, producing one more. Thus D joined with S produces five tuples:
(Lin, north, bolt)
(Lin, north, screw)
(Moe, north, bolt)
(Moe, north, screw)
(Nia, south, nut)Now trace S joined with N by item.
bolt produces two tuples, screw produces none, and nut produces one. Thus S joined with N produces three tuples:
(north, bolt, job1)
(north, bolt, job2)
(south, nut, job3)After the common head projection, both body-join trees return five driver–job pairs. Compare their logical row volumes.
The driver-first plan has join-output sizes 5, 5, so \(W_0=10\). The job-first plan has sizes 3, 5, so \(W_0=8\).
All three input relations had cardinality three, but the first joins had cardinalities five and three. Join cardinality depends on how many tuples agree at each shared value, not only on the input relation sizes.
The ordinary first joins above both added attributes. Now change the query; approved uses only a variable already present in handles:
approved_task(person, task) :-
member(person, team),
handles(team, task),
approved(task).Its instance is
member handles approved
(Ana, red) (red, build) (build)
(Ben, red) (red, test) (ship)
(Cy, blue) (blue, ship)Which handles tuple has no matching approved fact?
(red, test). The approved relation contains build and ship, but not test.
If member joins handles before that tuple is removed, how many tuples reach the final approved join?
Five:
(Ana, red, build)
(Ana, red, test)
(Ben, red, build)
(Ben, red, test)
(Cy, blue, ship)The unapproved test tuple has combined with both red-team members.
Instead join handles with approved first. What reaches the member join?
Only the two supported tuples:
(red, build)
(blue, ship)After the common head projection, both body-join trees return (Ana, build), (Ben, build), and (Cy, ship). Compare their logical row volumes.
Joining member with handles first gives sizes 5, 3, so \(W_0=8\). Joining handles with approved first gives sizes 2, 3, so \(W_0=5\). The second plan removes (red, test) before it can expand into two tuples.
Three join-order effects
After the common head projection, each pair of body-join trees below returns the same final relation. The order changes which complete valuations are produced before that projection.
| First-step situation | Comparison on the observed instance | Effect of the order |
|---|---|---|
| No shared variable | D joined with S: 4, 8, \(W_0=12\); D times N: 16, 8, \(W_0=24\) | With no agreement to check, the first step creates a Cartesian intermediate. |
| Shared variables and both joins add attributes | D joined with S: 5, 5, \(W_0=10\); S joined with N: 3, 5, \(W_0=8\) | Equal input sizes can still produce different join cardinalities because shared values occur with different frequencies. |
| Shared variable and the right side adds no attribute | member joined with handles: 5, 3, \(W_0=8\); handles filtered by approved: 2, 3, \(W_0=5\) | The semijoin prefilter removes (red, test) before it expands across two members. |