Re: Git's database structure

From: Jon Smirl <jonsmirl@gmail.com>
Date: Sep 4, 2007, 21:54 UTC
Message-ID: <9e4733910709041454i189e6629k78ddeb89797276b3@mail.gmail.com>
In-Reply-To: <20070904212507.GA24434@thunk.org>

On 9/4/07, Theodore Tso <tytso@mit.edu> wrote:

Show 28 quoted lines

> On Tue, Sep 04, 2007 at 01:44:47PM -0400, Jon Smirl wrote:
> > The current data store design is not very flexible. Databases solved
> > the flexibility problem long ago. I'm just wondering if we should
> > steal some good ideas out of the database world and apply them to git.
> > Ten years from now we may have 100GB git databases and really wish we
> > had more flexible ways of querying them.
>
> Databases solved the flexibility problem, at the cost of performance.
> And if you use full normalized form in your database scheme, it costs
> you even more in performance, because of all of the joins that you
> need in order get the information you need to do, you know, useful
> work as opposed to database wanking.
>
> If you take a look at the really big databases with super high
> performance requirements, say like those used to managed airline
> tickets/reservation/fares, you will find that they are not normalized,
> and they are not relational; they can't afford to be.  And if you take
> a look at some of git competition that use relational databases to
> store their SCM data, and take a look at how loooooong they they take
> to do even basic operations, I would say that the onus is on you to
> prove that normalization is actually a win in terms of real (not
> theoretical) advantages, and that it doesn't cause performance to go
> into the toilet.
>
> I think the fundamental disconnect here is that no one is buying your
> claim that just because the data design is "more flexible" that this
> is automatically a good thing in and of itself, and we should even for
> a moment, "put performance aside".

It is very easy to get bogged down in performance arguments on database design when the correct answer is that there are always lots of different ways to achieve the same goal. I wanted to defer debating performance until we closely looked at the relationships between the data at an abstract level.

Since git hasn't stored all of the fields in the object table (the path is encoded in the index) we are never going to be able to build an alternative way of indexing the object table. Not being able to build alternative indexes is likely to cause problems when the database starts getting really big. Without an index every query that can't use the path name index is reduced to doing full table scans.

A few things that could benefit from alternative indexing, blame, full-text search, automating the Maintainers file, etc.

I'm just asking if we really want to make full table scans the only possible way to implement these types of queries. If the answer is no, then let's first explore how to fix things at an abstract level before diving into the performance arguments.

An obvious parallel from the file system world is the locate database and how it is forced to continuously rescan the file system and store full path names.

Show 9 quoted lines

>
> I also don't think that attempting to force git's data structures into
> database terms makes sense; it is much closer to an filesystem using
> an object based store --- and very few people except for folks like
> Hans Resiers believes that Filesystems and Database should be
> unified....
>
>                                                 - Ted
>

-- 
Jon Smirl
jonsmirl@gmail.com