systemxlabs/bustubx

[WIP] A relational database written in Rust for educational purpose, heavily inspired by cmu-db/bustub. (CMU 15-445).

bustubx's Issues

Support subquery sql

maybe we can consider adding some bench tests?

Add hash join executor

Pushdown limit rule

Index nested loop join

https://zhenghe.gitbook.io/open-courses/cmu-15-445-645-database-systems/join-algorithms#index-nested-loop-join

Combine operators rule

Support order by sql

Direct IO

We should use direct io to avoid os cache which is duplicated with buffer pool.
https://users.rust-lang.org/t/how-does-rust-use-directio/93210/3
https://stackoverflow.com/questions/50879965/does-rusts-standard-library-support-direct-io-file-access

Refactor Vec<u8> with bytes crate

https://github.com/tokio-rs/bytes

Sort merge join

https://zhenghe.gitbook.io/open-courses/cmu-15-445-645-database-systems/join-algorithms#sort-merge-join

why the terminal print debug info?

Refactor optimizer data structure from graph to tree

Now optimizer maintains a graph data structure to store plan nodes, but actually we just use graph as tree. We don't benefit from graph, instead it makes code harder to read.

Support group by sql

Better plan tree printing for debugging

Column pruning rule

Support default value in schema

Support join sql

• binder supports join
• logical plan supports join
• physical plan supports nested loop join
• join executor
• support left/right/full join after null type support added

Improve b+ tree deletion implementation

Maybe we can extract some common methods.

Support delete sql

Support creating index

RBO framework

Pushdown predicates rule

Save and load catalog from disk

Use RAII to unpin page

Introduce tracing to do profiling

https://github.com/tokio-rs/tracing

Support null in tuple format

Now, tuple format is

| column1 bytes | column2 bytes | ... |

We should add null bitmap or something to support null.

Reference:
https://relph1119.github.io/mysql-learning-notes/#/mysql/04-%E4%BB%8E%E4%B8%80%E6%9D%A1%E8%AE%B0%E5%BD%95%E8%AF%B4%E8%B5%B7-InnoDB%E8%AE%B0%E5%BD%95%E7%BB%93%E6%9E%84

Support reusing page after page deallocated

Support update sql

Index concurrency control

Refactor insert sql

refer to https://github.com/cmu-db/bustub/blob/master/src/include/binder/statement/insert_statement.h

Support left/right/full join

This work needs null support.

Introduce criterion.rs and add benchmark test

https://course.rs/test/benchmark.html

Add index scan executor

Refactor column name

Places that use column

1. select_list field in SelectStatement (Binder). eg. select a from t1, select * from t1
2. physical project node output_schema method
3. physical join node output_schema method. eg. select * from t1 cross join t2
4. subquery. eg. select a from (select * from t1)

Introduce the `comfy-table` component to format and display table data

https://crates.io/crates/comfy-table