Re: Git's database structure

[Andreas Ericsson <ae@op5.se>]

Jon Smirl wrote:
> On 9/4/07, Theodore Tso <tytso@mit.edu> wrote:
>> 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.
> 

But you cannot. Git is performance-critical, for the same reason every
other performance-critical application is: It's a tool to save human
time. Linux development *could* be done using patchfiles by the bundle
and masses of tarballs. It's just not the fastest way to do it, so enter
git, and lots of problems just go away. It's not the only way of doing
it, but it saves time. If you were to add 2 seconds to each commit,
that's several months of developer time that is lost every day!


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

We can still build alternative indexes. They just have to be separate
from the DAG and the current indexing scheme. Junio has pointed out
ways of doing this already.

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

I've said it before; The most common delimiter used today is paths. It's
a behaviour git was designed to handle well, because it *is* the most
common way of limiting and separating content. It's not some random
fluke that has made git perform very well on actions that commonly
performed in large scale software projects; Linus designed it that way
from the start, and kudos to him for a job well done.

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

Yes, but getting rid of the tree objects and storing pathnames in
blob objects would penalize log-viewing, diffs and merges, which
are far more common operations than full-text searches in a software
project.

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

Personally, I really don't care. But you should really have read Junio's
mail a bit more carefully. He explained about 'notes' that can be attached
to commits and contain arbitrary data. By all means, create your indexes
there and use them for whatever you like, but leave the foundation on which
git was built *alone*. The design hasn't changed since April 2006 (subtrees
were introduced April 26, I think), because it's a *good* design.

-- 
Andreas Ericsson                   andreas.ericsson@op5.se
OP5 AB                             www.op5.se
Tel: +46 8-230225                  Fax: +46 8-230231