Module grammar

Expand description

§Substrait Text Format Grammar

This document describes the grammar for the human-readable Substrait text format used by substrait-explain. This format allows you to write Substrait query plans in a concise, readable text format that can be parsed back into full Substrait protobuf plans.

§Overview

The Substrait text format consists of two main sections:

Extensions Section (optional) - Defines URIs and function/type extensions
Plan Section - Contains the actual query plan with relations

§Design Principles

The grammar is designed around several concrete choices that make it practical and consistent:

§1. Single-Line, Structured Relations

All relations follow the same structure: Name[arguments => columns]

Name: The relation type (Read, Filter, Project, etc.)
Arguments: Relation-specific: input expressions, field references, or function calls
- Arguments follow a regular pattern (tuple, input expression, etc.) or combination, and should map directly to Substrait proto fields. Uses tuples for compound arguments, with literals, expressions, and enums for values.
Arrow: => separates arguments from output columns
Columns: Output column names and types

Every relation fits on one line with indentation showing hierarchy. This uniform pattern makes it easy to parse any relation, understand input/output structure, and add new relation types.

§2. SQL-Like References, Literals, and Enums

Field references: $0, $1, etc.
Types are shown inline with literals and column names: 42:i64, 'hello':string
Nullability is explicit: string? for nullable, string for non-nullable

This prevents ambiguity and makes plans self-documenting while being familiar to SQL developers.

§3. Extension Support and Structured Syntax

Extensions section defines URIs and function/type mappings.
Function calls can include anchors: add#10@1($0, $1).
Clear structural boundaries: [] for relations, <> for types, () for functions.
Maintains full Substrait compatibility while keeping the text format readable and parseable.

§4. Hierarchical Organization

Section headers (===) separate major components.
2-space indentation shows query plan hierarchy.
Consistent formatting across all document elements.

The format maps directly to Substrait protobuf messages, with relations, expressions, types, and extensions corresponding to their respective protobuf structures.

§Grammar Notation

This document uses PEG (Parsing Expression Grammar) notation:

"text" - Literal text
element? - Optional element
element* - Zero or more repetitions
element+ - One or more repetitions
element1 / element2 - Choice (try element1 first)
- Implementation Note: Pest uses | instead of /
element1 element2 - Sequence
- Implementation Note: Pest uses ~ for explicit concatenation

§Basic Example

=== Extensions
URIs:
  @  1: https://github.com/substrait-io/substrait/blob/main/extensions/functions_arithmetic.yaml
Functions:
  # 10 @  1: add
  # 11 @  1: multiply

=== Plan
Root[result]
  Project[$0, $1, add($0, $1)]
    Read[orders => quantity:i32?, price:i64]

§Document Structure

A Substrait text format document consists of two main sections with specific formatting rules.

§Sections

The document uses === headers to separate major sections:

=== Extensions - Defines URIs and function/type mappings (optional)
=== Plan - Contains the actual query plan (required)

§Extension format

=== Extensions
URIs:
  @  uri_anchor: uri
  …
Functions:
  ##  anchor @  uri_anchor: name
  …
Types:
  ##  anchor @  uri_anchor: name
  …
Type Variations:
  ##  anchor @  uri_anchor: name
  …

Where anchor and uri_anchor are integers, uri is a text URI, and function, type, and type variation names are identifiers or quoted text.

§Plan Hierarchy and Indentation

Relations use indentation to show the query plan hierarchy:

Root level: No indentation (typically Root relation)
Child relations: Indented with 2 spaces per level
Each relation: On its own line with format Name[arguments => columns]

§Example

=== Extensions
URIs:
  @  1: https://github.com/substrait-io/substrait/blob/main/extensions/functions_arithmetic.yaml
Functions:
  # 10 @  1: gt

=== Plan
Root[result]                   // Level 0 (no indentation)
  Project[$0, $1]              // Level 1 (2 spaces)
    Filter[gt($0, 10) => $0]   // Level 2 (4 spaces)
      Read[data => a:i64]      // Level 3 (6 spaces)

§Basic Terminals

§Character Classes

letter := [a-zA-Z] - Alphabetic characters
digit := [0-9] - Numeric digits

§`name` and `identifier`

name := identifier / quoted_name
- Used for column names, function names, etc. It can be unquoted if it’s a valid identifier, or using “double quotes” if special characters are required (much like SQL)
- Examples: function_name, "quoted name"
identifier := letter (letter / digit / "_")*
- Used for columns, function names, etc. that are proper identifiers.
- Examples: table_name, my_function, col1
quoted_name := '"' ("\\" . / !'"' .)* '"'
- Used for columns, function names, etc. that are not valid as identifiers, and thus need quoting.
- Examples: "function name", "table.name", "table\.name", "function \"with some\nescapes\""

