lib/sql/src/statement/predicate.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const sql = @import("../root.zig");
3 const access_mod = @import("access.zig");
4 const ast_mod = @import("ast.zig");
5 const execute_mod = @import("execute.zig");
6 const result_mod = @import("result.zig");
7 const relation_mod = sql.relation;
8 const catalog_mod = sql.catalog;
9 const index_mod = sql.index;
10 const key = sql.key;
11 const page = sql.page;
12 const row = sql.row;
13
14 const Allocator = std.mem.Allocator;
15
16 pub const IndexedPredicate = struct {
17 field: usize,
18 index_slot: usize,
19 predicate_index: usize,
20 operator: ast_mod.PredicateOperator,
21 prefix_count: usize = 1,
22 equality_count: usize = 0,
23 prefix_fields: [relation_mod.max_index_fields]usize = undefined,
24 prefix_predicates: [relation_mod.max_index_fields]usize = undefined,
25 cost: access_mod.AccessCost = .{},
26 };
27
28 pub const ScannedPredicate = struct {
29 field: usize,
30 predicate_index: usize,
31 collation: row.Collation,
32 operator: ast_mod.PredicateOperator,
33 cost: access_mod.AccessCost = .{},
34 };
35
36 pub const RowidPredicate = struct {
37 predicate_index: usize,
38 operator: ast_mod.PredicateOperator,
39 };
40
41 pub fn rowidEqualityOnly(predicates: []const ast_mod.Predicate) ?ast_mod.Expression {
42 if (predicates.len != 1) return null;
43 const predicate = predicates[0];
44 if (predicate.operator != .eq) return null;
45 return switch (predicate.column) {
46 .rowid => predicate.value,
47 .field => null,
48 };
49 }
50
51 pub fn firstRowidPredicate(predicates: []const ast_mod.Predicate, operator: ast_mod.PredicateOperator) ?usize {
52 for (predicates, 0..) |predicate, offset| {
53 if (predicate.operator != operator) continue;
54 switch (predicate.column) {
55 .rowid => return offset,
56 .field => {},
57 }
58 }
59 return null;
60 }
61
62 pub fn firstRowidRangePredicate(predicates: []const ast_mod.Predicate) ?usize {
63 for (predicates, 0..) |predicate, offset| {
64 if (predicate.operator == .eq) continue;
65 switch (predicate.column) {
66 .rowid => return offset,
67 .field => {},
68 }
69 }
70 return null;
71 }
72
73 pub const RuntimePredicates = struct {
74 predicates: []ast_mod.Predicate,
75 values: []row.Value,
76 heap_predicates: bool,
77 heap_values: bool,
78
79 pub fn deinit(self: RuntimePredicates, allocator: Allocator) void {
80 if (self.heap_predicates) allocator.free(self.predicates);
81 if (self.heap_values) allocator.free(self.values);
82 }
83 };
84
85 pub const OwnedPredicates = struct {
86 predicates: []ast_mod.Predicate,
87 values: []row.Value,
88
89 pub fn deinit(self: *OwnedPredicates, allocator: Allocator) void {
90 for (self.values) |value| result_mod.freeValue(allocator, value);
91 allocator.free(self.values);
92 allocator.free(self.predicates);
93 self.* = undefined;
94 }
95 };
96
97 pub fn runtimePredicates(prepared: *const execute_mod.Prepared, source: []const ast_mod.Predicate, allocator: Allocator, predicate_stack: []ast_mod.Predicate, value_stack: []row.Value) ast_mod.Error!RuntimePredicates {
98 const count = source.len;
99 const predicates = if (count <= predicate_stack.len)
100 predicate_stack[0..count]
101 else
102 try allocator.alloc(ast_mod.Predicate, count);
103 errdefer if (count > predicate_stack.len) allocator.free(predicates);
104 const values = if (count <= value_stack.len)
105 value_stack[0..count]
106 else
107 try allocator.alloc(row.Value, count);
108 errdefer if (count > value_stack.len) allocator.free(values);
109 for (predicates, values, source) |*predicate, *value, origin| {
110 predicate.* = origin;
111 value.* = prepared.expressionValue(origin.value);
112 }
113 return .{
114 .predicates = predicates,
115 .values = values,
116 .heap_predicates = count > predicate_stack.len,
117 .heap_values = count > value_stack.len,
118 };
119 }
120
121 pub fn ownedPredicates(allocator: Allocator, prepared: *const execute_mod.Prepared, source: []const ast_mod.Predicate) ast_mod.Error!OwnedPredicates {
122 const count = source.len;
123 const predicates = try allocator.alloc(ast_mod.Predicate, count);
124 errdefer allocator.free(predicates);
125 const values = try allocator.alloc(row.Value, count);
126 errdefer allocator.free(values);
127 var initialized: usize = 0;
128 errdefer for (values[0..initialized]) |value| result_mod.freeValue(allocator, value);
129 for (predicates, values, source) |*predicate, *value, origin| {
130 predicate.* = origin;
131 value.* = try result_mod.copyValue(allocator, prepared.expressionValue(origin.value));
132 initialized += 1;
133 }
134 return .{
135 .predicates = predicates,
136 .values = values,
137 };
138 }
139
140 pub fn selectPredicateCount(select: ast_mod.Select) usize {
141 return select.predicates.len;
142 }
143
144 pub fn selectPredicateAt(select: ast_mod.Select, index: usize) ast_mod.Predicate {
145 return select.predicates[index];
146 }
147
148 pub fn validatePredicates(predicates: []const ast_mod.Predicate, definitions: []const catalog_mod.ColumnDefinition) ast_mod.Error!void {
149 for (predicates) |predicate| {
150 switch (predicate.column) {
151 .rowid => {},
152 .field => |name| _ = access_mod.columnIndex(definitions, name) orelse return error.ColumnNotFound,
153 }
154 }
155 }
156
157 pub fn scannedPredicate(select: ast_mod.Select, handle: *const catalog_mod.RelationHandle, stats: ?*const catalog_mod.RelationStats) ast_mod.Error!?ScannedPredicate {
158 var offset: usize = 0;
159 while (offset < selectPredicateCount(select)) : (offset += 1) {
160 const predicate = selectPredicateAt(select, offset);
161 switch (predicate.column) {
162 .rowid => {},
163 .field => |name| {
164 const field = access_mod.columnIndex(handle.definitions, name) orelse return error.ColumnNotFound;
165 return .{
166 .field = field,
167 .predicate_index = offset,
168 .collation = handle.definitions[field].column.collation,
169 .operator = predicate.operator,
170 .cost = access_mod.scanCost(stats),
171 };
172 },
173 }
174 }
175 return null;
176 }
177
178 pub fn rowBytesMatchPredicates(predicates: []const ast_mod.Predicate, values: []const row.Value, handle: *const catalog_mod.RelationHandle, rowid: i64, bytes: []const u8) ast_mod.Error!bool {
179 const view = try row.View.init(bytes);
180 return try rowViewMatchPredicates(predicates, values, handle, rowid, view);
181 }
182
183 pub fn rowViewMatchPredicates(predicates: []const ast_mod.Predicate, values: []const row.Value, handle: *const catalog_mod.RelationHandle, rowid: i64, view: row.View) ast_mod.Error!bool {
184 for (predicates, values) |predicate, value| {
185 if (!try rowViewMatchPredicate(predicate, value, handle, rowid, view)) return false;
186 }
187 return true;
188 }
189
190 pub fn rowViewMatchPredicate(predicate: ast_mod.Predicate, value: row.Value, handle: *const catalog_mod.RelationHandle, rowid: i64, view: row.View) ast_mod.Error!bool {
191 return switch (predicate.column) {
192 .rowid => rowidMatches(rowid, predicate.operator, try rowidFromValue(value)),
193 .field => |name| field: {
194 const field = access_mod.columnIndex(handle.definitions, name) orelse return error.ColumnNotFound;
195 break :field valueMatches(try view.column(field), predicate.operator, value, handle.definitions[field].column.collation);
196 },
197 };
198 }
199
200 pub fn indexRowMatchesPredicates(predicates: []const ast_mod.Predicate, values: []const row.Value, handle: *const catalog_mod.RelationHandle, index_slot: usize, index_values: []const row.Value, rowid: i64) ast_mod.Error!bool {
201 const spec = handle.specs[index_slot];
202 for (predicates, values) |predicate, value| {
203 const matches = switch (predicate.column) {
204 .rowid => rowidMatches(rowid, predicate.operator, try rowidFromValue(value)),
205 .field => |name| field: {
206 const field = access_mod.columnIndex(handle.definitions, name) orelse return error.ColumnNotFound;
207 const position = access_mod.fieldPosition(spec.fields, field) orelse return false;
208 break :field valueMatches(index_values[position], predicate.operator, value, handle.definitions[field].column.collation);
209 },
210 };
211 if (!matches) return false;
212 }
213 return true;
214 }
215
216 /// Decodes a covered index entry into `values` and `scratch`. Returns the decoded field values
217 /// when the entry satisfies every predicate, and null when a predicate rejects it.
218 pub fn coveredIndexValues(
219 predicates: []const ast_mod.Predicate,
220 predicate_values: []const row.Value,
221 handle: *const catalog_mod.RelationHandle,
222 index_slot: usize,
223 entry: index_mod.Entry,
224 values: *[catalog_mod.max_columns]row.Value,
225 scratch: *[page.size]u8,
226 ) ast_mod.Error!?[]const row.Value {
227 const decoded = try key.decodeIndex(values, scratch, entry.key);
228 if (decoded.values.len != handle.specs[index_slot].fields.len) return error.InvalidKey;
229 if (!try indexRowMatchesPredicates(
230 predicates,
231 predicate_values,
232 handle,
233 index_slot,
234 decoded.values,
235 entry.rowid,
236 )) return null;
237 return decoded.values;
238 }
239
240 pub fn indexedPrefixValues(indexed: IndexedPredicate, values: []const row.Value, target: *[relation_mod.max_index_fields]row.Value) []const row.Value {
241 for (0..indexed.prefix_count) |offset| target[offset] = values[indexed.prefix_predicates[offset]];
242 return target[0..indexed.prefix_count];
243 }
244
245 pub fn rowidFromValue(value: row.Value) ast_mod.Error!i64 {
246 return switch (value) {
247 .integer => |integer| integer,
248 else => error.ExpectedRowId,
249 };
250 }
251
252 pub fn rowidStart(operator: ast_mod.PredicateOperator, value: i64) ?i64 {
253 return switch (operator) {
254 .eq, .lt, .lte => null,
255 .gt, .gte => value,
256 };
257 }
258
259 pub fn rowidEnd(operator: ast_mod.PredicateOperator, value: i64) ?i64 {
260 return switch (operator) {
261 .eq, .gt, .gte => null,
262 .lt => value,
263 .lte => if (value == std.math.maxInt(i64)) null else value + 1,
264 };
265 }
266
267 pub fn indexedRangeStart(indexed: IndexedPredicate, values: []const row.Value) ?index_mod.Bound {
268 return switch (indexed.operator) {
269 .eq => null,
270 .lt, .lte => if (indexed.equality_count == 0)
271 null
272 else
273 .{ .values = values[0..indexed.equality_count], .inclusive = true },
274 .gt => .{ .values = values, .inclusive = false },
275 .gte => .{ .values = values, .inclusive = true },
276 };
277 }
278
279 pub fn indexedRangeEnd(indexed: IndexedPredicate, values: []const row.Value) ?index_mod.Bound {
280 return switch (indexed.operator) {
281 .eq => null,
282 .lt => .{ .values = values, .inclusive = false },
283 .lte => .{ .values = values, .inclusive = true },
284 .gt, .gte => if (indexed.equality_count == 0)
285 null
286 else
287 .{ .values = values[0..indexed.equality_count], .inclusive = true },
288 };
289 }
290
291 pub fn rowidMatches(left: i64, operator: ast_mod.PredicateOperator, right: i64) bool {
292 return switch (operator) {
293 .eq => left == right,
294 .lt => left < right,
295 .lte => left <= right,
296 .gt => left > right,
297 .gte => left >= right,
298 };
299 }
300
301 pub fn valueMatches(left: row.Value, operator: ast_mod.PredicateOperator, right: row.Value, collation: row.Collation) bool {
302 const order = row.compareValues(left, right, collation);
303 return switch (operator) {
304 .eq => order == .eq,
305 .lt => order == .lt,
306 .lte => order == .lt or order == .eq,
307 .gt => order == .gt,
308 .gte => order == .gt or order == .eq,
309 };
310 }
311
312 pub fn predicateField(handle: *const catalog_mod.RelationHandle, predicate: ast_mod.Predicate) ?usize {
313 return switch (predicate.column) {
314 .rowid => null,
315 .field => |name| access_mod.columnIndex(handle.definitions, name),
316 };
317 }
318
319 pub fn predicateExpression(select: ast_mod.Select, predicate_index: usize, values: ?[]const row.Value) ast_mod.Expression {
320 if (values) |runtime_values| return .{ .literal = runtime_values[predicate_index] };
321 return selectPredicateAt(select, predicate_index).value;
322 }
323
324 pub fn literalValue(value: ast_mod.Expression) ?row.Value {
325 return switch (value) {
326 .literal => |literal| literal,
327 .parameter => null,
328 };
329 }
330
331 pub fn literalPrefixValues(
332 target: *[relation_mod.max_index_fields]row.Value,
333 select: ast_mod.Select,
334 candidate: IndexedPredicate,
335 prefix_count: usize,
336 values: ?[]const row.Value,
337 ) ?[]const row.Value {
338 var offset: usize = 0;
339 while (offset < prefix_count) : (offset += 1) {
340 const expression = predicateExpression(select, candidate.prefix_predicates[offset], values);
341 target[offset] = literalValue(expression) orelse return null;
342 }
343 return target[0..prefix_count];
344 }