168 Query Optimisation

This chapter explains how typed path navigation and the algebraic properties of Predica’s operators enable systematic query optimisation. Much ordinary navigation can be compiled directly. Where a query combines set-valued paths, many apparently distinct operations (such as selection and constraint application) can be expressed as ordinary joins. That part of the query can be treated as a join graph and reordered using associativity and commutativity to minimise intermediate cardinalities.

Compiling path expressions directly

A compiler works with path expressions directly to implement queries; it does not need to translate them into logic frames. The logic denotation provides a precise specification of what each path expression means, ensuring that users and compiler writers share the same definition of the language.

For example, mycircle.centre.x can be implemented as simple navigation through the attributes of nested data structures: first from mycircle to its centre, and then from that value to its x attribute. The compiler can analyse and optimise this navigation directly. Its implementation is correct when it preserves the meaning given by the logic denotation in the language specification.

Typed navigation and relational query planning

In relational DBMSs such as PostgreSQL, a query states which results are required without normally prescribing a physical route between tables. When a query joins several tables, the optimiser may need to choose the join order, select among nested-loop, hash, and merge joins, and decide whether each input should be obtained through an index or a scan. These decisions depend on statistical estimates of cardinality and selectivity. The number of possible plans grows rapidly with the number of joined relations, so a substantial part of relational query optimisation consists of searching for a sufficiently inexpensive execution plan.

In Predica, a typed path often supplies a natural route through the model. An expression such as mycircle.centre.x already describes navigation from one nested value to another. The compiler does not need to rediscover that route by considering alternative join trees: it can follow the centre attribute and then the x attribute, much like compiling ordinary field access in a programming language. Cost-based choices remain important where paths are multi-valued, inverse, indexed, or combined with constraints, but ordinary structural navigation requires much less planning.

Representation follows the type structure

The mapping from a Predica schema into its physical representation tends to dominate how query implementation is understood. That mapping will often naturally mirror the nested types and local relationships already present in the logical model. The resulting implementation is made from structures such as objects, fields, maps, collections, and pointers, so a path expression is normally understood as navigation through those structures.

For a simple example, suppose a circle and its centre are represented by nested structures:

struct PointFloat32
{
    float x;
    float y;
};

struct CircleFloat32
{
    PointFloat32 centre;
    float radius;
};

Here mycircle.centre.x maps directly onto two field accesses. The layout has already embodied the route expressed by the path, so there is no choice of join order or join algorithm to recover during query planning.

Now suppose the same values are mapped directly onto unnested relations:

Circle(circle_id, centre_id, radius)
Point(point_id, x, y)

Obtaining the same x value requires matching Circle.centre_id with Point.point_id. With more levels of nesting, each level can introduce another relation and another join. The relational implementation must then decide how to perform those joins and whether to use indexes or scans. If a query combines several such paths, it may also have to choose their evaluation order using estimates of selectivity and intermediate cardinality.

The familiar suppliers, parts, and shipments example shows the difference more clearly. In the relational model it is natural to begin with three relations, with the shipment relation containing supplier and part keys. Predica best practice instead pushes the relationships down into the types that expose them:

entity Supplier
{
    Integer id;
    Shipment shipment* where shipment.supplier = this;
    key {id};
}

entity Part
{
    Integer id;
    Color color;
    Shipment shipment* where shipment.part = this;
    key {id};
}

entity Shipment
{
    Supplier supplier;
    Part part;
    Integer qty;
    key {supplier, part};
}

entity ShipmentsSystem
{
    Supplier supplier*;
    Part part*;
    → Shipment shipment* = either supplier.shipment, part.shipment;
}

A natural representation gives the shipments system maps of suppliers and parts. Each supplier and part has a local collection of pointers to shipments, and the pointers from both sides can refer to the same shared shipment object. The shipment in turn refers to its supplier and part. The implementation is therefore more naturally pictured as a typed graph than as three flat tables.

For example, the path s.supplier.[id = 17].shipment.part.color suggests the following execution directly:

supplier-map lookup
→ supplier's local shipment collection
→ shared shipment object
→ part pointer
→ color attribute

The path through the data has already been organised by the Predica schema and preserved by its representation. The compiler need not begin with a mental picture of three n-ary relations and then discover a three-way join plan. Pushing relationships down is therefore not merely a surface-syntax convenience: it gives queries direct, typed routes through the model.

Multiple directions without a single hierarchy

An important relational-model argument must nevertheless be taken seriously. An n-ary relation does not privilege one direction of navigation. Given the relations

Supplier(supplier_id, ...)
Part(part_id, ...)
Shipment(supplier_id, part_id, quantity)

a query can proceed from suppliers through shipments to parts, from parts through shipments to suppliers, or directly from shipments to either endpoint. Indexes and join plans can be chosen independently of this symmetric logical representation. This is a genuine strength of the relational model.

If Predica physically stored the same information only as the following tree, the traditional criticism of hierarchical databases would apply:

