81

I need to learn how databases work in order to use them more efficiently, and my way of learning is by doing.

I want to create my own database system. I am not referring to creating a pseudo-database that would use query to parse files; this would simply be a filesystem interface with a query language. I am talking about the actual structure of a database engine. And since what I have in mind is neither relational nor document-oriented (it's "node-oriented", if that even exists), I would need any resource to be as abstract and high-level as possible.

So how would I go about creating that? What resources/tutorials/books can I read to understand?

The language does not matter in the slightest. Ideally, the code would be pseudo-code to illustrate the concept, not tied to a particular language, but anything would do. I was not able to find anything on the matter on google (since I am so illiterate on the subject, maybe I am just not entering the right search).

If such resources are not available, then I guess something about how to create a client would at least be a step in the right direction.

Improve this question
23
  • 17
    Why not write a compiler instead? Or even better, your own operating system? If you are really serious about writing your own database, there are a thousand and one open source databases out there: Study their source code, contribute a few patches. Then start thinking of building your own.
    – yannis
    Nov 25, 2011 at 6:20
  • 13
    I knew I was going to get bashed :) As I said, the purpose is to learn. I studied open-source DBs, but their codebase is too huge to get a real grasp; that's why I want to build from the ground up, beginning small and expanding until I get a real feel of how things work. THEN it will be useful for me to deeply study what has been done.
    – Xananax
    Nov 25, 2011 at 6:30
  • 9
    I studied open-source DBs, but their codebase is too huge: If something like redis or flockdb is too huge for you to read, I don't see how you'll cope writing or own database.
    – yannis
    Nov 25, 2011 at 6:37
  • 18
    @YannisRizos In fairness, reading code (imo) is much more difficult than writing it yourself.
    – user41310
    Nov 25, 2011 at 6:44
  • 18
    @Xananax: don't listen to the frogs (crystal-reflections.com/stories/story_73.htm). Do whatever you enjoy and it is not necessary to have an objective to take pleasure in the process.
    – user2567
    Nov 25, 2011 at 9:15

8 Answers 8

Reset to default
82

(it's "node-oriented", if that even exists)

Start here. When dealing with a complex application like a database (even a simple database is a complex application), you should be familiar with the history of the domain and the proper terminology and have at least a very high level idea of the architecture. You could start from the Wikipedia article on Database. Spent a few days reading all the articles on the related concepts and the different database types.

And since what I have in mind is neither relational nor document-oriented

Next, you pick Relational or NoSQl. If you pick NoSQL, you should pick one type of NoSQL. That's extremely important, you won't find any architectural documents that discuss all different database families. It doesn't really matter which one you pick, just pick one and stick with it.

The language does not matter in the slightest.

Yes it does (unfortunately), because after you pick a database family you should start exploring code from open source databases of that family. There are a few generic guidelines on what to look for:

  • Relatively small codebase,
  • Architectural documents or at least a development blog,
  • The database you pick should be close to what's considered generic in the family, it'd be harder to learn from if it's highly specialised.

A few examples that fit:

Get the source, compile it and play around with it. You don't have to submit patches or anything that fancy, just explore the code and make small alterations here and there to see what happens. It's an incremental process, the more you play around with it the easier it'll be to understand what the code does. If the first project you picked seems extremely hard to understand, just move on to the next one.

Another great option would be to concentrate on building an engine for MySQL, as @N.B. suggests in an earlier answer.

If you do reach a point where you are able to do something useful with the codebase, get involved in the project's community, that's the easiest way to find more detailed resources on the concepts involved.

And then, finally, start working on your database. At first you could just write up an extremely scaled down clone of the code you've been exploring. It doesn't have to be original, quite a few great projects started out as clones or forks.

What resources/tutorials/books can I read to understand?

There are quite a few books:

And a few hundred others, plus a myriad of academic papers you could easily trace via Google. You need to define what you want to do first, and then search for a book. Getting involved with a community of fellow database authors will also help you narrow down the list of books and perhaps get a lot better suggestions than the above.

Good luck! I'm expecting a comment with a link to your repository when you're done. And if you're never done, make sure you leave a comment reminding me that I still haven't finished that compiler I started writing in 2001.

Improve this answer
8
  • 6
    this is nice post
    – Chani
    Nov 25, 2011 at 17:23
  • 3
    This is super! Even more coming from you :) I'd like to accept almost each other answer but since I gotta pick one this has to be it. I'm expecting a comment with a link to your repository when you're done: most definitely! Thanks again, to you and everyone else, this was really uplifting.
    – Xananax
    Nov 25, 2011 at 19:49
  • 5
    And for anyone coming here looking for the same answers: I find flockDB to be the best candidate to learn, the codebase is really small, the code very readable (although I don't speak scala) and easy to understand.
    – Xananax
    Nov 25, 2011 at 19:55
  • @Yannis, Btw which of the books you recommend are the ones that you have read?
    – Pacerier
    Nov 2, 2014 at 14:31
  • @Xananax Sooo how is it coming along ? Any repository we can look at ? :)
    – Radu Murzea
    Sep 29, 2016 at 11:19
33

You should just do it and stop thinking too much. Enjoying the learning process and enthousiasm are gifts.

Asking others if it's a good idea is certainly not a good strategy. If I had listened to all the frogs, I would still work at Ikea today pushing shopping cart from the parking to the depot.

