tiny.sql.index

1const std = @import("std");2const file = @import("file.zig");3const key = @import("key.zig");4const page = @import("page.zig");5const row = @import("row.zig");6const trace = @import("trace.zig");7const tree = @import("tree.zig");8const wal = @import("wal.zig");910const Allocator = std.mem.Allocator;1112pub const Error = tree.Error || row.Error || key.Error;1314pub const Options = struct {15    tree: tree.Options,16    columns: []const row.Column = &.{},17};1819pub const Entry = struct {20    rowid: i64,21    key: []const u8,22    payload: []const u8 = "",23};2425pub const Bound = struct {26    values: []const row.Value,27    inclusive: bool,28};2930pub const Reader = struct {31    entries: tree.Reader,32    columns: []const row.Column,3334    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    }4041    /// 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();5152        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    }5960    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();6970        try self.rangeProjection(target, allocator, start, end, .key);71    }7273    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();8283        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    }9192    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();100101        try self.lookupProjection(target, allocator, prefix, .key);102    }103104    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();112113        try self.lookupProjection(target, allocator, prefix, .value);114    }115116    pub fn summarize(self: *const Reader) Error!tree.Summary {117        const phase = trace.scope("index.summarize");118        defer phase.end();119120        return try self.entries.summarize();121    }122123    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                prefix139            else140                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            else147                prefix;148        } else null;149        try self.entries.scan(&target.entries, allocator, start_key, end_key, projection);150    }151152    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};166167pub const Index = struct {168    entries: tree.Tree,169    columns: []const row.Column,170171    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    }177178    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    }184185    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();188189        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    }194195    pub fn putIn(self: *Index, write: *tree.Write, rowid: i64, values: []const row.Value) Error!void {196        try self.putPayloadIn(write, rowid, values, "");197    }198199    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();202203        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    }208209    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    }217218    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();221222        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    }227228    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    }236237    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    }249250    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    }262263    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    }275276    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    }287288    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    }299300    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    }306307    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();310311        return try self.entries.summarizeIn(write);312    }313};314315pub const Scan = struct {316    entries: tree.Scan,317318    pub fn deinit(self: *Scan) void {319        self.entries.deinit();320        self.* = undefined;321    }322323    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};334335test "secondary index stores duplicate values in rowid order" {336    var tmp = std.testing.tmpDir(.{});337    defer tmp.cleanup();338339    {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 });346347        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    }354355    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();360361    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);370371    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);377378    _ = 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}385386test "secondary index stores payloads in rowid order" {387    var tmp = std.testing.tmpDir(.{});388    defer tmp.cleanup();389390    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 });396397    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 });401402    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);412413    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}418419test "secondary index range scan uses encoded value bounds" {420    var tmp = std.testing.tmpDir(.{});421    defer tmp.cleanup();422423    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 });429430    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 });435436    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);442443    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);455456    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}468469test "secondary index honors configured text collation" {470    var tmp = std.testing.tmpDir(.{});471    defer tmp.cleanup();472473    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 });479480    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 });487488    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}495496fn testingHeader() wal.Header {497    return .{498        .sequence = 801,499        .salt = .{ .first = 0x7171_9191, .second = 0x5353_6363 },500    };501}502503fn recoveredHeader() wal.Header {504    return .{505        .sequence = 802,506        .salt = .{ .first = 0x8888_aaaa, .second = 0xbbbb_9999 },507    };508}

1pub const index = @import("index.zig");