Fair intersection of seekable iterators

Michael Arntzenius · 2025

Read Fair intersection of seekable iterators by Michael Arntzenius (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-26016.txt.

Introduction

Michael Arntzenius, working alone, links two ideas from computing that seem far apart: fair search in a logic language and efficient database joins. The language miniKanren, a descendant of Prolog, gained fame for a complete yet efficient search that interleaves work fairly between alternatives. It bounds how much work goes to one branch before switching to the next.

Arntzenius shows that the same fairness by bounded work idea gives an elegant way to build worst case optimal joins. The method combines database tables with strong guarantees on running time. His approach uses a seekable iterator interface, where a reader can jump ahead in a sorted stream, and it fits a shallow embedding in functional languages.

Catalog record

CREATORMichael Arntzenius
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE22 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-26016

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fair intersection of seekable iterators Michael Arntzenius Abstract . miniKanren’s key semantic advance over Prolog is to implement a complete yet efficient search strategy, fairly interleaving execution between disjuncts. This fairness is accomplished by bounding how much work is done exploring one disjunct before switching to the next. We show that the same idea—fairness via bounded work—underlies an elegant compositional approach to implementing worst-case optimal joins using a seekable iterator interface, suitable for shallow embedding in functional languages. 1. Our approach and its scope This paper originates in early work towards the implemention of a relational programming language inspired by Datalog and modern database query engine techniques, in particular, worst-case optimal joins ( Ngo et al. 2012 ) and specifically Leapfrog Triejoin ( Veldhuizen 2014 ) . Join algorithms often have set intersection algorithms at their core. In implementing the ‘leapfrog’ intersection of Leapfrog Triejoin, we discovered it was not compositional—a k -way intersection cannot be decomposed into nested binary intersections without loss of performance. We show how to restore compositionality by borrowing a trick from miniKanren’s complete disjunctive search. This permits shallowly embedding efficient multi-way set intersection in a functional language. Although we do not describe it here, we have extended this to full conjunctive queries. In future we hope to extend it to full-fledged logic programming. We present our work in Haskell because algebraic data types clarify its presentation and laziness is convenient for representing potentially infinite search spaces. Neither is essential: any disciplined programmer can observe a typing discipline; any language with closures, objects, or similar features can encode laziness. 2. Fair union of streams When multiple rules apply to the current goal, Prolog tries them in order, exploring each to exhaustion before starting the next. If exploring a rule fails to terminate, later rules are not visited, and potential solutions they might generate are lost. If we think of goal-directed search as yielding a stream of solutions, Prolog implements disjunction between rules as stream concatenation. In Haskell, using laziness to represent possibly-infinite streams, we might implement this like so: ⬇ data Stream a = Empty | Yield a ( Stream a ) append Empty ys = ys append ( Yield x xs ) ys = Yield x ( append xs ys ) – keep focus on xs As we’ve hinted, concatenation is an incomplete search strategy: append xs ys will never visit ys if xs is infinite. We can fix this by interleaving xs and ys instead: ⬇ interleave Empty ys = ys interleave ( Yield x xs ) ys = Yield x ( interleave ys xs ) – swap focus to ys However, this is complete only if both streams are productive —they must not loop indefinitely without producing either Yield. Unfortunately, simple and desirable operations on lazy lists may not preserve productivity. For instance, a productive infinite list becomes unproductive if filtered to a finite subset. Consider the even prime numbers: ⬇ filter :: ( a -> Bool ) -> Stream a -> Stream a {- definition omitted -} primes = Yield 2 ( Yield 3 ( Yield 5 …)) {- full definition omitted -} evenPrimes = filter even primes twoThreeFour = interleave evenPrimes ( Yield 3 ( Yield 4 Empty )) Here, evenPrimes is equivalent to ⊥ , where \bot is an unproductive infinite loop. Because of this, twoThreeFour is equivalent to ⊥ ) ; the call to interleave gets stuck evaluating the \bot in evenPrimes before it can yield interleave is complete only when its arguments are productive. 0 0 footnotetext: This incompleteness afflicts the work of Kiselyov et al. 2005 . Their interleave is in effect the CPS translation of ours. We implemented twoThreeFour at type SFKT Identity Int and found that runIdentity (solve twoThreeFour) returned 2:3: \bot . More directly, if we let , then observe (evenOdds ‘interleave‘ return 0) is \bot , but observe (return 0 ‘interleave‘ evenOdds) is 0. To find a complete stream union operator, we make an analogy to fairness in concurrent programming, which means that ‘‘every process gets a chance to make progress, regardless of what other processes do’’ ( Owicki and Lamport 1982 ) , although it has no singular formal definition ( Kwiatkowska 1989 ; Völzer et al. 2005 ) . We can imagine streams as processes that make progress toward finding solutions when evaluated. In this analogy, stream union is a 2-to-1 multiplexing scheduler that allocates the time given to it between two sub-processes. Completeness requires fairness: one stream may not permanently block the other from making progress. Interleaving elements between streams is not sufficient, because finding the next element (or determining none exists) can require an infinite amount of work, blocking execution of the other stream. We therefore need all streams to yield control after doing at most finite work. Under lazy evaluation, we yield control when we produce a constructor. Therefore, we extend Later that yields control to the consumer without giving further information: ⬇ data Stream a = Empty | Yield a ( Stream a ) | Later ( Stream a ) Kanren ( Hemann and Friedman 2013 ) , which it implements as thunks; as Haskell is lazy, we need not explicitly thunk them. As in µKanren, we actually ensure a stronger property, which we will call Later, disallowing unbroken infinite repetition of TODO: intuitive justification for this. We can ensure this property conservatively by guarding all recursion with For instance, we must redefine primes to be equivalent to Later is unimportant so long as it occurs infinitely often. 0 0 footnotetext: In many cases it is possible to be less conservative, for instance in our definitions of union and filter below. There is a long line of work on type systems that ensure productivity by checking recursion is appropriately guarded which could be applied here, including Nakano 2000 , Birkedal et al. 2012 , and Atkey and McBride 2013 . Using this, we implement fair stream union (µKanren’s mplus): ⬇ union Empty ys = ys union ( Yield x xs ) ys = Yield x ( union xs ys ) -- keep focus on xs union ( Later xs ) ys = Later ( union ys xs ) -- swap focus to ys as well as filter (related to but less expressive than µKanren’s bind): ⬇ filter p Empty = Empty filter p ( Yield x xs ) = if p x then Yield x xs ’ else xs ’ where xs ’ = filter p xs filter p ( Later xs ) = Later ( filter p xs ) Note that union and filter preserve union acts as a cooperative scheduler, using filter and union, we can define twoThreeFour completely: ⬇ twoThreeFour = union ( filter even primes ) ( Yield 3 ( Yield 4 Empty )) If we assume primes is Yield 2 (Later ...), then twoThreeFour is equivalent to Yield 2 (Later (Yield 3 (Yield 4 \bot )) ) , where color indicates source: filter even primes generates the the blue terms Yield 2 , Later , \color[rgb]{0,0,1}\bot , while Yield 3 (Yield 4 Empty) generates the red terms Yield 3 , Yield 4 . Complete disjunction, then, is accomplished by bounding the work

Read the complete text