§`enum`

Enum fields in arguments are represented as &-prefixed variants (e.g., &AscNullsFirst), matching the Substrait proto definition. This applies to all enum fields in relation arguments.

§Syntax

enum := "&" identifier

§Examples

&AscNullsFirst, &AscNullsLast, &DescNullsFirst, &DescNullsLast - sort directions

§`literal`

A literal can come in the form of an integer, float, boolean, or string, and can have an optional additional type:

literal := (integer / float / boolean / string) (":" type)?

integer := "-"? digit+
- Examples: 42, -10, 0
- Default to i64 type; other integer types may be assigned
float := "-"? digit+ "." digit+
- Examples: 3.14, -2.5, 1.0
- Default to fp64 type; other float types may be assigned
boolean := "true" / "false"
- Examples: true, false
- May only be boolean type
string := "'" ("\\" . / !"'" .)* "'"
- Examples: 'hello', 'table name', 'C:\path\to\file', 'line1\nline2', 'quote\'s here'
- Default to string type; other types may also be assigned
typed_literal := string ":" type
- String literals with type annotations for non-primitive types
- Examples: '2023-01-01':date, '2023-12-25T14:30:45.123':timestamp

TODO: The current Pest grammar only supports integer and string. The grammar needs to be extended to support float, boolean, and typed literals as described above.

§Types

The type syntax in this grammar follows the standard Substrait type definition syntax, with extensions to support anchors and URI references for user-defined types.

§Type Syntax Overview

All types follow this general pattern:

type := "u!"? name anchor? uri_anchor? nullability? parameters?

Where:

