Skip to content
flixPublic

About

No description, website, or topics provided.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Latest commit

 

History

19 Commits

Folders and files

Repository files navigation

🤡 sqlslop 🤡

Warning: this is an AI SLOP project purely intended to benchmark the Flix compiler. It is NOT intended to actually be used for anything.

A read-only SQLite 3 engine written in pure Flix (0.79.0), no Java interop. It opens unmodified SQLite database files; the goal is to run SELECT queries against them. See PLAN.md for the architecture and milestones.

Status

Milestone State
M0 Bytes decoders, fixture generator done
M1 Header, Pager effect and handlers, sqlslop info done
M2 Record, table b-tree scan (leaf and interior pages), sqlite_schema, tables/schema commands done
M3 overflow chains, rowid seek, page cache in the CLI done
M4 SQL lexer/parser for SELECT and CREATE TABLE/INDEX, column binding (affinity, rowid alias) done
M5 Eval + Exec: single-table SELECT with WHERE, ORDER BY, LIMIT/OFFSET, scalar functions; golden tests vs Python done
M6 aggregates, GROUP BY/HAVING, DISTINCT, inner/left/cross nested-loop joins done
M7 index b-trees: seeks for equality prefixes and ranges, planner picks them, explain done
M8 CLI: REPL with dot-commands, `--format=table csv
M9 derived tables FROM (SELECT …), views, JOIN … USING, NATURAL JOIN done
M10 subqueries in expressions: IN (SELECT …), EXISTS, scalar, uncorrelated and correlated done
M11 compound SELECT (UNION [ALL], INTERSECT, EXCEPT), VALUES, RIGHT/FULL OUTER JOIN done
M12 common table expressions and WITH RECURSIVE done
M13 GLOB, collations (NOCASE/RTRIM, index seeks included), NULLS FIRST/LAST, IS DISTINCT FROM, printf, iif, date/time functions done
M14 window functions: ranking, lag/lead, first/last/nth_value, aggregates over PARTITION BY … ORDER BY … with ROWS/RANGE frames, named windows done
M15 WITHOUT ROWID tables, covering indexes, ORDER BY through an index, LIKE/GLOB prefix ranges done
M16 hash joins, LIMIT early termination, join reordering, a second golden database next

Usage

Build once with java -jar flix.jar build-jar to get artifact/sqlslop.jar, or run from source with java -jar flix.jar run -- <args> as below.

Interactive session

$ java -jar flix.jar run -- test/fixtures/Chinook_Sqlite.sqlite
sqlslop> .tables
Album
Artist
Customer
Employee
Genre
Invoice
InvoiceLine
MediaType
Playlist
PlaylistTrack
Track
sqlslop> SELECT ArtistId, Name FROM Artist
    ...>   WHERE Name LIKE '%jobim%' ORDER BY ArtistId;
ArtistId  Name
--------  --------------------
46        Antônio Carlos Jobim
sqlslop> .explain SELECT * FROM Track WHERE AlbumId = 1
    SEARCH Track USING INDEX IFK_TrackAlbumId (AlbumId=?)
  FILTER
PROJECT 9 columns
sqlslop> .format csv
sqlslop> SELECT COUNT(*) AS n FROM PlaylistTrack WHERE PlaylistId = 1;
n
3290
sqlslop> SELECT Name FORM Artist;
Error: parse error: unexpected 'Artist'
  SELECT Name FORM Artist;
                   ^
sqlslop> .quit

A statement ends at a line ending in ;. Dot-commands: .tables, .indexes [table], .schema [table], .explain <sql>, .format table|csv|json (also .mode), .help, .quit; end of input also quits.

One-shot queries and formats

java -jar flix.jar run -- --format=json test/fixtures/Chinook_Sqlite.sqlite "SELECT g.Name AS genre, COUNT(*) AS tracks FROM Track t JOIN Genre g ON g.GenreId = t.GenreId GROUP BY g.GenreId ORDER BY tracks DESC LIMIT 3"
[{"genre":"Rock","tracks":1297},
{"genre":"Latin","tracks":579},
{"genre":"Metal","tracks":374}]

--format=csv writes a header line and quotes fields that need it; --format=table (the default) aligns columns and shows NULL as empty. In JSON, blobs become hex strings. A failed statement prints the error with its position to stderr and exits with status 1.

Inspecting a file

java -jar flix.jar run -- info test/fixtures/Chinook_Sqlite.sqlite
file                 test/fixtures/Chinook_Sqlite.sqlite
file size            1067008 bytes
page size            1024
reserved bytes/page  0
usable bytes/page    1024
page count           1042
freelist pages       199
freelist trunk page  8
text encoding        UTF-8
file format          write 1 / read 1 (rollback journal)
schema cookie        64
schema format        4
user version         0
application id       0
change counter       31278
auto vacuum          none
default cache size   0
written by sqlite    3.36.0
java -jar flix.jar run -- test/fixtures/Chinook_Sqlite.sqlite "SELECT TrackId, Name, UnitPrice FROM Track WHERE AlbumId = 1 ORDER BY TrackId LIMIT 3"
TrackId  Name                                     UnitPrice
-------  ---------------------------------------  ---------
1        For Those About To Rock (We Salute You)  0.99
6        Put The Finger On You                    0.99
7        Let's Get It Up                          0.99
java -jar flix.jar run -- tables test/fixtures/Chinook_Sqlite.sqlite   # one table name per line, sorted
java -jar flix.jar run -- schema test/fixtures/Chinook_Sqlite.sqlite   # every CREATE statement
java -jar flix.jar run -- schema test/fixtures/Chinook_Sqlite.sqlite Album
java -jar flix.jar run -- explain test/fixtures/Chinook_Sqlite.sqlite "SELECT * FROM Album al JOIN Track t ON t.AlbumId = al.AlbumId WHERE al.ArtistId = 1"
    SEARCH Album USING INDEX IFK_AlbumArtistId (ArtistId=?)
  INNER JOIN SEARCH Track USING INDEX IFK_TrackAlbumId (AlbumId=?)
PROJECT 12 columns
CREATE TABLE [Album]
(
    [AlbumId] INTEGER  NOT NULL,
    [Title] NVARCHAR(160)  NOT NULL,
    [ArtistId] INTEGER  NOT NULL,
    CONSTRAINT [PK_Album] PRIMARY KEY  ([AlbumId]),
    FOREIGN KEY ([ArtistId]) REFERENCES [Artist] ([ArtistId])
		ON DELETE NO ACTION ON UPDATE NO ACTION
);
CREATE INDEX [IFK_AlbumArtistId] ON [Album] ([ArtistId]);

Exit status is 1 when the database cannot be opened or a one-shot statement fails, and 2 for bad arguments. Only UTF-8 databases are accepted; UTF-16 files are rejected with a clear error.

Layout

src/SqlSlop.flix            parent module, version string
src/SqlSlop/SqlError.flix   SqlError enum: Io | Corrupt | Unsupported | Parse | Runtime
src/SqlSlop/Fail.flix       eff Fail { fail(e: SqlError): Void } and Fail.toResult
src/SqlSlop/Bytes.flix      big-endian ints, SQLite varints, IEEE 754 binary64 (pure Flix)
src/SqlSlop/Header.flix     the 100-byte database header
src/SqlSlop/Pager.flix      eff Pager { header(), page(n) }; runWithBytes, runWithFileRead,
                            withCache and withCounting middleware
src/SqlSlop/Value.flix      Value enum: Null | Integer | Real | Text | Blob
src/SqlSlop/Emit.flix       eff Emit[t] { emit(x) } with collect/count handlers
src/SqlSlop/Record.flix     record format (serial types) -> Vector[Value]
src/SqlSlop/BTree.flix      page headers, cells, overflow chains, tableScan(root) emitting
                            (rowid, payload), tableSeek(root, rowid) by binary search,
                            forEachIndexEntry(root, lower, upper) pruned in-order walk of an index
src/SqlSlop/Schema.flix     sqlite_schema entries; tableInfo/indexInfo bind columns, affinity, rowid alias
src/SqlSlop/Sql.flix        reserved words
src/SqlSlop/Sql/Token.flix  tokens with positions
src/SqlSlop/Sql/Lexer.flix  tokenizer: words, quoted identifiers ("x", `x`, [x]), numbers, 'strings', X'blobs', comments
src/SqlSlop/Sql/Ast.flix    expressions, SELECT, CREATE TABLE/INDEX, and a canonical printer
src/SqlSlop/Sql/Cursor.flix eff Cursor { peek, peekAt, position, advance } for the parser state
src/SqlSlop/Sql/Parser.flix recursive-descent parser with SQLite's precedence; errors carry positions
src/SqlSlop/Eval.flix       value semantics: storage-class order, 3-valued logic, affinity, arithmetic
                            with overflow-to-real, %!.15g real formatting, LIKE, scalar functions
src/SqlSlop/Plan.flix       binder and planner: names -> row slots across joined tables, WHERE pushdown,
                            access path per table (rowid seek, index range, scan), aggregate calls -> slots,
                            explain
src/SqlSlop/Exec.flix       push-based operators over Emit[Row]: Scan, Lookup, Filter, NestedLoop,
                            Aggregate, Sort, Project, Distinct, Limit
tools/golden.py             runs tools/golden_queries.txt through Python's sqlite3 -> test/golden/chinook.json
src/SqlSlop/Cli.flix        command line: REPL, dot-commands, table/csv/json output
src/Main.flix               entry point
tools/mkfixtures.py         generates test/Fixtures.flix and test/fixtures/pagesize64k.db
tools/fetch_chinook.sh      re-downloads the Chinook reference database and checks its SHA-256
test/                       @Test suites and fixtures

Code above the pager never touches the file: it performs Pager.page(n) and a handler decides where the bytes come from. runWithBytes serves pages from an in-memory vector, runWithFileRead loads a file once through the standard FileRead effect, and errors are raised with the Fail effect and turned into a Result at the boundary:

let result = run {
    Pager.header()
} with Pager.runWithFileRead(path)
  with Fail.toResult;

Tests

java -jar flix.jar check
java -jar flix.jar test

The SQL subset that runs: SELECT [DISTINCT] over tables, views and derived tables (SELECT …) AS d, joined with inner, left, right, full and cross joins (ON, USING or NATURAL), combined with UNION [ALL], INTERSECT and EXCEPT, VALUES lists, WHERE, GROUP BY/HAVING with count, sum, total, avg, min, max, group_concat (also DISTINCT inside them), ORDER BY (by expression, alias or column number), LIMIT/OFFSET, the expression grammar below, and the scalar functions length, upper, lower, abs, coalesce, ifnull, nullif, typeof, substr, instr, trim, ltrim, rtrim, round, hex, replace, quote, min, max, iif, sign, unicode, char, printf/format (%d %i %s %f %x %X %% with flags, width and precision) and the date/time functions date, time, datetime, julianday, unixepoch, strftime (formats YYYY-MM-DD[ HH:MM[:SS[.SSS]]], HH:MM[:SS] or a Julian day; modifiers ±N days|hours|minutes|seconds|months|years, start of day|month|year, weekday N, unixepoch; no now, no time zones). Comparisons, ORDER BY and GROUP BY honour COLLATE BINARY|NOCASE|RTRIM, explicit or from the column, and an index with a matching collation serves the seek. WHERE conjuncts are pushed to the earliest table they can be evaluated at. Access paths, chosen per table: rowid = k is a table b-tree seek; an equality prefix of an index's columns plus an optional </<=/>/>=/BETWEEN range on the next column is an index range walk followed by a rowid seek per hit, or by no seek at all when the index holds every column the query reads (USING COVERING INDEX); LIKE 'prefix%' on a NOCASE index and GLOB 'prefix*' on a BINARY one become ranges; an ORDER BY that matches the access path's own order (rowid order for a scan, index order after the equality prefix, primary-key order for a WITHOUT ROWID table) needs no sort. WITHOUT ROWID tables are read from their primary-key b-tree and their secondary indexes carry the key. Automatic PRIMARY KEY indexes are used; only non-partial, ascending indexes with BINARY, NOCASE or RTRIM collations are considered. Anything else is a scan, and joins without a usable key materialise the right table once. sqlslop explain shows the choice. Subqueries in expressions may refer to the enclosing queries' columns; uncorrelated ones are evaluated once, correlated ones per row, with the inner table reached through an index when the correlation allows. The full grammar:

[WITH [RECURSIVE] name [(cols)] AS (SELECT ...), ...]
SELECT [DISTINCT] cols FROM src [AS a] {[NATURAL] [LEFT|RIGHT|FULL|INNER|CROSS] JOIN src [ON e | USING (c, ...)] | , src}
{UNION [ALL] | INTERSECT | EXCEPT} SELECT ...      (ORDER BY / LIMIT apply to the whole)
VALUES (e, ...), (e, ...)                          (columns column1, column2, ...)
src: table | view | cte | (SELECT ...) | (VALUES ...)
A recursive CTE is `initial-select UNION [ALL] step-select` where the step names
the CTE; rows are produced breadth-first from a queue. A LIMIT on the body stops
it; without one, a million rows is an error rather than a hang.
[WHERE e] [GROUP BY e, ...] [HAVING e] [ORDER BY e [ASC|DESC], ...] [LIMIT n [OFFSET m]]
e: literals, t.c, unary - + NOT, || * / % + - < <= > >= = != IS [NOT] AND OR,
   IS [NOT] NULL, IS [NOT] DISTINCT FROM, [NOT] IN (...), [NOT] IN (SELECT ...),
   [NOT] EXISTS (SELECT ...), (SELECT ...) as a scalar, [NOT] LIKE p [ESCAPE c],
   [NOT] GLOB p, [NOT] BETWEEN a AND b, e COLLATE name, CASE, CAST(e AS type),
   f(args), count(*)
ORDER BY e [ASC|DESC] [NULLS FIRST|LAST]
f(args) OVER ([name] [PARTITION BY e, ...] [ORDER BY terms] [ROWS|RANGE BETWEEN b AND b])
   with row_number, rank, dense_rank, percent_rank, cume_dist, ntile, lag, lead,
   first_value, last_value, nth_value and the aggregates; WINDOW name AS (...)
   after HAVING; RANGE frames take only UNBOUNDED and CURRENT ROW bounds
CREATE TABLE with inline and table-level constraints (FOREIGN KEY, CHECK, DEFAULT,
   COLLATE, ON CONFLICT clauses are parsed and ignored), WITHOUT ROWID detected
CREATE [UNIQUE] INDEX ... ON t (cols) [WHERE e]
CREATE VIEW v [(cols)] AS SELECT ...

Three kinds of tests:

  • Hermetic unit tests over hex-embedded databases from tools/mkfixtures.py (Python's built-in sqlite3), which also records the PRAGMA values the Flix code must reproduce, plus IEEE 754 and varint vectors. The tiny fixture's five rows cover every storage class; overflow has a row that needs overflow pages; freelist has a dropped table.
  • Files under test/fixtures/ read through FileRead: pagesize64k.db for 65536-byte pages and large.db with 10 000 rows across interior pages and a 100 kB blob in an overflow chain.
  • The unmodified Chinook database (test/fixtures/Chinook_Sqlite.sqlite, MIT, from lerocha/chinook-database v1.4.5), a file written by SQLite itself with freelist pages, autoindexes and table-level constraints.
  • Differential golden tests: every query in tools/golden_queries.txt is run by Python's sqlite3 (python3 tools/golden.py writes test/golden/chinook.json) and the engine must reproduce the column names and every row bit-exactly, reals included. Adding a query is one line in that file.

Regenerate fixtures with python3 tools/mkfixtures.py from the repository root. The whole suite, golden queries included, runs in well under a minute on the 1 MB Chinook file (about 45 s on a laptop, most of it the 110 golden queries); CI runs check and test on every push.

About

No description, website, or topics provided.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages