Sqlite3.Database.pq

// SPDX-License-Identifier: Apache-2.0
//
// Sqlite3.Database.pq — read SQLite database files in pure Power Query M.
// No ODBC, no ADO.NET provider, no Python/R, no custom connector required.
// Paste into a blank query (name it Sqlite3.Database), or wrap as a function
// in your PBIX / dataflow.
//
// Usage:
//   let
//       Sqlite3.Database = <this expression>,
//       db  = Sqlite3.Database(File.Contents("C:\path\to\your.db")),  // nav table
//       tbl = db{[Name = "my_table"]}[Data]
//   in
//       tbl
//
// Options (optional second argument, all keys optional):
//   MaxRows  number — decode at most this many rows per table.
//
// This function is also the shared SQLite core for the GeoPackage (gpkg/) and
// MBTiles (mbtiles/) readers in this repository: they expect a query named
// Sqlite3.Database next to them. Fix b-tree or record-decoding bugs here, once.
//
// Supported: ordinary rowid tables, all serial types, overflow pages,
//            INTEGER PRIMARY KEY rowid aliasing, UTF-8/UTF-16LE/UTF-16BE,
//            ALTER TABLE ADD COLUMN short records, multi-level b-trees.
// Not supported: WITHOUT ROWID tables (index b-tree layout), virtual tables,
//            reading un-checkpointed data from a -wal file (see notes at end).
// Precision: integers decode exactly across the full signed 64-bit range
//            (8-byte serial types via BinaryFormat.SignedInteger64); downstream M
//            arithmetic on them may still coerce to double past 2^53.

