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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/// A lightweight, copy-able identifier for interned strings.
///
/// # What is a Symbol?
///
/// A `Symbol` is a numeric handle that represents a string stored in an
/// [`Interner`]. Instead of passing `String` or `&str` around the entire
/// compiler/database pipeline, we pass a `Symbol` — a single `u32`.
///
/// This matters because:
/// - `String` is 24 bytes on the stack + heap allocation
/// - `Symbol` is 4 bytes on the stack, no heap allocation
/// - Comparing two `Symbol`s is a single integer comparison (`u32 == u32`)
/// - Comparing two `String`s requires scanning every character
///
/// # Why interning?
///
/// In a SQL engine, the same identifier appears many times:
///
/// ```sql
/// SELECT users.id, users.name, users.email
/// FROM users
/// WHERE users.id = 1
/// ```
///
/// Without interning: `"users"` allocates a new `String` 4 times.
/// With interning: `"users"` is stored once, referenced as `Symbol(3)` everywhere.
///
/// This means:
/// - Zero redundant heap allocations for repeated identifiers
/// - O(1) equality checks instead of O(n) string scans
/// - Smaller AST nodes, catalog entries, and plan nodes
/// - Better cache locality — plan nodes fit in fewer cache lines
///
/// # How it works
///
/// ```text
/// "users" ─── intern() ──→ Symbol(0)
/// "id" ─── intern() ──→ Symbol(1)
/// "name" ─── intern() ──→ Symbol(2)
/// "users" ─── intern() ──→ Symbol(0) ← same symbol, no new allocation
/// ```
///
/// To get the string back: `interner.resolve(Symbol(0))` → `"users"`
///
/// # Usage in the pipeline
///
/// Every layer of the engine uses `Symbol` instead of `String` for names:
///
/// ```text
/// Parser → produces Symbol from source &str via Interner
/// AST → stores Symbol in ColumnDef, TableRef, FunctionParam etc.
/// Binder → looks up Symbol in Catalog, compares Symbols for resolution
/// Logical Plan → Symbol in column references, table references
/// Optimizer → Symbol comparisons for predicate pushdown, projection pruning
/// Executor → Symbol for column lookup in row batches
/// Catalog → Symbol as HashMap keys for O(1) table/column lookup
/// ```
///
/// # Properties
///
/// - [`Copy`] — passed by value everywhere, no `.clone()` needed
/// - [`Eq`] + [`Hash`] — usable as `HashMap` keys directly
/// - [`PartialEq`] — `sym_a == sym_b` is a single integer comparison
///
;