OLAP – Phase 5 Vectorized Expressions and Scan/Filter/Project
The storage layer can persist and read columnar data. Now we need to query it. This phase builds the execution engine’s foundation: expressions that evaluate on entire vectors at once (2048 rows per call), and three physical operators — SeqScan, Filter, and Projection — that form the basic query pipeline.
The key insight is vectorized execution: instead of evaluating amount > 100 one row at a time, we evaluate it on 2048 rows at once in a tight loop. This eliminates per-row function call overhead and lets the CPU pipeline and cache work efficiently.
In DuckDB, these are Expression (src/include/duckdb/planner/expression.hpp), PhysicalTableScan (src/execution/operator/scan/physical_table_scan.cpp), PhysicalFilter, and PhysicalProjection.
Here is the roadmap for the phases to come:
- Phase 5: Vectorized expressions and scan/filter/project
- Phase 6: Hash aggregation
- Phase 7: Hash join
- Phase 8: SQL parser
- Phase 9: Query planner and optimizer
- Phase 10: Sorting, parallel execution, REPL, and server
Full Source Code
The code referenced in this post can be found in https://gitlab.com/kimserey.lam/olap-learn.
Physical Operator Interface
Every operator in the execution pipeline implements a simple Volcano-style iterator:
1
2
3
4
5
type PhysicalOperator interface {
Init()
Next() *vector.DataChunk
Close()
}
Operators form a tree: a parent pulls data from its children by calling Next(). When Next() returns nil, the input is exhausted.
Expressions
An Expression takes a DataChunk (the current batch of rows) and returns a Vector (one result per row):
1
2
3
4
type Expression interface {
Execute(chunk *vector.DataChunk) *vector.Vector
ResultType() vector.LogicalType
}
ColumnRefExpr
References a column by index — just returns the existing vector from the chunk:
1
2
3
4
5
6
7
8
type ColumnRefExpr struct {
ColumnIndex int
ReturnType vector.LogicalType
}
func (e *ColumnRefExpr) Execute(chunk *vector.DataChunk) *vector.Vector {
return chunk.Column(e.ColumnIndex)
}
ConstantExpr
Returns a constant vector — a single value broadcast to all rows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type ConstantExpr struct {
Value any
Typ vector.LogicalType
}
func (e *ConstantExpr) Execute(chunk *vector.DataChunk) *vector.Vector {
v := vector.NewConstantVector(e.Typ)
if e.Value == nil {
v.SetNullValue(0)
} else {
v.SetValue(0, e.Value)
}
v.SetCount(chunk.Count())
return v
}
ComparisonExpr
Compares two sub-expressions element-wise, producing a boolean vector:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
type ComparisonExpr struct {
Left Expression
Right Expression
Op ComparisonType // Equal, NotEqual, LessThan, etc.
}
func (e *ComparisonExpr) Execute(chunk *vector.DataChunk) *vector.Vector {
left := e.Left.Execute(chunk)
right := e.Right.Execute(chunk)
count := chunk.Count()
result := vector.NewFlatVector(vector.Boolean)
result.SetCount(count)
bools := result.BoolData()
for i := 0; i < count; i++ {
li := vecIdx(left, i)
ri := vecIdx(right, i)
if !left.IsValid(li) || !right.IsValid(ri) {
result.SetNull(i) // NULL propagation
continue
}
bools[i] = compareAtIndex(left, li, right, ri, e.Op)
}
return result
}
The vecIdx helper returns 0 for constant vectors (always read the single value) or i for flat vectors:
1
2
3
4
5
6
func vecIdx(v *vector.Vector, i int) int {
if v.IsConstant() {
return 0
}
return i
}
ConjunctionExpr (AND / OR)
Combines boolean vectors with SQL three-valued logic. The key subtlety: NULL AND false = false (not NULL), because false short-circuits regardless:
1
2
3
4
5
6
7
8
9
10
case ConjAnd:
if aValid && !aBools[ai] {
bools[i] = false // false AND anything = false
} else if bValid && !bBools[bi] {
bools[i] = false // anything AND false = false
} else if aValid && bValid {
bools[i] = aBools[ai] && bBools[bi]
} else {
result.SetNull(i) // NULL AND true = NULL
}
ArithmeticExpr
Performs arithmetic (+, -, *, /) with type promotion and null propagation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func (e *ArithmeticExpr) Execute(chunk *vector.DataChunk) *vector.Vector {
left := e.Left.Execute(chunk)
right := e.Right.Execute(chunk)
for i := 0; i < count; i++ {
if !left.IsValid(li) || !right.IsValid(ri) {
result.SetNull(i)
continue
}
lf := toFloat64(left, li)
rf := toFloat64(right, ri)
if e.Op == ArithDiv && rf == 0 {
result.SetNull(i) // division by zero → NULL
continue
}
// compute and store result
}
}
Type promotion follows the rule: if either operand is Float64, the result is Float64; otherwise if either is Int64, the result is Int64; otherwise Int32.
Sequential Scan with Zone Map Pruning
The scan operator reads DataChunks from a table’s row groups, optionally using zone maps to skip row groups that can’t contain matches:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
type SeqScanOperator struct {
table *catalog.Table
columnIndices []int
predicate *ZoneMapPredicate
rgIdx int
}
func (s *SeqScanOperator) Next() *vector.DataChunk {
for s.rgIdx < len(s.table.RowGroups) {
rg := s.table.RowGroups[s.rgIdx]
s.rgIdx++
if s.predicate != nil && s.canSkip(rg) {
continue // zone map says no match possible
}
chunk := rg.ToDataChunk(s.columnIndices)
if chunk.Count() > 0 {
return chunk
}
}
return nil
}
Zone map pruning is a coarse-grained filter — it eliminates entire row groups (122,880 rows) before any decompression happens. The fine-grained filter (row-level) is handled by the FilterOperator.
Filter Operator
The filter evaluates a predicate expression, converts the boolean result to a SelectionVector, and compacts the chunk to only include matching rows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func (f *FilterOperator) Next() *vector.DataChunk {
for {
chunk := f.child.Next()
if chunk == nil {
return nil
}
sel := f.executor.Select(f.predicate, chunk)
if sel.Count() == 0 {
continue // no matches, try next chunk
}
if sel.Count() == chunk.Count() {
return chunk // all match, pass through
}
return compactChunk(chunk, sel) // partial match
}
}
compactChunk copies only the matching rows (identified by the SelectionVector) into a new DataChunk:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func compactChunk(chunk *vector.DataChunk, sel *vector.SelectionVector) *vector.DataChunk {
types := chunk.Types()
result := vector.NewDataChunk(types)
for col := 0; col < chunk.ColumnCount(); col++ {
src := chunk.Column(col)
dst := result.Column(col)
for _, idx := range sel.Indices() {
if !src.IsValid(int(idx)) {
dst.AppendNull()
} else {
appendTyped(dst, src, int(idx))
}
}
}
result.SetCount(sel.Count())
return result
}
Projection Operator
The projection evaluates a list of output expressions and assembles the results into a new DataChunk:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
type ProjectionOperator struct {
child PhysicalOperator
expressions []Expression
}
func (p *ProjectionOperator) Next() *vector.DataChunk {
chunk := p.child.Next()
if chunk == nil {
return nil
}
types := make([]vector.LogicalType, len(p.expressions))
for i, expr := range p.expressions {
types[i] = expr.ResultType()
}
result := vector.NewDataChunk(types)
for i, expr := range p.expressions {
v := expr.Execute(chunk)
result.SetColumn(i, v)
}
result.SetCount(chunk.Count())
return result
}
The Pipeline
A query like SELECT region, amount * 1.1 FROM orders WHERE amount > 100 becomes:
1
2
3
ProjectionOperator [region, amount * 1.1]
└── FilterOperator [amount > 100]
└── SeqScanOperator [orders, columns: region, amount]
Data flows bottom-up: SeqScan yields DataChunks → Filter keeps only rows where amount > 100 → Projection computes the output columns.
Summary
The execution engine processes data in 2048-row batches through a pipeline of operators. Expressions evaluate on entire vectors at once, with null propagation and type promotion. Zone map pruning at the scan level eliminates row groups before decompression, and SelectionVector-based filtering at the operator level avoids unnecessary data copying.