(source as binary, optional options as nullable record) as table =>
let
    bin = Binary.Buffer(source),

    opts       = if options = null then [] else options,
    OptMaxRows = Record.FieldOrDefault(opts, "MaxRows", null),

    //==================== low-level byte access ====================
    Slice = (b as binary, offset as number, count as number) as binary =>
        if count <= 0 then #binary({})
        else Binary.Range(b, offset, count),

    UInt16BEFormat = BinaryFormat.ByteOrder(BinaryFormat.UnsignedInteger16, ByteOrder.BigEndian),
    UInt32BEFormat = BinaryFormat.ByteOrder(BinaryFormat.UnsignedInteger32, ByteOrder.BigEndian),
    // a contiguous run of big-endian u16 (the cell pointer array) is a sequential
    // structure: one slice plus one list format beats n separate slice+parse calls
    UInt16BEListFormat = (n as number) as function => BinaryFormat.List(UInt16BEFormat, n),

    // Signed big-endian formats hoisted once; dispatched per cell for serial types
    // 2/4/6. Unlike the old accumulate-to-double path these decode the full 64-bit
    // range exactly (8-byte integers above 2^53 no longer round). Widths BinaryFormat
    // cannot express (3- and 6-byte, serial types 3/5) keep the accumulate helper
    // with precomputed sign constants.
    Int16BEFormat = BinaryFormat.ByteOrder(BinaryFormat.SignedInteger16, ByteOrder.BigEndian),
    Int32BEFormat = BinaryFormat.ByteOrder(BinaryFormat.SignedInteger32, ByteOrder.BigEndian),
    Int64BEFormat = BinaryFormat.ByteOrder(BinaryFormat.SignedInteger64, ByteOrder.BigEndian),

    Float64BEFormat = BinaryFormat.ByteOrder(BinaryFormat.Double, ByteOrder.BigEndian),
    ReadByte = (b as binary, offset as number) as number => BinaryFormat.Byte(Binary.Range(b, offset, 1)),
    UIntBE = (b as binary) as number => List.Accumulate(Binary.ToList(b), 0, (s, c) => s * 256 + c),
    // signed decode of the two odd widths only (3 bytes = 2^23/2^24, 6 bytes = 2^47/2^48)
    Int3BE = (b as binary) as number =>
        let u = UIntBE(b) in if u >= 8388608 then u - 16777216 else u,
    Int6BE = (b as binary) as number =>
        let u = UIntBE(b) in if u >= 140737488355328 then u - 281474976710656 else u,
    
    Byte = (off as number) as number => ReadByte(bin, off),
    UInt2 = (off as number) as number => UInt16BEFormat(Binary.Range(bin, off, 2)),
    UInt4 = (off as number) as number => UInt32BEFormat(Binary.Range(bin, off, 4)),
    VarintAt = (b as binary, offset as number) as record =>
        let f = (o as number, v as number, n as number) as record =>
                let by = ReadByte(b, o)
                in if n = 8 then [Value = v * 256 + by, Size = 9]
                    else if by < 128 then [Value = v * 128 + by, Size = n + 1]
                    else @f(o + 1, v * 128 + (by - 128), n + 1)
        in
            f(offset, 0, 0),

    //==================== file header ====================
    // The 100-byte header is read once, front to back, at fixed small offsets:
    // rule 5 in context/PERF.md — a sequential structure may stay streaming, and
    // a hoisted BinaryFormat.Record says what the layout is instead of scattering
    // magic offsets through the query.
    HeaderFormat = BinaryFormat.Record([
        Magic        = BinaryFormat.Text(15, TextEncoding.Utf8),   //  0  "SQLite format 3"
        NulTerm      = BinaryFormat.Byte,                          // 15  \0
        PageSizeRaw  = UInt16BEFormat,                             // 16  1 means 65536
        WriteVersion = BinaryFormat.Byte,                          // 18  1 = journal, 2 = WAL
        ReadVersion  = BinaryFormat.Byte,                          // 19
        ReservedSize = BinaryFormat.Byte,                          // 20  unused bytes per page
        Unused       = BinaryFormat.Binary(35),                    // 21  fractions, counters, sizes
        EncodingId   = UInt32BEFormat                              // 56  1 = UTF-8, 2/3 = UTF-16
    ]),
    hdr = HeaderFormat(
              if Binary.Length(bin) < 100
              then error Error.Record("DataFormat.Error",
                       "Not a SQLite 3 database file",
                       "file is shorter than the 100-byte header")
              else Binary.Range(bin, 0, 100)),
    Magic = hdr[Magic],
    ps0   = if Magic <> "SQLite format 3"
            then error Error.Record("DataFormat.Error", "Not a SQLite 3 database file", Magic)
            else hdr[PageSizeRaw],
    PageSize   = if ps0 = 1 then 65536 else ps0,
    WriteVer   = hdr[WriteVersion],              // 1 = rollback journal, 2 = WAL
    Reserved   = hdr[ReservedSize],
    Usable     = PageSize - Reserved,
    EncodingId = hdr[EncodingId],
    Enc = if EncodingId = 2 then TextEncoding.Unicode            // UTF-16LE
          else if EncodingId = 3 then TextEncoding.BigEndianUnicode
          else TextEncoding.Utf8,

    // overflow thresholds for table b-tree leaves
    Xmax = Usable - 35,
    Mmin = Number.IntegerDivide((Usable - 12) * 32, 255) - 23,

    //==================== b-tree traversal (table b-trees) ====================
    // returns list of [Rowid = number, Payload = binary]
    CollectCells = (pageNum as number) as list =>
        let
            pageOff = (pageNum - 1) * PageSize,
            base    = pageOff + (if pageNum = 1 then 100 else 0),
            ptype   = Byte(base),
            ncells  = UInt2(base + 3),
            hdrSize = if ptype = 5 then 12 else 8,
            // cell pointer array: ncells contiguous 2-byte offsets relative to the
            // start of the page — one slice, one list format, one pass
            offs = if ncells = 0 then {}
                   else List.Transform(
                            UInt16BEListFormat(ncells)(
                                Slice(bin, base + hdrSize, ncells * 2)),
                            (p) => pageOff + p),

            ReadLeafCell = (o as number) as record =>
                let
                    pv      = VarintAt(bin, o),
                    P       = pv[Value],
                    rv      = VarintAt(bin, o + pv[Size]),
                    dstart  = o + pv[Size] + rv[Size],
                    payload =
                        if P <= Xmax then Slice(bin, dstart, P)
                        else
                        let
                            K      = Mmin + Number.Mod(P - Mmin, Usable - 4),
                            inline = if K <= Xmax then K else Mmin,
                            head   = Slice(bin, dstart, inline),
                            first  = UInt4(dstart + inline),
                            chunks = List.Generate(
                                () => [pg = first],
                                (s) => s[pg] <> 0,
                                (s) => [pg = UInt4((s[pg] - 1) * PageSize)],
                                (s) => Slice(bin, (s[pg] - 1) * PageSize + 4, Usable - 4)),
                            full   = Binary.Combine({head} & chunks)
                        in
                            Slice(full, 0, P)
                in
                    [Rowid = rv[Value], Payload = payload]
        in
            if ncells = 0 and ptype = 13 then {}
            else if ptype = 13 then
                List.Transform(offs, ReadLeafCell)
            else if ptype = 5 then
                let
                    children  = List.Transform(offs, (o) => UInt4(o)),
                    rightmost = UInt4(base + 8),
                    all       = children & {rightmost}
                in
                    List.Combine(List.Transform(all, (p) => @CollectCells(p)))
            else
                error Error.Record("DataFormat.Error",
                    "Page " & Number.ToText(pageNum) &
                    " is not a table b-tree page (type " & Number.ToText(ptype) & ")." &
                    " WITHOUT ROWID tables and indexes are not supported.", null),

    //==================== record (row) decoding ====================
    SerialSize = (st as number) as number =>
        if st = 0 or st = 8 or st = 9 then 0
        else if st <= 4 then st                       // 1..4 -> 1..4 bytes
        else if st = 5 then 6
        else if st = 6 or st = 7 then 8
        else if st >= 12 then Number.IntegerDivide(st - 12, 2)
        else error Error.Record("DataFormat.Error",
                 "Reserved SQLite serial type " & Number.ToText(st), null),

    // Serial types 0-9 are the fixed-width scalars. Indexing a hoisted list of
    // readers dispatches in one step; the old if-chain made text and blob — the
    // common case in most databases — fall through all ten comparisons first.
    ScalarReaders = {
        (p, o) => null,                                                       //  0  NULL
        (p, o) => let u = ReadByte(p, o) in if u >= 128 then u - 256 else u,  //  1  int8
        (p, o) => Int16BEFormat(Slice(p, o, 2)),                              //  2  int16
        (p, o) => Int3BE(Slice(p, o, 3)),                                     //  3  int24
        (p, o) => Int32BEFormat(Slice(p, o, 4)),                              //  4  int32
        (p, o) => Int6BE(Slice(p, o, 6)),                                     //  5  int48
        (p, o) => Int64BEFormat(Slice(p, o, 8)),                              //  6  int64
        (p, o) => Float64BEFormat(Slice(p, o, 8)),                            //  7  IEEE 754
        (p, o) => 0,                                                          //  8  constant 0
        (p, o) => 1                                                           //  9  constant 1
    },

    DecodeValue = (payload as binary, off as number, st as number) as any =>
        if st < 10 then ScalarReaders{st}(payload, off)
        else if st < 12 then
            error Error.Record("DataFormat.Error",
                "Reserved SQLite serial type " & Number.ToText(st), null)
        else if Number.Mod(st, 2) = 0 then Slice(payload, off, SerialSize(st))       // blob
        else Text.FromBinary(Slice(payload, off, SerialSize(st)), Enc),              // text

    // The `acc & {x}` appends below are O(cols^2) per row. Deliberately left that
    // way: converting this walk to a List.Generate cursor was measured twice (2026-
    // 07-22, and again on 2026-08-06) and regressed, because List.Generate pays two
    // closure calls and two state-record allocations per column on every row, and
    // returns a lazy list that then has to be buffered before the INTEGER PRIMARY
    // KEY fixup can index it. At realistic column counts that constant factor costs
    // more than the quadratic term it removes. Revisit only for genuinely wide
    // tables, and only with a wide fixture to measure against.
    DecodeRecord = (payload as binary) as list =>
        let
            hv   = VarintAt(payload, 0),
            hlen = hv[Value],
            readTypes = (o as number, acc as list) as list =>
                if o >= hlen then acc
                else let v = VarintAt(payload, o)
                     in @readTypes(o + v[Size], acc & {v[Value]}),
            stypes = readTypes(hv[Size], {}),
            ends   = List.Accumulate(stypes, {hlen}, (s, t) => s & {List.Last(s) + SerialSize(t)}),
            starts = List.RemoveLastN(ends, 1)
        in
            List.Transform(List.Positions(stypes),
                (i) => DecodeValue(payload, starts{i}, stypes{i})),

    //==================== CREATE TABLE parsing (best effort) ====================
    // returns [Columns = list of text, IpkIndex = nullable number]
    ParseColumns = (sql as text) as record =>
        let
            openPos  = Text.PositionOf(sql, "("),
            closePos = Text.PositionOf(sql, ")", Occurrence.Last),
            inner    = Text.Range(sql, openPos + 1, closePos - openPos - 1),
            chars    = Text.ToList(inner),
            walked = List.Accumulate(chars,
                [depth = 0, q = null, cur = "", parts = {}],
                (s, c) =>
                    if s[q] <> null then
                        [depth = s[depth], q = (if c = s[q] then null else s[q]),
                         cur = s[cur] & c, parts = s[parts]]
                    else if c = """" or c = "'" or c = "`" then
                        [depth = s[depth], q = c, cur = s[cur] & c, parts = s[parts]]
                    else if c = "[" then
                        [depth = s[depth], q = "]", cur = s[cur] & c, parts = s[parts]]
                    else if c = "(" then
                        [depth = s[depth] + 1, q = null, cur = s[cur] & c, parts = s[parts]]
                    else if c = ")" then
                        [depth = s[depth] - 1, q = null, cur = s[cur] & c, parts = s[parts]]
                    else if c = "," and s[depth] = 0 then
                        [depth = 0, q = null, cur = "", parts = s[parts] & {s[cur]}]
                    else
                        [depth = s[depth], q = null, cur = s[cur] & c, parts = s[parts]]),
            rawParts = walked[parts] & {walked[cur]},
            norm = (t as text) as text =>
                Text.Trim(Text.Replace(Text.Replace(Text.Replace(t,
                    "#(tab)", " "), "#(cr)", " "), "#(lf)", " ")),
            FirstIdent = (t0 as text) as text =>
                let t = norm(t0),
                    c0 = Text.Start(t, 1)
                in  if c0 = """" or c0 = "'" or c0 = "`" then
                        Text.Range(t, 1, Text.PositionOf(Text.Range(t, 1), c0))
                    else if c0 = "[" then
                        Text.Range(t, 1, Text.PositionOf(t, "]") - 1)
                    else
                        Text.Split(t, " "){0},
            constraintKw = {"PRIMARY", "UNIQUE", "CHECK", "FOREIGN", "CONSTRAINT"},
            colParts = List.Select(rawParts,
                (p) => not List.Contains(constraintKw, Text.Upper(FirstIdent(p)))),
            cols = List.Transform(colParts, FirstIdent),
            ipkCandidates = List.Select(List.Positions(colParts),
                (i) => let u = Text.Upper(norm(colParts{i}))
                       in  Text.Contains(u, "INTEGER") and Text.Contains(u, "PRIMARY KEY")),
            ipk = if List.Count(ipkCandidates) = 1 then ipkCandidates{0} else null
        in
            [Columns = cols, IpkIndex = ipk],

    //==================== table materialization ====================
    DecodeTable = (rootPage as number, sql as text) as table =>
        let
            parsed = ParseColumns(sql),
            cols   = parsed[Columns],
            ipk    = parsed[IpkIndex],
            ncols  = List.Count(cols),
            cells0 = CollectCells(rootPage),
            cells  = if OptMaxRows = null then cells0 else List.FirstN(cells0, OptMaxRows),
            rows = List.Transform(cells, (c) =>
                let
                    vals   = DecodeRecord(c[Payload]),
                    padded = vals &
                             List.Repeat({null}, List.Max({0, ncols - List.Count(vals)})),
                    fixed  = if ipk = null then padded
                             else List.Transform(List.Positions(padded),
                                     (i) => if i = ipk and padded{i} = null
                                            then c[Rowid] else padded{i})
                in fixed),
            result = try Table.FromRows(rows, cols)
                     otherwise Table.FromRows(rows)   // schema-parse mismatch fallback
        in
            result,

    //==================== sqlite_master / navigation ====================
    masterCells = CollectCells(1),
    masterRows  = List.Transform(masterCells, (c) => DecodeRecord(c[Payload])),
    master      = Table.FromRows(
                      List.Transform(masterRows,
                          (r) => r & List.Repeat({null}, List.Max({0, 5 - List.Count(r)}))),
                      {"type", "name", "tbl_name", "rootpage", "sql"}),

    userTables = Table.SelectRows(master,
        each [type] = "table" and not Text.StartsWith([name], "sqlite_")),

    nav0 = Table.AddColumn(userTables, "Data", each
        let rp = [rootpage], sq = [sql] in
        if rp = null or rp = 0 then
            error Error.Record("DataFormat.Error", "Virtual table — no b-tree storage", [name])
        else if Text.Contains(Text.Upper(sq), "WITHOUT ROWID") then
            error Error.Record("DataFormat.Error", "WITHOUT ROWID tables are not supported", [name])
        else DecodeTable(rp, sq),
        type table),

    nav = Table.SelectColumns(
              Table.RenameColumns(nav0, {{"name", "Name"}, {"rootpage", "RootPage"}, {"sql", "SQL"}}),
              {"Name", "RootPage", "SQL", "Data"})
              meta [
                  Sqlite3.PageSize   = PageSize,
                  Sqlite3.Encoding   = EncodingId,
                  Sqlite3.WalMode    = (WriteVer = 2)   // true => a -wal file may hold newer data
              ]
in
    nav