You don't have to justify yourself like Ayende did in that interesting post. The question was:

However as a pragmatic developer, I am wondering what new this project is offering in a saturated market where you have quite mature alternatives like CouchDB, MongoDB, Tokyo, Redis, and many more ? Many of these products are also cross platform and run at C speed with a proven record, being used in very big web sites where their sharding capabilities and fault tolerance have been pushed far.

If you take your pleasure in the process, don't be worry about the objective, you already won.

Improve this answer
3
  • 6
    +1 , very thoughtful and teaching reply :-) ... really nice answer to someone who wants to do somehting
    – Pankaj Upadhyay
    Nov 25, 2011 at 11:51
  • Very nice indeed. I was on the verge of accepting this. I didn't because I thought yannis's answer to be more to the point, and more likely to help people having the same question. But this was definitely encouraging. Thanks a lot.
    – Xananax
    Nov 25, 2011 at 19:51
  • Yannis answer is better than mine and deserve your choice
    – user2567
    Nov 25, 2011 at 21:13
7

"(it's "node-oriented", if that even exists)". - This may be why you are not finding much!

Dive in with version 0.1 and see where you get. You may learn more from trying to produce what you want that from asking what you "should" do. Give it a few days and then review where you've got.

About 18 years ago I wrote a basic database system (for fun, go figure) with btree indexes and learned an awful lot.

Improve this answer
5

Sounds like a great project. Apparently your goal is not to create a production software, but to learn about databases and the process of creating a database system.

I don't really think you need to do a lot of research. It seems like the purpose is to get the experience of what goes in to creating a node-based database system.

Here's how I would get started:

  1. Choose your favorite language or a language that you want to improve.
  2. Create the node object (or whatever is closest in your language). Figure out how to link them.
  3. Make a short list of SQL statements that you will implement first.
  4. Decide how to save the data. One obvious solution is to serialize all the nodes, load them when the program starts, and save them when the program ends.

After you get the basics working, you will have much more insight into what is difficult or problematic. Then you can do some research about it, find some improvements, and integrate them.

Improve this answer
3
  • 1
    I am following the steps you suggested. 1,2,3 are no problem. However, I am stumped by #4. In the case of large amounts of data, how would I load in memory only the relevant parts? I thought of storing everything as binary data and keep another index file, but what if the user is not querying by index? I still would have to loop through the whole file...I guess it's time for another question
    – Xananax
    Nov 27, 2011 at 1:48
  • Why not just store everything in memory? If you dedicate 1 GB, that would hold a lot of data. Alternately, store each binary data node on disk, and then you would have 1 GB for text. That is a lot of text. Anyway, I think handling a database larger than 1GB is not central to the exercise.
    – B Seven
    Nov 27, 2011 at 2:11
  • Also, you can create many methods to efficiently work within 1 GB of memory. You can improve that part of the system later. One solution is to load all the node information into memory, but store the data of each node on disk. That way you can efficiently traverse the nodes, and only access the disk to retrieve the data you really need.
    – B Seven
    Nov 27, 2011 at 2:11
4

MySQL has pluggable storage engine structure, it might be an idea to check out how engines are created to work for MySQL.

Improve this answer
3
  • Link is broken.
    – Joseph Garvin
    Nov 28, 2021 at 1:18
  • @JosephGarvin then you can google the updated one and suggest an edit.
    – Mjh
    Nov 15, 2022 at 13:58
  • Or I could just downvote your answer. That's the time I have to contribute today. FWIW, I did google, and there is not an obvious direct hit in the first page of results.
    – Joseph Garvin
    Nov 15, 2022 at 22:44
4

Writing your own database “so as to understand how it all works” is the only good reason to do so (since databases are crazy hard to get right, and difficult to prove correct). You're crazy, but in a good way!

In order to see how it's done, I suggest looking at SQLite. The SQLite source is only about 1.3MB compressed, and it's a fully ACID-compliant transactional database. It's also public domain and the main author's a nice guy who I'm sure will be happy to answer your questions. (I think the trickiest bits come in how to truly commit information to disk; persuading OSes and hardware to stop lying and really write the transaction NOW is surprisingly difficult and why I'm so glad I never have to write a DB.)

Improve this answer
2
  • 1
    The SQLite codebase approaches 0,2*10^6 loc (5mb decompressed), it's not that small.
    – yannis
    Nov 25, 2011 at 12:14
  • 2
    @Yannis: Compare with MySQL or PostgreSQL or any of the other server DB systems…
    – Donal Fellows
    Nov 26, 2011 at 14:51
3

Buy a book:

http://www.springer.com/computer/database+management+%26+information+retrieval/book/978-1-84628-394-9

Indexes are imho the most important aspect of databases today. Study the alternatives that exists like binary trees.

Also read about cartesian product which is a way to calculate how complex joins will be.

Improve this answer
3

I need to learn how databases work

Learn relational algebra.

Find a small DB engine, learn the source.

in order to use them more efficiently

Nope. You need to learn how to efficiently use a database. You might be a better driver if you understand how your car works, but you'll be a much better driver if you really focus on driving.

Take the traditional routes: take a course, read a book, peer review, ask questions, use the index luke.

Improve this answer
1
  • 6
    Learn relational algebra. Assuming op is interested in relational databases of course...
    – yannis
    Nov 25, 2011 at 16:06

Not the answer you're looking for? Browse other questions tagged or ask your own question.