dborchard/tiny-db

Tiny Database: Query Engine, Storage Engine, Calcite, ANTLR

TinyDB

A tiny database that supports Btree Index, Planner and Parser.

Sample Queries

• Without Index

create table T1 ( A int, B varchar(9) );
insert into T1 (A, B) values (1, 'Alice');
insert into T1 (A, B) values (2, 'Bob');
select A,B from T1;
select A,B from T1 where A=1;

Output

>
+---+-------+
| a | b     |
+---+-------+
| 1 | Alice |
| 2 | Bob   |
+---+-------+
>
+---+-------+
| a | b     |
+---+-------+
| 1 | Alice |
+---+-------+

• With Index

create table T2 ( A int, B varchar(9) );
create index A_IDX on T2(A);
insert into T2 (A, B) values (1, 'Alice');
insert into T2 (A, B) values (2, 'Bob');
select A,B from T2;
select A,B from T2 where A=1;

>
+---+-------+
| a | b     |
+---+-------+
| 1 | Alice |
| 2 | Bob   |
+---+-------+

> index on a used
+---+-------+
| a | b     |
+---+-------+
| 1 | Alice |
+---+-------+

NOTE: Delete the tinydb data directory to start fresh.

Features

• Frontend

  • Naive Parser
  • ANTLR MySQL Parser (Apache ShardingSphere Parser Library)

• Query Engine

  • Basic Query Engine (Supporting Projection, Selection etc)
  • Rule Based Planners (use BTree Index if available on that field)
  • Calcite backed Query Engine (Currently supports ScannableTable and not ModifiableTable)
  • Calcite Optimizer [Todo]

• Index

  • Naive B+Tree Index
  • Library backed B+Tree Index (davidmoten bplustree library, Delete not supported by library)

• Storage Engine

  • File Manager, Block, Page

• CLI interface

TODO

• Recovery Manager (WAL)
• Transactions
• Concurrency Manager
• Buffer Manager

Notes

This work is a derived from SimpleDB

Current Limitations

• Not implemented Primary Key, Unique Key etc.
• If we create index after the data is inserted, there is some anomaly.
• Currently only supports Varchar, int.

tiny-db's Issues

BplusTree Key's are not generic

In ConstantSerializer we are assuming Index as Integer. We need to modify that logic to be generic enough for Constant class.

public class ConstantSerializer implements Serializer<D_Constant> {

  @Override
  public D_Constant read(LargeByteBuffer bb) {
    int ival = bb.getInt();
    return new D_Constant(ival);
  }

UPDATE Table having invalid ANTLR Parser logic

There is an issue with the "where" condition for ANTLR Parser implementation.

tinysql> select A,B from T2;
+---+---------+
| A | B       |
+---+---------+
| 1 | 'Alice' |
| 2 | 'Bob'   |
+---+---------+

tinysql> update T2 SET A=1 where A=2;
1 row updated.
tinysql> select A,B from T2;
+---+---------+
| A | B       |
+---+---------+
| 1 | 'Alice' |
| 2 | 'Bob'   |
+---+---------+