Programmers increasingly write database queries as reusable functions. A security filter, a "join through the ownership chain" helper, or a mapping template takes a query as input and returns a new query. These are called query functionals: higher-order functions whose arguments and results are queries rather than data. Current systems handle them by expanding every call into a flat SQL query, then optimizing it. Databases also carry integrity constraints, such as primary keys, foreign keys, and inclusion dependencies. A good optimizer can use these rules to delete joins that cannot change the answer. The two ideas have never been joined in a working system. The one engine that compiles higher-order templates to SQL shares repeated subqueries but knows nothing about constraints. The constraint-based optimizers accept only flat first-order queries, and they choke when those queries are large.
We propose to give each parameter of a query functional a constraint signature: a small set of keys, foreign keys, and inclusions that any argument is promised to satisfy. The body of the functional is then optimized once, symbolically, with the parameter treated as an unknown relation that obeys its signature. The result is a simplified functional that is provably equivalent for every conforming argument. It can be reused at every call site, and the only check at each call is that the argument meets the signature. Optimization cost then scales with the size of the template rather than the size of its expansion. The open question is how much optimization power this modular approach gives up compared with optimizing each fully expanded query, which is the correct but unscalable alternative. This note is built around measuring that tradeoff.
Core Claim
Let a functional be $F = \lambda q.\,B(q)$, where $B$ is a positive relational query that mentions the parameter $q$ alongside base relations. Let $\Sigma$ be the database constraints and $\Sigma_q$ the signature of $q$. Treat $q$ as a fresh relation symbol and run chase-and-backchase on $B$ under $\Sigma \cup \Sigma_q$. The chase adds every fact the constraints imply. The backchase then searches that enlarged query for minimal equivalent subqueries. Together they produce a smaller body $B'$. The central soundness fact is short. Take any argument query $Q$ and any database $D$ satisfying $\Sigma$ such that $Q(D)$ satisfies $\Sigma_q$. Extending $D$ with $q := Q(D)$ gives an instance of $\Sigma \cup \Sigma_q$, on which $B$ and $B'$ agree. So $B'(Q) \equiv B(Q)$ on every such database. What remains is to certify that $Q$ satisfies $\Sigma_q$. We make that certification compositional: each optimized functional also exports an output signature, which is the set of constraints its result is guaranteed to satisfy, inferred during the chase. Signatures then flow through a program the way types do.
The claim to test is that, on realistic template workloads over keyed schemas, template-level optimization recovers most of the join eliminations that whole-query optimization finds. It should also stay tractable in the regime where whole-query optimization times out, and it should beat structural sharing alone at execution time. We explicitly expect some loss of completeness: some redundancies only appear once the argument's internal structure is visible. Quantifying that loss is a primary result, not a footnote.
Relation to Prior Work
Two papers supply the method. The chase-and-backchase of Physical Data Independence, Constraints, and Optimization with Universal Plans expands a first-order path-conjunctive query into a "universal plan" containing every access path the constraints allow. It then proves that every minimal plan is a subquery of that universal plan. We reuse the algorithm unchanged, but apply it to a lambda body with a symbolic parameter rather than to a closed query. Positive higher-order queries embeds positive relational algebra in a simply-typed lambda calculus. It shows that higher-order containment is $\Pi_2^p$-complete, rising to PSPACE-complete with inclusion dependencies. That paper decides containment; it does not construct optimized plans, and it never touches an engine. We borrow its normal forms and its un-nested fragment. The un-nested fragment is also the restriction under which Higher-Order Functions and Structured Datatypes shows higher-order queries cost no more than their first-order core. This fragment is our scope.
HOMES: A Higher-Order Mapping Evaluation System motivates the work and is the direct competitor. It compiles lambda-calculus templates to PostgreSQL, represents shared subqueries as a directed acyclic graph (DAG), and materializes shared nodes chosen by a cost model. Its optimizer is purely structural. If a template produces joins that a foreign key makes redundant, HOMES keeps them. Our proposal adds the semantic layer HOMES lacks and keeps its sharing machinery for everything we cannot eliminate.
Two papers constrain the design. Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries decides SQL equivalence under keys and foreign keys using U-semirings, an algebraic encoding of queries in which constraints become identities. It is complete only for unions of conjunctive queries, and its normalization can fail to terminate with cyclic key and foreign-key dependencies. We therefore restrict signatures to constraint classes with terminating chases, and we use this procedure only as an independent checker on instantiated outputs. Semantic Acyclicity Under Constraints maps where constraint reasoning stays decidable and shows that full tuple-generating dependencies make it undecidable. This tells us which signature languages are safe to allow.
The first-order proof-driven planner of PDQ is a first-order point of comparison, and TorchQL is an application motivation. PDQ and Querying with Access Patterns and Integrity Constraints show how much constraints buy in first-order planning. TorchQL shows that practitioners already write higher-order relational code with constraints, but it uses those constraints only as runtime checks.
Research Program
We will build the system in four parts. The first is a small template language: order-two, un-nested functionals over positive relational algebra with parameter signatures drawn from keys, functional dependencies, and acyclic inclusion dependencies. The second is a signature-aware optimizer. It chases each lambda body once, with parameters as fresh symbols, and backchases to a minimal body, keeping the universal plan's alternatives so a cost model can pick among them. The third is output-signature inference, so that nested calls can be certified without expansion; when certification fails, the optimizer falls back to optimizing the call site after expansion. The fourth is a backend that hands the reduced templates to HOMES-style DAG sharing and materialization before generating SQL for PostgreSQL.
The main analysis is a completeness gap study. We will characterize, first on examples and then as a theorem where possible, the redundancies that template-level optimization provably misses. We conjecture that it misses exactly those whose witness joins cross the boundary between the body and an argument's internal atoms not captured by the signature. We will then test whether enriching signatures with inferred output constraints closes that gap in practice.
Baselines
The naive reference point is full beta-reduction, meaning every call is substituted and expanded into one flat query, which PostgreSQL then optimizes. On the HOMES workload this is catastrophic. HOMES reports TPC-H Query 3, a 16-join template, at "5.3 hours" at scale 1 and "timed out after 12 hours" at scale 5. We will rerun it on our hardware only up to the same timeout.
The strongest existing method is HOMES itself, with DAG sharing plus cost-based materialization. It reports 8.0 seconds at scale 1 and 10.1 seconds at scale 5 on Query 3. It is the strongest competitor because it is the only system that already avoids expansion blowup on higher-order templates. We will reimplement its sharing and materialization policy on the same PostgreSQL instance, with the same memory and temporary-table budget and the same scale factors. Our system will run that identical backend after semantic reduction, so the only difference is the constraint step. Beating it means lower end-to-end time, including optimization time, on templates where constraints imply redundancy, with no regression beyond noise on templates where they do not.
The completeness reference is expanded chase-and-backchase. Here we fully expand each call, apply HOMES sharing, and run first-order chase-and-backchase on each shared node under $\Sigma$. This gives the upper bound on eliminations whenever it terminates. We give it the same optimizer time limit as our system. We score our system by the fraction of its eliminated joins we recover and by the ratio of optimization times.
The key ablation removes signatures, so that parameters carry no constraints and only $\Sigma$ on base relations is used. This isolates whether the parameter interfaces, as opposed to plain constraint use inside the template, account for the gains. A second ablation turns off output-signature inference to measure how much compositionality contributes.
Why not just…?
Why not just expand everything and run a first-order constraint optimizer? When it terminates, this is the correct answer, which is why it serves as our completeness reference rather than a straw man. The problem is scale. The expansion sizes in HOMES are what made naive execution take hours. The backchase enumerates subqueries of the universal plan, and Axiomatic Foundations reports verification "within 30 seconds for most cases" only on inputs whose size barely grows during normalization. Our experiments sweep template depth to find the crossover. If expanded optimization stays fast at every realistic depth, the case for modularity weakens to reuse across call sites, and we will say so.
Why not just combine HOMES sharing with per-node constraint optimization? This is the most serious threat, because shared DAG nodes are already smaller than the full expansion. The difference is that a shared node is optimized separately at each instantiation and loses redundancies that span a node boundary. A signature, by contrast, optimizes once against all conforming arguments. The expanded chase-and-backchase baseline above includes sharing precisely to settle this. If it matches our elimination rate at similar optimization cost, the contribution reduces to call-site reuse, and we would reframe the work around that.
Why not just let PostgreSQL's cost-based optimizer handle it? Join reordering does not delete a join whose removal requires a foreign-key argument. The file notes that 10 of the rewrites studied by Axiomatic Foundations need constraints as preconditions, and first-order planners in Querying with Access Patterns and Integrity Constraints found "6 out of 20" queries answerable without constraints. We will nonetheless declare all TPC-H keys and foreign keys to PostgreSQL in the naive baseline, so that any built-in constraint use it has is credited to it.
Why not just cache optimized first-order plans per instantiation? Caching helps only when identical arguments recur. Parameterized security filters and mapping templates apply to many distinct argument queries, each of which would miss the cache. We will report cache hit rates on our workloads, obtained by replaying call traces, alongside the signature approach.
Proposed Experiments
The workload has three parts. The first is TPC-H at scale factors 1 and 5, using the declared keys and foreign keys, and running the HOMES Query 3 template together with a new family of templates: ownership-chain filters, lookup-through-dimension helpers, and iterated self-join generators. Each is parameterized by depth so redundancy grows with nesting. The second is the Apache Calcite rewrite test cases used by Axiomatic Foundations, where UDP proved "33 out of 39", lifted into functionals by abstracting one input relation as a parameter. This tests whether template-level optimization rediscovers constraint-dependent rewrites. The third is the 20 TPC-H conjunctive queries of Querying with Access Patterns and Integrity Constraints, rewritten as calls to shared helper functionals.
We will measure four things: optimization time, execution time, total end-to-end time, and joins eliminated relative to the expanded chase-and-backchase reference. We found no reported result on Lacuna for constraint-based optimization of higher-order query templates, so every semantic-reduction number here will be new. Soundness is checked in two independent ways. We compare result bags on generated instances, and we run U-semiring equivalence checks on instantiated outputs within its supported fragment.
The decisive checks are three. First, on Query 3 and the depth-parameterized templates, our system must beat reimplemented HOMES end-to-end at both scales. Second, on the depths where expanded chase-and-backchase terminates, template-level optimization should recover a large majority of its eliminations; a recovery below half would falsify the practical claim. Third, the no-signature ablation must lose most of the gain; if it does not, the signature idea is not doing the work.
References
- Physical Data Independence, Constraints, and Optimization with Universal Plans
- Positive higher-order queries
- HigherOrder Functions and Structured Datatypes
- HOMES: A Higher-Order Mapping Evaluation System
- Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries
- Semantic Acyclicity Under Constraints
- PDQ: Proof-driven Query Answering over Web-based Data
- Querying with Access Patterns and Integrity Constraints
- TorchQL: A Programming Framework for Integrity Constraints in Machine Learning