nukep/llamadb

[Not maintained] A SQL database written in Rust

LlamaDB

Fair warning: this project is not maintained.

Do not use this for anything important, like... for anything. This is a database I wrote for the fun of it. It will never be production-ready.

LlamaDB is a simple SQL database, written entirely in the Rust programming language.

Building

LlamaDB is built using the nightly builds of Rust and Cargo. For installation instructions, go to http://www.rust-lang.org.

To use the CLI, navigate to the cli/ directory and run cargo run. You'll be greeted by the friendly llamadb> prompt, with whom you can enter SQL queries. To exit the CLI, press Ctrl+D.

Examples, Features and TODO

For a quick rundown of implemented features, see the Usage guide.

See the issue tracker for unimplemented features and bugs: https://github.com/nukep/llamadb/issues

About

I started this mostly as a learning project so that I could learn SQL and its implementation details better. This project may or may not go anywhere; we'll just have to see.

The other reason I started this was to see how the Rust programming language could be used to write large projects such as SQL databases. So far, I think it's working out fairly well. :)

Special thanks

A HUGE THANKS goes out to SQLite and the SQLite documentation. Their wonderful docs helped shed some light on the SQL syntax and other crucial details such as their B-Tree implementation.

llamadb's Issues

JOIN syntax

• INNER JOIN
• LEFT JOIN
• RIGHT JOIN
• FULL OUTER JOIN

INNER JOIN can currently be emulated with a traditional Cartesian + WHERE join.
It would be nice to allow for the INNER JOIN syntax as an alternative for those who prefer it (such as myself!).

OUTER JOIN cannot currently be emulated. The only way to get an outer join is to implement the syntax.

Join tables using indices

Currently, all joins are executed using nested scans. This can obviously be bad for performance.

This would need to be implemented at the query compiler at the optimization stage.

Can't paste multi-line statements into CLI

This is a rather frustrating bug/limitation for those of us who like to copy and paste multi-lined text into the CLI. If a multi-line string is pasted, only the first line will be inputted.

rust-linenoise is used to drive the CLI input. Enabling multi-line mode with linenoise::set_multiline(1); doesn't seem to have any effect on my machine (64-bit Linux, using gnome-terminal).

INSERT values using expressions

Currently, INSERT only works with simple number or string expressions; it cannot fold expressions into a single variant value.

The goal is to be able to run:

INSERT INTO mytable VALUES (5 * 4, NULL), (0, (SELECT avg(x) FROM othertable));

INSERT using a SELECT query

The goal is to be able to run:

INSERT INTO table_a SELECT count(*), avg(a) FROM table_b GROUP BY category;

ORDER BY

Aggregate/Scalar functions checklist

List of functions to implement

Aggregate functions

• COUNT(*)
• COUNT
• SUM
• AVG
• GROUP_CONCAT
• MIN
• MAX

Scalar functions

• ABS
• LENGTH
• ROUND
• FLOOR
• CEIL
• TRUNC
• TYPEOF

Auto-incrementing columns

The goal is to be able to run:

CREATE TABLE mytable (
  id U32 INC,
  name VARCHAR
);

INSERT INTO mytable (name) VALUES ('Alex'), ('Bob'), ('Caroline');

SELECT * FROM mytable;
/*
-----------------
| id | name     |
-----------------
| 0  | Alex     |
| 1  | Bob      |
| 2  | Caroline |
-----------------
*/

Aliases for INC: AUTOINCREMENT

Implement B+Tree and file pager, remove tempdb

Rust's data structures obviously can't be committed to disk, so a cache-friendly file format should be implemented.

SELECT without FROM

It'd be useful for simple logic tests and fiddling:

SELECT 'Hello' || 'World' AS message, 5 * '6';
/*
-------------------
| message    | _0 |
-------------------
| HelloWorld | 30 |
-------------------
*/

I'm electing not to use dummy tables like DUAL. :)

