Re: Git's database structure

["Jon Smirl" <jonsmirl@gmail.com>]

On 9/5/07, Andreas Ericsson <ae@op5.se> wrote:
> 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.


This is why I wanted to separate the abstract data structure design
discussion from the performance one. In the flat design indexes are
like caches and can be created and destroyed. There will definitely be
an index created on the the paths. This index will work like the
current tree nodes. The difference is that this index is a cache
unlike the current tree nodes which are an immutable part of the the
data base.

The path name field needs to be moved back into the blobs to support
alternative indexes. For example I want an index on the Signed-off-by
field. I use this index to give me the SHAs for the blobs
Signed-off-by a particular person. In the current design I have no way
of recovering the path name for these blobs other than a brute force
search following every path looking for the right SHA.



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


-- 
Jon Smirl
jonsmirl@gmail.com