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.
| 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 |
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.
$ 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.
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.
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.
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;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-insqlite3), which also records thePRAGMAvalues the Flix code must reproduce, plus IEEE 754 and varint vectors. Thetinyfixture's five rows cover every storage class;overflowhas a row that needs overflow pages;freelisthas a dropped table. - Files under
test/fixtures/read throughFileRead:pagesize64k.dbfor 65536-byte pages andlarge.dbwith 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, fromlerocha/chinook-databasev1.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.txtis run by Python'ssqlite3(python3 tools/golden.pywritestest/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.