Draft
The Tuple That Waited
Conversation 3.2 — Iterators and the State Between Results
The tuple that waited
Keep the cinema instance from 3.1. Here it is in physical arrays, with positions written beside the tuples.
| Position | Movies: Title | Director | Actor |
|---|---|---|---|
| 0 | filmA | Bergman | actor1 |
| 1 | filmA | Bergman | actor2 |
| 2 | filmB | Other | actor3 |
| Position | Pariscope: Theater | Title | Schedule |
|---|---|---|---|
| 0 | Champo | filmA | 18:00 |
| 1 | Champo | filmA | 21:00 |
| 2 | Rialto | filmB | 20:00 |
| Position | Location: Theater | Address | Phone |
|---|---|---|---|
| 0 | Champo | addr1 | phone1 |
| 1 | Rialto | addr2 | phone2 |
This time ask for the actor, showing time, and address:
appearance(c, s, a) :-
Movies(t, d, c),
Pariscope(h, t, s),
Location(h, a, p).How many answers?
Five. Each of actor1 and actor2 has two showing times at addr1. Actor3 has one at addr2.
Changing the head made the showings visible. In theater_address, several of these witnesses gave the same answer.
Use the plan from 3.1: scan Movies, look up Pariscope by Title, then look up Location by Theater. Call the first join $J_1$ and the second $J_2$.
The consumer wants to inspect one answer, then decide whether to ask for another. How would you give $J_2$ its input?
The algebra gives $J_1$ a relation as its result. So I would first put that relation in an array, then let $J_2$ read it.
Suppose that intermediate has a million matches, and the consumer stops after the first answer. What did the array strategy commit us to?
Producing and storing all million intermediate tuples before $J_2$ could even start. Much of that work might never be used.
Could $J_2$ ask for just one match now, and another only if it needs it?
To find the address for the first showing, which of the other four matches does $J_2$ need?
None. Once $J_1$ has (filmA,Bergman,actor1,Champo,18:00), $J_2$ has the Theater value it needs.
We could pass that tuple on. But where does $J_1$ wait while $J_2$ uses it? If I simply restart it on the next request, I will get the same match again.
Start with an easier computation. A Movies scan has returned $M_0$. What must it remember to answer another request?
Position 1, the next unread position. It need not copy the whole relation.
Write every transition for this three-element array. Let Some(u) mean one returned tuple and None mean exhaustion. Return the new position alongside the result.
| Old position | Result | New position |
|---|---|---|
| 0 | Some(M₀) | 1 |
| 1 | Some(M₁) | 2 |
| 2 | Some(M₂) | 3 |
| 3 | None | 3 |
Position 3 stays at 3. Another request cannot invent another movie.
Replace Movies by a fixed array $R$ of length $n$, including $n=0$.
The state is $i\in\{0,\ldots,n\}$, initially 0, and
With an empty array, the first request is already the second case.
Now open the Title lookup for filmA. Its matching Pariscope positions are $K=[0,1]$. What is its state?
An offset $q$ in that sequence: 0, then 1, then 2 for exhaustion. At offset $q<2$, it fetches $P_{K[q]}$ and advances $q$.
For filmB, $K=[2]$. Is its initial state 2?
No. Its initial offset is 0. The first fetch is $P_{K[0]}=P_2$.
The position inside the match list and the position inside Pariscope are different numbers.
Does an arbitrary Pariscope iterator let us ask for filmB?
It only promises the next result of the computation it already represents. We need an additional operation that accepts a Title and starts the right computation.
$J_1$ has just returned $M_0\bowtie P_0$. Can it now forget $M_0$?
Yes, the Movies scan has moved to position 1.
Who will produce $M_0\bowtie P_1$?
Oh. $J_1$ still owes actor1 the 21:00 showing. It must keep $M_0$ while the Title lookup advances.
Its child scan is already past $M_0$, but its own work with $M_0$ is not finished.
Give $J_1$ three possible situations: it needs an outer tuple, it is matching a retained outer tuple, or it is done. What happens in each?
In Need, request the next Movies tuple. If there is one, retain it and initialize its Title lookup. Otherwise become Done.
In Match, request the next tuple of that lookup. Return the combined tuple if there is one. Otherwise return internally to Need.
In Done, return None.
Suppose an outer movie has no showing. Should that failed lookup make $J_1$ return None?
No. Other movies may still have showings. One call to $J_1$ must continue through empty lookups until it finds a result or exhausts its outer input.
Now use $J_1$ as $J_2$'s outer iterator. What changes in that definition?
The outer child becomes $J_1$. The retained tuple now contains both movie and showing attributes. Its Theater initializes a Location lookup.
$J_2$ can use the same algorithm without knowing how $J_1$ produces tuples.
Request the first answer, then the second. Record the source positions used and what remains pending.
| Request | Witness | Pending work after the return |
|---|---|---|
| 1 | $(M_0,P_0,L_0)$ | $J_1$ retains $M_0$, next Title-match offset 1; $J_2$'s current Location lookup is exhausted |
| 2 | $(M_0,P_1,L_0)$ | $J_1$ retains $M_0$, next Title-match offset 2; $J_2$'s new Location lookup is exhausted |
The answers are (actor1,18:00,addr1) and (actor1,21:00,addr1). The second request did not advance the Movies scan.
And the third?
The exhausted Location lookup sends $J_2$ back to $J_1$. Its exhausted Title lookup makes $J_1$ request $M_1$, then initialize another filmA lookup at offset 0.
The witness is $(M_1,P_0,L_0)$, giving (actor2,18:00,addr1). The same Title does not make the two actors interchangeable.
What whole intermediate relation did we store?
None. Each join retained its current outer tuple and inner progress. The indexes and backing arrays already existed.
The relation denoted by $J_1$ is still well defined, even though we never put all of it in one array.
Now the consumer wants all five matches. It calls $J_1$ five times for tuples and once more to discover exhaustion. Suppose each return crosses an operator boundary with some fixed overhead. How could we cross that boundary less often without collecting the entire result?
Return a bounded group of results per request. We would keep the ability to resume, but share that overhead among several tuples.
We would also make the caller wait for a group. The useful group size depends on the consumer and the implementation.
Use a capacity of three. Where does the first group end?
Its matching source-position pairs are
batch 1: (0,0), (0,1), (1,0)
batch 2: (1,1), (2,2)After batch 1, $M_1$ still has one showing left. The batch boundary must save that pending match. Two calls return data, and a third discovers exhaustion, under this same explicit end-of-stream protocol.
Call such a group a batch. Did it reduce the number of movie–showing matches that the query requires?
No. All five remain. The change amortizes the boundary overhead; it does not remove a relational result or guarantee a lower total running time.
Does collecting three scalar results already make the computation vectorized?
It changes the unit passed to the caller. To compute over column vectors, we must also change the work inside the batch.
And a final batch can be short. We cannot throw away its two results.
Suppose Pariscope has no index. Could a hash join still offer next?
Yes, after building a temporary table. Its private state would include that table as well as its probe progress.
The interface does not promise that preparation is cheap, or that every join uses an index supplied beforehand.
Our consumer stops after two answers. The operator still owns its temporary table and open input. If it releases them only when next reaches None, what happens?
The consumer will never make that call. We need a separate way to release resources when it stops early.
Preparation must happen before the first request, and cleanup must be possible without requesting another result.
Volcano names those operations open and close. Does close mean “run the query to exhaustion”?
No. It means release the resources this instance owns. Exhaustion and cleanup are different events.
One last change. Location gains another tuple for Champo, with a different address. What must $J_2$ do after returning the first address?
Keep its current $J_1$ tuple and finish that Location lookup before asking $J_1$ for another showing. Otherwise it loses the second address.
Every level has its own unfinished work.
If we return to the old head (h,a), can projection simply return one pair for every witness?
That would repeat (Champo,addr1) four times. Our relations are sets, so the result still needs duplicate elimination.
Streaming the witnesses did not change what projection means.
Resumable evaluation
A pull plan lets a consumer request the next result of an operator. Each operator retains the progress needed to resume. A request may cause many internal reads and may pass through several children before producing one result. An empty inner lookup is not exhaustion of the enclosing join.
For the chosen indexed plan, keyed access initializes an inner iterator, and the join retains its outer tuple until that iterator ends. Composition does not require materializing each logical intermediate. Batch boundaries must preserve the same unfinished work. Access capabilities, join algorithms, processing units, and lifecycle protocols remain distinct choices, all subject to the query's original set semantics.