Hacker News Reader

Comment by geedy | Hacker News Reader

I am the author of LittleD.

I am more than happy to answer any questions. It has mostly been an academic project while I was doing during my undergrad, but I am now looking at continuing the project as part of a Ph.D. Of course, I would love to coordinate a broader development of this project. :)

You may also be interested in another project I and some lab mates have been working on over the last couple of years, IonDB: https://github.com/iondbproject/iondb.

EDIT: You might also be interested in the initial paper, which can be found here: https://people.ok.ubc.ca/rlawrenc/research/Papers/LittleD.pd...

I investigated query precompilation in another paper I am waiting to here back on, and once everything has been a little better tested, that code will get pushed out as well. :)

And seriously, if anybody is interested in contributing, I would love to have some help. Get in contact with me!

View on HN

How did you learn to write a database from scratch? What books, courses, tutorials do you recommend?

I took a computer science course at the University of British Columbia's Okanagan campus called COSC404 under Professor Ramon Lawrence (who is/was also my research supervisor at UBC), which was on database implementation. It was here that I learned most of the material.

I took the same course @geedy is speaking of (with him, in fact) and there are two good comparable resources I'm aware of:

(1) Ramon's (excellent!) lecture notes themselves are currently (but not always) available on his website: https://people.ok.ubc.ca/rlawrenc/teaching/404/notes/index.h...

(2) Garcia-Molina, Ullman and Widom's book and courses taught on their work: http://www.amazon.ca/Database-System-Implementation-Hector-G... http://infolab.stanford.edu/~ullman/dbsi.html

Any reason you targeted "IoT" devices specifically? If it's a good DB, and has a small footprint, I'm sure more than just "IoT" devs will take interest.

I did not target "IoT" specifically if I am honest. Its one of the use cases I envision. But sensors and motes would could find just as much use, or anything having to collect and store data to make decisions with over time.

What is the computational complexity of looking up, adding and deleting a single row?

Is it comparable with binary trees [O(n log n)] and hashtables [O(1) on average]?

That is one area LittleD needs some improvement. We only support CREATE TABLE, INSERT, SELECT right now. O(1) for inserts because we only append.

That said, IonDB was in part motivated to be a storage engine for LittleD. Then you basically get exactly what you described: your choice of underlying dictionary data-structure for the performance characteristics you need. It will also make UPDATE/DELETE a breeze, once we incorporate the two code-bases!

Binary trees are log(n), not n*log(n)

You're right. n*log(n) is for building the BST in Tree sort.

How does this implementation compares to sqlite?

SQLite has many more features. It has more types, more functions, more SQL support. It also requires significantly more resources; they claim 100KiB of heap space and 4KiB of stack space with at least 300KiB of compiled code, stripped as small as possible. I don't know what this means.

LittleD gives you the bare basics, using well under 100K of compiled code, and under 1K of RAM for average queries, period. You will soon be able to strip out the query translator and "precompile" your queries with parameters to bring the total compiled code down to under 35K on device. This is not always desirable, but in some cases can be very useful.

Add more usage examples! Or even a tutorial. :)

I know I absolutely could make that README a lot better, and add an example set of code.

Reply on news.ycombinator.com