Supplier
└── Shipment
    └── Part

Finding shipments by part would then go against the privileged direction. It might require scanning all suppliers, duplicating data under a second hierarchy, or reorganising the database. A change in the required access direction could consequently force changes to both the physical schema and the programs that traverse it.

The direct representation suggested by the Predica model above is not such a tree. It is a typed graph with useful navigation in several directions:

ShipmentsSystem
├── suppliers: map<SupplierId, Supplier>
├── parts:     map<PartId, Part>
│
├── Supplier ──shipment[]──┐
│                         ▼
│                      Shipment
│                         ▲
└── Part ─────shipment[]───┘

Shipment ──supplier──→ Supplier
Shipment ──part──────→ Part

One shared shipment object can appear in the local shipment collections of both its supplier and its part. The following paths are consequently all natural:

supplier.shipment.part
part.shipment.supplier
shipment.supplier
shipment.part

The local collections under Supplier and Part are, in physical terms, comparable to maintaining indexes on both Shipment.supplier and Shipment.part. Predica is therefore not claiming that one arbitrary hierarchy makes every direction efficient. It allows the logical model and its direct representation to expose several typed directions over the same entities.

Multiple access directions have a cost

Supporting these directions is not free. If a system contains one hundred million shipments, efficient navigation in both directions requires physical structures corresponding to both supplier → shipments and part → shipments. A relational implementation might use two B-tree indexes. A direct Predica implementation might use two local collections of pointers. Either approach consumes storage and adds work when shipments are inserted, removed, or changed.

If only Supplier.shipment has an efficient representation, then Part.shipment cannot also be efficient by virtue of the path syntax alone. It must be supported by another index or local collection, calculated as an inverse mapping, found by a scan, or obtained using some other planned operation. Predica does not eliminate the physical-design problem; it gives common access paths a natural typed expression and, usually, a direct representation.

The two local shipment collections must not be treated as independent logical facts or as copied shipment records. They are constrained or derived views of the same shared Shipment entities. There remains one logical fact that a shipment has a particular supplier and part. Materialising navigation from both endpoints is analogous to constructing several indexes over one relation: it provides several access paths without introducing several independent sources of truth.

What physical independence means here

Predica’s physical-independence claim is that a query specifies logical navigation without specifying the mechanism that implements each step. For example,

part.shipment.supplier

does not say whether part.shipment is represented by a vector of pointers, a B-tree, a persistent index, a computed inverse, a cached derived collection, or a relational join. Similarly, a reference from a shipment to a part could be a memory pointer, an object identifier, a smart pointer that loads an object on demand, or a foreign-key lookup. The representation can change without changing the path or its meaning.

This is physical independence, but it is not physical neutrality and does not promise automatic efficiency. A path can remain valid while performing poorly until an appropriate representation or index is supplied. No representation can make every possible access pattern equally efficient without paying the cost of maintaining the corresponding access structures.

Query optimisation is especially pressing when an implementation maps a nested model onto unnested relations. Navigation already present in the source path must then be reconstructed by a join plan. When the physical layout preserves the nesting and graph relationships, ordinary navigation maps onto structural access and requires fewer planning decisions. More generally, the closer the physical representation is to the navigational shape of common queries, the less of that structure an optimiser must recover.

Predica does not require the physical representation to preserve this nesting. If the supplier model is stored in ordinary unnested SQL tables, the compiler or database backend must reconstruct the same path using joins and inherits the associated planning problem. The logic denotation remains the same in either implementation; it specifies the result, while the representation determines how naturally the source path maps onto an execution route.

Why some schema changes can remain local

Predica’s claims about resilience to schema changes do not follow from nesting alone. Several other properties of the language contribute:

• Entities belong to logical sorts. A Supplier is logically identified as an entity in the Supplier domain. Queries need not use an exposed surrogate identifier as the identity of the supplier.
• Keys are constraints rather than identity plumbing. A key can support lookup and indexing without requiring every relationship and query to copy and compare the key attributes.
• Relationships are typed attributes. shipment.part denotes a Part; the query need not explicitly equate Shipment.part_id with Part.id.
• Cardinality constraints are local. They are declared on the relevant attribute instead of being propagated through foreign-key columns and join conditions in many parts of an unnested schema.
• Inverse and derived relationships can expose additional directions. They need not introduce an independent source of truth.
• Collection representations are replaceable. A vector can be replaced by a B-tree, hash map, or persistent collection without changing the logical declaration or the paths that use it.

For example, changing the representation of ShipmentsSystem.supplier from a vector to a B-tree does not change queries. Adding an index for Part.color need not change the path s.part.[color = red]. These are physical changes behind stable logical expressions.

A genuine logical change can still affect queries. Removing or changing the meaning of an attribute cannot be hidden by physical independence. Changing a singular relationship into a many-valued relationship may also invalidate assumptions made by existing expressions. Predica reduces the propagation of incidental changes to keys, cardinality declarations, and representations; it does not make semantic changes disappear.

