Re: (Real) Database Design

The issues in optimizing performance for data storage are primarily hardware/operating-system driven. A partial list of the issues/thoughts/concerns would include:

A hard-drive generally has seek-times in the milli-second range. RAM has seek-times in the nano-second range. That's a million-to-one difference.
Most datastores, like MySQL, are optimized for data retrieval. This is because the number of retrievals vs. the number of updates is generally in the 100k-to-one to million-to-one category. (That's based on experience and anecdotal evidence. Various applications have various needs. To compare - I work with two apps right now. One is almost completely retrieval and the other is about 100k-to-1.)
Although the SQL standard doesn't mandate data types (and SQLite, for instance, doesn't use them), most datastores will use them because that information can reduce the amount of space taken for a given row. By reducing space, you reduce the seek time for finding records. For example, if you know a column is INT(7), that means it's less than 2^24. That's 3 bytes storing it as an integer, instead of 7 as a string. (And up to 8, if you store it as a null-terminated string.) Over a million rows, that can save 4 megabytes. In addition, if you use an integer there, you can justify using fixed-length rows, which trades space (you potentially use more per row) for speed (you know exactly how wide each row is, so you only have one seek vs. potentially thousands in a naive implementation.)
A really neat fact about datastores is that optimizing for space actually ends up optimizing for speed, in the general case. This is because datastores are almost completely I/O-bound. The less you have to use the hard-drive, the less time you take. Also - CPU's are improving much much faster than hard-drives. (At least, over platter-based hard-drives.) So, using some form of data compression on a per-row may make sense. (And, some datastores like Oracle and MySQL do offer this option for retrieve-only tables, but that system can be easily improved upon.)
A concern you have to take into account is the block size. This is the smallest chunk of physical space the operating system will allocate for storage. In most OS'es, this is either 512bytes or 1024bytes. In keeping with the desire to reduce the amount of seek time, you should be aware of this number.

Your questions are actually the same question, from different directions. There is a better way of structuring the data, and that's by keeping the metadata around. Basically, the most important piece of metadata you want is the rowsize. That tells you where the data is that you're looking for. You also want to keep some set of indices which allow you to quickly determine which row numbers have what data in what column. As for storing this metadata ... most datastores keep a separate storage area for this. Oracle keeps it as part of the data file and MySQL keeps it as a separate file (at least for MyISAM tables).

Column types, sizes, referential integrity ... that's all used to aid the developer. SQLite is a good example of a datastore that doesn't make any use of that stuff. (Well, very, very little use.) Column types and sizes can also help the datastore in some optimizations when calculating rowsize. (q.v. above as to why this is important.)

Oh - if you want any sort of decent performance, you will end up rewriting this in C.

This won't help in the actual implementation, but look for stuff written by Fabian Pascal on some theory behind efficient data storage, especially with the relational model. He has a lot of ... good ... articles on the web.

Updates:Wording changes on the sidenote about compression on a per-row basis. Added an example of savings when using data types.

------
We are the carpenters and bricklayers of the Information Age.

Then there are Damian modules.... *sigh* ... that's not about being less-lazy -- that's about being on some really good drugs -- you know, there is no spoon. - flyingmoose

I shouldn't have to say this, but any code, unless otherwise stated, is untested

Comment on Re: (Real) Database Design

