Skip to main content

Module optimizer

Module optimizer 

Source
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:

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§

ArrayOptimizer
Extension trait for optimizing array trees using reduce/reduce_parent rules.