Push ifs up, fors down: a blog post ties the idiom to query planning and category theory

The post starts from a recommendation in TigerBeetle's Tiger Style document: keep all switch and if statements in the parent function, move non-branchy logic into helper functions, and let one function handle all control flow. In the document's words, 'push ifs up and fors down'. The post reads this as moving conditionals toward the caller or earlier in a pipeline, and loops toward batch processing, a tight branch-free loop. It says matklad has also blogged about the principle.

The post describes matklad's two moves with an example. Pushing an if up: instead of frobnicate(walrus: Option) unpacking the option inside, the caller handles the None case and the function takes a plain Walrus. The function's type then states its precondition and the input space narrows, which acts as a form of filtering. Pushing a for down: instead of calling frobnicate(walrus) in a loop, provide frobnicate_batch(walruses) with the loop inside, so the hot loop runs without a branch and is a candidate for vectorization. The moves compose. Given a Vec<Option>, the caller drops the Nones with filter_map and collects a Vec, and frobnicate_batch never sees a None.

The first extension is to relational databases. In SQL query planning, projections and selections should run as early as possible and joins be deferred, so that joins run on the smallest inputs the query semantics allow. The vocabulary is upside-down: a query plan is a tree with table scans at the leaves, data flows up, so 'down the tree' means 'earlier in execution'. An optimizer that pushes a predicate down is doing what the rest of the post calls 'up' or 'early'. Projections cut the width of the data, selections (WHERE) cut the rows. The 'for' side corresponds to vectorized or batch execution. Volcano-style execution calls each operator once per tuple through a virtual next(). Vectorized execution calls each operator once per batch of a thousand or so tuples and runs a tight loop inside. That is frobnicate versus frobnicate_batch in a query engine: per-call overhead and per-call decisions are paid once per batch, and the inner loop is branch-light and cache-friendly.

The second extension is to functional programming and category theory. A predicate p : A -> Bool defines the subset {a in A | p a} with an inclusion morphism, which is a subobject; the hooked arrow marks a monomorphism, an injective function in Set. Before the rewrite, the callee takes any A and runs the test inside; after, the caller runs the test and the callee's input type is the subset, represented in code as Walrus instead of Option. Option is the coproduct 1 + Walrus. A function out of a coproduct is, by its universal property, a pair of functions, one per summand, and pushing the if up factors that pair apart: the caller handles the 1 summand and the core function is the Walrus component.

The post then treats 'filter before you map'. The expressions filter p (map f xs) and map f (filter p xs) are not equivalent, because in the first p inspects the output of f and in the second the input. The law that relates them is filter p . map f == map f . filter (p . f). It follows from parametricity. The post factors filter through Maybe: keep p x returns Just x if p x holds, otherwise Nothing, and filter p = catMaybes . map (keep p). filter p itself is not a natural transformation, since p fixes the element type, but catMaybes is, with map g . catMaybes == catMaybes . map (fmap g). A short calculation using keep p . f == fmap f . keep (p . f) and that naturality gives the law. The right-hand side is not automatically cheaper, since filter (p . f) still computes f for every element. It pays off when p . f simplifies to a cheap predicate q on the input, typically because p inspects a part of the value that f leaves alone. Then f runs only on survivors. Both sides remain a single O(n) pass; the saving is the calls to f on elements that would be discarded.

The summary lists the constraints. Taking an if out of a loop is valid when the condition is loop-invariant; a per-element condition cannot leave the loop and can only move to the boundary, recorded in a type such as Walrus instead of Option. Pushing a selection below a join is valid when the predicate references columns from only one side of the join. Filtering before mapping is valid via the law above and saves work only when p . f reduces to a cheap predicate on the input. The post concludes that algebra tells you which rewrites are legal, and in the filter/map case the naturality of catMaybes drives that legality. The fors-down part is more about cost than equivalence: you change the arrow from A -> B to [A] -> [B] so the setup cost is paid once per batch.

Key facts

The idiom comes from TigerBeetle's Tiger Style: keep control flow in the parent function and push ifs up and fors down; matklad has also blogged about it.
Pushing an if up means the caller handles None and the function takes a plain Walrus; pushing a for down means frobnicate_batch(walruses) with the loop inside, a candidate for vectorization.
In query plans, 'pushing down' a predicate means evaluating it earlier; vectorized execution calls each operator once per batch of a thousand or so tuples instead of once per row.
The law filter p . map f == map f . filter (p . f) holds by parametricity and the naturality of catMaybes, but the rewritten side still computes f for every element unless p . f reduces to a cheap predicate.
Legality conditions: the if must be loop-invariant to leave a loop, and a selection can go below a join only if the predicate touches columns from one side of the join.

Why it matters

The post takes a rule of thumb from a style guide and explains why it works in terms of two other fields. The database view shows the same shape in query planning: filter early, join late, process in batches. The functional view shows what is actually being claimed: moving a condition to the caller narrows the callee's input type, and moving a loop down changes the arrow from A -> B to [A] -> [B] so setup cost is paid once per batch. It also makes clear that the ifs-up half is about where a decision lives, while the fors-down half is about cost.

Who it affects

Programmers who structure functions and loops, especially in performance-sensitive code where a branch-free inner loop matters. The database material is relevant to anyone reading query plans or building query engines. The category theory section is aimed at readers who like to reason about code algebraically; the code examples (Rust-style Option and Vec, Haskell-style filter and map) are readable without it.

How to use it

Where a function branches on an optional input, move the branch to the caller and give the function a plain type. Where a function is called in a loop, offer a batch version with the loop inside. Compose them: discard the Nones and unwrap in the caller, then pass the resulting collection to the batch function. In queries, apply selections and projections below joins. When rewriting filter after map, use filter p . map f == map f . filter (p . f), and expect real savings only when p . f reduces to a cheap predicate on the input.

How solid is it

This is an explanatory essay, not a study. The post gives no benchmarks or measured speedups. The functional programming section shows its derivation step by step, and the database claims describe well-known planning practice in general terms without naming specific systems; the post does not say which database engines use vectorized execution, and the batch size of a thousand or so tuples is approximate and not tied to a particular engine. The post cites Tiger Style first for the idiom and does not say whether matklad's post is its origin.

Risks and caveats

The rewrites are conditional. An if can leave a loop only if its condition is loop-invariant; a per-element condition cannot, and can only move to the boundary as a type. A selection can be pushed below a join only if its predicate references columns from one side. Filter before map is not automatically cheaper, since filter (p . f) still calls f on every element. Both versions of that rewrite are a single O(n) pass, so the gain is only the avoided calls to f. The fors-down change is justified by cost, not equivalence, so it needs a real setup cost to amortize.

“push ifs up and fors down”

— Tiger Style document, TigerBeetle