lib/sql/src/index.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const file = @import("file.zig");
3 const key = @import("key.zig");
4 const page = @import("page.zig");
5 const row = @import("row.zig");
6 const trace = @import("trace.zig");
7 const tree = @import("tree.zig");
8 const wal = @import("wal.zig");
9
10 const Allocator = std.mem.Allocator;
11
12 pub const Error = tree.Error || row.Error || key.Error;
13
14 pub const Options = struct {
15 tree: tree.Options,
16 columns: []const row.Column = &.{},
17 };
18
19 pub const Entry = struct {
20 rowid: i64,
21 key: []const u8,
22 payload: []const u8 = "",
23 };
24
25 pub const Bound = struct {
26 values: []const row.Value,
27 inclusive: bool,
28 };
29
30 pub const Reader = struct {
31 entries: tree.Reader,
32 columns: []const row.Column,
33
34 pub fn open(snapshot: file.Snapshot, options: Options) Error!Reader {
35 return .{
36 .entries = try tree.Reader.open(snapshot, options.tree),
37 .columns = options.columns,
38 };
39 }
40
41 /// Starts a scan of the entries from `start` up to `end` in `target`.
42 pub fn scan(
43 self: *const Reader,
44 target: *Scan,
45 allocator: Allocator,
46 start: ?[]const row.Value,
47 end: ?[]const row.Value,
48 ) Error!void {
49 const phase = trace.scope("index.scan");
50 defer phase.end();
51
52 try self.range(
53 target,
54 allocator,
55 if (start) |values| .{ .values = values, .inclusive = true } else null,
56 if (end) |values| .{ .values = values, .inclusive = false } else null,
57 );
58 }
59
60 pub fn range(
61 self: *const Reader,
62 target: *Scan,
63 allocator: Allocator,
64 start: ?Bound,
65 end: ?Bound,
66 ) Error!void {
67 const phase = trace.scope("index.range");
68 defer phase.end();
69
70 try self.rangeProjection(target, allocator, start, end, .key);
71 }
72
73 pub fn scanPayloads(
74 self: *const Reader,
75 target: *Scan,
76 allocator: Allocator,
77 start: ?[]const row.Value,
78 end: ?[]const row.Value,
79 ) Error!void {
80 const phase = trace.scope("index.scan_payloads");
81 defer phase.end();
82
83 try self.rangeProjection(
84 target,
85 allocator,
86 if (start) |values| .{ .values = values, .inclusive = true } else null,
87 if (end) |values| .{ .values = values, .inclusive = false } else null,
88 .value,
89 );
90 }
91
92 pub fn lookup(
93 self: *const Reader,
94 target: *Scan,
95 allocator: Allocator,
96 prefix: []const row.Value,
97 ) Error!void {
98 const phase = trace.scope("index.lookup");
99 defer phase.end();
100
101 try self.lookupProjection(target, allocator, prefix, .key);
102 }
103
104 pub fn lookupPayloads(
105 self: *const Reader,
106 target: *Scan,
107 allocator: Allocator,
108 prefix: []const row.Value,
109 ) Error!void {
110 const phase = trace.scope("index.lookup_payloads");
111 defer phase.end();
112
113 try self.lookupProjection(target, allocator, prefix, .value);
114 }
115
116 pub fn summarize(self: *const Reader) Error!tree.Summary {
117 const phase = trace.scope("index.summarize");
118 defer phase.end();
119
120 return try self.entries.summarize();
121 }
122
123 fn rangeProjection(
124 self: *const Reader,
125 target: *Scan,
126 allocator: Allocator,
127 start: ?Bound,
128 end: ?Bound,
129 projection: tree.Projection,
130 ) Error!void {
131 var start_bytes: [page.size]u8 = undefined;
132 var start_end_bytes: [page.size]u8 = undefined;
133 var end_bytes: [page.size]u8 = undefined;
134 var end_end_bytes: [page.size]u8 = undefined;
135 const start_key = if (start) |bound| start_key: {
136 const prefix = try key.encodeIndexPrefix(&start_bytes, bound.values, self.columns);
137 break :start_key if (bound.inclusive)
138 prefix
139 else
140 try key.encodePrefixEnd(&start_end_bytes, prefix);
141 } else null;
142 const end_key = if (end) |bound| end_key: {
143 const prefix = try key.encodeIndexPrefix(&end_bytes, bound.values, self.columns);
144 break :end_key if (bound.inclusive)
145 try key.encodePrefixEnd(&end_end_bytes, prefix)
146 else
147 prefix;
148 } else null;
149 try self.entries.scan(&target.entries, allocator, start_key, end_key, projection);
150 }
151
152 fn lookupProjection(
153 self: *const Reader,
154 target: *Scan,
155 allocator: Allocator,
156 prefix: []const row.Value,
157 projection: tree.Projection,
158 ) Error!void {
159 var start_bytes: [page.size]u8 = undefined;
160 var end_bytes: [page.size]u8 = undefined;
161 const start_key = try key.encodeIndexPrefix(&start_bytes, prefix, self.columns);
162 const end_key = try key.encodePrefixEnd(&end_bytes, start_key);
163 try self.entries.scan(&target.entries, allocator, start_key, end_key, projection);
164 }
165 };
166
167 pub const Index = struct {
168 entries: tree.Tree,
169 columns: []const row.Column,
170
171 pub fn open(database: *file.Database, options: Options) Error!Index {
172 return .{
173 .entries = try tree.Tree.open(database, options.tree),
174 .columns = options.columns,
175 };
176 }
177
178 pub fn reader(self: *const Index, snapshot: file.Snapshot) Error!Reader {
179 return .{
180 .entries = try self.entries.reader(snapshot),
181 .columns = self.columns,
182 };
183 }
184
185 pub fn put(self: *Index, rowid: i64, values: []const row.Value, options: file.CommitOptions) Error!file.Commit {
186 const phase = trace.scope("index.put");
187 defer phase.end();
188
189 var write = try tree.Write.beginTree(&self.entries);
190 defer write.deinit();
191 try self.putPayloadIn(&write, rowid, values, "");
192 return try write.commit(options);
193 }
194
195 pub fn putIn(self: *Index, write: *tree.Write, rowid: i64, values: []const row.Value) Error!void {
196 try self.putPayloadIn(write, rowid, values, "");
197 }
198
199 pub fn putPayload(self: *Index, rowid: i64, values: []const row.Value, payload: []const u8, options: file.CommitOptions) Error!file.Commit {
200 const phase = trace.scope("index.put_payload");
201 defer phase.end();
202
203 var write = try tree.Write.beginTree(&self.entries);
204 defer write.deinit();
205 try self.putPayloadIn(&write, rowid, values, payload);
206 return try write.commit(options);
207 }
208
209 pub fn putPayloadIn(self: *Index, write: *tree.Write, rowid: i64, values: []const row.Value, payload: []const u8) Error!void {
210 var key_bytes: [page.size]u8 = undefined;
211 const encoded = key.encodeIndex(&key_bytes, values, self.columns, rowid) catch |err| switch (err) {
212 error.OutputTooSmall => return error.KeyTooLarge,
213 else => return err,
214 };
215 try write.put(&self.entries, encoded, payload);
216 }
217
218 pub fn delete(self: *Index, rowid: i64, values: []const row.Value, options: file.CommitOptions) Error!file.Commit {
219 const phase = trace.scope("index.delete");
220 defer phase.end();
221
222 var write = try tree.Write.beginTree(&self.entries);
223 defer write.deinit();
224 try self.deleteIn(&write, rowid, values);
225 return try write.commit(options);
226 }
227
228 pub fn deleteIn(self: *Index, write: *tree.Write, rowid: i64, values: []const row.Value) Error!void {
229 var key_bytes: [page.size]u8 = undefined;
230 const encoded = key.encodeIndex(&key_bytes, values, self.columns, rowid) catch |err| switch (err) {
231 error.OutputTooSmall => return error.KeyTooLarge,
232 else => return err,
233 };
234 try write.delete(&self.entries, encoded);
235 }
236
237 pub fn scan(
238 self: *const Index,
239 target: *Scan,
240 allocator: Allocator,
241 start: ?[]const row.Value,
242 end: ?[]const row.Value,
243 ) Error!void {
244 var read = try self.entries.database.beginRead();
245 defer read.deinit();
246 const opened = try self.reader(read.snapshot());
247 try opened.scan(target, allocator, start, end);
248 }
249
250 pub fn range(
251 self: *const Index,
252 target: *Scan,
253 allocator: Allocator,
254 start: ?Bound,
255 end: ?Bound,
256 ) Error!void {
257 var read = try self.entries.database.beginRead();
258 defer read.deinit();
259 const opened = try self.reader(read.snapshot());
260 try opened.range(target, allocator, start, end);
261 }
262
263 pub fn scanPayloads(
264 self: *const Index,
265 target: *Scan,
266 allocator: Allocator,
267 start: ?[]const row.Value,
268 end: ?[]const row.Value,
269 ) Error!void {
270 var read = try self.entries.database.beginRead();
271 defer read.deinit();
272 const opened = try self.reader(read.snapshot());
273 try opened.scanPayloads(target, allocator, start, end);
274 }
275
276 pub fn lookup(
277 self: *const Index,
278 target: *Scan,
279 allocator: Allocator,
280 prefix: []const row.Value,
281 ) Error!void {
282 var read = try self.entries.database.beginRead();
283 defer read.deinit();
284 const opened = try self.reader(read.snapshot());
285 try opened.lookup(target, allocator, prefix);
286 }
287
288 pub fn lookupPayloads(
289 self: *const Index,
290 target: *Scan,
291 allocator: Allocator,
292 prefix: []const row.Value,
293 ) Error!void {
294 var read = try self.entries.database.beginRead();
295 defer read.deinit();
296 const opened = try self.reader(read.snapshot());
297 try opened.lookupPayloads(target, allocator, prefix);
298 }
299
300 pub fn summarize(self: *const Index) Error!tree.Summary {
301 var read = try self.entries.database.beginRead();
302 defer read.deinit();
303 const opened = try self.reader(read.snapshot());
304 return try opened.summarize();
305 }
306
307 pub fn summarizeIn(self: *const Index, write: *const tree.Write) Error!tree.Summary {
308 const phase = trace.scope("index.summarize_in");
309 defer phase.end();
310
311 return try self.entries.summarizeIn(write);
312 }
313 };
314
315 pub const Scan = struct {
316 entries: tree.Scan,
317
318 pub fn deinit(self: *Scan) void {
319 self.entries.deinit();
320 self.* = undefined;
321 }
322
323 pub fn next(self: *Scan) Error!?Entry {
324 if (try self.entries.next()) |entry| {
325 return .{
326 .rowid = try key.decodeIndexRowId(entry.key),
327 .key = entry.key,
328 .payload = entry.bytes,
329 };
330 }
331 return null;
332 }
333 };
334
335 test "secondary index stores duplicate values in rowid order" {
336 var tmp = std.testing.tmpDir(.{});
337 defer tmp.cleanup();
338
339 {
340 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
341 .paths = .{ .database = "index.db", .wal = "index.wal" },
342 .header = testingHeader(),
343 });
344 defer database.deinit();
345 try database.reserve(.{ .wal_frames = 96 });
346
347 var index = try Index.open(&database, .{ .tree = .{ .meta_page = 3, .root_page = 4 } });
348 _ = try index.put(3, &.{.{ .text = "orange" }}, .{ .durability = .buffered });
349 _ = try index.put(2, &.{.{ .text = "apple" }}, .{ .durability = .buffered });
350 _ = try index.put(-1, &.{.{ .text = "apple" }}, .{ .durability = .buffered });
351 _ = try index.put(7, &.{.{ .text = "pear" }}, .{ .durability = .buffered });
352 try database.syncWal();
353 }
354
355 var reopened = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
356 .paths = .{ .database = "index.db", .wal = "index.wal" },
357 .header = recoveredHeader(),
358 });
359 defer reopened.deinit();
360
361 var index = try Index.open(&reopened, .{ .tree = .{ .meta_page = 3, .root_page = 4 } });
362 var scan: Scan = undefined;
363 try index.scan(&scan, std.testing.allocator, null, null);
364 defer scan.deinit();
365 try std.testing.expectEqual(@as(i64, -1), (try scan.next()).?.rowid);
366 try std.testing.expectEqual(@as(i64, 2), (try scan.next()).?.rowid);
367 try std.testing.expectEqual(@as(i64, 3), (try scan.next()).?.rowid);
368 try std.testing.expectEqual(@as(i64, 7), (try scan.next()).?.rowid);
369 try std.testing.expect(try scan.next() == null);
370
371 var lookup: Scan = undefined;
372 try index.lookup(&lookup, std.testing.allocator, &.{.{ .text = "apple" }});
373 defer lookup.deinit();
374 try std.testing.expectEqual(@as(i64, -1), (try lookup.next()).?.rowid);
375 try std.testing.expectEqual(@as(i64, 2), (try lookup.next()).?.rowid);
376 try std.testing.expect(try lookup.next() == null);
377
378 _ = try index.delete(-1, &.{.{ .text = "apple" }}, .{ .durability = .buffered });
379 var remaining: Scan = undefined;
380 try index.lookup(&remaining, std.testing.allocator, &.{.{ .text = "apple" }});
381 defer remaining.deinit();
382 try std.testing.expectEqual(@as(i64, 2), (try remaining.next()).?.rowid);
383 try std.testing.expect(try remaining.next() == null);
384 }
385
386 test "secondary index stores payloads in rowid order" {
387 var tmp = std.testing.tmpDir(.{});
388 defer tmp.cleanup();
389
390 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
391 .paths = .{ .database = "index.db", .wal = "index.wal" },
392 .header = testingHeader(),
393 });
394 defer database.deinit();
395 try database.reserve(.{ .wal_frames = 96 });
396
397 var index = try Index.open(&database, .{ .tree = .{ .meta_page = 3, .root_page = 4 } });
398 _ = try index.putPayload(4, &.{.{ .text = "apple" }}, "four", .{ .durability = .buffered });
399 _ = try index.putPayload(1, &.{.{ .text = "apple" }}, "one", .{ .durability = .buffered });
400 _ = try index.putPayload(3, &.{.{ .text = "orange" }}, "three", .{ .durability = .buffered });
401
402 var lookup: Scan = undefined;
403 try index.lookupPayloads(&lookup, std.testing.allocator, &.{.{ .text = "apple" }});
404 defer lookup.deinit();
405 const first = (try lookup.next()).?;
406 try std.testing.expectEqual(@as(i64, 1), first.rowid);
407 try std.testing.expectEqualStrings("one", first.payload);
408 const second = (try lookup.next()).?;
409 try std.testing.expectEqual(@as(i64, 4), second.rowid);
410 try std.testing.expectEqualStrings("four", second.payload);
411 try std.testing.expect(try lookup.next() == null);
412
413 var key_lookup: Scan = undefined;
414 try index.lookup(&key_lookup, std.testing.allocator, &.{.{ .text = "apple" }});
415 defer key_lookup.deinit();
416 try std.testing.expectEqual(@as(usize, 0), (try key_lookup.next()).?.payload.len);
417 }
418
419 test "secondary index range scan uses encoded value bounds" {
420 var tmp = std.testing.tmpDir(.{});
421 defer tmp.cleanup();
422
423 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
424 .paths = .{ .database = "index.db", .wal = "index.wal" },
425 .header = testingHeader(),
426 });
427 defer database.deinit();
428 try database.reserve(.{ .wal_frames = 96 });
429
430 var index = try Index.open(&database, .{ .tree = .{ .meta_page = 3, .root_page = 4 } });
431 _ = try index.put(10, &.{.{ .integer = -3 }}, .{ .durability = .buffered });
432 _ = try index.put(11, &.{.{ .integer = 0 }}, .{ .durability = .buffered });
433 _ = try index.put(12, &.{.{ .integer = 1 }}, .{ .durability = .buffered });
434 _ = try index.put(13, &.{.{ .integer = 3 }}, .{ .durability = .buffered });
435
436 var scan: Scan = undefined;
437 try index.scan(&scan, std.testing.allocator, &.{.{ .integer = 0 }}, &.{.{ .integer = 3 }});
438 defer scan.deinit();
439 try std.testing.expectEqual(@as(i64, 11), (try scan.next()).?.rowid);
440 try std.testing.expectEqual(@as(i64, 12), (try scan.next()).?.rowid);
441 try std.testing.expect(try scan.next() == null);
442
443 var inclusive: Scan = undefined;
444 try index.range(
445 &inclusive,
446 std.testing.allocator,
447 .{ .values = &.{.{ .integer = 0 }}, .inclusive = true },
448 .{ .values = &.{.{ .integer = 3 }}, .inclusive = true },
449 );
450 defer inclusive.deinit();
451 try std.testing.expectEqual(@as(i64, 11), (try inclusive.next()).?.rowid);
452 try std.testing.expectEqual(@as(i64, 12), (try inclusive.next()).?.rowid);
453 try std.testing.expectEqual(@as(i64, 13), (try inclusive.next()).?.rowid);
454 try std.testing.expect(try inclusive.next() == null);
455
456 var exclusive_start: Scan = undefined;
457 try index.range(
458 &exclusive_start,
459 std.testing.allocator,
460 .{ .values = &.{.{ .integer = 0 }}, .inclusive = false },
461 null,
462 );
463 defer exclusive_start.deinit();
464 try std.testing.expectEqual(@as(i64, 12), (try exclusive_start.next()).?.rowid);
465 try std.testing.expectEqual(@as(i64, 13), (try exclusive_start.next()).?.rowid);
466 try std.testing.expect(try exclusive_start.next() == null);
467 }
468
469 test "secondary index honors configured text collation" {
470 var tmp = std.testing.tmpDir(.{});
471 defer tmp.cleanup();
472
473 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
474 .paths = .{ .database = "index.db", .wal = "index.wal" },
475 .header = testingHeader(),
476 });
477 defer database.deinit();
478 try database.reserve(.{ .wal_frames = 96 });
479
480 const columns = [_]row.Column{.{ .collation = .nocase }};
481 var index = try Index.open(&database, .{
482 .tree = .{ .meta_page = 3, .root_page = 4 },
483 .columns = &columns,
484 });
485 _ = try index.put(2, &.{.{ .text = "Alpha" }}, .{ .durability = .buffered });
486 _ = try index.put(1, &.{.{ .text = "alpha" }}, .{ .durability = .buffered });
487
488 var lookup: Scan = undefined;
489 try index.lookup(&lookup, std.testing.allocator, &.{.{ .text = "ALPHA" }});
490 defer lookup.deinit();
491 try std.testing.expectEqual(@as(i64, 1), (try lookup.next()).?.rowid);
492 try std.testing.expectEqual(@as(i64, 2), (try lookup.next()).?.rowid);
493 try std.testing.expect(try lookup.next() == null);
494 }
495
496 fn testingHeader() wal.Header {
497 return .{
498 .sequence = 801,
499 .salt = .{ .first = 0x7171_9191, .second = 0x5353_6363 },
500 };
501 }
502
503 fn recoveredHeader() wal.Header {
504 return .{
505 .sequence = 802,
506 .salt = .{ .first = 0x8888_aaaa, .second = 0xbbbb_9999 },
507 };
508 }