Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Re^2: (Real) Database Design

by Anonymous Monk
on Jul 14, 2004 at 20:02 UTC ( [id://374418]=note: print w/replies, xml ) Need Help??


in reply to Re: (Real) Database Design
in thread (Real) Database Design

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 :)

Replies are listed 'Best First'.
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

      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! :)

        The data layout is actually very similar to how MySQL lays out its MyISAM-type tables. (InnoDB is laid out differently.)

        Separating records on disk isn't that difficult. Basically, you need to keep track in your metadata where in the datafile each record starts. That is usually done in one of two ways:

        1. If your records are of a fixed length, you keep track of which record it is. So, if your records are 80 bytes long and you're looking for record N, you seek to position 80 * (N - 1).
        2. If your reocrds are of variable length, you store the seek position for each record in your metadata file.

        Now, you're trying to figure out how you know which records to look for. Well, it's quite simple. You generally are saying something like "Give me all the records that have such-and-such qualities." Well, in your metadata, you will hopefully have a cache of those qualities. So, if you're looking for all records that have ColumnA = 'Foo", you might have an index on ColumnA and you'll have a list of all the various values that it has and which records each value corresponds to. If you cannot use an index, you will have to do what's called a full-table scan. This means you have to look through the entire file checking ColumnA for its value. This is EXTREMELY expensive, often taking 100x (or more) as long. Then there's primary keys and foreign keys and all sorts of craziness. But, it all boils down to what information about the record you have cached and what you haven't.

        As for caching to RAM ... databases will generally keep as much in RAM as possible. The most common strategy I've seen is to keep as much in RAM as possible, removing data as needed from the oldest data first. Oracle tends to store any rows that have been retrieved. MySQL will store the results of queries that have been executed.

        I think I've kind of started an answer on the seeking question. Here, my theoretical knowledge is weaker. I've a lot of experience in optimizing SQL queries with indices and well-formed queries, but little in how the engine executes those commands. For that, consult prior art.

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

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://374418]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others perusing the Monastery: (4)
As of 2024-03-29 14:46 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found