Optimizing Relational Queries over Array-Valued Data in Columnar Systems Maroua Zeblah
arXiv:2604.01967v1 [cs.DB] 2 Apr 2026
Tyrex team, Univ. Grenoble Alpes, CNRS, Inria & Core Engine team, Opensee, Paris [email protected]
Pierre Genevès
Tyrex team, Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France
Etienne Couritas
Core Engine team, Opensee, Paris [email protected]
Nils Gesbert
Tyrex team, Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France
ABSTRACT Modern analytical workloads increasingly combine relational data with array-valued attributes. While columnar database systems efficiently process such workloads, their ability to optimize queries that interleave relational operators with array manipulations remains limited. This paper introduces A3D-RA, an extended relational algebra supporting array-valued attributes, together with a comprehensive framework for algebraic reasoning and optimization. We formalize its data model and semantics, develop a complete set of equivalence-preserving transformation rules capturing pairwise interactions between relational and array operators, and propose a plan enumeration strategy with an optimality guarantee that remains polynomial in all non-join operators. We design A3D-RA as a modular, backend-independent optimization layer that can be instantiated over existing analytical database systems. Experimental results across three high-performance engines on a real-world workload show consistent performance gains enabled by the proposed algebraic optimization layer.
1
INTRODUCTION
Modern analytical workloads increasingly involve array-valued data, such as time series in financial applications, feature vectors in machine learning pipelines, or sensor readings in IoT systems. Such data naturally combines relational structure (e.g., trades, customers, devices) with multi-dimensional arrays stored as attributes. It is often stored in a denormalized form [18] and processed using column-oriented database engines such as Amazon Redshift [14], Snowflake [8], Apache Pinot [17], DuckDB [29], Umbra [26], and ClickHouse [33]. Column stores are particularly well suited to readheavy analytical workloads of this kind, as they support efficient compression [1] and vectorized execution [4]. While denormalization and array-valued attributes improve data locality and simplify
Sarah Chlyah
Tyrex team, Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France
Nabil Layaïda
Tyrex team, Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France
modeling, they also introduce fundamental challenges for query processing and optimization. Many existing database engines support the evaluation of array operations through proprietary extensions or user-defined functions [30], but these mechanisms often lack a unified algebraic foundation, leaving room for further optimization opportunities of high-level analytical queries. To address this gap, we propose A3D-RA, a formal and modular algebraic optimization framework for processing queries that combine relational and array operations. Rather than targeting a specific execution engine, A3D-RA is designed as a DBMS-agnostic logical optimization layer that can be instantiated on top of existing analytical systems supporting array-valued attributes. The goal is to extend the expressive power of relational algebra to efficiently handle array-valued attributes commonly used in analytical systems, thus enabling a systematic and global exploration of operator interactions.
Contributions. Specifically, this paper makes the following contributions: (i) we introduce an extended relational algebra (A3D-RA) that supports array-valued attributes, defining its data model together with the syntax and formal semantics of its operators; (ii) we propose a comprehensive and compositional set of equivalencepreserving transformation rules capturing the interactions between all pairs of relational and array operators, enabling algebraic reasoning and systematic plan rewriting in the presence of arrays; (iii) we present a plan enumeration strategy with an optimality guarantee that is polynomial in all non-join operators; and finally (iv) we design A3D-RA as a modular optimization layer that can be instantiated over different database engines. We denote by A3DRA[X] the instantiation of our framework over a backend system X. We implement a prototype with a pluggable backend architecture and evaluate three instantiations (A3DRA[ClickHouse], A3DRA[Umbra], and A3DRA[Snowflake]) on queries derived from a real-world financial workload. The results demonstrate that our algebraic framework consistently unlocks optimization opportunities beyond those explored by native optimizers, without requiring modifications to the underlying execution engines.
2 THE A3D-EXTENDED REL. ALGEBRA 2.1 Data model The considered data model extends the classical relational algebra to efficiently handle denormalized and multidimensional data. In this model, a relation is defined as a set of tuples, where each tuple (also called mapping or row) maps column names to values. Unlike traditional relational models, our approach supports columns that can hold arrays of values, enabling the representation of hierarchical and multidimensional data in a compact and flexible form. Formally, we define the following sets: • 𝔙 an infinite set of values, including scalars and arrays • ℭ an infinite set of column names Definition 1 (Tuple). A tuple is a partial function 𝑡 : ℭ → 𝔙 whose domain is finite. If 𝑑𝑜𝑚(𝑡) = {𝑐 1, . . . , 𝑐𝑛 }, 𝑡 can also be seen as the set {𝑐 1 → 𝑡 (𝑐 1 ), . . . , 𝑐𝑛 → 𝑡 (𝑐𝑛 )}. Definition 2 (Relation). Let C be a finite set of column names. A relation 𝑅 of type C is a finite set of tuples 𝑡 : C → 𝔙. We partition C into disjoint subsets: 𝑆 ⊆ C(scalar columns), 𝐴 ⊆ C(array columns), such that C = 𝑆 ∪ 𝐴 and 𝑆 ∩ 𝐴 = ∅. Each tuple 𝑡 ∈ 𝑅 then satisfies: (1) For every scalar column 𝑐 ∈ 𝑆, 𝑡 (𝑐) ∈ 𝑉scalar . (2) For every array column 𝑐 ∈ 𝐴, 𝑡 (𝑐) ∈ 𝑉array = M (𝑉scalar ), where M (𝑉scalar ) denotes the set of all finite sequences of values from 𝑉scalar . Ö Ö Hence, equivalently, 𝑅 ⊆ 𝑉scalar × 𝑉array, subject to |𝑅| < ∞. 𝑐 ∈𝑆
𝑐 ∈𝐴
Definition 3 (Semantic Correspondence of Arrays). Assume a binary semantic correspondence relation ∼ ⊆ 𝑉 × 𝑉 over a universe of values 𝑉 . Two arrays 𝐴 = [𝑎 1, 𝑎 2, . . . , 𝑎𝑛 ] and 𝐵 = [𝑏 1, 𝑏 2, . . . , 𝑏𝑛 ] are said to be semantically corresponding (denoted 𝐴 ≈ 𝐵) if and only if: (1) They have the same length 𝑛, and (2) For every index 𝑖 ∈ {1, . . . , 𝑛}, 𝑎𝑖 ∼ 𝑏𝑖 . That is, 𝐴 ≈ 𝐵 ⇔ 𝐴 = 𝐵 ∧ ∀ 𝑖 = 1, . . . , 𝑛, 𝑎𝑖 ∼ 𝑏𝑖 . Each pair (𝑎𝑖 , 𝑏𝑖 ) thus stands in the semantic correspondence relation.
2.2
Syntax and Semantics of A3D-RA terms
The A3D-RA algebra extends the traditional relational algebra by incorporating operators for transforming and computing over relations that contain array columns. 2.2.1 Terms. The core syntax of terms is defined in Fig. 1. Base terms are relation variables 𝑅. The first three operators are standard from classical relational algebra: two relations can be joined with the natural join operator Z; one relation can be filtered using the selection operation 𝜎𝜃 where 𝜃 is a filter (further detailed below); and the projection operator 𝜋𝐿 (𝜑) selects the desired columns 𝐿 in 𝜑 while discarding other columns. The three operators ArrayJoin, Array-filter, and Aggregation enable transformations and computations over array-valued columns, while Derive creates new columns. The formal semantics of all operators, including their behavior over array-typed attributes, are given in Fig. 2.
𝜑
::= | | | | | | |
𝑅 𝜑 1 ⊲⊳ 𝜑 2 𝜎𝜃 (𝜑 ) 𝜋𝐿 (𝜑 ) 𝜙𝑎:𝑛,𝜃 (𝜑 ) 𝜇𝑎:𝑛 (𝜑 ) 𝛿 𝑦=𝑓 (𝑥 1 ,...,𝑥𝑠 ) (𝜑 ) Γ𝐺,𝑓 (𝑥 1 ,...,𝑥𝑠 ):𝑛 (𝜑 )
term relation variable natural join filtering projection array-filter arrayJoin derive aggregate
Figure 1: Syntax of A3D-RA terms. 2.2.2 Filters. The standard filter operation 𝜎𝜃 , which operates on a relation by keeping only a subset of its tuples, depends on a predicate 𝜃 indicating which tuples are to be kept. This predicate can be seen as a function from mappings to booleans. The predicate can be any legally formed expression that involves: constants (i.e., members of any column domain); column names (i.e., a subset of the columns from the expression on which the filter is applied); arithmetic comparisons (=, ≠ , <, ⩽, >, ⩾); and logical operators (and, or, not). Definition 4 (Invertible Predicate). Let 𝜃 be a predicate of the form 𝑥 ↦→ 𝑅(𝑥, 𝑣) where 𝑣 is a constant, 𝑅 a binary relation (e.g., =, >, ≤). Let 𝑓 be a transformation function. The predicate 𝜃 ◦ 𝑓 : 𝑥 ↦→ 𝑅(𝑓 (𝑥), 𝑣) is said to be invertible if there exist a relation 𝑅 ′ and a function 𝑓 ′ such that: 𝑅(𝑓 (𝑥), 𝑣) ≡ 𝜃 ′ (𝑥) where 𝜃 ′ : 𝑥 ↦→ 𝑅 ′ (𝑥, 𝑓 ′ (𝑣)). Notice that 𝑓 ′ (𝑣) is a constant so that 𝜃 ′ avoids computing 𝑓 while yielding the same result as 𝜃 ◦ 𝑓 . For example, 3 − 𝑥 < 15 can be rewritten into 𝑥 > −12. 2.2.3 Array-Join Operator 𝜇. The arrayJoin operator 𝜇𝑎:𝑛 (𝜑) unnests the array column 𝑎, creating one row per element while duplicating the other columns of 𝜑. This expansion increases the number of rows proportionally to the array size, producing the flattened columns. For example: id vals 1 10 arrayJoin(vals) id vals 1 20 1 [10, 20, 30] −−−−−−−−−−−→ 1 30 2 [5, 15] 2 5 2 15
Formally, its interpretation is: n o J𝜇𝑎:𝑛 (𝜑)K = {𝑐 → 𝑣 ∈ 𝑡 | 𝑐 ≠ 𝑎} ∪ {𝑛 → 𝑒} 𝑒 ∈ 𝑡 (𝑎) ∧ 𝑡 ∈ J𝜑K
where subscripts indicate that 𝑎 is the array column to be flattened; and 𝑛 (optional) denotes the new name for the scalar column resulting from the array. If not specified, the original name 𝑎 is reused. This convention consistently applies to all operators generating new or transformed columns. As shown in Fig. 2, the arrayJoin operator can simultaneously unnest multiple array columns of equal length per row, ensuring element-wise alignment across arrays. 2.2.4 Array-Filter Operator 𝜙. The arrayFilter operator 𝜙𝑎:𝑛,𝜃 (𝜑) applies a predicate 𝜃 to the elements of an array column 𝑎, returning a new array that contains only the elements satisfying 𝜃 . The number of rows in 𝜑 is preserved, although some arrays may become empty. This operator is also extended to multiple corresponding array columns, denoted as 𝜙 (𝑎1 :𝑛1 ,...,𝑎𝑘 :𝑛𝑘 ,𝜃 ) (𝜑), ensuring that positional correspondence
J𝜑 1 ⊲⊳ 𝜑 2 K = {𝑡 1 ∪ 𝑡 2 | 𝑡 1 ∈ J𝜑 1 K ∧ 𝑡 2 ∈ J𝜑 2 K ∧ ∀𝑐 ∈ 𝑑𝑜𝑚 (𝑡 1 ) ∩ 𝑑𝑜𝑚 (𝑡 2 ) 𝑡 1 (𝑐 ) = 𝑡 2 (𝑐 ) }
J𝜎𝜃 (𝜑 )K = {𝑡 | 𝑡 ∈ J𝜑K ∧ 𝜃 (𝑡 ) = ⊤} n o J𝜋𝐿 (𝜑 )K = {𝑐 → 𝑣 ∈ 𝑡 | 𝑐 ∈ 𝐿} 𝑡 ∈ J𝜑K n o J𝜙𝑎:𝑛,𝜃 (𝜑 )K = 𝑐 → 𝑣 ∈ 𝑡 𝑐 ∉ {𝑎, 𝑛} ∪ 𝑛 → {𝑒 | 𝑒 ∈ 𝑣 ∧ 𝜃 (𝑒 ) } 𝑎 → 𝑣 ∈ 𝑡 𝑡 ∈ J𝜑K n o 𝑗 𝑗 𝑗 J𝜙 (𝑎1 :𝑛1 ...𝑎𝑘 :𝑛𝑘 ,𝜃 ) (𝜑 )K = 𝑐 → 𝑣 ∈ 𝑡 𝑐 ∉ {𝑎 1 , 𝑛 1 ...𝑎𝑘 , 𝑛𝑘 } ∪ 𝑛𝑖 → {𝑒𝑖 | 1 ⩽ 𝑗 ⩽ 𝑠 ∧ 𝜃 (𝑒 1 ...𝑒𝑘 ) } 1 ⩽ 𝑖 ⩽ 𝑘 ∧ 𝑎𝑖 → [𝑒𝑖1 ...𝑒𝑖𝑠 ] ∈ 𝑡 𝑡 ∈ J𝜑K n o 𝑗 J𝜇𝑎1 :𝑛1 ,...,𝑎𝑘 :𝑛𝑘 (𝜑 )K = 𝑐 → 𝑣 ∈ 𝑡 𝑐 ∉ {𝑎 1 , 𝑛 1 ...𝑎𝑘 , 𝑛𝑘 } ∪ 𝑛𝑖 → 𝑒𝑖 1 ⩽ 𝑖 ⩽ 𝑘 ∧ 𝑎𝑖 → [𝑒𝑖1 ...𝑒𝑖𝑠 ] ∈ 𝑡 𝑡 ∈ J𝜑K ∧ 1 ⩽ 𝑗 ⩽ 𝑠 ∧ 𝑠 = |𝑡 (𝑎𝑖 ) | n o J𝛿 𝑦=𝑓 (𝑥 1 ,...,𝑥𝑠 ) (𝜑 )K = 𝑐 → 𝑣 ∈ 𝑡 𝑐 ∉ 𝑦 ∪ 𝑦 → 𝑓 (𝑣1 ...𝑣𝑠 ) 1 ⩽ 𝑗 ⩽ 𝑠 ∧ 𝑥 𝑗 → 𝑣 𝑗 ∈ 𝑡 𝑡 ∈ J𝜑K n o JΓ𝐺,𝑓 (𝑥 1 ...𝑥 1 ) :𝑛 ...𝑓 (𝑥 𝑘 ...𝑥 𝑘 ) :𝑛 (𝜑 )K = 𝑦 ∪ 𝑛𝑖 → 𝑎𝑖 1 ⩽ 𝑖 ⩽ 𝑘 ∧ 𝑎𝑖 = 𝑓 (𝑆𝑖 ) ∧ 𝑆𝑖 = { (𝑣1 ...𝑣𝑠𝑖 ) | 𝑡 ∈ J𝜑K ∧ 𝑡 .𝐺 = 𝑦.𝐺 ∧ ∀ 𝑗 ∈ {1...𝑠𝑖 }, 𝑥 𝑖𝑗 → 𝑣 𝑗 ∈ 𝑡 } 𝑦 ∈ J𝜋𝐺 (𝜑 )K 1
1
𝑠1
1
𝑘
1
𝑠𝑘
𝑘
Figure 2: Semantics of A3D-RA. between arrays is maintained after filtering (i.e., the filter is applied across all of them in a coordinated way).
data, whereas arrayJoin multiplies rows by array lengths.
2.2.5 Derive Operator 𝛿. The derive operator 𝛿 𝑦=𝑓 (𝑥 1 ,...,𝑥𝑠 ) (𝜑) extends a relation 𝜑 with a new column 𝑦, whose values are obtained by applying a function 𝑓 to one or more existing columns (𝑥 1, . . . , 𝑥𝑠 ). The function 𝑓 may represent arithmetic, string, or other domain-specific transformations. We assume that its computational cost is linear with respect to the total length of the input arrays. When applied to array columns, the operator relies on the arrayMap (𝑓 ) construct, where 𝑓 is applied element-wise to the arrays provided as parameters.
When a filter 𝜎𝜃 targets columns produced by arrayJoin, it can be rewritten as an arrayFilter on the original arrays. To preserve element-wise correspondence, the arrayFilter is applied jointly across all columns involved. This rule-based transformation reduces the number of elements flattened, minimizing intermediate results, particularly for wide arrays.
2.2.6 Aggregation Operator Γ. The aggregation operator Γ𝐺,𝑓 (𝑥 1 ,...,𝑥𝑠 ):𝑛 (𝜑) groups the rows of a relation 𝜑 according to a set of attributes 𝐺 and computes aggregate values using a function 𝑓 over columns (𝑥 1, . . . , 𝑥𝑘 ). If 𝐺 is empty, the entire relation is treated as a single group. The operator produces one row per group, with the result of 𝑓 stored in a column 𝑛 (defaulting to 𝑓 (𝑥 1, . . . , 𝑥𝑘 )). Multiple aggregations can be computed simultaneously, denoted by Γ𝐺,𝑓1 (𝑥 1 ,...,𝑥 1 ):𝑛1 ,...,𝑓𝑘 (𝑥 𝑘 ,...,𝑥 𝑘 ):𝑛𝑘 (𝜑).
This rule filters out empty arrays before applying arrayJoin operator, reducing unnecessary expansions. This optimization is costbased, as its effectiveness depends on the selectivity of the filter—if most arrays are empty, the gain is significant; otherwise, the overhead of filtering may outweigh the benefit.
1
3
𝑠1
1
𝑠𝑘
GENERATING NEW QUERY PLANS
We present the equivalence-preserving transformation rules for A3D-RA, derived from a systematic analysis of pairwise operator interactions (Table 1). Rules are classified as rule-based, when universally beneficial regardless of data statistics or implementation details, and cost-based, when their application depends on estimated execution cost.
3.1
Aggregation-free rewrite rules
3.1.1
Commutativity of ArrayJoin. 𝜇𝑎2 :𝑛2 (𝜇𝑎1 :𝑛1 (𝜑)) ≡ 𝜇𝑎1 :𝑛1 (𝜇𝑎2 :𝑛2 (𝜑))
(R1)
arrayJoin is commutative over distinct attributes: changing the order does not affect the result. 3.1.2
Pushing Down Filter under ArrayJoin. 𝜎𝜃 (𝜇𝑎𝑖 :𝑛𝑖 (𝜑)) ≡ 𝜇𝑎𝑖 :𝑛𝑖 (𝜎𝜃 (𝜑))
(R2.1)
A filter 𝜎𝜃 can be pushed below arrayJoin 𝜇 if 𝜃 does not reference the flattened columns 𝑛𝑖 introduced by the arrayJoin. This is a rule-based transformation as filter pushdown reduces intermediate
𝜎𝜃 (𝜇𝑎𝑖 :𝑛𝑖 (𝜑)) ≡ 𝜇𝑎𝑖 :𝑛𝑖 (𝜙 (𝑎𝑖 :𝑛𝑖 ,𝜃 ) (𝜑))
3.1.3
Eliminating Empty Arrays Before arrayJoin. 𝜇𝑎:𝑛 (𝜑) ≡ 𝜇𝑎:𝑛 (𝜎𝑎!=[ ] (𝜑))
3.1.4
(R2.2)
(R2.3)
Pushing Down Projection under ArrayJoin. (R3)
𝜋𝐿∪{𝑛𝑖 } (𝜇𝑎𝑖 :𝑛𝑖 (𝜑)) ≡ 𝜋𝐿∪{𝑛𝑖 } (𝜇𝑎𝑖 :𝑛𝑖 (𝜋𝐿∪{𝑎𝑖 } (𝜑)))
When a projection selects all columns produced by arrayJoin, it can be pushed below the operator, replacing transposed columns 𝑛𝑖 with the original arrays 𝑎𝑖 . It is a rule-based transformation as it reduces the number of columns that have to be materialized by the arrayJoin operator. 3.1.5
Pushing Down Join under ArrayJoin. 𝜇𝑎𝑖 :𝑛𝑖 (𝜑 1 ) ⊲⊳ 𝜑 2 ≡ 𝜇𝑎𝑖 :𝑛𝑖 (𝜑 1 ⊲⊳ 𝜑 2 )
(R4.1)
The join with 𝜑 2 can be performed either before or after the arrayJoin on 𝜑 1 , depending on its effect on intermediate result size. This is a cost-based decision: if the join reduces or preserves the size of its inputs, it can be applied first; otherwise, the choice depends on the relative selectivity of the join compared to the number of elements in 𝑎𝑖 . 𝜇𝑎𝑖 :𝑛𝑖 ,𝑏 𝑗 :𝑚 𝑗 (𝜑 1 ⊲⊳ 𝜑 2 ) ≡ 𝜇𝑎𝑖 :𝑛𝑖 ,𝐼 (𝛿𝐼 =𝑎𝑟𝑟𝑎𝑦𝐸𝑛𝑢𝑚𝑒𝑟𝑎𝑡𝑒 (𝑎1 ) (𝜑 1 )) ⊲⊳ 𝜇𝑏 𝑗 :𝑚 𝑗 ,𝐼 (𝛿𝐼 =𝑎𝑟𝑟𝑎𝑦𝐸𝑛𝑢𝑚𝑒𝑟𝑎𝑡𝑒 (𝑏 1 ) (𝜑 2 )) (R4.2) For an arrayJoin applied to corresponding attributes 𝑎𝑖 and 𝑏 𝑗 in 𝜑 1 and 𝜑 2 , the transformation uses arrayEnumerate to generate indices [1, . . . , length(𝑎𝑖 )] and enforces their equality, ensuring aligned matching of array elements.
Operators ArrayJoin (𝜇) ArrayFilter (𝜙) Derive (𝛿) Aggregate (Γ)
Filter (𝜎) R2.1 R2.2 R2.3
Proj (Π)
ArrayJoin (𝜇)
ArrayFilter (𝜙)
Derive (𝛿)
Join (⊲⊳)
R3
R1
R6
R5.1 R5.2
R4.1 R4.2
R8
R9
-
R7
R11.1 R11.2
R10.1 R10.2 R10.3
R14
-
-
R12
R15
-
R17.1 R17.2 R17.3
R20
R19
R21
R13.1 R13.2 R16 R18
Rule-based transformations
Cost-based transformations
Table 1: Rewrite Rules of A3D-RA. 3.1.6
Pushing Down Derive under ArrayJoin. 𝛿 𝑦=𝑓 (𝑥 1 ,...,𝑥𝑠 ) (𝜇𝑎𝑖 :𝑛𝑖 (𝜑)) ≡ 𝜇𝑎𝑖 :𝑛𝑖 (𝛿 𝑦=𝑓 (𝑥 1 ,...,𝑥𝑠 ) (𝜑))
3.1.11 (R5.1)
When the derived expression does not involve the array elements introduced by the arrayJoin, the derive operation can be pushed below the join without any modification. This transformation is rule-based, as it avoids redundant computation over the expanded rows generated by the arrayJoin. 𝛿 𝑦=𝑓 (𝑛) (𝜇𝑎:𝑛 (𝜑)) ≡ 𝜇 𝑦 (𝛿 𝑦=arrayMap ( 𝑓 ) (𝑎) (𝜑))
(R5.2)
In the case where the derived column 𝑦 depends on the array elements produced by the arrayJoin, the transformation remains valid by rewriting the expression using arrayMap (𝑓 ) . 3.1.7
Pushing down ArrayFilter under ArrayJoin. 𝜙𝑏:𝑚,𝜃 (𝜇𝑎𝑖 :𝑛𝑖 (𝜑)) ≡ 𝜇𝑎𝑖 :𝑛𝑖 (𝜙𝑏:𝑚,𝜃 (𝜑))
(R6)
An arrayFilter can be pushed below arrayJoin when the filtered array 𝑏 is independent of the arrays 𝑎𝑖 being flattened. This rule-based transformation is more efficient, since filtering before expansion avoids generating unnecessary rows. 3.1.8
Commutativity of ArrayFilter. 𝜙𝑎2 :𝑛2 ,𝜃 2 (𝜙𝑎1 :𝑛1 ,𝜃 1 (𝜑)) ≡ 𝜙𝑎1 :𝑛1 ,𝜃 1 (𝜙𝑎2 :𝑛2 ,𝜃 2 (𝜑))
(R7)
arrayFilter operators commute: filtering on 𝑎 1 and 𝑎 2 yields the same result regardless of order. Each filter acts independently on its array, without interfering with others. 3.1.9
Pushing Down Filter under ArrayFilter. 𝜎𝜃 (𝜙𝑎:𝑛,𝜃𝑎 (𝜑)) ≡ 𝜙𝑎:𝑛,𝜃𝑎 (𝜎𝜃 (𝜑))
(R8)
A global filter 𝜎𝜃 can be pushed below an arrayFilter when 𝜃 is independent of the array condition 𝜃 𝑎 . This rule-based transformation is always beneficial: the filter reduces input rows before array processing, while arrayFilter only shrinks arrays horizontally. 3.1.10
Pushing Down Projection under ArrayFilter. 𝜋𝐿∪{𝑛} (𝜙𝑎:𝑛,𝜃 (𝜑)) ≡ 𝜋𝐿∪{𝑛} (𝜙𝑎:𝑛,𝜃 (𝜋𝐿∪{𝑎} (𝜑)))
(R9)
A projection can be pushed below arrayFilter if it preserves the source array 𝑎 used to derive 𝑛. This rule-based transformation is always safe and efficient: projecting early reduces columns processed and minimizes data access.
Distribution of ArrayFilter over Join. 𝜙 (𝑎:𝑛,𝜃 ) (𝜑 1 ⊲⊳ 𝜑 2 ) ≡ 𝜙 (𝑎:𝑛,𝜃 ) (𝜑 1 ) ⊲⊳ 𝜑 2
(R10.1)
The arrayFilter operation distributes over a join when the filtered attribute 𝑎 involves only attributes from one of the joined expressions, or for the case of corresponding arrays 𝑎𝑖 as shown in R10.2: 𝜙 (𝑎1 :𝑛1 ,...,𝑎𝑘 :𝑛𝑘 ,𝜃 ) (𝜑 1 ⊲⊳ 𝜑 2 ) ≡ 𝜙 (𝑎1 :𝑛1 ,...,𝑎𝑘 :𝑛𝑘 ,𝜃 ) (𝜑 1 ) ⊲⊳ 𝜑 2 (R10.2) For arrayFilter applied on two attributes 𝑎 and 𝑏 involving 𝜑 1 and 𝜑 2 , respectively, arrayFilter can be distributed over the join by separating the arrayFilter across the two expressions, provided there is no correspondence between the two columns 𝑎 and 𝑏. 𝜙 (𝑎:𝑛,𝜃𝑎 ),(𝑏:𝑚,𝜃𝑏 ) (𝜑 1 ⊲⊳ 𝜑 2 ) ≡ 𝜙 (𝑎:𝑛,𝜃𝑎 ) (𝜑 1 ) ⊲⊳ 𝜙 (𝑏:𝑚,𝜃𝑏 ) (𝜑 2 ) (R10.3) These are a cost-based transformations: the decision to push down the arrayFilter depends on the selectivity and complexity of the filter condition, as well as the selectivity of the join. 3.1.12
Commutativity of ArrayFilter and Derive.
𝜙𝑎:𝑛,𝜃 (𝛿 𝑦=𝑓 (𝑥 1 ,...,𝑥𝑠 ) (𝜑)) ≡ 𝛿 𝑦=𝑓 (𝑥 1 ,...,𝑥𝑠 ) (𝜙𝑎:𝑛,𝜃 (𝜑))
(R11.1)
This equivalence holds when the derived column 𝑦 = 𝑓 (𝑥 1, . . . , 𝑥𝑠 ) is computed independently of the array 𝑎 being filtered by the arrayFilter condition 𝜃 . 𝜙 𝑦:𝑛,𝜃 (𝛿 𝑦=arrayMap ( 𝑓 ) (𝑎) (𝜑)) ≡ 𝛿 𝑦=arrayMap ( 𝑓 ) (𝑎) (𝜙𝑎:𝑛,𝜃 ′ (𝜑)) (R11.2) When an arrayFilter is applied to a derived array 𝑦 and the predicate is invertible (𝜃 (𝑦) ≡ 𝜃 ′ (𝑎), see Definition 4), it can be pushed below the derive. This rule-based transformation avoids computing 𝑓 on irrelevant elements; if 𝑦 is unused later, the derive may also be eliminated. 3.1.13
Commutativity of Derive.
𝛿 𝑦2 =𝑓2 (𝑧1 ,...,𝑧 𝑗 ) (𝛿 𝑦1 =𝑓1 (𝑥 1 ,...,𝑥𝑖 ) (𝜑)) ≡ 𝛿 𝑦1 =𝑓1 (𝑥 1 ,...,𝑥𝑖 ) (𝛿 𝑦2 =𝑓2 (𝑧1 ,...,𝑧 𝑗 ) (𝜑))
(R12) The derivation operation is commutative when the columns on which the second derivation is applied do not depend on the columns resulting from the first derivation, i.e., 𝑦1 ∉ {𝑧 1, . . . , 𝑧 𝑗 }. 3.1.14
Pushing Down Filter under Derive. 𝜎𝜃 (𝛿 𝑦=𝑓 (𝑥 1 ,...,𝑥𝑠 ) (𝜑)) ≡ 𝛿 𝑦=𝑓 (𝑥 1 ,...,𝑥𝑠 ) (𝜎𝜃 (𝜑))
(R13.1)
When the filter 𝜃 does not reference the derived column 𝑦, it can be pushed below the derive operation. This rule-based transformation reduces the number of rows before derivation. 3.1.15
Invertibility of Filter Applied to Derived Column. 𝜎𝜃 (𝑦) (𝛿 𝑦=𝑓 (𝑥 ) (𝜑)) ≡ 𝛿 𝑦=𝑓 (𝑥 ) (𝜎𝜃 ′ (𝑥 ) (𝜑))
Pushing Down Projection under Derive.
𝜋𝐿∪{𝑦 } (𝛿 𝑦=𝑓 (𝑥 1 ,...,𝑥𝑠 ) (𝜑)) ≡ 𝜋𝐿∪{𝑦 } (𝛿 𝑦=𝑓 (𝑥 1 ,...,𝑥𝑠 ) (𝜋𝐿∪{𝑥 1 ,...,𝑥𝑠 } (𝜑)))
(R14) A projection on a column 𝑦 = 𝑓 (𝑥 1, . . . , 𝑥𝑠 ) can be pushed below derive if it retains all columns 𝑥 1, . . . , 𝑥𝑠 . This rule-based transformation reduces the data processed in subsequent operations. 3.1.17
Distribution of Derive over Join. 𝛿 𝑦=𝑓 (𝑥 1 ,...,𝑥𝑠 ) (𝜑 1 ⊲⊳ 𝜑 2 ) ≡ 𝛿 𝑦=𝑓 (𝑥 1 ,...,𝑥𝑠 ) (𝜑 1 ) ⊲⊳ 𝜑 2
(R15)
The derive operation can be pushed below a join when all its input columns 𝑥 1, . . . , 𝑥𝑠 come from a single input (e.g., 𝜑 1 ). This is a cost-based transformation: if the join significantly increases row count (e.g., many-to-many), pushing down derive reduces data processed; otherwise, applying the join first is more efficient.
3.2
Aggregation rewrite rules
3.2.1
Swapping of filtering with aggregation: 𝜎𝜃𝐺 (Γ𝐺,𝑓 (𝑥 1 ,...,𝑥𝑠 ):𝑛 (𝜑)) ≡ Γ𝐺,𝑓 (𝑥 1 ,...,𝑥𝑠 ):𝑛 (𝜎𝜃𝐺 (𝜑))
Agg (𝑖 ) min max count sum sum, count
Agg ( 𝑓 ) min max sum sum sum, sum
Table 2: Decomposition of aggregate functions
(R13.2)
When a filter is applied to a derived column 𝑦 = 𝑓 (𝑥), and the predicate 𝜃 (𝑦) = 𝜃 ◦ 𝑓 (𝑥) is invertible (Definition 4), the filter can be rewritten and pushed below the derive operator by applying the inverse transformation directly on the original column 𝑥. This rule-based transformation pushes the filter down to the original column thereby reducing intermediate data and enabling the execution engine to leverage existing indexes. Furthermore, if the derived column 𝑦 is used solely for filtering and is not projected later, it can be eliminated, avoiding unnecessary computations. 3.1.16
Agg min max count sum avg
3.2.2
Introducing Pre-aggregation under ArrayJoin.
(1) Aggregating flattened array column by a scalar column: using AggForEach () as a pre-vertical aggregation that aggregates the corresponding array items position-wise, then applying arrayAgg() function that aggregate array elements: Γ𝑠,𝑎𝑔𝑔 (𝑎):𝑛 (𝜇𝐴:𝑎 (𝜑)) ≡ 𝛿𝑛=𝑎𝑟𝑟𝑎𝑦𝐴𝑔𝑔 (𝑁 ) (Γ𝑠,𝑎𝑔𝑔𝐹𝑜𝑟 𝐸𝑎𝑐ℎ (𝐴):𝑁 (𝜑))
(R17.1) (2) Aggregating scalar column by flattened array column: perform pre-agg operation before flattening the grouping array column:
Γ𝑎,𝑎𝑔𝑔 (𝑠 ):𝑛 (𝜇𝐴:𝑎 (𝜑)) ≡ Γ𝑎,𝑎𝑔𝑔 (𝑠 ):𝑛 (𝜇𝐴:𝑎 (Γ𝐴,𝑎𝑔𝑔 (𝑠 ):𝑛 (𝜑)))
(R17.2)
(3) Aggregating flattened array column by its corresponding flattened array column: using AggForEach () as a prevertical aggregation that aggregates the corresponding array items position-wise, then applying the final aggregation operation after flattened the corresponding arrays: Γ𝑎1 ,𝑎𝑔𝑔 (𝑎2 ):𝑛 (𝜇𝐴1 :𝑎1 ,𝐴2 :𝑎2 (𝜑)) ≡ Γ𝑎1 ,𝑎𝑔𝑔 (𝑛):𝑛 (𝜇𝐴1 :𝑎1 ,𝑁 :𝑛 (Γ𝐴1 ,𝑎𝑔𝑔𝐹𝑜𝑟 𝐸𝑎𝑐ℎ (𝐴2 ):𝑁 (𝜑))) 3.2.3
(R17.3)
Introducing Pre-aggregation under Filter: Γ𝐺,𝑎𝑔𝑔 (𝑋 ):𝑚 (𝜎𝜃 𝐿 (𝜑)) ≡
(R16)
The filter can be pushed down under the aggregation if the columns being filtered by 𝜃𝐺 are a subset of the grouping columns 𝐺. This transformation is cost-based, as its benefit depends on the selectivity of the filter and the granularity of the aggregation. Definition 5 (Distributive aggregation). An Aggregation function Agg is said to be distributive when there exist a function 𝐹 Agg , a function 𝑇Agg , and an associative operator ⊕Agg such that Agg({{𝑒 1, ..., 𝑒𝑛 }}) = 𝑇Agg (𝐹 Agg (𝑒 1 ) ⊕Agg ... ⊕Agg 𝐹 Agg (𝑒𝑛 )) Example 3.1. sum, Avg, and distinct are distributive aggregations, and we have: • 𝐹 sum and 𝑇sum are the identity function and ⊕sum = +. • 𝐹 Avg : 𝑒 → (𝑒, 1), 𝑇Avg : (𝑠, 𝑐) → 𝑠/𝑐, and (𝑠 1, 𝑐 1 ) ⊕Avg (𝑠 2, 𝑐 2 ) = (𝑠 1 + 𝑠 2, 𝑐 1 + 𝑐 2 ) • 𝐹 distinct : 𝑒 → {{𝑒}}, 𝑇distinct = 𝑖𝑑 , and ⊕distinct = ∪ Note that any distributive aggregation Agg can be decomposed into two aggregations denoted Agg (𝑖 ) and Agg (𝑓 ) , where Agg (𝑖 ) = reduce(⊕, map(𝐹 Agg, .)) and Agg (𝑓 ) = 𝑇Agg (reduce(⊕, .)). Table 2 illustrates this decomposition for common aggregation functions. We suppose in the following that all aggregations are distributive.
Γ𝐺,Agg ( 𝑓 ) (𝑚):𝑚 (𝜎𝜃 𝐿 (Γ𝐺∪𝐿,Agg (𝑖 ) (𝑋 ):𝑚 (𝜑)))
(R18)
This rule introduces a pre-aggregation under the filter operator by adding the filtered columns 𝐿 to the grouping columns of the inner aggregation. This rule is applicable when the filter columns do not intersect with the aggregated metrics 𝑋 . 3.2.4
Introducing Pre-aggregation under Derive:
Γ𝐺,𝑎𝑔𝑔 (𝑋 ):𝑚 (𝛿 𝑦=𝑓 (𝑥 1 ,...,𝑥𝑠 ) (𝜑)) ≡ Γ𝐺,Agg ( 𝑓 ) (𝑚):𝑚 (𝛿 𝑦=𝑓 (𝑥 1 ,...,𝑥𝑠 ) (Γ𝐺∪{𝑥 1 ,...,𝑥𝑠 },Agg (𝑖 ) (𝑋 ):𝑚 (𝜑)))
(R19)
This rule introduces a pre-aggregation under the derive operator by adding the input columns (𝑥 1, . . . , 𝑥𝑠 ) of the derivation function 𝑓 to the grouping columns of the inner aggregation. If 𝑓 is injective, the final aggregation can be omitted. 3.2.5
Introducing Pre-aggregation Under arrayFilter. Γ𝐺,𝑎𝑔𝑔 (𝑋 ):𝑚 (𝜙𝑎:𝑛,𝜃 (𝜑)) ≡ Γ𝐺,Agg (𝑓 ) (𝑚):𝑚 (𝜙𝑎:𝑛,𝜃 (Γ𝐺∪{𝑎},Agg (𝑖 ) (𝑋 ):𝑚 (𝜑)))
(R20)
This rule introduces a pre-aggregation under the arrayFilter operator by adding the column 𝑎 to the grouping columns of the inner aggregation.
3.2.6
Distribution of aggregation over join. Γ𝐺 1 ∪𝐺 2 ,Agg(𝑋 ):𝑛 (𝜑 1 ⊲⊳ 𝜑 2 ) ≡ Γ𝐺 1 ∪𝐺 2 ,Agg (𝑓 ) (𝑚):𝑛 (Γ𝐺 1 ∪{ 𝑗𝑘 },Agg (𝑖 ) (𝑋 ):𝑚 (𝜑 1 ) ⊲⊳ 𝜑 2 )
(R21)
This rule introduces a pre-aggregation below the join when the aggregated attributes 𝑋 belong exclusively to one join operand. It decomposes the aggregation into two stages: a local pre-aggregation (Agg (𝑖 ) ) on 𝜑 1 grouped by 𝐺 1 ∪{ 𝑗𝑘 }, followed by a final aggregation (Agg (𝑓 ) ) after the join. The previous transformations (R17.1-R21) are cost-based. Aggregations significantly reduce intermediate results when the granularity is much smaller than input size (|𝐺 | ≪ |𝜑 |, which is most often the case in practice with large datasets). Otherwise, the benefit of these transformations depend on the aggregation granularity, the complexity of the derive function, and the filter’s selectivity.
4
EXPLORATION OF QUERY PLANS
Equivalence-preserving transformation rules, such as those proposed in Sec. 3, can always be implemented within a Volcano-style optimization framework [13]. Volcano’s transformational engine systematically explores alternative query plans by applying rewrite rules until no new expressions are generated. While this approach is general and extensible, the number of possible rewritings grows exponentially with query size, making exhaustive enumeration impractical for complex queries. Another option is to use a greedy optimizer which uses the rule categorisation presented in Sec. 3. Whenever a transformation rule pattern is detected, it systematically applies it if it is rule-based, and if it is cost-based it tests whether the cost condition is satisfied in order to apply it. Such an optimizer would be much faster but lacks an overall optimality guarantee as it uses local decisions only. As a third strategy, we propose an enumeration method that provides an optimality guarantee, and whose complexity is polynomial to the number operators other than joins.
4.1
Overall Optimization Process
The optimization process proceeds in three main stages: preprocessing, enumeration, and post-processing. 4.1.1 Pre-processing. The purpose of preprocessing is to prepare the query plan for the subsequent enumeration stage, in particular by applying transformations that introduce new operators, so that the subsequent enumeration stage only needs to consider operator reordering. Projections are first pulled to the top of the query tree. Next, all transformations which introduce new operations are applied (Rules R2.2, R2.3). To explore all opportunities to apply R2.2, we proceed as follows. For each array column 𝑎, we push all filters 𝜎𝜃𝑎 downward as much as possible and, if necessary, pull 𝜇𝑎 upward until a subterm of the form 𝜎𝜃 (𝜇𝑎 (𝜑)) is reached. If such a term is encountered, the rule is applied; otherwise it is not applicable. Applying R2.3 simply consists in inserting a filter that removes empty arrays below arrayJoin operators. 4.1.2 Enumeration. The enumeration stage aims to compute an execution plan with an optimal ordering of operators. It builds on earlier work on optimizing join queries in the presence of expensive filters [6]. The core idea is to replace exhaustive exploration of filter
permutations with a ranking-based order inspired by results from the task scheduling domain [25, 34]. We adapt this approach to the A3D-RA algebra by (i) generalizing ranking to unary operators other than filters, such as derive, array filters, and array joins, and (ii) accounting for precedence constraints between operators, such as: a derive operation which produces column 𝑐 needs to take place before any operation which uses 𝑐. We then combine this ranking of unary operators with a state-of-the-art top-down join enumeration technique [9, 12] which we adapt to take derive operations (which can be used to compute new join keys) into account. This design promotes extensibility: new unary operators can be integrated by defining ranking and precedence constraints, while different join enumeration strategies can be plugged in independently. 4.1.3 Post-processing. Finally, the post-processing step applies pre-aggregation rules–i.e. aggregation rules that introduce preaggregations (see Sec. 2.2.6)– to the optimal term identified during enumeration, producing the final optimized query plan. Rule application proceeds iteratively from the selected plan until no further aggregation rule is applicable. Pre-aggregation rules are deferred to this phase for two reasons. First, they introduce new operators and are therefore not considered during the enumeration phase, which is dedicated to operator reorderings. Second, pre-aggregations can be blocking and thus interfere with the exploration of reorderings. Deferring their application ensures that the enumeration phase can consider all relevant reorderings of non-blocking operators. In practice, this design choice is further justified by the fact that aggregation operators are typically few in number and often appear near the root of the query plan, making a dedicated post-processing phase both effective and inexpensive.
4.2
Enumeration Method
We now describe the enumeration stage in more details. 4.2.1 Enumeration Algorithm. Enumeration is performed by Algorithm 1, which takes as input the initial query 𝑄 and a join graph 𝐺 where a node represents a relation and an edge links two nodes when a join predicate exists between them. Joins are enumerated top-down by recursively partitioning the graph (Partition method is detailed in Sec. 4.2.3). When enumerating a join, the original [6] optimizer identifies the filters that are applicable beneath that join, sorts them by rank, and generates plans where only the first 𝑖 filters are pushed below the join, for all 𝑖. Algorithm 1 extends this approach by considering all unary operators applicable below each side of the join (lines 13-14). These operators are sorted according to the ranking strategy described in Sec 4.2.2. Since we have derive operators that can generate join keys, these operators need to be performed before the joins using those keys. This is why the algorithm (in lines 15 and 16) computes the index 𝑜𝑖 of the last operator that needs to be performed before the join, then computes plans where the first 𝑖 operators are pushed with 𝑖 starting from 𝑜𝑖. The presence of derive operations can also lead to infeasible joins, i.e., joins whose key is produced by different relations that do not belong to the same subset (𝑝𝑖 ). All such cases are detected by the Valid function (line 9), which checks for the existence of an operator that must be applied before the join but cannot be applied to either side of it.
best is a memoization structure used to store the optimal plan corresponding to each enumerated combination of (1) set of joined base relations and (2) set of operators applied within the associated join tree. It is used to construct bigger expressions using already computed sub-expressions and thus avoids redundant computations. best[𝑝, 𝑡] stores the optimal plan that joins the relations in 𝑝 while applying the operators in 𝑡 under the root join, whereas best[𝑝] denotes the collection of best[𝑝, 𝑡] for all enumerated 𝑡.
Algorithm 1: Enumeration of Algebraic Terms Enumerate(𝐺, 𝑄): if 𝑏𝑒𝑠𝑡 [𝐺 ] ≠ ∅ then 3 return
1 2
// already been computed
if 𝐺 contains a single node then 𝑏𝑒𝑠𝑡 [𝐺 ] ← 𝐺 6 return
4
5
foreach Partition (𝑝 1 , 𝑝 2 ) of 𝐺 do Enumerate(𝑝 1 , 𝑄); Enumerate(𝑝 2 , 𝑄) 9 if ¬ Valid(𝑝 1 , 𝑝 2 ) then 10 Continue 7
8
11 12 13
14 15 16 17 18 19 20 21
foreach 𝑠 ∈ 𝑏𝑒𝑠𝑡 [𝑝 1 ] do foreach 𝑡 ∈ 𝑏𝑒𝑠𝑡 [𝑝 2 ] do 𝑜 1 ← Applicable(𝑠, 𝑄) // sorted applicable operators on 𝑠 𝑜 2 ← Applicable(𝑡 , 𝑄) 𝑜𝑖 1 ← last index of operator that must be applied on 𝑠 𝑜𝑖 2 ← last index of operator that must be applied on 𝑡 for 𝑖 ← 𝑜𝑖 1 to |𝑜 1 | do for 𝑗 ← 𝑜𝑖 2 to |𝑜 2 | do 𝑗𝑜𝑖𝑛 ← (𝑜 1 [0..𝑖 ] (𝑠 ) ) Z (𝑜 2 [0..𝑗 ] (𝑡 ) ) if cost(join) < 𝑏𝑒𝑠𝑡 [𝐺, 𝑜𝑝𝑠 ( 𝑗𝑜𝑖𝑛) ] then 𝑏𝑒𝑠𝑡 [𝐺, 𝑜𝑝𝑠 ( 𝑗𝑜𝑖𝑛) ] ← 𝑗𝑜𝑖𝑛
4.2.2 Sorting unary operations. Consider a sequence of filters, 𝜎𝜃 1 (𝜎𝜃 2 (. . . 𝜎𝜃𝑛 (𝑅) . . .)). Assume that each 𝜃𝑖 has an average computing cost per tuple 𝑐𝑖 and average selectivity 𝑠𝑖 ∈ [0, 1], such that for any relation 𝑆, we can estimate that 𝜎𝜃𝑖 (𝑆) costs 𝑐𝑖 |𝑆 | to compute and yields a result containing 𝑠𝑖 |𝑆 | tuples. Then it has been proved [6, 15] that, when the filters are independent, the overall cost of the sequence is minimized by applying them in descending 𝑖 order of their ranks 1−𝑠 𝑐𝑖 . Applying this ranking metric to A3D-RA operators would assign rank 0 to all operators which do not reduce the number of tuples in the input relation, since their selectivity is 1. Consequently, they would all be applied last, in arbitrary order. However, we can do better by noticing that, while operators such as array filters do not reduce the number of tuples, they reduce the size of the array columns on which they operate. The cost of an operator therefore depends not only on the vertical selectivity of preceding operators, but also on what we call their horizontal selectivity—that is, how much they reduce the size of the arrays. Using these metrics, we
define the following relation ≲ on unary operators: 𝑖 ∈ {𝜎, Γ}, 𝑗 ∈ {𝜙, 𝛿 }, 𝑖 and 𝑗 process different arrays 1−𝑠𝑖 𝑐𝑖 𝑎 when 𝑖 ∈ 𝜎, Γ 1−𝑠 𝑖 ≲ 𝑗 ⇐⇒ 𝑖 𝑟 ≥ 𝑟 , where 𝑟 = 𝑖 𝑗 𝑖 𝑐𝑖 when 𝑖 ∈ 𝜙𝜃 𝑎 , 𝛿 𝑦=𝑓 (𝑎) 1− |𝑎 | when 𝑖 = 𝜇 𝑎 𝑐𝑖
where 𝑠𝑖 denotes the vertical selectivity of operator 𝑖, 𝑐𝑖 its cost per tuple (or per array element when operating on an array column), 𝑠𝑖𝑎 its horizontal selectivity on array 𝑎, and |𝑎| the average size of array column 𝑎. Selectivity and per-tuple cost estimation is detailed in Sec. 4.2.4. Ordering operators by ≲ yields an optimal order under the assumptions about cost and selectivity which we detail in section 4.2.5. However, a simple sorting is not always applicable because unary operators cannot be applied in just any order. For instance, a filter on column 𝑐 cannot precede a derive operator that produces 𝑐. To handle such dependencies, we follow techniques from the task scheduling literature [25]. Precedence constraints. Semantic restrictions constraining the order of operators are naturally expressed as precedence constraints, forming a directed acyclic graph (DAG) called a precedence graph. An edge from an operator 𝑜 1 to an operator 𝑜 2 means that 𝑜 1 needs to be applied before 𝑜 2 . When the precedence graph is seriesparallel [25], efficient polynomial-time algorithms exist for constructing an order that is consistent with precedence constraints while minimizing cost. Beyond series-parallel constraints, the problem is shown to be NP-hard [19]. A precedence graph is not seriesparallel if and only if it contains four nodes in a Z-shaped relation [10, 20], i. e. with precedence constraints 𝐴 < 𝐶, 𝐵 < 𝐶 and 𝐵 < 𝐷. In such a structure, the optimal solution may have 𝐴 before 𝐵 or the reverse. Adding an edge between them in either direction eliminates the 𝑍 and restores the series-parallel property, but potentially at the cost of optimality. In our solution, we consider the following heuristic: when a Z-structure is detected, we add an edge from 𝑜 1 to 𝑜 2 if 𝑜 1 ≲ 𝑜 2 , and an edge from 𝑜 2 to 𝑜 1 otherwise. 4.2.3 Join enumeration. We use join graphs for cross-product-free top-down join enumeration [9, 12]. These works propose efficient graph partitioning methods for dividing the join graph (partition function of algorithm 1) into two subsets. In classical relational algebra, the join graph is a graph where a node represents a base relations, and an edge represents a join predicate between two nodes. In our extended algebra, there are cases where a join predicate involves a column produced by a derive operator which might use columns coming from more than one base relation. To make previous techniques applicable to our algebra, we extend the join graph construction in the following way: for each join predicate, we determine the sets of relations 𝐿 and 𝑅 that are involved in the left and right side of the join respectively. An edge (𝑙, 𝑟 ) is then produced for all 𝑙 ∈ 𝐿 and 𝑟 ∈ 𝑅. This way, no join is missed. However, unfeasible joins can be produced and are detected using the Valid function mentioned in Sec. 4.1. 4.2.4 Rank Estimation. Enumeration relies on a per-operator rank determined by its selectivity and per-tuple cost. The cost 𝑐 of a unary operator is estimated as 𝑐 = 𝑐𝑡 × |𝑅|, where 𝑐𝑡 denotes
the operator’s per-tuple cost and |𝑅| the cardinality of its input relation. In the context of A3D-RA, the dominant component of the per-tuple cost typically arises from iterating over array elements. Accordingly, we approximate 𝑐𝑡 by the average length of the array column processed by the operator, and by 1 when the column is atomic. Refined estimations of per-tuple costs is beyond the scope of this paper; such estimates can also be provided by the user. Selectivity estimation relies on the notion of the relative frequency of a value 𝑣 in a column 𝐶, defined as the ratio between the number of occurrences of 𝑣 and the total number of rows in 𝐶. To improve the accuracy of selectivity estimates, we account for the underlying data distribution of each column. A dedicated statistics module maintains different statistics depending on the data distribution: for low-cardinality columns, exact statistics are maintained in the form of a mapping (𝑣 ↦→ 𝑓 𝑟 ). For columns whose values are nearly uniformly distributed, only the average frequency is stored. For skewed distributions (normal, left-skewed, right-skewed), clustering is applied using the K-Means algorithm to group values into clusters of low intra-dispersion. For array-typed columns, two types of statistics are captured: Array statistics (𝑠𝑡𝑎𝑡𝑠 𝑎𝑟𝑟𝑎𝑦 ), representing the array distribution, and Row statistics (𝑠𝑡𝑎𝑡𝑠 𝑟𝑜𝑤 ), representing the row distribution. Using these statistics, selectivities are estimated for different types of predicates, and for atomic and array columns. 4.2.5 Optimality. We show that the ordering computed by Algorithm 1 is optimal. The idea of ordering filters by rank [15] originates in the task scheduling literature [25, 34], where Smith’s theorem establishes optimal scheduling for cost functions satisfying the Adjacent Pairwise Interchange (API) property. Property 1 (API property). A cost function 𝑓 satisfies the API property if there exists a transitive and complete binary relation ≲ such that, for any jobs 𝑖 and 𝑗, 𝑖 ≲ 𝑗 =⇒ 𝑓 (𝑢, 𝑖, 𝑗, 𝑣) ≤ 𝑓 (𝑢, 𝑗, 𝑖, 𝑣)
for all sequences 𝑢, 𝑣.
Here, 𝑓 (𝑢, 𝑖, 𝑗, 𝑣) denotes the cost of executing sequence 𝑢, followed by 𝑖, then 𝑗, then 𝑣. Smith’s theorem states that if 𝑓 satisfies the API property, any permutation consistent with ≲ is optimal. Assume the following: • the columns involved in filtering predicates are statistically independent; • when a filter is applied on a column that is used as an aggregation key, it does not affect the average number of tuples per value of the key; • the cost of aggregation is proportional to the input size (as is typically the case for hash-based aggregation algorithms). Under these assumptions, we show that the API property holds for the relation ≲ (Sec. 4.2.2) together with the cost model of the unary operators 𝜎, 𝜙 , 𝜇, 𝛿, and Γ which we call rankable operators. Proof sketch. Let 𝑖 and 𝑗 be two operators such that 𝑖 ≲ 𝑗, and let 𝑢 and 𝑣 be any two sequences of operators. We recall that 𝑠𝑜 denotes the selectivity of operator 𝑜 and 𝑐𝑜 its cost per tuple. When 𝑖, and 𝑗 are filters, = we have 𝑓 (𝑢, 𝑖, 𝑗, 𝑣) = 𝑓 (𝑢) + Î Î ( 𝑜 ∈𝑢 𝑠𝑜 )𝑐𝑖 |𝑅| + ( 𝑜 ∈𝑢 𝑠𝑜 )𝑠𝑖 𝑐 𝑗 |𝑅| + 𝑓𝑢,𝑖,𝑗 (𝑣) and 𝑓 (𝑢, 𝑗, 𝑖, 𝑣) =
Î Î 𝑓 (𝑢) + ( 𝑜 ∈𝑢 𝑠𝑜 )𝑐 𝑗 |𝑅| + ( 𝑜 ∈𝑢 𝑠𝑜 )𝑠 𝑗 𝑐𝑖 |𝑅| + 𝑓𝑢,𝑖,𝑗 (𝑣). 𝑓𝑢,𝑖,𝑗 (𝑣) denotes the cost of 𝑣 after applying the sequence 𝑢, 𝑖, 𝑗, and |𝑅| denotes the size of the input relation. So 𝑓 (𝑢, 𝑖, 𝑗, 𝑣) − 𝑓 (𝑢, 𝑗, 𝑖, 𝑣) = 1−𝑠 𝑖 𝑐𝑖 (1 − 𝑠 𝑗 )|𝑅| − 𝑐 𝑗 (1 − 𝑠𝑖 )|𝑅| ≤ 0 because 𝑐 𝑗 𝑗 ≤ 1−𝑠 𝑐𝑖 . When 𝑖 is a filter and 𝑗 is an array-filter that process different arrays Î Î we have 𝑓 (𝑢, 𝑖, 𝑗, 𝑣) = 𝑓 (𝑢) + ( 𝑜 ∈𝑢 𝑠𝑜 )𝑐𝑖 |𝑅| + ( 𝑜 ∈𝑢 𝑠𝑜 )𝑠𝑖 𝑐 𝑗 |𝑅| + Î Î 𝑓𝑢,𝑖,𝑗 (𝑣), and 𝑓 (𝑢, 𝑗, 𝑖, 𝑣) = 𝑓 (𝑢) + ( 𝑜 ∈𝑢 𝑠𝑜 )𝑐 𝑗 |𝑅| + ( 𝑜 ∈𝑢 𝑠𝑜 )𝑐𝑖 |𝑅| + 𝑓𝑢,𝑖,𝑗 (𝑣). So 𝑓 (𝑢, 𝑖, 𝑗, 𝑣) − 𝑓 (𝑢, 𝑗, 𝑖, 𝑣) = 𝑐 𝑗 (𝑠𝑖 − 1)|𝑅| ≤ 0. Similarly, we can show the property for all combination of operations. □ Chaudhuri and Shim [6] show that, to optimize a query containing both filters and joins, it suffices to consider all rewritings in which filters are ordered (joins may appear between them). The same argument extends to rankable operators beyond filters. Algorithm 1 enumerates exactly such rewritings. In conclusion, under the assumptions stated above, Algorithm 1 finds an optimal ordering of A3D operators. 4.2.6 Complexity. The original algorithm by Chaudhuri and Shim [6] is proven to be polynomial with respect to the number of filters. The complexity regarding the number of joins depends on the chosen join enumeration strategy. Since join enumeration is a NP-hard problem, existing exhaustive join enumeration algorithms are exponential with respect to the number of joins. The adaptations we made to the original algorithm are all polynomial with respect to the number of operators. Hence, our approach is polynomial to the number of all operators except joins.
5
EXPERIMENTS
We report on an experimental evaluation of A3D-RA.
5.1
System Architecture
The A3D optimizer is designed as a modular, backend-independent, logical optimization layer that can be instantiated over different database systems. For a given backend system 𝑋 , we denote by A3DRA[𝑋 ] the corresponding instantiation of our framework. The architecture consists of three main components, as illustrated in Figure 3. The Logical Plan Generator translates input queries into the A3D algebraic representation. The Plan Optimization module—comprising transformation rules, a cost model, and an enumeration strategy—explores the space of semantically equivalent plans to identify the estimated most efficient execution plan. The cost model leverages data statistics and parameters provided by the target DBMS 𝑋 to estimate the cost of candidate plans. Finally, the Translator converts the optimized algebraic plan back into an executable query in the native syntax of 𝑋 .
5.2
Experimental Protocol
5.2.1 Considered dataset. We consider a real-world use case from our industrial partner, which operates large-scale analytical workloads on financial data. The company maintains a denormalized, multidimensional schema designed to support interactive analytical queries involving grouping, filtering, and aggregation. A distinctive feature of this industrial data model is the explicit use of Array-typed columns to represent repeated or hierarchical attributes—such as nested transaction codes, multi-level categorizations, or composite financial indicators—within a single fact table.
Plan Optimization
Cost Model
Transformation Rules
Query
Logical Plan Generator
algebraic Plan
Data Stats / Parameters
Enumeration Strategy
Optimized Plan Translator Optimized Query
DBMS
Query Result
Figure 3: A3D-Optimizer System Architecture. Each row may contain one or more arrays corresponding to additional analytical dimensions. This design eliminates costly joins while preserving the ability to perform complex multidimensional analyses directly within a columnar layout. The considered dataset comprises over 100 million rows, exhibiting a high degree of heterogeneity across both scalar and array columns. Data distributions vary depending on business semantics and domain context, including uniform, left- and right-skewed, and normal patterns. Furthermore, array columns exhibit two distinct forms of variability: (i) array-level distribution, reflecting the diversity of distinct values per row, and (ii) row-level distribution, capturing the overall frequency of repeated values across rows. Array sizes also vary significantly across attributes. This multilevel variability, diversity and complexity of the dataset make it a challenging benchmark. It enables the evaluation of algebraic transformations across varying data distributions, allowing us to assess the real-world performance of the proposed framework in an authentic industrial setting. 5.2.2 Real and Synthetic Query Workloads. We evaluate A3D-RA on (i) 18 real-world analytical queries involving array flattening, array filtering, derived dimensions, and multidimensional aggregation, and (ii) a synthetic workload designed to isolate individual transformation rules under controlled selectivity and cardinality parameters. All queries are given at [37]. 5.2.3 Considered Backends. We instantiate A3D-RA over three state-of-the-art analytical database systems: ClickHouse [33], Umbra [26], and Snowflake [8]. These systems were selected because they consistently rank among the top-performing engines in recent large-scale analytical benchmarks [33]. ClickHouse is a columnoriented analytical DBMS with native support for array-typed attributes. Umbra is a modern in-memory analytical system with an advanced cost-based optimizer and vectorized execution engine. Snowflake is a cloud-based analytical data warehouse supporting semi-structured data, including arrays. 5.2.4 Comparative Analyses. We first evaluate the quality of the generated execution plans, as measured by query runtime. For each query and each considered backend system 𝑋 , we compare
two configurations: 𝑋 , where the original query is optimized and executed using the DBMS’s built-in optimizer; and A3DRA[𝑋 ], where the same query is first translated into A3D-RA, optimized using our algebraic framework, translated back into the native query language of 𝑋 , and then executed by the same DBMS engine. Importantly, in both configurations the underlying execution engine remains unchanged. The only difference lies in the logical optimization phase. We then quantify the overhead introduced by A3D-RA by measuring its optimization time separately. 5.2.5 Execution Setup. ClickHouse and Umbra experiments were conducted locally on a laptop equipped with an AMD RyzenTM 5 PRO 3500U processor with 24.0 GiB of RAM, running Ubuntu 25.04. Umbra was executed using the official Docker image (umbradb/umbra:latest). Snowflake experiments were conducted on the cloud using two warehouse configurations: X-Small (XS) (8 vCPUs, 16 GB RAM) and Large (L) (8×8 vCPUs, 8×16 GB RAM). A timeout threshold of 1200 s was set for each query execution. All reported execution times represent the average of three runs.
5.3
Experimental Results
5.3.1 Real-World Query Evaluation. Figure 4 presents the execution time comparison with ClickHouse and Umbra, and Figure 5 shows the results for Snowflake on two warehouse configurations (XSmall and Large). In both figures, hatched bars indicate queries that encounter memory limit errors, and missing bars represent queries that could not be translated due to unsupported language features. ClickHouse. The A3D-Optimizer delivers significant performance improvements across all successfully translated queries. For 16 queries that execute successfully in native ClickHouse, A3D achieves speedups ranging from 2.84× to 38.75×, with a mean of 11.02×. The most remarkable improvements are observed for Q16 (38.75× faster, from 614.6s to 15.9s), Q13 (20.85× faster), and Q8 (14.30× faster). Notably, queries Q14 and Q18 encounter memory limit errors in native ClickHouse but execute successfully with A3D optimization (completing in 15.8s and 13.5s respectively), demonstrating that our transformations not only improve performance but also enable the execution of otherwise infeasible queries by reducing intermediate result sizes. Umbra. For Umbra, A3D optimization demonstrates particularly strong results in resolving memory limitations. Seven queries (Q1, Q2, Q6, Q7, Q9, Q10, Q17) that fail with memory limit errors in native Umbra execute successfully with A3D optimization, completing in 1.1–6.4s. This highlights the effectiveness of our transformations in reducing memory consumption through early filtering and pre-aggregation. For six queries that execute successfully in native Umbra (Q3, Q4, Q5, Q8, Q11, Q12), A3D achieves moderate speedups with a mean of 1.32×, demonstrating consistent but modest performance gains. Five queries (Q13, Q14, Q15, Q16, Q18) could not be translated by A3D due to unsupported language features. Snowflake. On the X-Small (XS) warehouse, A3D achieves consistent speedups for 13 evaluated queries (Q1–Q12, Q17), ranging from 1.76× to 14.68× with a mean of 5.35×. The most significant gains are observed for Q17 (14.68×), Q3 (8.70×), and Q4 (6.19×).
ClickHouse A3D on ClickHouse
Umbra A3D on Umbra
Memory Limit
Execution Time (s)
Execution Time (s) Log Scale
103
102
101
100
30 25 20 15 10 5 0
ClickHouse A3D On ClickHouse
Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10 Q11 Q12 Q13 Q14
Queries
Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10 Q11 Q12 Q13 Q14 Q15 Q16 Q17 Q18
Queries
Figure 6: Impact of pushing filters under ArrayJoin.
Snowflake WH XS A3D on Snowflake WH XS
Snowflake WH Large A3D on Snowflake WH Large
Execution Time (s)
102
ClickHouse A3D On ClickHouse
100 80 60 40 20 0
101
Q1
Q2
Q3
Queries
Q4
Q5
Q6
Figure 7: Impact of pushing derive under ArrayJoin. Q1
Q2
Q3
Q4
Q5
Q6
Q7
Q8
Q9 Q10 Q11 Q12 Q13 Q15 Q17
Queries
Figure 5: Snowflake runtime: native vs. A3D-RA.
On the Large warehouse, baseline Snowflake performance improves substantially due to increased computational resources. A3D optimization continues to provide speedups for all 13 evaluated queries, ranging from 1.17× to 2.73× with a mean of 1.75×. The best improvements are for Q3 (2.73×), Q17 (2.50×), and Q4 (2.15×). Results show that A3D optimization delivers significant performance gains across different system architectures, with particularly strong results on ClickHouse (mean 11.02×) and Snowflake XS (mean 5.35×). In addition to improving raw performance, A3D can also enable the execution of queries that would otherwise exceed memory limits. For example, queries 14 and 18 are not feasible on ClickHouse without A3D optimizations. 5.3.2 Rule Impact Analysis. To isolate the source of the observed gains, we evaluate whether they stem from a single dominant rule or the combined effect of the entire set using synthetic workloads on ClickHouse, which supports all queries. Impact of pushing down filters under ArrayJoin. Fig. 6 illustrates rules (R2.1–R2.3), which push filters below ArrayJoin. A3DOptimizer achieves speedups ranging from 1.7× to 4× by jointly reducing cardinalities vertically (through 𝜎 filters) and horizontally (through arrayFilter). For Q4, horizontal filtering yields a 3.8× speedup: even with moderately selective filters (≈50%), horizontal reduction drastically limits flattening costs on large arrays. For other queries (Q5–Q7, Q11, Q14), gains range from 1.7× to 2.6× due to combined vertical and horizontal filtering. Queries with minimal improvement (Q1–Q3, Q10, Q13) have low filter selectivity, limiting optimization opportunities.
Execution Time (s)
Execution Time (s) Log Scale
Figure 4: ClickHouse and Umbra runtime: native vs. A3D-RA.
ClickHouse DF-J Plan J-DF Plan Plan chosen by A3D-Optimizer
40 30 20 10 0
Q1
Q2
Q3
Queries
Q4
Q5
Q6
Figure 8: Non-invertible filters: DF-J and J-DF plans. Impact of pushing down derive under ArrayJoin. Fig. 7 shows rules (R5.1, R5.2), which push derive beneath ArrayJoin. A3DOptimizer achieves speedups ranging from 1.61× to 2.79× and consistently outperforms ClickHouse’s native optimizer, where derive operations remain above array flattening. For Q1–Q2, precomputing independent derivations avoids redundant evaluations on duplicated rows. For Q3–Q6, applying transformations at the array level before flattening avoids per-row function calls. Invertibility of Filters. Fig. 8 and 9 analyze the impact of filter invertibility on query performance. In the first case (Fig. 8), where the filter is non-invertible, two alternative plans are possible: applying the derive before the filter then join (DF-J), or performing the join first (J-DF). In contrast, Fig. 9 illustrates the case of invertible filters, where three alternative plans can be considered: FJD, FDJ, and JFD. The A3D-Optimizer consistently selects the most efficient plan. A notable performance gap is observed among the different strategies, particularly for Q5 and Q6, where the join operation significantly increases the cardinality of intermediate results. Introducing Pre-aggregations. Fig. 10 illustrates the impact of distributing aggregations through the introduction of preaggregations. Performance improvements range from 1.52× to 9.22×. The most significant gain is observed for Q4 (9.22× speedup), where
Execution Time (s)
40 30
ClickHouse FJD Plan FDJ Plan JFD Plan Plan chosen by A3D-Optimizer
20 10 0
Q1
Q2
Q3
Queries
Q4
Q5
Q6
Execution Time (s)
Figure 9: Invertible filters: alternative plans.
ClickHouse A3D On ClickHouse
50 40 30 20 10 0
Q1
Q2
Q3
Q4
Queries
Q5
Q6
Q7
Figure 10: Impact of Introducing Pre-aggregations. (a) Pattern A (b) Pattern B
𝜎𝜃 𝑦
𝜎𝜃 1 ∧...∧𝜃𝑛 𝛿 𝑦=𝑓 (𝑎) 𝜇𝑎𝑟𝑟 1 ,...,𝑎𝑟𝑟𝑛 𝜇𝑎 𝑅 𝑅
Optimization Time (s)
Figure 11: Two example patterns used in scalability analysis. 3.0 2.5 2.0 1.5 1.0 0.5 0.0
Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10 Q11 Q12 Q13 Q14 Q15 Q16 Q17 Q18
Queries
Figure 12: Optimization time for 18 real-world queries. pushing an aggregation below an arrayJoin on a large table substantially reduces intermediate data size. Overall, the performance gains arise from a cumulative effect of all transformation rules, with a particularly strong impact from those pushing operators below arrayJoin to enable array-level computation, and from pre-aggregation rules—especially under arrayJoin—that reduce intermediate results and execution costs. 5.3.3 Optimization Time. We now evaluate the optimization overhead introduced by the A3D-Optimizer. Optimization time is measured from the input query to the optimized algebraic plan—before translation to the target DBMS (Figure 3). This measurement is thus independent of the underlying database system.
Optimization Time on Real-World Queries. Figure 12 shows the optimization time for the 18 real-world queries. Optimization times range from 1.05s to 2.80s, with a mean of 1.89s. To assess the costbenefit trade-off, we compute the optimization payoff (OP) as the ratio of execution time gain to optimization cost for each query across all evaluated systems. For ClickHouse, the OP ranges from 9.6× to 515.7× with a mean of 70.4×, demonstrating that each second of optimization saves 70.4 seconds of execution time on average. For instance, query Q16 incurs 1.16s of optimization cost while achieving 598.7s of execution time savings, resulting in an OP of 515.7×. For Snowflake XS, the OP ranges from 11.3× to 37.6× with a mean of 21.5×. For Umbra and Snowflake Large, the OP is more modest (0.8× and 1.1× on average respectively), as most Umbra queries encounter memory limits in the baseline and Snowflake Large already achieves very high performance, limiting the absolute time savings. Overall, the optimization overhead is negligible compared to the performance benefits obtained, especially on ClickHouse and Snowflake XS where OP exceeds 20× on average. Scalability Analysis. We assess how optimization time scales with query complexity, which we define as the number of patterns present in a query. A pattern is a sequence of algebraic operators applied to array-typed columns (see Figure 11). As shown in Section 4.2.6, A3DRA optimization admits a theoretical polynomial upper bound for non-join array operations, and adding patterns directly increases this structural complexity. To study this, we vary two parameters: the number of patterns and the number of arrays per pattern. We consider two patterns shown in Figure 11. Pattern A represents a typical transformation pipeline with ArrayJoin, Derive, and Filter operators, while Pattern B shows multiple arrays being processed with combined filters. We use Pattern A to evaluate scalability with respect to the number of patterns (Figure 13) and Pattern B to evaluate scalability with respect to the number of arrays per pattern (Figure 14). Figure 13 presents the scalability analysis with respect to the number of patterns (pattern A). As the number of patterns increases from 1 to 150, optimization time grows from 0.024s to 416s. The loglog regression analysis (subplot c) reveals a polynomial complexity with an exponent 𝑘 ≈ 2.0, indicating quadratic growth (𝑅 2 > 99%). The normalized growth factor (subplot b) stabilizes around 1.1–1.2 per additional pattern, suggesting predictable scaling behavior. Figure 14 examines scalability with respect to the number of arrays per pattern (pattern B). When varying the number of arrays from 1 to 20, optimization time increases from 0.012s to 14s. The log-log regression yields 𝑘 ≈ 2.2, indicating super-quadratic but still polynomial growth (𝑅 2 = 98.84%). The local growth factor (subplot b) shows an initial spike but stabilizes around 1.15 for higher array counts. This suggests that while multiple arrays increase optimization complexity, the cost remains manageable for typical analytical queries that rarely exceed 10–15 array columns per pattern.
6
RELATED WORK
Arrays in Databases. The idea of supporting arrays in database systems has a long history. Early work on the nested relational model and the Non First Normal Form (NF2 ) data model [18, 27] extended the relational paradigm to allow attributes that are themselves collections. At the query language level, several algebras and
101 100 10 1 0
20
40
60
80
100
Number of Patterns
120
140
(b) Growth per pattern 3.5 3.0 2.5 2.0 1.5 1.0
0
20
40
60
80
100
Number of Patterns
120
140
(c) Log-log regression
6
log(Optimization Time)
102
Normalized Growth Factor
Optimization Time (s)
(a) Log-scale
Data Fit: k 2.00
4 2 0 2 4
0
1
2
3
log(Number of Patterns)
4
5
100 10 1 10 2
2.5
5.0
7.5
10.0 12.5 15.0 17.5 20.0
Number of Arrays
(b) Local growth factor
8 6 4 2 2.5
5.0
7.5
10.0 12.5 15.0 17.5 20.0
log(Optimization Time)
Optimization Time (s)
(a) Log-scale 101
Growth Factor (n / n-1)
Figure 13: Scaling optimization behavior with number of patterns: (a) log-scale, (b) growth factor, (c) log-log regression.
(c) Log-log regression Data Fit: k 2.24
2 0 2 4
Number of Arrays
0.0
0.5
1.0
1.5
2.0
log(Number of Arrays)
2.5
3.0
Figure 14: Scaling optimization behavior with number of arrays per pattern: (a) log-scale, (b) growth factor, (c) log-log regression. formalisms for arrays were proposed, such as AQL [21], RasQL [3], AML [23], RAM [36], and ArrayQL [22, 32]. Building on these foundations, several dedicated array database systems were developed. RasDaMan [3] pioneered array-oriented storage and query processing, emphasizing raster data. SciDB [7] introduced an array-native data model with specialized operators for scientific and analytical workloads. TileDB [28] proposed a universal storage engine for dense and sparse arrays. MonetDB [4, 16] sought to integrate array processing into a columnar relational system, proposing an SQL dialect with array operators. At the same time, mainstream relational systems have gradually incorporated arrays, though typically in an ad-hoc fashion. PostgreSQL introduced native array types and functions, enabling applications to store and manipulate arrays inside relations. More recent systems such as Google BigQuery [24], SparkSQL [2], Snowflake [8], DuckDB (in-memory) [29], Umbra [26], and most recently ClickHouse [33] extend SQL with array-valued functions and user-defined operators. The work on integrating ArrayQL in Umbra [31, 32] provides a set of array operators expressible in relational algebra, its goal is to embed multidimensional array computations into the relational engine. In contrast, our work extends the relational algebra itself with array-valued attributes and compositional transformation rules, enabling systematic optimization of queries that freely interleave relational and array operators. A recent survey [30] provides an in-depth comparison of existing array data management techniques. It observes that no array algebra and query language have gained general acceptance so far. A key reason is that most existing approaches rely heavily on user-defined functions or system-specific extensions, without providing an explicit algebraic foundation that integrates with relational optimization. Our work takes a different approach: instead of building a specialized array DBMS or exposing arrays only via ad hoc extensions, we extend relational algebra itself to treat arrays as first-class citizens, in the spirit of the seminal NF2 work [18]. We
instantiate the framework on top of ClickHouse [33], Umbra [26] and Snowflake [8], demonstrating its practical benefits. Denormalized Data and Column Stores. Beyond arrays, the database community has long studied richer data models that extend relations with nested or semi-structured data. The nested relational algebra [18] formalized operators over nested collections, and subsequent work on unnesting and query flattening [5, 11] addressed optimization challenges. Semi-structured data in JSON format has driven widespread extensions to SQL. These extensions illustrate a general trend: relational systems increasingly embrace denormalized data, moving beyond traditional first normal form. This trend is particularly pronounced in analytical workloads, where denormalized schemas with wide tables and nested attributes are common. Column-oriented database systems, beginning with MonetDB [4] and C-Store [35] and followed by many successors, have proven to be a natural fit for such workloads. They exploit contiguity, compression, and vectorized execution. ClickHouse [33] is a recent column store, with native support for array-valued attributes, which was shown to outperform several state-of-the-art systems [33], including PostgreSQL, Redshift [14], Pinot [17], Umbra [26] and Snowflake [8]. Our prototype implementation, instanciated on top of ClickHouse [33], Umbra [26], and Snowflake [8], demonstrates that algebraic extensions can still unlock further optimization opportunities, with each of these systems.
7
CONCLUSION
This paper introduced an extended relational algebra supporting array-valued attributes, together with a framework for algebraic reasoning and optimization. We defined its formal foundations, a complete set of equivalence-preserving transformation rules, and a plan enumeration strategy with an optimality guarantee and a polynomial complexity in all non-join operators. We designed A3D-RA as a modular, backend-independent optimization layer
that can be instantiated over existing analytical database systems. Experimental results across three analytical engines on a real-world workload demonstrate that the framework can improve query execution performance without requiring modifications to the underlying execution engines. These results show the benefits of treating array operations as first-class algebraic constructs, allowing the optimizer to perform global, systematic rewrites that jointly consider relational and array operators.
REFERENCES [1] Daniel Abadi, Samuel Madden, and Miguel Ferreira. 2006. Integrating compression and execution in column-oriented database systems. In Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data (Chicago, IL, USA) (SIGMOD ’06). Association for Computing Machinery, New York, NY, USA, 671–682. https://doi.org/10.1145/1142473.1142548 [2] Michael Armbrust, Reynold S. Xin, Cheng Lian, Yin Huai, Davies Liu, Joseph K. Bradley, Xiangrui Meng, Tomer Kaftan, Michael J. Franklin, Ali Ghodsi, and Matei Zaharia. 2015. Spark SQL: Relational Data Processing in Spark. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (Melbourne, Victoria, Australia) (SIGMOD ’15). Association for Computing Machinery, New York, NY, USA, 1383–1394. https://doi.org/10.1145/2723372.2742797 [3] Peter Baumann, Andreas Dehmel, Paula Furtado, Roland Ritsch, and Norbert Widmann. 1998. The Multidimensional Database System RasDaMan. In SIGMOD 1998, Proceedings ACM SIGMOD International Conference on Management of Data, June 2-4, 1998, Seattle, Washington, USA, Laura M. Haas and Ashutosh Tiwary (Eds.). ACM Press, 575–577. https://doi.org/10.1145/276304.276386 [4] Peter A. Boncz, Marcin Zukowski, and Niels Nes. 2005. MonetDB/X100: HyperPipelining Query Execution. In Second Biennial Conference on Innovative Data Systems Research, CIDR 2005, Asilomar, CA, USA, January 4-7, 2005, Online Proceedings. www.cidrdb.org, 225–237. http://cidrdb.org/cidr2005/papers/P19.pdf [5] Peter Buneman, Shamim A. Naqvi, Val Tannen, and Limsoon Wong. 1995. Principles of Programming with Complex Objects and Collection Types. Theor. Comput. Sci. 149, 1 (1995), 3–48. https://doi.org/10.1016/0304-3975(95)00024-Q [6] Surajit Chaudhuri and Kyuseok Shim. 1999. Optimization of queries with userdefined predicates. ACM Trans. Database Syst. 24, 2 (June 1999), 177–228. https: //doi.org/10.1145/320248.320249 [7] Philippe Cudré-Mauroux, Hideaki Kimura, Kian-Tat Lim, Jennie Rogers, Roman Simakov, Emad Soroush, Pavel E. Velikhov, Daniel L. Wang, Magdalena Balazinska, Jacek Becla, David J. DeWitt, Bobbi Heath, David Maier, Samuel Madden, Jignesh M. Patel, Michael Stonebraker, and Stanley B. Zdonik. 2009. A Demonstration of SciDB: A Science-Oriented DBMS. Proc. VLDB Endow. 2, 2 (2009), 1534–1537. https://doi.org/10.14778/1687553.1687584 [8] Benoit Dageville, Thierry Cruanes, Marcin Zukowski, Vadim Antonov, Artin Avanes, Jon Bock, Jonathan Claybaugh, Daniel Engovatov, Martin Hentschel, Jiansheng Huang, Allison W. Lee, Ashish Motivala, Abdul Q. Munir, Steven Pelley, Peter Povinec, Greg Rahn, Spyridon Triantafyllis, and Philipp Unterbrunner. 2016. The Snowflake Elastic Data Warehouse. In Proceedings of the 2016 International Conference on Management of Data (San Francisco, California, USA) (SIGMOD ’16). Association for Computing Machinery, New York, NY, USA, 215–226. https: //doi.org/10.1145/2882903.2903741 [9] David DeHaan and Frank Wm. Tompa. 2007. Optimal top-down join enumeration. In Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data (Beijing, China) (SIGMOD ’07). Association for Computing Machinery, New York, NY, USA, 785–796. https://doi.org/10.1145/1247480.1247567 [10] Moshe Dror and George Steiner. 2010. ‘Strong’–‘weak’ precedence in scheduling: Extensions to series–parallel orders. Discrete Applied Mathematics 158, 16 (2010), 1767–1776. https://doi.org/10.1016/j.dam.2010.06.015 [11] Leonidas Fegaras. 1998. Query unnesting in object-oriented databases. In Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data (Seattle, Washington, USA) (SIGMOD ’98). Association for Computing Machinery, New York, NY, USA, 49–60. https://doi.org/10.1145/276304.276310 [12] Pit Fender, Guido Moerkotte, Thomas Neumann, and Viktor Leis. 2012. Effective and Robust Pruning for Top-Down Join Enumeration Algorithms. In 2012 IEEE 28th International Conference on Data Engineering. 414–425. https://doi.org/10. 1109/ICDE.2012.27 [13] Goetz Graefe. 1994. Volcano - An Extensible and Parallel Query Evaluation System. IEEE Trans. Knowl. Data Eng. 6, 1 (1994), 120–135. https://doi.org/10. 1109/69.273032 [14] Anurag Gupta, Deepak Agarwal, Derek Tan, Jakub Kulesza, Rahul Pathak, Stefano Stefani, and Vidhya Srinivasan. 2015. Amazon Redshift and the Case for Simpler Data Warehouses. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (Melbourne, Victoria, Australia) (SIGMOD ’15). Association for Computing Machinery, New York, NY, USA, 1917–1923. https://doi.org/10.1145/2723372.2742795 [15] Joseph M. Hellerstein and Michael Stonebraker. 1993. Predicate migration: optimizing queries with expensive predicates. SIGMOD Rec. 22, 2 (June 1993), 267–276. https://doi.org/10.1145/170036.170078 [16] Stratos Idreos, Fabian Groffen, Niels Nes, Stefan Manegold, K. Sjoerd Mullender, and Martin L. Kersten. 2012. MonetDB: Two Decades of Research in Columnoriented Database Architectures. IEEE Data Eng. Bull. 35, 1 (2012), 40–45. http: //sites.computer.org/debull/A12mar/monetdb.pdf [17] Jean-François Im, Kishore Gopalakrishna, Subbu Subramaniam, Mayank Shrivastava, Adwait Tumbde, Xiaotian Jiang, Jennifer Dai, Seunghyun Lee, Neha Pawar, Jialiang Li, and Ravi Aringunram. 2018. Pinot: Realtime OLAP for 530 Million Users. In Proceedings of the 2018 International Conference on Management of Data (Houston, TX, USA) (SIGMOD ’18). Association for Computing Machinery, New York, NY, USA, 583–594. https://doi.org/10.1145/3183713.3190661
[18] G. Jaeschke and H. J. Schek. 1982. Remarks on the algebra of non first normal form relations. In Proceedings of the 1st ACM SIGACT-SIGMOD Symposium on Principles of Database Systems (Los Angeles, California) (PODS ’82). Association for Computing Machinery, New York, NY, USA, 124–138. https://doi.org/10. 1145/588111.588133 [19] F. P. Kelly. 1982. A Remark on Search and Sequencing Problems. Mathematics of Operations Research 7, 1 (1982), 154–157. http://www.jstor.org/stable/3689367 [20] A. Schulz Lawler smt, M. Queyranne and D. Shmoys. 2006. Weighted sum of completion times. (2006). https://doi.org/10.1016/j.dam.2010.06.015 [21] Leonid Libkin, Rona Machlin, and Limsoon Wong. 1996. A Query Language for Multidimensional Arrays: Design, Implementation, and Optimization Techniques. In Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Quebec, Canada, June 4-6, 1996, H. V. Jagadish and Inderpal Singh Mumick (Eds.). ACM Press, 228–239. https://doi.org/10.1145/ 233269.233335 [22] David Maier, Peter Baumann, Martin Kersten, Kee-Tae Lim, and Michael Stonebraker. 2012. ArrayQL Algebra: Version 3. Technical Report. XLDB. http: //www.xldb.org/wp-content/uploads/2012/09/ArrayQL-Algebra-v3+.pdf [23] Arunprasad P. Marathe and Kenneth Salem. 2002. Query processing techniques for arrays. The VLDB Journal 11, 1 (Aug. 2002), 68–91. https://doi.org/10.1007/ s007780200062 [24] Sergey Melnik, Andrey Gubarev, Jing Jing Long, Geoffrey Romer, Shiva Shivakumar, Matt Tolton, and Theo Vassilakis. 2010. Dremel: Interactive Analysis of Web-Scale Datasets. Proc. VLDB Endow. 3, 1 (2010), 330–339. https: //doi.org/10.14778/1920841.1920886 [25] C.L. Monma. 1981. Sequencing with general precedence constraints. Discrete Applied Mathematics 3, 2 (1981), 137–150. https://doi.org/10.1016/0166-218X(81) 90038-X [26] Thomas Neumann and Michael J. Freitag. 2020. Umbra: A Disk-Based System with In-Memory Performance. In 10th Conference on Innovative Data Systems Research, CIDR 2020, Amsterdam, The Netherlands, January 12-15, 2020, Online Proceedings. www.cidrdb.org. http://cidrdb.org/cidr2020/papers/p29-neumanncidr20.pdf [27] G. Özsoyoğlu, Z. M. Özsoyoğlu, and V. Matos. 1987. Extending relational algebra and relational calculus with set-valued attributes and aggregate functions. ACM Trans. Database Syst. 12, 4 (Nov. 1987), 566–592. https://doi.org/10.1145/32204. 32219 [28] Stavros Papadopoulos, Kushal Datta, Samuel Madden, and Timothy Mattson. 2016. The TileDB array data storage manager. Proc. VLDB Endow. 10, 4 (Nov. 2016), 349–360. https://doi.org/10.14778/3025111.3025117 [29] Mark Raasveldt and Hannes Mühleisen. 2019. DuckDB: an Embeddable Analytical Database. In Proceedings of the 2019 International Conference on Management of Data (SIGMOD ’19). Association for Computing Machinery, New York, NY, USA, 1981–1984. https://doi.org/10.1145/3299869.3320212 [30] Florin Rusu. 2023. Multidimensional Array Data Management. Foundations and Trends in Databases 12, 2-3 (2023), 69–220. https://doi.org/10.1561/1900000069 [31] Maximilian Schüle, Tobias Götz, Alfons Kemper, and Thomas Neumann. 2021. ArrayQL for Linear Algebra within Umbra. In Proceedings of the 33rd International Conference on Scientific and Statistical Database Management (Tampa, FL, USA) (SSDBM ’21). Association for Computing Machinery, New York, NY, USA, 193–196. https://doi.org/10.1145/3468791.3468838 [32] Maximilian E. Schüle, Tobias Götz, Alfons Kemper, and Thomas Neumann. 2022. ArrayQL Integration into Code-Generating Database Systems. In Proceedings of the 25th International Conference on Extending Database Technology, EDBT 2022, Edinburgh, UK, March 29 - April 1, 2022, Julia Stoyanovich, Jens Teubner, Paolo Guagliardo, Milos Nikolic, Andreas Pieris, Jan Mühlig, Fatma Özcan, Sebastian Schelter, H. V. Jagadish, and Meihui Zhang (Eds.). OpenProceedings.org, 1:40– 1:51. https://doi.org/10.5441/002/EDBT.2022.04 [33] Robert Schulze, Tom Schreiber, Ilya Yatsishin, Ryadh Dahimene, and Alexey Milovidov. 2024. ClickHouse - Lightning Fast Analytics for Everyone. Proc. VLDB Endow. 17, 12 (Aug. 2024), 3731–3744. https://doi.org/10.14778/3685800.3685802 [34] Wayne E. Smith. 1956. Various optimizers for single-stage production. Naval Research Logistics Quarterly 3 (1956), 59–66. https://api.semanticscholar.org/ CorpusID:120614124 [35] Michael Stonebraker, Daniel J. Abadi, Adam Batkin, Xuedong Chen, Mitch Cherniack, Miguel Ferreira, Edmond Lau, Amerson Lin, Samuel Madden, Elizabeth J. O’Neil, Patrick E. O’Neil, Alex Rasin, Nga Tran, and Stanley B. Zdonik. 2005. C-Store: A Column-oriented DBMS. In Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway, August 30 - September 2, 2005, Klemens Böhm, Christian S. Jensen, Laura M. Haas, Martin L. Kersten, Per-Åke Larson, and Beng Chin Ooi (Eds.). ACM, 553–564. http://www.vldb. org/archives/website/2005/program/paper/thu/p553-stonebraker.pdf [36] Alex van Ballegooij. 2004. RAM: A Multidimensional Array DBMS. In Current Trends in Database Technology - EDBT 2004 Workshops, EDBT 2004 Workshops PhD, DataX, PIM, P2P&DB, and ClustWeb, Heraklion, Crete, Greece, March 14-18, 2004, Revised Selected Papers (Lecture Notes in Computer Science), Wolfgang Lindner, Marco Mesiti, Can Türker, Yannis Tzitzikas, and Athena Vakali (Eds.), Vol. 3268. Springer, 154–165. https://doi.org/10.1007/978-3-540-30192-9_15
[37] Maroua Zeblah, Etienne Couritas, Sarah Chlyah, Pierre Genevès, Nils Gesbert, and Nabil Layaïda. 2026. Queries and Experimental Details for “Optimizing
Relational Queries over Array-Valued Data in Columnar Systems”. https://gitlab. inria.fr/tyrex-public/a3dra.