Replies are listed 'Best First'.
Re^2: (Real) Database Design by Anonymous Monk on Jul 14, 2004 at 20:02 UTC
A truly knowledgeable reply! Many thanks :) I had a feeling that the operating system and how it views/interprets files would play a major role in the design. As for the hardware, I'll just be using x86 for now (until the xbox 2 comes out ;). As for the issue of storing meta data, having it in the same file as the table appeals to me. It would appear to my (rather limited) sight that having to access a separate location to retrieve the meta data would unecessarily complicate things. The issue then becomes the exact format of metadata storage. Is a fixed length at the start of a file the best approach? As more columns are entered this would seem to collapse. How about non-data type meta data such as the names of columns? If anyone knows of an example implementation or can offer advice on this it would greatly assist me. Now for my sillier question. As for the data files, they would have to be binary files right? All that I'll end up having is a stream of 1s and 0s that the OS attaches a label to? (As you can see I still have a bit of a conceptual leap to make ;). The Linux kernel doesn't interpret a file as anything more than a stream of bytes, correct? So when I have a data column with 01101011 the dbm will choose to interpret it as a character or as an integer based on the meta data right? If this is all correct, can anyone provide pointers to standards about common representation of data types (especially floating point numbers?). As for the language of choice, C would be the highest level language that I'd end up writing this in. I'd like to understand the core theory first though before I start writing my spaghetti. The points about block size and loading as much as possible into ram are well taken. They do make me think of one other question - how would I have to change (if at all) the structure of the db in ram as compared to on disk? Could I just load it all into a struct that's generated based on the file's meta data? Many thanks again for the excellent replies so far :)	[reply]
Re^3: (Real) Database Design by dragonchild (Archbishop) on Jul 14, 2004 at 20:20 UTC
When I was speaking of hardware, I was speaking of the performance limitations of the hard-drive as opposed to RAM and CPU. The actual architecture is unimportant because the operating system deals with that. The important thing is the ratio between retrieving data from a hard-drive and retrieving the same data from RAM. You actually do want to have the metadata in a separate file than the actual data itself. In fact, you want it on a separate hard-drive, if possible. That way, your machine can read both files at the same time - taking advantage of multiple and/or dual-core CPUs. This also means that you can modify the metadata without having to re-write the data file. Metadata is usually a very small amount of data as opposed to the actual data itself. Remember - a database is usually only useful once you get beyond 3-8 tables and/or 10-20k rows. Metadata usually doesn't get beyond 10-20 kilobytes. Data is usually in the megabytes. You don't want to relocate 20M just to add another constraint to your 3K of metadata. This also allows you to (initially) keep your metadata in some human-readable form, like YAML or XML. (Or even Apache's configuration format, readable with Config::ApacheFormat.) That can make initial development a little easier. Or not. To answer your sillier question - every single file is a binary file, from everything's perspective. The only thing that makes a file text vs. binary is how a program has been told to interpret it. For example, FTP makes a distinction between the two only so it can translate \n in Unis to \r\n in Windows to \r in Mac. That's it. (Well, I'm sure VMS and OS/360 have their own linefeed characters, but who uses those? grins) You will want to pack your data instead of naively storing it as characters. This reduces the space used, which reduces the time it takes to find a given record. Packing data according to various schemes is the topic of several graduates theses, and well beyond the limited discussion here. (I would suggest googling and having several cases of Jolt available. Oh - and don't buy Doom3 when it comes out on August 6th if you actually want to get this project done.) The important thing is that most of the character packing and unpacking work has already been done for you. You just have to know where to find it. Your last question about data structure representation is misguided. You will not be working with the data as it is stored on disk. You will always be loading it from disk into RAM, then manipulating it there. Most metadata exists to reduce the amount of stuff that is retrieved from disk and converted into some useful data structure that lives in RAM. Remember - a database isn't some magical program that is somehow different from every other program in how it interacts with the world. It's just a complex application that, at its heart, does the following: Stores data on disk in a compact form Retrieves selected data from disk as fast as possible The reason this technology is so important is that retrieving selected data from disk as fast as possible is the heart of modern business. The key is selected. Every single application in the world can be viewed as a report on data stored in some datastore transformed in some way, with some giving the ability to modify that data and write it back to the datastore. The trick is only pullling back the data that the user wants to retrieve. Oh - and doing it as fast as possible, preferably beneath the human threshold (about a tenth of a second). ------ We are the carpenters and bricklayers of the Information Age. Then there are Damian modules.... sigh* ... that's not about being less-lazy -- that's about being on some really good drugs -- you know, there is no spoon.* - flyingmoose I shouldn't have to say this, but any code, unless otherwise stated, is untested	[reply]
Re^4: (Real) Database Design by Anonymous Monk on Jul 14, 2004 at 20:51 UTC
This has been a most insightful conversation! I think you've already answered most of my questions (and more importantly, potential questions). I would appreciate any advice you have on the following structure of events, but I think I'm almost ready to begin. So the basic structure of the database (from one perspective) would go something like this: Database is laid out in a hierarchal directory design. Tables are files on the disk with meta data stored elsewhere (preferably on a separate disk) possibly mirroring the hierarchal structure of the data dir tree. Files are (naturally) binary in nature, the exact representation of the data types shall be determined after much googleage and jolt consumption. (I'm still a little fuzzy on how to separate records in the data file - can I just a fix row length in the meta files and go by that?) As for reading data from the disk as fast as possible - any last tips on caching to ram? As I see it, try to determine the most used data and ensure it's always in ram. For the small dbs I'm planning on building at first it won't be a problem to load the entire database into ram. Seeking specific data from a file - determine applicable fields, iterate over them checking their contents, return the matching results. Any last performance tips here? This might just be random ramblings at this point, I think you've pointed me in the right direction now. Thanks again for all the help! :)	[reply]
Re^5: (Real) Database Design by dragonchild (Archbishop) on Jul 15, 2004 at 02:04 UTC