5 ms·

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 a

by geedy 11y ago

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 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.pdf 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!

krashidov 11y ago
How did you learn to write a database from scratch? What books, courses, tutorials do you recommend?
- geedy 11y ago
  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.
- gburt 11y ago
  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.html 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-Garcia-Molina/dp/0130402648 http://www.amazon.ca/Database-System-Implementation-Hector-G... http://infolab.stanford.edu/~ullman/dbsi.html http://infolab.stanford.edu/~ullman/dbsi.html
nerfhammer 11y ago
Add more usage examples! Or even a tutorial. :)
- geedy 11y ago
  I know I absolutely could make that README a lot better, and add an example set of code.
Alupis 11y ago
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.
- geedy 11y ago
  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.
niutech 11y ago
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]?
- geedy 11y ago
  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!
- schrodinger 11y ago
  Binary trees are log(n), not n*log(n)
  - niutech 11y ago
    You're right. n*log(n) is for building the BST in Tree sort.
israrkhan 11y ago
How does this implementation compares to sqlite?
- geedy 11y ago
  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.

by geedy 11y ago

krashidov 11y ago

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

geedy 11y ago
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.
gburt 11y ago
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.html 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-Garcia-Molina/dp/0130402648 http://www.amazon.ca/Database-System-Implementation-Hector-G... http://infolab.stanford.edu/~ullman/dbsi.html http://infolab.stanford.edu/~ullman/dbsi.html

nerfhammer 11y ago

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

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

Alupis 11y ago

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.

geedy 11y ago
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.

niutech 11y ago

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]?

geedy 11y ago
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!
schrodinger 11y ago
Binary trees are log(n), not n*log(n)
- niutech 11y ago
  You're right. n*log(n) is for building the BST in Tree sort.

israrkhan 11y ago

How does this implementation compares to sqlite?

geedy 11y ago
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.