Expand description
The optimizer applies metadata-only rewrite rules (reduce and reduce_parent) in a
fixpoint loop until no more transformations are possible.
Optimization runs between execution steps, which is what enables cross-step optimizations:
after a child is decoded, new reduce_parent rules may match that were previously blocked.
There are three public entry points on ArrayOptimizer:
ArrayOptimizer::optimizeuses only static rules registered on encoding vtables, and only rewrites the root node.ArrayOptimizer::optimize_ctxalso consults the session’s activekernels::ArrayKernelsregistry before static parent-reduce rules, so this is the entry point used by execution. It optimizes the root, then the descendants below it that were never optimized, then the root again if a child changed.ArrayOptimizer::optimize_recursiveis the same asArrayOptimizer::optimize_ctx.
With a session, the optimizer works top down. It first tries the rules of a node on its children
as they are, so a rule that drops or replaces a child does not optimize that child first. Then
it optimizes the children that were never optimized, and if any child changed, it tries the
rules of the node again. Thus a parent rule or kernel keyed on a child’s encoding still sees
that encoding rather than a lazy wrapper around it, such as a slice of an FSST array under a
LIKE. Children already optimized are left without visiting their subtrees.
Whenever a rule rewrites a node, the nodes the rule built are optimized bottom up before the
next pass on the node. Otherwise two rules that are inverses of each other, such as
slice(get_item(s)) and get_item(slice(s)), could rewrite the node back and forth.
Each array records whether the optimizer has taken it to its fixpoint. A new array starts unoptimized, and optimizing with a session marks the arrays it returns, so optimizing an array again returns it without trying any rule. The optimizer marks a node only after it optimized the children of the node, so the descendants of a marked node are marked too. The mark does not record the session: an array optimized with one session is not optimized again with a session that registers more kernels.
Modules§
- kernels
- Session-scoped registry for optimizer kernels.
- rules
- Metadata-only rewrite rules for the optimizer (Layers 1 and 2 of the execution model).
Traits§
- Array
Optimizer - Extension trait for optimizing array trees using reduce/reduce_parent rules.