lib/sql/src/relation.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const file = @import("file.zig");
3 const index_mod = @import("index.zig");
4 const key = @import("key.zig");
5 const page = @import("page.zig");
6 const row = @import("row.zig");
7 const space_mod = @import("space.zig");
8 const table_mod = @import("table.zig");
9 const trace = @import("trace.zig");
10 const tree = @import("tree.zig");
11 const wal = @import("wal.zig");
12
13 const Allocator = std.mem.Allocator;
14
15 pub const Error = space_mod.Error || table_mod.Error || index_mod.Error || row.Error || Allocator.Error || error{
16 IndexOutOfBounds,
17 SecondaryIndexCorrupt,
18 TooManyIndexes,
19 TooManyIndexFields,
20 };
21
22 pub const max_indexes: usize = 8;
23 pub const max_index_fields: usize = 8;
24
25 pub const IndexSpec = struct {
26 root_page: u32,
27 fields: []const usize,
28 columns: []const row.Column = &.{},
29 };
30
31 pub const Scan = table_mod.Scan;
32
33 pub const Edit = union(enum) {
34 put: Put,
35 update: Update,
36 delete: i64,
37
38 pub const Put = struct {
39 rowid: i64,
40 bytes: []const u8,
41 };
42
43 pub const Assignment = struct {
44 column: usize,
45 value: row.Value,
46 };
47
48 pub const Update = struct {
49 rowid: i64,
50 assignments: []const Assignment,
51 };
52 };
53
54 pub fn cloneAssignments(allocator: Allocator, assignments: []const Edit.Assignment) Error![]Edit.Assignment {
55 const cloned = try allocator.alloc(Edit.Assignment, assignments.len);
56 var count: usize = 0;
57 errdefer freeAssignments(allocator, cloned[0..count]);
58 for (assignments, cloned) |assignment, *target| {
59 target.* = .{
60 .column = assignment.column,
61 .value = switch (assignment.value) {
62 .nil, .integer => assignment.value,
63 .text => |text| .{ .text = try allocator.dupe(u8, text) },
64 .blob => |blob| .{ .blob = try allocator.dupe(u8, blob) },
65 },
66 };
67 count += 1;
68 }
69 return cloned;
70 }
71
72 pub fn freeAssignments(allocator: Allocator, assignments: []const Edit.Assignment) void {
73 for (assignments) |assignment| switch (assignment.value) {
74 .nil, .integer => {},
75 .text => |text| allocator.free(text),
76 .blob => |blob| allocator.free(blob),
77 };
78 allocator.free(assignments);
79 }
80
81 pub fn applyUpdate(allocator: Allocator, bytes: []const u8, assignments: []const Edit.Assignment) Error![]u8 {
82 const view = try row.View.init(bytes);
83 const count = view.columnCount();
84 const values = try allocator.alloc(row.Value, count);
85 defer allocator.free(values);
86 var cursor = view.cursor();
87 for (values, 0..) |*value, column| value.* = try cursor.column(column);
88 for (assignments) |assignment| {
89 if (assignment.column >= count) return error.ColumnOutOfBounds;
90 values[assignment.column] = assignment.value;
91 }
92 const size = try row.encodedSize(values);
93 const merged = try allocator.alloc(u8, size);
94 errdefer allocator.free(merged);
95 _ = try row.encode(merged, values);
96 return merged;
97 }
98
99 pub const Options = struct {
100 table_root: u32 = 2,
101 indexes: []const IndexSpec = &.{},
102 };
103
104 const Indexed = struct {
105 index: index_mod.Index,
106 fields: []const usize,
107 };
108
109 const ReadIndexed = struct {
110 index: index_mod.Reader,
111 fields: []const usize,
112 };
113
114 pub const Summary = struct {
115 table: tree.Summary,
116 indexes: [max_indexes]tree.Summary,
117 index_count: usize,
118 };
119
120 pub const Reader = struct {
121 space: space_mod.Reader,
122 table: table_mod.Reader,
123 indexes: [max_indexes]ReadIndexed = undefined,
124 index_count: usize,
125
126 pub fn open(space: *const space_mod.Reader, options: Options) Error!Reader {
127 if (options.indexes.len > max_indexes) return error.TooManyIndexes;
128 var reader = Reader{
129 .space = space.*,
130 .table = try space.rowidTable(options.table_root),
131 .index_count = options.indexes.len,
132 };
133 for (options.indexes, 0..) |spec, offset| {
134 if (spec.fields.len > max_index_fields) return error.TooManyIndexFields;
135 reader.indexes[offset] = .{
136 .index = try space.index(spec.root_page, spec.columns),
137 .fields = spec.fields,
138 };
139 }
140 return reader;
141 }
142
143 pub fn lastRowId(self: *const Reader) Error!?i64 {
144 return try self.table.lastRowId();
145 }
146
147 pub fn get(self: *const Reader, allocator: Allocator, rowid: i64) Error!?[]u8 {
148 return try self.table.get(allocator, rowid);
149 }
150
151 pub fn valueLength(self: *const Reader, rowid: i64) Error!?usize {
152 return try self.table.valueLength(rowid);
153 }
154
155 pub fn getInto(self: *const Reader, rowid: i64, target: []u8) Error!?[]u8 {
156 return try self.table.getInto(rowid, target);
157 }
158
159 pub fn scan(
160 self: *const Reader,
161 target: *Scan,
162 allocator: Allocator,
163 start: ?i64,
164 end: ?i64,
165 ) Error!void {
166 try self.table.scan(target, allocator, start, end);
167 }
168
169 pub fn scanProjected(
170 self: *const Reader,
171 target: *Scan,
172 allocator: Allocator,
173 start: ?i64,
174 end: ?i64,
175 projection: table_mod.Projection,
176 ) Error!void {
177 try self.table.scanProjected(target, allocator, start, end, projection);
178 }
179
180 pub fn lookup(
181 self: *const Reader,
182 target: *index_mod.Scan,
183 allocator: Allocator,
184 index_slot: usize,
185 prefix: []const row.Value,
186 ) Error!void {
187 if (index_slot >= self.index_count) return error.IndexOutOfBounds;
188 try self.indexes[index_slot].index.lookup(target, allocator, prefix);
189 }
190
191 pub fn indexScan(
192 self: *const Reader,
193 target: *index_mod.Scan,
194 allocator: Allocator,
195 index_slot: usize,
196 start: ?[]const row.Value,
197 end: ?[]const row.Value,
198 ) Error!void {
199 if (index_slot >= self.index_count) return error.IndexOutOfBounds;
200 try self.indexes[index_slot].index.scan(target, allocator, start, end);
201 }
202
203 pub fn indexRange(
204 self: *const Reader,
205 target: *index_mod.Scan,
206 allocator: Allocator,
207 index_slot: usize,
208 start: ?index_mod.Bound,
209 end: ?index_mod.Bound,
210 ) Error!void {
211 if (index_slot >= self.index_count) return error.IndexOutOfBounds;
212 try self.indexes[index_slot].index.range(target, allocator, start, end);
213 }
214
215 pub fn summarize(self: *const Reader) Error!Summary {
216 var summary = Summary{
217 .table = try self.table.summarize(),
218 .indexes = undefined,
219 .index_count = self.index_count,
220 };
221 for (0..self.index_count) |offset| {
222 summary.indexes[offset] = try self.indexes[offset].index.summarize();
223 }
224 return summary;
225 }
226 };
227
228 const AppliedEdit = struct {
229 rowid: i64,
230 base: ?[]u8,
231 current: ?[]const u8,
232 merged: ?[]u8 = null,
233
234 fn deinit(self: *AppliedEdit, allocator: Allocator) void {
235 if (self.merged) |bytes| allocator.free(bytes);
236 if (self.base) |bytes| allocator.free(bytes);
237 self.* = undefined;
238 }
239
240 fn adoptMerged(self: *AppliedEdit, allocator: Allocator, bytes: []u8) void {
241 if (self.merged) |previous| allocator.free(previous);
242 self.merged = bytes;
243 self.current = bytes;
244 }
245 };
246
247 pub const Relation = struct {
248 space: space_mod.Space,
249 table: table_mod.Table,
250 indexes: [max_indexes]Indexed = undefined,
251 index_count: usize,
252
253 pub fn open(space: *const space_mod.Space, options: Options) Error!Relation {
254 if (options.indexes.len > max_indexes) return error.TooManyIndexes;
255 var relation = Relation{
256 .space = space.*,
257 .table = try space.rowidTable(options.table_root),
258 .index_count = options.indexes.len,
259 };
260 for (options.indexes, 0..) |spec, offset| {
261 if (spec.fields.len > max_index_fields) return error.TooManyIndexFields;
262 relation.indexes[offset] = .{
263 .index = try space.index(spec.root_page, spec.columns),
264 .fields = spec.fields,
265 };
266 }
267 return relation;
268 }
269
270 pub fn reader(self: *const Relation, snapshot: file.Snapshot) Error!Reader {
271 const opened_space = try self.space.reader(snapshot);
272 var opened = Reader{
273 .space = opened_space,
274 .table = try opened_space.rowidTable(self.table.rows.root_page),
275 .index_count = self.index_count,
276 };
277 for (0..self.index_count) |offset| {
278 opened.indexes[offset] = .{
279 .index = try opened_space.index(
280 self.indexes[offset].index.entries.root_page,
281 self.indexes[offset].index.columns,
282 ),
283 .fields = self.indexes[offset].fields,
284 };
285 }
286 return opened;
287 }
288
289 pub fn put(self: *Relation, allocator: Allocator, rowid: i64, values: []const row.Value, options: file.CommitOptions) Error!file.Commit {
290 const phase = trace.scope("relation.put");
291 defer phase.end();
292
293 const bytes = try allocator.alloc(u8, try row.encodedSize(values));
294 defer allocator.free(bytes);
295 const encoded = try row.encode(bytes, values);
296 return try self.applyEdits(allocator, &.{.{ .put = .{
297 .rowid = rowid,
298 .bytes = encoded,
299 } }}, options);
300 }
301
302 pub fn putEncoded(self: *Relation, allocator: Allocator, rowid: i64, bytes: []const u8, options: file.CommitOptions) Error!file.Commit {
303 const phase = trace.scope("relation.put_encoded");
304 defer phase.end();
305
306 return try self.applyEdits(allocator, &.{.{ .put = .{
307 .rowid = rowid,
308 .bytes = bytes,
309 } }}, options);
310 }
311
312 pub fn update(self: *Relation, allocator: Allocator, rowid: i64, assignments: []const Edit.Assignment, options: file.CommitOptions) Error!file.Commit {
313 const phase = trace.scope("relation.update");
314 defer phase.end();
315
316 return try self.applyEdits(allocator, &.{.{ .update = .{
317 .rowid = rowid,
318 .assignments = assignments,
319 } }}, options);
320 }
321
322 pub fn delete(self: *Relation, allocator: Allocator, rowid: i64, options: file.CommitOptions) Error!file.Commit {
323 const phase = trace.scope("relation.delete");
324 defer phase.end();
325
326 return try self.applyEdits(allocator, &.{.{ .delete = rowid }}, options);
327 }
328
329 pub fn applyEdits(self: *Relation, allocator: Allocator, edits: []const Edit, options: file.CommitOptions) Error!file.Commit {
330 const phase = trace.scope("relation.apply_edits");
331 defer phase.end();
332
333 var write = try self.space.beginWrite();
334 defer write.deinit();
335 try self.applyEditsIn(allocator, &write, edits);
336 return try write.commit(options);
337 }
338
339 pub fn applyEditsIn(
340 self: *Relation,
341 allocator: Allocator,
342 write: *tree.Write,
343 edits: []const Edit,
344 ) Error!void {
345 const phase = trace.scope("relation.apply_edits_in");
346 defer phase.end();
347 try write.claimBatch(self.table.rows.root_page);
348
349 var states: std.AutoArrayHashMapUnmanaged(i64, AppliedEdit) = .empty;
350 defer {
351 for (states.values()) |*state| state.deinit(allocator);
352 states.deinit(allocator);
353 }
354
355 const base_reader = try self.reader(write.snapshot);
356 for (edits) |edit| {
357 try accumulateEdit(allocator, &base_reader, &states, edit);
358 }
359 for (states.values()) |state| try self.applyEditStateIn(write, state);
360 }
361
362 pub fn lastRowId(self: *const Relation) Error!?i64 {
363 var read = try self.space.database.beginRead();
364 defer read.deinit();
365 const opened = try self.reader(read.snapshot());
366 return try opened.lastRowId();
367 }
368
369 pub fn get(self: *const Relation, allocator: Allocator, rowid: i64) Error!?[]u8 {
370 var read = try self.space.database.beginRead();
371 defer read.deinit();
372 const opened = try self.reader(read.snapshot());
373 return try opened.get(allocator, rowid);
374 }
375
376 pub fn valueLength(self: *const Relation, rowid: i64) Error!?usize {
377 var read = try self.space.database.beginRead();
378 defer read.deinit();
379 const opened = try self.reader(read.snapshot());
380 return try opened.valueLength(rowid);
381 }
382
383 pub fn getInto(self: *const Relation, rowid: i64, target: []u8) Error!?[]u8 {
384 var read = try self.space.database.beginRead();
385 defer read.deinit();
386 const opened = try self.reader(read.snapshot());
387 return try opened.getInto(rowid, target);
388 }
389
390 pub fn scan(
391 self: *const Relation,
392 target: *Scan,
393 allocator: Allocator,
394 start: ?i64,
395 end: ?i64,
396 ) Error!void {
397 var read = try self.space.database.beginRead();
398 defer read.deinit();
399 const opened = try self.reader(read.snapshot());
400 try opened.scan(target, allocator, start, end);
401 }
402
403 pub fn scanProjected(
404 self: *const Relation,
405 target: *Scan,
406 allocator: Allocator,
407 start: ?i64,
408 end: ?i64,
409 projection: table_mod.Projection,
410 ) Error!void {
411 var read = try self.space.database.beginRead();
412 defer read.deinit();
413 const opened = try self.reader(read.snapshot());
414 try opened.scanProjected(target, allocator, start, end, projection);
415 }
416
417 pub fn lookup(
418 self: *const Relation,
419 target: *index_mod.Scan,
420 allocator: Allocator,
421 index_slot: usize,
422 prefix: []const row.Value,
423 ) Error!void {
424 var read = try self.space.database.beginRead();
425 defer read.deinit();
426 const opened = try self.reader(read.snapshot());
427 try opened.lookup(target, allocator, index_slot, prefix);
428 }
429
430 pub fn indexScan(
431 self: *const Relation,
432 target: *index_mod.Scan,
433 allocator: Allocator,
434 index_slot: usize,
435 start: ?[]const row.Value,
436 end: ?[]const row.Value,
437 ) Error!void {
438 var read = try self.space.database.beginRead();
439 defer read.deinit();
440 const opened = try self.reader(read.snapshot());
441 try opened.indexScan(target, allocator, index_slot, start, end);
442 }
443
444 pub fn indexRange(
445 self: *const Relation,
446 target: *index_mod.Scan,
447 allocator: Allocator,
448 index_slot: usize,
449 start: ?index_mod.Bound,
450 end: ?index_mod.Bound,
451 ) Error!void {
452 var read = try self.space.database.beginRead();
453 defer read.deinit();
454 const opened = try self.reader(read.snapshot());
455 try opened.indexRange(target, allocator, index_slot, start, end);
456 }
457
458 pub fn summarize(self: *const Relation) Error!Summary {
459 var read = try self.space.database.beginRead();
460 defer read.deinit();
461 const opened = try self.reader(read.snapshot());
462 return try opened.summarize();
463 }
464
465 pub fn validateIndexes(self: *const Relation, allocator: Allocator) Error!void {
466 const phase = trace.scope("relation.validate_indexes");
467 defer phase.end();
468
469 var table_scan: Scan = undefined;
470 try self.scan(&table_scan, allocator, null, null);
471 defer table_scan.deinit();
472 while (try table_scan.next()) |entry| {
473 const view = try entry.view();
474 var index_offset: usize = 0;
475 while (index_offset < self.index_count) : (index_offset += 1) {
476 const indexed = &self.indexes[index_offset];
477 var projected: [max_index_fields]row.Value = undefined;
478 const values = try projectView(view, indexed.fields, &projected);
479 if (!try indexContainsRowid(allocator, &indexed.index, values, entry.rowid)) return error.SecondaryIndexCorrupt;
480 }
481 }
482
483 var index_offset: usize = 0;
484 while (index_offset < self.index_count) : (index_offset += 1) {
485 const indexed = &self.indexes[index_offset];
486 var index_scan: index_mod.Scan = undefined;
487 try indexed.index.scan(&index_scan, allocator, null, null);
488 defer index_scan.deinit();
489 while (try index_scan.next()) |entry| {
490 const bytes = (try self.table.get(allocator, entry.rowid)) orelse return error.SecondaryIndexCorrupt;
491 defer allocator.free(bytes);
492 const view = try row.View.init(bytes);
493 var projected: [max_index_fields]row.Value = undefined;
494 const values = try projectView(view, indexed.fields, &projected);
495 var decoded_values: [max_index_fields]row.Value = undefined;
496 var scratch: [page.size]u8 = undefined;
497 const decoded = try key.decodeIndex(decoded_values[0..], scratch[0..], entry.key);
498 const valid = decoded.rowid == entry.rowid and valuesEqual(values, decoded.values, indexed.index.columns);
499 if (!valid) return error.SecondaryIndexCorrupt;
500 }
501 }
502 }
503
504 fn putViewIndexesIn(self: *Relation, write: *tree.Write, rowid: i64, view: row.View) Error!void {
505 var offset: usize = 0;
506 while (offset < self.index_count) : (offset += 1) {
507 var projected: [max_index_fields]row.Value = undefined;
508 const indexed = try projectView(view, self.indexes[offset].fields, &projected);
509 try self.indexes[offset].index.putIn(write, rowid, indexed);
510 }
511 }
512
513 fn deleteIndexesIn(self: *Relation, write: *tree.Write, rowid: i64, view: row.View) Error!void {
514 var offset: usize = 0;
515 while (offset < self.index_count) : (offset += 1) {
516 var projected: [max_index_fields]row.Value = undefined;
517 const indexed = try projectView(view, self.indexes[offset].fields, &projected);
518 try self.indexes[offset].index.deleteIn(write, rowid, indexed);
519 }
520 }
521
522 fn accumulateEdit(
523 allocator: Allocator,
524 base_reader: *const Reader,
525 states: *std.AutoArrayHashMapUnmanaged(i64, AppliedEdit),
526 edit: Edit,
527 ) Error!void {
528 const state = try appliedEdit(
529 allocator,
530 base_reader,
531 states,
532 editRowid(edit),
533 );
534 switch (edit) {
535 .put => |put_edit| {
536 _ = try row.View.init(put_edit.bytes);
537 state.current = put_edit.bytes;
538 },
539 .update => |update_edit| {
540 const current = state.current orelse return error.KeyNotFound;
541 state.adoptMerged(allocator, try applyUpdate(allocator, current, update_edit.assignments));
542 },
543 .delete => {
544 if (state.current == null) return error.KeyNotFound;
545 state.current = null;
546 },
547 }
548 }
549
550 fn appliedEdit(
551 allocator: Allocator,
552 base_reader: *const Reader,
553 states: *std.AutoArrayHashMapUnmanaged(i64, AppliedEdit),
554 rowid: i64,
555 ) Error!*AppliedEdit {
556 if (states.getPtr(rowid)) |state| return state;
557
558 const base = try base_reader.get(allocator, rowid);
559 errdefer if (base) |bytes| allocator.free(bytes);
560 try states.putNoClobber(allocator, rowid, .{
561 .rowid = rowid,
562 .base = base,
563 .current = if (base) |bytes| bytes else null,
564 });
565 return states.getPtr(rowid).?;
566 }
567
568 fn applyEditStateIn(self: *Relation, write: *tree.Write, state: AppliedEdit) Error!void {
569 if (state.base) |base| {
570 if (state.current) |current| {
571 if (std.mem.eql(u8, base, current)) return;
572 try self.deleteIndexesIn(write, state.rowid, try row.View.init(base));
573 try self.table.putEncodedIn(write, state.rowid, current);
574 try self.putViewIndexesIn(write, state.rowid, try row.View.init(current));
575 } else {
576 try self.deleteIndexesIn(write, state.rowid, try row.View.init(base));
577 try self.table.deleteIn(write, state.rowid);
578 }
579 } else if (state.current) |current| {
580 try self.table.putEncodedIn(write, state.rowid, current);
581 try self.putViewIndexesIn(write, state.rowid, try row.View.init(current));
582 }
583 }
584 };
585
586 fn editRowid(edit: Edit) i64 {
587 return switch (edit) {
588 .put => |put| put.rowid,
589 .update => |update| update.rowid,
590 .delete => |rowid| rowid,
591 };
592 }
593
594 fn indexContainsRowid(allocator: Allocator, index: *const index_mod.Index, values: []const row.Value, rowid: i64) Error!bool {
595 var lookup: index_mod.Scan = undefined;
596 try index.lookup(&lookup, allocator, values);
597 defer lookup.deinit();
598 while (try lookup.next()) |entry| {
599 if (entry.rowid == rowid) return true;
600 }
601 return false;
602 }
603
604 fn projectView(view: row.View, fields: []const usize, target: *[max_index_fields]row.Value) Error![]row.Value {
605 if (fields.len > target.len) return error.TooManyIndexFields;
606 return try view.project(fields, target[0..]);
607 }
608
609 fn valuesEqual(left: []const row.Value, right: []const row.Value, columns: []const row.Column) bool {
610 if (left.len != right.len) return false;
611 for (left, right, 0..) |left_value, right_value, offset| {
612 const collation = if (offset < columns.len) columns[offset].collation else row.Collation.binary;
613 if (row.compareValues(left_value, right_value, collation) != .eq) return false;
614 }
615 return true;
616 }
617
618 test "relation reader scans and looks up one fixed snapshot" {
619 var tmp = std.testing.tmpDir(.{});
620 defer tmp.cleanup();
621
622 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
623 .paths = .{ .database = "relation-reader.db", .wal = "relation-reader.wal" },
624 .header = testingHeader(),
625 });
626 defer database.deinit();
627 try database.reserve(.{ .wal_frames = 160 });
628
629 const space_options = space_mod.Options{
630 .roots = &.{
631 .{ .root_page = 2, .identity_page = 4 },
632 .{ .root_page = 3, .identity_page = 5 },
633 },
634 };
635 const space = try space_mod.Space.open(&database, space_options);
636 const specs = [_]IndexSpec{.{ .root_page = 3, .fields = &.{0} }};
637 const options = Options{ .table_root = 2, .indexes = &specs };
638 var mutable = try Relation.open(&space, options);
639 _ = try mutable.put(std.testing.allocator, 1, &.{.{ .text = "alpha" }}, .{});
640 _ = try mutable.put(std.testing.allocator, 2, &.{.{ .text = "beta" }}, .{});
641
642 var read = try database.beginRead();
643 defer read.deinit();
644 const read_space = try space_mod.Reader.open(read.snapshot(), space_options);
645 const reader = try Reader.open(&read_space, options);
646 _ = try mutable.put(std.testing.allocator, 3, &.{.{ .text = "alpha" }}, .{});
647
648 try std.testing.expectEqual(@as(?i64, 2), try reader.lastRowId());
649 var scan: Scan = undefined;
650 try reader.scan(&scan, std.testing.allocator, null, null);
651 defer scan.deinit();
652 try std.testing.expectEqual(@as(i64, 1), (try scan.next()).?.rowid);
653 try std.testing.expectEqual(@as(i64, 2), (try scan.next()).?.rowid);
654 try std.testing.expect(try scan.next() == null);
655
656 const found = (try reader.get(std.testing.allocator, 2)).?;
657 defer std.testing.allocator.free(found);
658 try std.testing.expectEqual(found.len, (try reader.valueLength(2)).?);
659 var row_buffer: [32]u8 = undefined;
660 try std.testing.expectEqualSlices(u8, found, (try reader.getInto(2, &row_buffer)).?);
661
662 var lookup: index_mod.Scan = undefined;
663 try reader.lookup(&lookup, std.testing.allocator, 0, &.{.{ .text = "alpha" }});
664 defer lookup.deinit();
665 try std.testing.expectEqual(@as(i64, 1), (try lookup.next()).?.rowid);
666 try std.testing.expect(try lookup.next() == null);
667 const summary = try reader.summarize();
668 try std.testing.expectEqual(@as(usize, 2), summary.table.entries);
669 try std.testing.expectEqual(@as(usize, 2), summary.indexes[0].entries);
670 try std.testing.expectEqual(@as(u64, 2), (try reader.table.rows.identity()).entries);
671 const index_tree = try reader.space.tree(3);
672 try std.testing.expectEqual(@as(u64, 2), (try index_tree.identity()).entries);
673
674 try std.testing.expect(!@hasDecl(tree.Reader, "put"));
675 try std.testing.expect(!@hasDecl(table_mod.Reader, "put"));
676 try std.testing.expect(!@hasDecl(index_mod.Reader, "put"));
677 try std.testing.expect(!@hasDecl(space_mod.Reader, "beginWrite"));
678 try std.testing.expect(!@hasDecl(Reader, "put"));
679 try std.testing.expect(!@hasDecl(Reader, "applyEdits"));
680 }
681
682 test "relation maintains secondary index through replace and reopen" {
683 var tmp = std.testing.tmpDir(.{});
684 defer tmp.cleanup();
685
686 {
687 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
688 .paths = .{ .database = "relation.db", .wal = "relation.wal" },
689 .header = testingHeader(),
690 });
691 defer database.deinit();
692 try database.reserve(.{ .wal_frames = 160 });
693
694 const space = try space_mod.Space.open(&database, .{ .roots = &.{ .{ .root_page = 2 }, .{ .root_page = 3 } } });
695 const specs = [_]IndexSpec{.{ .root_page = 3, .fields = &.{0} }};
696 var relation = try Relation.open(&space, .{ .table_root = 2, .indexes = &specs });
697 _ = try relation.put(std.testing.allocator, 7, &.{ .{ .integer = 1 }, .{ .text = "one" } }, .{ .durability = .buffered });
698 _ = try relation.put(std.testing.allocator, 7, &.{ .{ .integer = 2 }, .{ .text = "two" } }, .{ .durability = .buffered });
699 try database.syncWal();
700 }
701
702 var reopened = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
703 .paths = .{ .database = "relation.db", .wal = "relation.wal" },
704 .header = recoveredHeader(),
705 });
706 defer reopened.deinit();
707
708 const space = try space_mod.Space.open(&reopened, .{ .roots = &.{ .{ .root_page = 2 }, .{ .root_page = 3 } } });
709 const specs = [_]IndexSpec{.{ .root_page = 3, .fields = &.{0} }};
710 var relation = try Relation.open(&space, .{ .table_root = 2, .indexes = &specs });
711
712 var old_lookup: index_mod.Scan = undefined;
713 try relation.lookup(&old_lookup, std.testing.allocator, 0, &.{.{ .integer = 1 }});
714 defer old_lookup.deinit();
715 try std.testing.expect(try old_lookup.next() == null);
716
717 var new_lookup: index_mod.Scan = undefined;
718 try relation.lookup(&new_lookup, std.testing.allocator, 0, &.{.{ .integer = 2 }});
719 defer new_lookup.deinit();
720 const entry = (try new_lookup.next()).?;
721 try std.testing.expectEqual(@as(i64, 7), entry.rowid);
722 try std.testing.expect(try new_lookup.next() == null);
723
724 const bytes = (try relation.get(std.testing.allocator, 7)).?;
725 defer std.testing.allocator.free(bytes);
726 const view = try row.View.init(bytes);
727 try std.testing.expectEqual(@as(i64, 2), (try view.column(0)).integer);
728 try std.testing.expectEqualStrings("two", (try view.column(1)).text);
729 }
730
731 test "relation delete removes table row and secondary index entry" {
732 var tmp = std.testing.tmpDir(.{});
733 defer tmp.cleanup();
734
735 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
736 .paths = .{ .database = "relation.db", .wal = "relation.wal" },
737 .header = testingHeader(),
738 });
739 defer database.deinit();
740 try database.reserve(.{ .wal_frames = 160 });
741
742 const space = try space_mod.Space.open(&database, .{ .roots = &.{ .{ .root_page = 2 }, .{ .root_page = 3 } } });
743 const specs = [_]IndexSpec{.{ .root_page = 3, .fields = &.{0} }};
744 var relation = try Relation.open(&space, .{ .table_root = 2, .indexes = &specs });
745 _ = try relation.put(std.testing.allocator, 4, &.{ .{ .integer = 9 }, .{ .text = "nine" } }, .{ .durability = .buffered });
746 _ = try relation.delete(std.testing.allocator, 4, .{ .durability = .buffered });
747
748 const missing = try relation.get(std.testing.allocator, 4);
749 if (missing) |bytes| std.testing.allocator.free(bytes);
750 try std.testing.expect(missing == null);
751
752 var lookup: index_mod.Scan = undefined;
753 try relation.lookup(&lookup, std.testing.allocator, 0, &.{.{ .integer = 9 }});
754 defer lookup.deinit();
755 try std.testing.expect(try lookup.next() == null);
756 try std.testing.expectError(error.KeyNotFound, relation.delete(std.testing.allocator, 4, .{ .durability = .buffered }));
757 }
758
759 test "relation applies edit batches to table and secondary indexes" {
760 var tmp = std.testing.tmpDir(.{});
761 defer tmp.cleanup();
762
763 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
764 .paths = .{ .database = "relation-batch.db", .wal = "relation-batch.wal" },
765 .header = testingHeader(),
766 });
767 defer database.deinit();
768 try database.reserve(.{ .wal_frames = 220 });
769
770 const space = try space_mod.Space.open(&database, .{ .roots = &.{ .{ .root_page = 2 }, .{ .root_page = 3 } } });
771 const specs = [_]IndexSpec{.{ .root_page = 3, .fields = &.{0} }};
772 var relation = try Relation.open(&space, .{ .table_root = 2, .indexes = &specs });
773
774 var one_buffer: [64]u8 = undefined;
775 var two_buffer: [64]u8 = undefined;
776 var three_buffer: [64]u8 = undefined;
777 const one = try row.encode(&one_buffer, &.{ .{ .integer = 1 }, .{ .text = "one" } });
778 const two = try row.encode(&two_buffer, &.{ .{ .integer = 2 }, .{ .text = "two" } });
779 const three = try row.encode(&three_buffer, &.{ .{ .integer = 3 }, .{ .text = "three" } });
780
781 _ = try relation.applyEdits(std.testing.allocator, &.{
782 .{ .put = .{ .rowid = 1, .bytes = one } },
783 .{ .put = .{ .rowid = 2, .bytes = two } },
784 }, .{ .durability = .buffered });
785 _ = try relation.applyEdits(std.testing.allocator, &.{
786 .{ .delete = 1 },
787 .{ .put = .{ .rowid = 2, .bytes = three } },
788 }, .{ .durability = .buffered });
789
790 const missing = try relation.get(std.testing.allocator, 1);
791 if (missing) |bytes| std.testing.allocator.free(bytes);
792 try std.testing.expect(missing == null);
793
794 const found = (try relation.get(std.testing.allocator, 2)).?;
795 defer std.testing.allocator.free(found);
796 const view = try row.View.init(found);
797 try std.testing.expectEqual(@as(i64, 3), (try view.column(0)).integer);
798 try std.testing.expectEqualStrings("three", (try view.column(1)).text);
799
800 var old_lookup: index_mod.Scan = undefined;
801 try relation.lookup(&old_lookup, std.testing.allocator, 0, &.{.{ .integer = 2 }});
802 defer old_lookup.deinit();
803 try std.testing.expect(try old_lookup.next() == null);
804
805 var new_lookup: index_mod.Scan = undefined;
806 try relation.lookup(&new_lookup, std.testing.allocator, 0, &.{.{ .integer = 3 }});
807 defer new_lookup.deinit();
808 try std.testing.expectEqual(@as(i64, 2), (try new_lookup.next()).?.rowid);
809 try std.testing.expect(try new_lookup.next() == null);
810
811 _ = try relation.applyEdits(std.testing.allocator, &.{
812 .{ .put = .{ .rowid = 9, .bytes = one } },
813 .{ .delete = 9 },
814 }, .{ .durability = .buffered });
815
816 {
817 var write = try space.beginWrite();
818 defer write.deinit();
819 try relation.applyEditsIn(
820 std.testing.allocator,
821 &write,
822 &.{.{ .put = .{ .rowid = 10, .bytes = one } }},
823 );
824 try std.testing.expectError(
825 error.WriteBatchRepeated,
826 relation.applyEditsIn(
827 std.testing.allocator,
828 &write,
829 &.{.{ .delete = 10 }},
830 ),
831 );
832 }
833 const discarded = try relation.get(std.testing.allocator, 10);
834 if (discarded) |bytes| std.testing.allocator.free(bytes);
835 try std.testing.expect(discarded == null);
836
837 var no_op_lookup: index_mod.Scan = undefined;
838 try relation.lookup(&no_op_lookup, std.testing.allocator, 0, &.{.{ .integer = 1 }});
839 defer no_op_lookup.deinit();
840 try std.testing.expect(try no_op_lookup.next() == null);
841 }
842
843 test "relation update merges assigned columns and maintains secondary index" {
844 var tmp = std.testing.tmpDir(.{});
845 defer tmp.cleanup();
846
847 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
848 .paths = .{ .database = "relation-update.db", .wal = "relation-update.wal" },
849 .header = testingHeader(),
850 });
851 defer database.deinit();
852 try database.reserve(.{ .wal_frames = 160 });
853
854 const space = try space_mod.Space.open(&database, .{ .roots = &.{ .{ .root_page = 2 }, .{ .root_page = 3 } } });
855 const specs = [_]IndexSpec{.{ .root_page = 3, .fields = &.{0} }};
856 var relation = try Relation.open(&space, .{ .table_root = 2, .indexes = &specs });
857 _ = try relation.put(std.testing.allocator, 4, &.{ .{ .integer = 9 }, .{ .text = "nine" } }, .{ .durability = .buffered });
858 _ = try relation.update(std.testing.allocator, 4, &.{.{ .column = 0, .value = .{ .integer = 12 } }}, .{ .durability = .buffered });
859
860 const found = (try relation.get(std.testing.allocator, 4)).?;
861 defer std.testing.allocator.free(found);
862 const view = try row.View.init(found);
863 try std.testing.expectEqual(@as(i64, 12), (try view.column(0)).integer);
864 try std.testing.expectEqualStrings("nine", (try view.column(1)).text);
865
866 var old_lookup: index_mod.Scan = undefined;
867 try relation.lookup(&old_lookup, std.testing.allocator, 0, &.{.{ .integer = 9 }});
868 defer old_lookup.deinit();
869 try std.testing.expect(try old_lookup.next() == null);
870
871 var new_lookup: index_mod.Scan = undefined;
872 try relation.lookup(&new_lookup, std.testing.allocator, 0, &.{.{ .integer = 12 }});
873 defer new_lookup.deinit();
874 try std.testing.expectEqual(@as(i64, 4), (try new_lookup.next()).?.rowid);
875 try std.testing.expect(try new_lookup.next() == null);
876 try relation.validateIndexes(std.testing.allocator);
877 }
878
879 test "relation update requires an existing row and known columns" {
880 var tmp = std.testing.tmpDir(.{});
881 defer tmp.cleanup();
882
883 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
884 .paths = .{ .database = "relation-update-missing.db", .wal = "relation-update-missing.wal" },
885 .header = testingHeader(),
886 });
887 defer database.deinit();
888 try database.reserve(.{ .wal_frames = 160 });
889
890 const space = try space_mod.Space.open(&database, .{ .roots = &.{.{ .root_page = 2 }} });
891 var relation = try Relation.open(&space, .{ .table_root = 2 });
892 try std.testing.expectError(error.KeyNotFound, relation.update(std.testing.allocator, 7, &.{.{ .column = 0, .value = .{ .integer = 1 } }}, .{ .durability = .buffered }));
893
894 _ = try relation.put(std.testing.allocator, 7, &.{ .{ .integer = 1 }, .{ .text = "one" } }, .{ .durability = .buffered });
895 try std.testing.expectError(error.ColumnOutOfBounds, relation.update(std.testing.allocator, 7, &.{.{ .column = 2, .value = .{ .integer = 5 } }}, .{ .durability = .buffered }));
896
897 var delete_then_update = [_]Edit{
898 .{ .delete = 7 },
899 .{ .update = .{ .rowid = 7, .assignments = &.{.{ .column = 0, .value = .{ .integer = 5 } }} } },
900 };
901 try std.testing.expectError(error.KeyNotFound, relation.applyEdits(std.testing.allocator, &delete_then_update, .{ .durability = .buffered }));
902 }
903
904 test "relation applies update edits within batches" {
905 var tmp = std.testing.tmpDir(.{});
906 defer tmp.cleanup();
907
908 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
909 .paths = .{ .database = "relation-update-batch.db", .wal = "relation-update-batch.wal" },
910 .header = testingHeader(),
911 });
912 defer database.deinit();
913 try database.reserve(.{ .wal_frames = 220 });
914
915 const space = try space_mod.Space.open(&database, .{ .roots = &.{ .{ .root_page = 2 }, .{ .root_page = 3 } } });
916 const specs = [_]IndexSpec{.{ .root_page = 3, .fields = &.{0} }};
917 var relation = try Relation.open(&space, .{ .table_root = 2, .indexes = &specs });
918
919 var fresh_buffer: [64]u8 = undefined;
920 const fresh = try row.encode(&fresh_buffer, &.{ .{ .integer = 1 }, .{ .text = "one" } });
921 _ = try relation.applyEdits(std.testing.allocator, &.{
922 .{ .put = .{ .rowid = 3, .bytes = fresh } },
923 .{ .update = .{ .rowid = 3, .assignments = &.{.{ .column = 0, .value = .{ .integer = 2 } }} } },
924 .{ .update = .{ .rowid = 3, .assignments = &.{.{ .column = 1, .value = .{ .text = "two" } }} } },
925 }, .{ .durability = .buffered });
926
927 const found = (try relation.get(std.testing.allocator, 3)).?;
928 defer std.testing.allocator.free(found);
929 const view = try row.View.init(found);
930 try std.testing.expectEqual(@as(i64, 2), (try view.column(0)).integer);
931 try std.testing.expectEqualStrings("two", (try view.column(1)).text);
932
933 var stale_lookup: index_mod.Scan = undefined;
934 try relation.lookup(&stale_lookup, std.testing.allocator, 0, &.{.{ .integer = 1 }});
935 defer stale_lookup.deinit();
936 try std.testing.expect(try stale_lookup.next() == null);
937
938 var live_lookup: index_mod.Scan = undefined;
939 try relation.lookup(&live_lookup, std.testing.allocator, 0, &.{.{ .integer = 2 }});
940 defer live_lookup.deinit();
941 try std.testing.expectEqual(@as(i64, 3), (try live_lookup.next()).?.rowid);
942 try std.testing.expect(try live_lookup.next() == null);
943 try relation.validateIndexes(std.testing.allocator);
944 }
945
946 test "relation validates secondary indexes against table rows" {
947 var tmp = std.testing.tmpDir(.{});
948 defer tmp.cleanup();
949
950 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
951 .paths = .{ .database = "relation-validate.db", .wal = "relation-validate.wal" },
952 .header = testingHeader(),
953 });
954 defer database.deinit();
955 try database.reserve(.{ .wal_frames = 160 });
956
957 const space = try space_mod.Space.open(&database, .{ .roots = &.{ .{ .root_page = 2 }, .{ .root_page = 3 } } });
958 const specs = [_]IndexSpec{.{ .root_page = 3, .fields = &.{0} }};
959 var relation = try Relation.open(&space, .{ .table_root = 2, .indexes = &specs });
960 _ = try relation.put(std.testing.allocator, 4, &.{ .{ .integer = 9 }, .{ .text = "nine" } }, .{ .durability = .buffered });
961
962 try relation.validateIndexes(std.testing.allocator);
963
964 _ = try relation.indexes[0].index.delete(4, &.{.{ .integer = 9 }}, .{ .durability = .buffered });
965 try std.testing.expectError(error.SecondaryIndexCorrupt, relation.validateIndexes(std.testing.allocator));
966 }
967
968 test "relation rejects orphaned secondary index entries" {
969 var tmp = std.testing.tmpDir(.{});
970 defer tmp.cleanup();
971
972 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
973 .paths = .{ .database = "relation-orphan.db", .wal = "relation-orphan.wal" },
974 .header = testingHeader(),
975 });
976 defer database.deinit();
977 try database.reserve(.{ .wal_frames = 160 });
978
979 const space = try space_mod.Space.open(&database, .{ .roots = &.{ .{ .root_page = 2 }, .{ .root_page = 3 } } });
980 const specs = [_]IndexSpec{.{ .root_page = 3, .fields = &.{0} }};
981 var relation = try Relation.open(&space, .{ .table_root = 2, .indexes = &specs });
982 _ = try relation.put(std.testing.allocator, 4, &.{ .{ .integer = 9 }, .{ .text = "nine" } }, .{ .durability = .buffered });
983 _ = try relation.indexes[0].index.put(99, &.{.{ .integer = 99 }}, .{ .durability = .buffered });
984
985 try std.testing.expectError(error.SecondaryIndexCorrupt, relation.validateIndexes(std.testing.allocator));
986 }
987
988 test "relation rejects mismatched secondary index entries" {
989 var tmp = std.testing.tmpDir(.{});
990 defer tmp.cleanup();
991
992 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
993 .paths = .{
994 .database = "relation-mismatch.db",
995 .wal = "relation-mismatch.wal",
996 },
997 .header = testingHeader(),
998 });
999 defer database.deinit();
1000 try database.reserve(.{ .wal_frames = 160 });
1001
1002 const space = try space_mod.Space.open(&database, .{
1003 .roots = &.{ .{ .root_page = 2 }, .{ .root_page = 3 } },
1004 });
1005 const specs = [_]IndexSpec{.{ .root_page = 3, .fields = &.{0} }};
1006 var relation = try Relation.open(&space, .{
1007 .table_root = 2,
1008 .indexes = &specs,
1009 });
1010 _ = try relation.put(
1011 std.testing.allocator,
1012 4,
1013 &.{ .{ .integer = 9 }, .{ .text = "nine" } },
1014 .{ .durability = .buffered },
1015 );
1016 _ = try relation.indexes[0].index.put(
1017 4,
1018 &.{.{ .integer = 99 }},
1019 .{ .durability = .buffered },
1020 );
1021
1022 try std.testing.expectError(
1023 error.SecondaryIndexCorrupt,
1024 relation.validateIndexes(std.testing.allocator),
1025 );
1026 }
1027
1028 test "relation rejects an index key larger than a page and stays writable" {
1029 var tmp = std.testing.tmpDir(.{});
1030 defer tmp.cleanup();
1031
1032 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
1033 .paths = .{ .database = "relation-widekey.db", .wal = "relation-widekey.wal" },
1034 .header = testingHeader(),
1035 });
1036 defer database.deinit();
1037 try database.reserve(.{ .wal_frames = 512 });
1038
1039 const space = try space_mod.Space.open(&database, .{ .roots = &.{ .{ .root_page = 2 }, .{ .root_page = 3 } } });
1040 const specs = [_]IndexSpec{.{ .root_page = 3, .fields = &.{0} }};
1041 var relation = try Relation.open(&space, .{ .table_root = 2, .indexes = &specs });
1042
1043 const sizes = [_]usize{ 512, 1024, 1900, 8000, 1000 };
1044 const expected = [sizes.len]?anyerror{ null, null, null, error.KeyTooLarge, null };
1045 var outcomes: [sizes.len]?anyerror = undefined;
1046 for (sizes, 0..) |size, ordinal| {
1047 const text = try std.testing.allocator.alloc(u8, size);
1048 defer std.testing.allocator.free(text);
1049 @memset(text, 'x');
1050 text[0] = @intCast('a' + ordinal);
1051 const values = [_]row.Value{ .{ .text = text }, .{ .integer = @intCast(size) } };
1052 const encoded = try std.testing.allocator.alloc(u8, try row.encodedSize(&values));
1053 defer std.testing.allocator.free(encoded);
1054 _ = try row.encode(encoded, &values);
1055 outcomes[ordinal] = null;
1056 _ = relation.applyEdits(std.testing.allocator, &.{.{ .put = .{
1057 .rowid = @intCast(ordinal + 1),
1058 .bytes = encoded,
1059 } }}, .{ .durability = .buffered }) catch |err| {
1060 outcomes[ordinal] = err;
1061 };
1062 }
1063 try std.testing.expectEqualSlices(?anyerror, &expected, &outcomes);
1064
1065 const missing = try relation.get(std.testing.allocator, 4);
1066 if (missing) |bytes| std.testing.allocator.free(bytes);
1067 try std.testing.expect(missing == null);
1068 const accepted = (try relation.get(std.testing.allocator, 5)).?;
1069 defer std.testing.allocator.free(accepted);
1070 try relation.validateIndexes(std.testing.allocator);
1071 }
1072
1073 test "relation put accepts rows larger than a page" {
1074 var tmp = std.testing.tmpDir(.{});
1075 defer tmp.cleanup();
1076
1077 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
1078 .paths = .{ .database = "relation-widerow.db", .wal = "relation-widerow.wal" },
1079 .header = testingHeader(),
1080 });
1081 defer database.deinit();
1082 try database.reserve(.{ .wal_frames = 512 });
1083
1084 const space = try space_mod.Space.open(&database, .{ .roots = &.{.{ .root_page = 2 }} });
1085 var relation = try Relation.open(&space, .{ .table_root = 2, .indexes = &.{} });
1086
1087 const sizes = [_]usize{ 4000, page.size, page.size * 4 };
1088 for (sizes, 0..) |size, ordinal| {
1089 const text = try std.testing.allocator.alloc(u8, size);
1090 defer std.testing.allocator.free(text);
1091 @memset(text, 'y');
1092 const values = [_]row.Value{ .{ .text = text }, .{ .integer = @intCast(size) } };
1093 _ = try relation.put(std.testing.allocator, @intCast(ordinal + 1), &values, .{ .durability = .buffered });
1094
1095 const stored = (try relation.get(std.testing.allocator, @intCast(ordinal + 1))).?;
1096 defer std.testing.allocator.free(stored);
1097 const view = try row.View.init(stored);
1098 try std.testing.expectEqualStrings(text, (try view.column(0)).text);
1099 }
1100 }
1101
1102 fn testingHeader() wal.Header {
1103 return .{
1104 .sequence = 1001,
1105 .salt = .{ .first = 0x9191_a2a2, .second = 0x6363_b4b4 },
1106 };
1107 }
1108
1109 fn recoveredHeader() wal.Header {
1110 return .{
1111 .sequence = 1002,
1112 .salt = .{ .first = 0xaaaa_7777, .second = 0xbbbb_8888 },
1113 };
1114 }