Relational planning and typed path optimisation

Preserving nesting therefore does not eliminate optimisation. An attribute or relationship implemented by a B-tree is comparable to a lookup in a std::map: an access structure is involved, but that alone does not create the global planning problem associated with joining many tables. More substantial choices arise when a path traverses a multi-valued or inverse relationship, when both an index and a scan are available, or when constraints and set-valued paths can be evaluated in different orders.

In those cases the optimiser may select access paths, push restrictions earlier, estimate candidate-set sizes, and reorder genuinely set-valued operations. For example, when a path reaches a collection of orders and then filters their items, the compiler may have to choose between scanning the collection and using an index on an item attribute. If two filters apply, it can first apply the one expected to leave the smaller candidate set. A Predica optimiser can therefore be thought of primarily as a typed path optimiser, with relational-style planning used where the structure of a query actually calls for it.

None of this weakens Predica’s grounding in logic. Its logic applies uniformly to user-defined types such as Circle and Point, to variants, and even to the attributes of enum values, which are predicates. The logic denotation fixes the meaning of all these expressions; it does not prescribe that they be implemented by materialising relations or executing table joins. Predica’s direct-mapping claim is that the logical type structure usually has a simple and useful implementation, not that this implementation is the only possible one or is optimal for every workload.

Selection as join

In Predica, selection is not a primitive operator. Instead, it is expressed as join with a constraint tuple. For example, the selection “attribute a must include value v” is represented by the single-valued constraint tuple { a ↦ {v} }, and selection is:

σa=v(t) = t ⊓ { a ↦ {v} }.

More generally, any finite conjunction of attribute-value constraints can be represented as a tuple, and applying those constraints is just another join. This means that selections, filters, and constraints are all instances of the same operator ⊓.

Join as the central optimisation primitive

Because join ⊓ is commutative, associative, and idempotent, any query built from joins and selections can be viewed as a set of joins over a collection of base relations and constraint tuples. The optimiser is therefore free to:

• Reorder joins: use associativity and commutativity to choose a join order that minimises intermediate result sizes.
• Push constraints down: treat selections as joins with constraint tuples and move them as close as possible to base relations.
• Combine constraints: merge multiple constraint tuples into a single tuple using join, avoiding repeated passes over the data.

Since join never creates Cartesian products (it is a true meet, not “product + filter”), the optimiser does not need special rules to avoid explosive intermediate results. All joins are structurally safe, and the main goal is to reduce cardinalities as early as possible.

Projection and cardinality reduction

Projection πA is domain restriction and distributes over both join and generalised union:

πA(t₁ ⊓ t₂) = πA(t₁) ⊓ πA(t₂),
πA(t₁ ⊔ t₂) = πA(t₁) ⊔ πA(t₂).

This allows the optimiser to push projections down as well, trimming attributes early to reduce the width of intermediate tuples. Combined with early constraint joins, this yields smaller, narrower intermediate relations, which is exactly what a cost-based optimiser wants.

Using expand in optimisation

The expand operator ! is primarily semantic, but its algebraic properties are still relevant for optimisation. Since expand commutes with join, generalised union, and projection:

(t₁ ⊓ t₂)! = t₁! ⊓ t₂!,
(t₁ ⊔ t₂)! = t₁! ⊔ t₂!,
πA(t!) = (πA(t))!,

the optimiser can reason about queries either in the MVA domain or in the expanded “possible worlds” domain, knowing that the two views are consistent. In practice, expand is usually avoided during execution because it increases cardinality, but its laws justify algebraic rewrites and equivalence checking.

Minus and conflict-aware pruning

Minus − removes possibilities inside tuples rather than removing whole tuples. It is monotone in its first argument and antitone in its second, and distributes over both join and generalised union:

(t₁ − t₂) ⊓ (t₁ − t₃) = t₁ − (t₂ ⊔ t₃),
(t₁ − t₂) ⊔ (t₁ − t₃) = t₁ − (t₂ ⊓ t₃).

These properties allow the optimiser to factor and reorder minus operations, pushing them closer to the data sources where they can prune possibilities early. Because Predica retains conflicting information (e.g. {red} ⊔ {blue} = {red, blue}), minus can be used to remove specific conflicting possibilities without discarding entire tuples, giving a more fine-grained form of conflict-aware pruning than classical relational difference.

Equivalence and rewrite rules

Finally, the expand operator provides a semantic notion of equivalence: two relations are information-equivalent exactly when their expansions coincide:

r₁! = r₂!.

This gives a solid foundation for algebraic rewrite rules: any transformation the optimiser applies must preserve !-equivalence. Since all core operators are monotone and commute appropriately with expand, the usual optimisation rewrites (join reordering, selection pushdown, projection pushdown, minus factoring) are sound with respect to this semantic criterion.