"u!" - Optional prefix for user-defined types
name - Type name (case-insensitive, lowercase preferred)
anchor := "#" integer - Extension anchor (e.g., #10)
uri_anchor := "@" integer - URI anchor (e.g., @1)
nullability := "?" - Optional nullability indicator (defaults to non-nullable)
parameters := "<" (param ("," param)*)? ">" - Optional type parameters
param := type / integer / name - Type parameter (type, integer, or name)

§Simple Types

Simple types are the basic Substrait types with optional nullability.

§Syntax

simple_type_name nullability?

§Simple Type Names

From official Substrait grammar, simple_type_name can be any of these literal strings:

boolean, i8, i16, i32, i64
fp32, fp64
string, binary
timestamp, timestamp_tz, date, time
interval_year, uuid

§Nullability

? - nullable
⁉ - unspecified nullability (not generally valid)
(nothing) - non-nullable

§Examples:


let plan_text = r#"
=== Plan
Root[result]
  Project[$0, $1]
    Read[data => int_field:i64, string_field:string?]
"#;

§Compound Types

Compound types follow the same syntax as standard Substrait parameterized types.

§Examples

// TODO: This example uses map type, which is not yet implemented in the parser.

use substrait_explain::parser::Parser;

let plan_text = r#"
=== Plan
Root[result]
  Project[$0, $1, $2]
    Read[data => list_field:list<i64>, map_field:map<string, i64>, struct_field:struct<i64, string?>]
"#;

let plan = Parser::parse(plan_text).unwrap();
assert_eq!(plan.relations.len(), 1);

§User-Defined Types

User-defined types extend the standard Substrait UDT syntax to support anchors and URI references.

§Syntax

"u!"? name anchor? uri_anchor? nullability? parameters?

§Key differences from standard Substrait

The u! prefix is optional (can be omitted when anchors are present)
Adds optional anchor and uri_anchor for extension references
Maintains compatibility with standard Substrait UDT syntax

§Examples

=== Extensions
URIs:
  @  1: https://example.com/types
  @  2: https://example.com/functions
Types:
  #  8 @  1: point
  #  9 @  1: custom_type
Functions:
  # 10 @  2: add

=== Plan
Root[result]
  Project[$0, $1, $2]
    Read[data => point_field:point#8@1?<i8>, custom_field:custom_type#9, prefixed_field:u!custom_type]

§Expressions

§Syntax

expression := function_call / reference / literal

§Examples

add($3, 10)            // Simple function call
add#10@2(#3, 10):int   // Function call with anchors and type

§Field References

Currently, only references to fields in the Relations’ input are supported.

§Syntax

reference := "$" integer

§Examples

use substrait_explain::parser::Parser;

let plan_text = r#"
=== Plan
Root[result]
  Project[$0, $1, $42]
    Read[data => field0:i64, field1:string, field42:boolean]
"#;

let plan = Parser::parse(plan_text).unwrap();
assert_eq!(plan.relations.len(), 1);

§Function Calls

§Syntax

function_call := name anchor? uri_anchor? "(" (expression ("," expression)*)? ")" (":" type)?

§Components

name - function name
anchor - optional anchor (e.g., #10)
uri_anchor - optional URI anchor (e.g., @1)
expression - as above
type - optional output type

§Aggregate Measures

Aggregate measures are used in the output of Aggregate relations. They can be either field references (to pass through existing fields) or aggregate function calls (to compute aggregates).

§Syntax

aggregate_measure := name anchor? uri_anchor? "(" expression ")" (":" type)? - aggregate function call with optional extension anchors and output type
Field references: $0, $1, …

§Examples

sum($2)
count($1)
avg($3):fp64
$0 (field reference to grouping field)

§Relations

Relations represent the operations in a query plan. Each relation is displayed on a single line with indentation showing the hierarchy.

§General Relation Grammar

All relations follow this general pattern:

§Syntax

relation := name "[" (arguments ("," named_arguments)? ("=>" columns)?)? "]"
columns := name ("," name)* / reference_list

Where:

name: The type of operation (Read, Filter, Project, Root, etc.)
arguments: Input expressions, field references, function calls, or other parameters (optional)
named_arguments: Named arguments (optional)
=>: Separator between arguments and output columns (optional, only present when both arguments and columns are specified)
columns: Output column names and types, or field references for pass-through (all relations specify outputs, but format varies)

§Example

RelationName[arguments, named_arguments => columns]

§Special cases

Root relation: Only specifies output column names, no arguments or => separator
Project relation: Only specifies expressions, no => separator or output columns
Some relations may use ‘…’ instead of column names when they pass through all fields

The exact structure varies by relation type, but all follow this basic pattern.

§Arguments

Arguments in relations can be literals, expressions, enums, or tuples thereof.

§Syntax

argument := literal / expression / enum / tuple
tuple := "(" argument ("," argument)* ")"
arguments := argument ("," argument)*
named_arguments := name "=" argument ("," name "=" argument)*

§Examples

Simple arguments: $0, 42, 'hello', &AscNullsFirst
Tuple arguments: ($0, &AscNullsFirst), (limit=10, offset=5)
Named arguments: limit=10, offset=5

§Root Relation

§Syntax

"Root" "[" (name ("," name)*)? "]"

§Example

=== Plan
Root[c, d]           // root with output columns c and d
  Project[$0, $1]
    Read[data => a:i64, b:string]

§Read Relation

§Syntax

"Read" "[" table_name "=>" (named_column ("," named_column)*)? "]"

§Components

table_name := name ("." name)* - table name, optionally qualified with schema/database
named_column := name ":" type - column name with type annotation

§Example

=== Plan
Root[result]
  Project[$0, $1]
    Read[schema.table => a:i64, b:string?]
Root[result2]
  Project[$0, $1]
    Read[orders => quantity:i32?, price:i64]

§Filter Relation

§Syntax

"Filter" "[" expression "=>" reference_list "]"

§Components

expression - boolean expression for filtering
reference_list := reference ("," reference)* - comma-separated list of field references to pass through

§Example

=== Extensions
URIs:
  @  1: https://github.com/substrait-io/substrait/blob/main/extensions/functions_arithmetic.yaml
Functions:
  # 10 @  1: gt

=== Plan
Root[result]
  Filter[gt($2, 100) => $0, $1, $2]
    Project[$0, $1, $2]
      Read[data => a:i64, b:string, c:i32]

§Project Relation

§Syntax

"Project" "[" (expression ("," expression)*)? "]"

§Components

expression - field reference, function call, or literal (see Expressions section)

§Example

=== Plan
Root[result]
  Project[$1, 42]                    // project field 1 and literal 42
    Read[data => a:i64, b:string]

§Aggregate Relation

§Syntax

"Aggregate" "[" group_by "=>" aggregate_output "]"

§Components

group_by := reference_list | "_" - comma-separated list of field references for grouping, or _ for global aggregation
aggregate_output := (reference | aggregate_measure) ("," (reference | aggregate_measure))* - comma-separated list of output items
aggregate_measure - field references or aggregate function calls. See Aggregate Measures section

§Example

=== Extensions
URIs:
  @  1: https://github.com/substrait-io/substrait/blob/main/extensions/functions_aggregate.yaml
Functions:
  # 10 @  1: sum
  # 11 @  1: count

=== Plan
Root[result]
  Aggregate[$0 => $0, sum($1), count($2)]           // Group by field 0
    Read[orders => category:string, amount:i64]

§Sort Relation

The Sort relation specifies sort fields and directions for ordering the input:

Sort[($0, &AscNullsFirst), ($1, &DescNullsLast) => $0, $1]

§Syntax

sort_relation := "Sort" "[" sort_fields "=>" reference_list "]"
sort_fields := sort_field ("," sort_field)*
sort_field := "(" reference "," sort_direction ")"
sort_direction := "&AscNullsFirst" / "&AscNullsLast" / "&DescNullsFirst" / "&DescNullsLast"

§Components

Each sort field is a tuple: (reference, sort_direction)
Sort directions follow the general enum syntax and specify null handling
The columns after => specify the output field order (typically a reference list)

§Join Relation

Syntax: "Join" "[" join_type "," expression "=>" reference_list "]"

Components:

join_type - Join type enum with & prefix (e.g., &Inner, &Left, &Right, &Outer)
expression - Join condition (boolean expression relating left and right inputs)
reference_list - Comma-separated list of field references for output columns

Field Reference Mapping:

For joins, field references map to the combined schema of left and right inputs:

$0, $1, … refer to left input fields
$n, $n+1, … refer to right input fields (where n = number of left fields)

Example:

=== Extensions
URIs:
  @  1: https://github.com/substrait-io/substrait/blob/main/extensions/functions_comparison.yaml
Functions:
  # 10 @  1: eq

=== Plan
Root[user_orders]
  Join[&Inner, eq($0, $2) => $0, $1, $3]
    Read[users => id:i64, name:string]        // Fields $0, $1
    Read[orders => user_id:i64, amount:i32]   // Fields $2, $3

§Complete Example

A complete query that joins users and orders tables, calculates total order value, filters for high-value orders, and groups by user to show total revenue per customer:

=== Extensions
URIs:
  @  1: https://github.com/substrait-io/substrait/blob/main/extensions/functions_comparison.yaml
  @  2: https://github.com/substrait-io/substrait/blob/main/extensions/functions_arithmetic.yaml
  @  3: https://github.com/substrait-io/substrait/blob/main/extensions/functions_aggregate.yaml
Functions:
  # 10 @  1: eq
  # 11 @  1: gt
  # 12 @  2: multiply
  # 13 @  3: sum

=== Plan
Root[customer_revenue]
  Aggregate[$0, $1 => $0, $1, sum($3)]
    Filter[gt($3, 100) => $0, $1, $2, $3]
      Project[$0, $1, $2, multiply($4, $5)]
        Join[&Inner, eq($0, $3) => $0, $1, $2, $3, $4, $5]
          Read[users => id:i64, name:string, region:string]
          Read[orders => user_id:i64, quantity:i32, price:i64]

Module grammarCopy item path

§Substrait Text Format Grammar

§Overview

§Design Principles

§1. Single-Line, Structured Relations

§2. SQL-Like References, Literals, and Enums

§3. Extension Support and Structured Syntax

§4. Hierarchical Organization

§Grammar Notation

§Basic Example

§Document Structure

§Sections

§Extension format

§Plan Hierarchy and Indentation

§Example

§Basic Terminals

§Character Classes

§name and identifier

§enum

§Syntax

§Examples

§literal

§Types

§Type Syntax Overview

§Simple Types

§Syntax

§Simple Type Names

§Nullability

§Examples:

§Compound Types

§Examples

§User-Defined Types

§Syntax

§Key differences from standard Substrait

§Examples

§Expressions

§Syntax

§Examples

§Field References

§Syntax

§Examples

§Function Calls

§Syntax

§Components

§Aggregate Measures

§Syntax

§Examples

§Relations

§General Relation Grammar

§Syntax

§Example

§Special cases

§Arguments

§Syntax

§Examples

§Root Relation

§Syntax

§Example

§Read Relation

§Syntax

§Components

§Example

§Filter Relation

§Syntax

§Components

§Example

§Project Relation

§Syntax

§Components

§Example

§Aggregate Relation

§Syntax

§Components

§Example

§Sort Relation

§Syntax

§Components

§Join Relation

§Complete Example

Module grammar

§`name` and `identifier`

§`enum`

§`literal`