Default column values should be made explicit

Columns should only be able to be omitted from INSERT if the column:

• is auto-incrementing, or
• has the DEFAULT constraint, with a provided default value

Build failed, during cargo run

thread 'rustc' panicked at 'Trying to convert unsized value to lval', /build/rust/src/rustc-1.0.0-alpha.2/src/librustc_trans/trans/datum.rs:495

Remove all unimplemented!() stubs

These are in place until their features are complete.

Put on crates.io, make the API stable enough to use as a standalone library

I don't feel that LlamaDB is at a point where it can serve as a standalone library yet. The library crate is currently a bunch of hacks that expose internals such as parser modules.

This issue needs to wait on #4 so that developers have a somewhat reasonable API to work with, as well as a file-based DB. tempdb won't be around for long!

Until then, the llamadb crate has been reserved on crates.io.

---

Nice-to-haves for the library:

• A sql!() macro that statically validates and compiles the SQL query (to an extent).
  • This may be hard to do without schema information.
  • At least have it validate the syntax, possibly compile into AST?
• A C API, for use by other programming languages.

Add an optimizer to the query compiler

Optimize away redundant temp-group-by's

SELECT avg(milliseconds) FROM track;

currently compiles into:

(temp-group-by :source_id 1
  (scan `track` :source_id 0
    (yield
      (column-field :source_id 0 :column_offset 0)
      (column-field :source_id 0 :column_offset 1)
      (column-field :source_id 0 :column_offset 2)
      (column-field :source_id 0 :column_offset 3)
      (column-field :source_id 0 :column_offset 4)
      (column-field :source_id 0 :column_offset 5)
      (column-field :source_id 0 :column_offset 6)
      (column-field :source_id 0 :column_offset 7)
      (column-field :source_id 0 :column_offset 8)))
  (group-by-values)
  (yield
    (avg :source_id 1 
      (column-field :source_id 1 :column_offset 6))))

---

The temp-group-by creates a redundant temporary group, when simply using the table's group could suffice. This could be done with a new scan-group function or similar.

(scan-group `track` :source_id 0
  (yield
    (avg :source_id 0
      (column-field :source_id 0 :column_offset 6))))

Column/Table constraints checklist

• NULL
• PRIMARY KEY
• FOREIGN KEY
• UNIQUE
• CHECK
• DEFAULT

cli: column reported ambiguous when it doesn't exist

llamadb> create table sup(id int);
Created (0.000s).
llamadb> select b from sup;
execution error: ambiguous column name: b

Column types checklist

• STRING
  • A variable-length UTF-8 string.
  • Alias: VARCHAR
• Ux, where x is >= 8 and <= 64, and is a multiple 8.
  • An unsigned integer.
• Ix, where x is >= 8 and <= 64, and is a multiple 8.
  • An signed integer.
  • Alias for I32: INT or INTEGER
• F64
  • A double-precision (64-bit) floating point number.
  • Alias: DOUBLE
• byte[]
  • A variable-length byte array.
• byte[N]
  • A fixed-length byte array.
• UUID
  • A universally unique identifier.
• JSON
  • A JSON document, encoded using MessagePack.
• BCRYPT
• SCRYPT
• PBKDF2

SQL logic test suite

To guarantee that SQL queries actually do as they're told, a very thorough test suite needs to be added.

Sqllogictest may be worth looking into: https://www.sqlite.org/sqllogictest/doc/trunk/about.wiki

UPDATE and DELETE

Expressions checklist

• Numbers
• Strings
• NULL
• Byte arrays
• Subqueries
• Aggregate function calls
• Scalar function calls
• Binary comparison: =, <>, <, <=, >, >=
• Binary arithmetic: +, -, *, /
• Unary -
• AND
• OR
• NOT
• ||
• EXISTS
• BETWEEN ... AND
• IN
• CASE
• IS NULL
• IS NOT NULL
• LIKE