{"thread":{"id":"9778","subject":"Git's database structure","startedAt":"2007-09-04T15:23:02Z","lastAt":"2007-09-07T00:33:57Z","messageCount":39,"participants":["Jon Smirl","Andreas Ericsson","Mike Hommey","Jeff King","Julian Phillips","Junio C Hamano","Reece Dunn","David Tweed","Theodore Tso","Andy Parkins","Kyle Moffett","Wincent Colaiuta","Johannes Schindelin","Steven Grimm","Martin Langhoff"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"52468","messageId":"9e4733910709040823k731f0ffchba1f93bdb4a8373d@mail.gmail.com","threadId":"9778","inReplyTo":null,"subject":"Git's database structure","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-09-04T15:23:02Z","receivedAt":"2007-09-04T15:23:02Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"Let's back up a little bit from \"Caclulating tree node\". What are the\nelements of git's data structures?\n\nRight now we have an index structure (tree nodes) integrated in to a\nbase table. Integrating indexing into the data is not normally done in\na database. Doing a normalization analysis like this may expose flaws\nin the way the data is structured. Of course we may also decide to\nleave everything the way it is.\n\nWhat about the special status of a rename? In the current model we\neffectively have three tables.\n\ncommit - a set of all SHAs in the commit, previous commit, comment, author, etc\nblob - a file, permissions, etc.\nfile names - name, SHA\n\nThe file name table is encoded as an index and it has been\nintermingled with the commit table.\n\nLooking at this from a set theory angle brings up the question, do we\nreally have three tables and file names are an independent variable\nfrom the blobs, or should file names be an attribute of the blob?\n\nHow this gets structured in the db is an independent question about\nhow renames get detected on a commit. The current scheme for detecting\nrenames by comparing diffs is working fine. The question is, once we\ndetect a rename how should it be stored?\n\nIgnoring the performance impacts and looking at the problem from the\nset theory view point, should:\nthe pathnames be in their own table with a row for each alias\nthe pathnames be stored as an attribute of the blob\n\nBoth of these are the same information, we're just looking at how\nthings are normalized.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"52473","messageId":"46DD7FE4.1060908@op5.se","threadId":"9778","inReplyTo":"9e4733910709040823k731f0ffchba1f93bdb4a8373d@mail.gmail.com","subject":"Re: Git's database structure","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2007-09-04T15:55:16Z","receivedAt":"2007-09-04T15:55:16Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Jon Smirl wrote:\n> Let's back up a little bit from \"Caclulating tree node\". What are the\n> elements of git's data structures?\n> \n> Right now we have an index structure (tree nodes) integrated in to a\n> base table. Integrating indexing into the data is not normally done in\n> a database. Doing a normalization analysis like this may expose flaws\n> in the way the data is structured. Of course we may also decide to\n> leave everything the way it is.\n> \n> What about the special status of a rename? In the current model we\n> effectively have three tables.\n> \n> commit - a set of all SHAs in the commit, previous commit, comment, author, etc\n\n> blob - a file, permissions, etc.\n> file names - name, SHA\n\ncommit - SHA1 of its parent(s) and its root-tree, along with\n author info and a free-form field\nblob - content addressable by *multiple trees*\nfile names - List of path-names inside a tree object.\n\n\nTo draw some sort of relationship model here, you'd have\n\ncommit 1<->M roottree\ntree M<->M tree\ntree M<->M blob\n\nAssuming SHA1 never collides (collisions rule out any form of storage,\nso we might as well hope it never happens), that leaves us with this:\n\nEach root tree can only ever belong to a single commit, unless you\nintentionally force git to make completely empty commits. git\nwon't complain about this, so long as you don't make two in the\nsame second, because it relies more heavily on the DAG than on\ndeveloper sanity.\n\nEach root tree can point to multiple sub-trees. The sub-trees can be\nlinked to any number of root-trees. \n\nBlobs can be linked to any number of tree objects, or even multiple\ntimes to the same tree object. This wouldn't be possible if the\nblob objects had their own pathnames stored inside them, so to speak.\n\n> \n> The file name table is encoded as an index and it has been\n> intermingled with the commit table.\n> \n> Looking at this from a set theory angle brings up the question, do we\n> really have three tables and file names are an independent variable\n> from the blobs, or should file names be an attribute of the blob?\n> \n\nFile names are not independant variables. They belong inside the\ntable created for them, which is the tree objects.\n\n> How this gets structured in the db is an independent question about\n> how renames get detected on a commit. The current scheme for detecting\n> renames by comparing diffs is working fine. The question is, once we\n> detect a rename how should it be stored?\n> \n\nDo you realize that you're contradicting yourself in two upon each\nother following sentences here?\n\nDetecting renames after the fashion works fine. Not storing them\nis part of the \"detect them by comparing diffs\".\n\n> Ignoring the performance impacts and looking at the problem from the\n> set theory view point, should:\n> the pathnames be in their own table with a row for each alias\n> the pathnames be stored as an attribute of the blob\n> \n> Both of these are the same information, we're just looking at how\n> things are normalized.\n> \n\nExcept that\n\ngit init\necho foo > a\ncp -a a b\ngit add .\ngit commit -m testing\ngit count-objects\n\nyields 3 objects at the moment; A commit-object, a tree object and *one*\nblob object. With your scheme the 2 blob objects would differ, and there\nwould be 4 of them. If you propose to ignore the path-name you have\neffectively broken support for having two identical files with different\nnames in the same directory.\n\nNow, can you please tell me what gains you're hoping to see with this\nnew layout of yours?\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"52475","messageId":"20070904160726.GA17509@glandium.org","threadId":"9778","inReplyTo":"46DD7FE4.1060908@op5.se","subject":"Re: Git's database structure","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2007-09-04T16:07:26Z","receivedAt":"2007-09-04T16:07:26Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Tue, Sep 04, 2007 at 05:55:16PM +0200, Andreas Ericsson wrote:\n> Each root tree can only ever belong to a single commit, unless you\n> intentionally force git to make completely empty commits. git\n> won't complain about this, so long as you don't make two in the\n> same second, because it relies more heavily on the DAG than on\n> developer sanity.\n\nActually, you don't need to be insane to have multiple commits pointing\nat the same root tree. It is actually very easy:\n- git clone\n- do some stuff on your master branch and commit\n- send your changes upstream\n- upstream applies as is\n- git pull\n\nYou now have everything merged, and the last commit on your master branch,\nwhile being a different commit object due to its parenting, has the same\nroot tree as the tip of the remote branch.\n\nMike\n"},{"id":"52476","messageId":"46DD8387.3040801@op5.se","threadId":"9778","inReplyTo":"20070904160726.GA17509@glandium.org","subject":"Re: Git's database structure","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2007-09-04T16:10:47Z","receivedAt":"2007-09-04T16:10:47Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Mike Hommey wrote:\n> On Tue, Sep 04, 2007 at 05:55:16PM +0200, Andreas Ericsson wrote:\n>> Each root tree can only ever belong to a single commit, unless you\n>> intentionally force git to make completely empty commits. git\n>> won't complain about this, so long as you don't make two in the\n>> same second, because it relies more heavily on the DAG than on\n>> developer sanity.\n> \n> Actually, you don't need to be insane to have multiple commits pointing\n> at the same root tree. It is actually very easy:\n> - git clone\n> - do some stuff on your master branch and commit\n> - send your changes upstream\n> - upstream applies as is\n> - git pull\n> \n> You now have everything merged, and the last commit on your master branch,\n> while being a different commit object due to its parenting, has the same\n> root tree as the tip of the remote branch.\n> \n\nThat explains why it felt so awkward writing that sentence. :)\nThanks for correcting me. Even so, one more M<->M relation-ship\ncertainly speaks for rather than against the current model.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"52478","messageId":"9e4733910709040919u3d252b91s2785ed4d20086c88@mail.gmail.com","threadId":"9778","inReplyTo":"46DD7FE4.1060908@op5.se","subject":"Re: Git's database structure","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-09-04T16:19:33Z","receivedAt":"2007-09-04T16:19:33Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/4/07, Andreas Ericsson wrote:\n> Jon Smirl wrote:\n> > Let's back up a little bit from \"Caclulating tree node\". What are the\n> > elements of git's data structures?\n> >\n> > Right now we have an index structure (tree nodes) integrated in to a\n> > base table. Integrating indexing into the data is not normally done in\n> > a database. Doing a normalization analysis like this may expose flaws\n> > in the way the data is structured. Of course we may also decide to\n> > leave everything the way it is.\n> >\n> > What about the special status of a rename? In the current model we\n> > effectively have three tables.\n> >\n> > commit - a set of all SHAs in the commit, previous commit, comment, author, etc\n>\n> > blob - a file, permissions, etc.\n> > file names - name, SHA\n>\n> commit - SHA1 of its parent(s) and its root-tree, along with\n> author info and a free-form field\n> blob - content addressable by *multiple trees*\n> file names - List of path-names inside a tree object.\n>\n>\n> To draw some sort of relationship model here, you'd have\n>\n> commit 1<->M roottree\n> tree M<->M tree\n> tree M<->M blob\n\nBy introducing tree nodes you have blended a specific indexing scheme\ninto the data. There are many other ways the path names could be\nindexed hash tables, binary trees, etc.\n\nThis problem exists in files systems. Since the path names have been\nencoded into the directory structures there is no way to query\nsomething like \"all files created yesterday\" from a file system\nwithout building another mapping table or a brute force search. I keep\nusing Google as an example, Google is indexing hierarchical URLs but\nthey do not use a hierarchical index to do it.\n\nDatabases keep the knowledge of how things are indexed out of the\ndata. A data structure analysis of git should remove the blended index\nand start from the set theory.\n\n> Assuming SHA1 never collides (collisions rule out any form of storage,\n> so we might as well hope it never happens), that leaves us with this:\n>\n> Each root tree can only ever belong to a single commit, unless you\n> intentionally force git to make completely empty commits. git\n> won't complain about this, so long as you don't make two in the\n> same second, because it relies more heavily on the DAG than on\n> developer sanity.\n>\n> Each root tree can point to multiple sub-trees. The sub-trees can be\n> linked to any number of root-trees.\n>\n> Blobs can be linked to any number of tree objects, or even multiple\n> times to the same tree object. This wouldn't be possible if the\n> blob objects had their own pathnames stored inside them, so to speak.\n>\n> >\n> > The file name table is encoded as an index and it has been\n> > intermingled with the commit table.\n> >\n> > Looking at this from a set theory angle brings up the question, do we\n> > really have three tables and file names are an independent variable\n> > from the blobs, or should file names be an attribute of the blob?\n> >\n>\n> File names are not independant variables. They belong inside the\n> table created for them, which is the tree objects.\n>\n> > How this gets structured in the db is an independent question about\n> > how renames get detected on a commit. The current scheme for detecting\n> > renames by comparing diffs is working fine. The question is, once we\n> > detect a rename how should it be stored?\n> >\n>\n> Do you realize that you're contradicting yourself in two upon each\n> other following sentences here?\n>\n> Detecting renames after the fashion works fine. Not storing them\n> is part of the \"detect them by comparing diffs\".\n>\n> > Ignoring the performance impacts and looking at the problem from the\n> > set theory view point, should:\n> > the pathnames be in their own table with a row for each alias\n> > the pathnames be stored as an attribute of the blob\n> >\n> > Both of these are the same information, we're just looking at how\n> > things are normalized.\n> >\n>\n> Except that\n>\n> git init\n> echo foo > a\n> cp -a a b\n> git add .\n> git commit -m testing\n> git count-objects\n>\n> yields 3 objects at the moment; A commit-object, a tree object and *one*\n> blob object. With your scheme the 2 blob objects would differ, and there\n> would be 4 of them. If you propose to ignore the path-name you have\n> effectively broken support for having two identical files with different\n> names in the same directory.\n>\n> Now, can you please tell me what gains you're hoping to see with this\n> new layout of yours?\n>\n> --\n> Andreas Ericsson andreas.ericsson@op5.se\n> OP5 AB www.op5.se\n> Tel: +46 8-230225 Fax: +46 8-230231\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"52481","messageId":"9e4733910709040928n6535e49esaf713b2c63ba0831@mail.gmail.com","threadId":"9778","inReplyTo":"9e4733910709040823k731f0ffchba1f93bdb4a8373d@mail.gmail.com","subject":"Re: Git's database structure","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-09-04T16:28:00Z","receivedAt":"2007-09-04T16:28:00Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"Another way of looking at the problem,\n\nLet's build a full-text index for git. You put a string into the index\nand it returns the SHAs of all the file nodes that contain the string.\nHow do I recover the path names of these SHAs?\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"52482","messageId":"46DD87FE.7020007@op5.se","threadId":"9778","inReplyTo":"9e4733910709040919u3d252b91s2785ed4d20086c88@mail.gmail.com","subject":"Re: Git's database structure","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2007-09-04T16:29:50Z","receivedAt":"2007-09-04T16:29:50Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Jon Smirl wrote:\n> On 9/4/07, Andreas Ericsson wrote:\n>> Jon Smirl wrote:\n>>> Let's back up a little bit from \"Caclulating tree node\". What are the\n>>> elements of git's data structures?\n>>>\n>>> Right now we have an index structure (tree nodes) integrated in to a\n>>> base table. Integrating indexing into the data is not normally done in\n>>> a database. Doing a normalization analysis like this may expose flaws\n>>> in the way the data is structured. Of course we may also decide to\n>>> leave everything the way it is.\n>>>\n>>> What about the special status of a rename? In the current model we\n>>> effectively have three tables.\n>>>\n>>> commit - a set of all SHAs in the commit, previous commit, comment, author, etc\n>>> blob - a file, permissions, etc.\n>>> file names - name, SHA\n>> commit - SHA1 of its parent(s) and its root-tree, along with\n>> author info and a free-form field\n>> blob - content addressable by *multiple trees*\n>> file names - List of path-names inside a tree object.\n>>\n>>\n>> To draw some sort of relationship model here, you'd have\n>>\n>> commit 1<->M roottree\n>> tree M<->M tree\n>> tree M<->M blob\n> \n> By introducing tree nodes you have blended a specific indexing scheme\n> into the data. There are many other ways the path names could be\n> indexed hash tables, binary trees, etc.\n> \n> This problem exists in files systems. Since the path names have been\n> encoded into the directory structures there is no way to query\n> something like \"all files created yesterday\" from a file system\n> without building another mapping table or a brute force search. I keep\n> using Google as an example, Google is indexing hierarchical URLs but\n> they do not use a hierarchical index to do it.\n> \n\nPathnames are by far the most common search-/delimiting criteria for\ngit though, so I fail to see why this is a problem for you.\n\n> Databases keep the knowledge of how things are indexed out of the\n> data. A data structure analysis of git should remove the blended index\n> and start from the set theory.\n> \n\nWhy? This is the core of the problem, really. You haven't specified a\nsingle, real-life reason *why* it should be any other way than it\nalready is. It sounds a bit to me as if you've been to a really\ninspiring seminar about \"how database-like things *should* be done\"\nand then decided to go berserk on your favourite database-like thing,\nwhich is git.\n\nCode and benchmarks or bust. In the meantime, I'll settle for a recount\nof what problems you're having with the current layout, or what gains\nyou're hoping to achieve with the new one. As it's the 3rd time I'm\nasking, this'll be the last.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"52483","messageId":"46DD887D.3090508@op5.se","threadId":"9778","inReplyTo":"9e4733910709040928n6535e49esaf713b2c63ba0831@mail.gmail.com","subject":"Re: Git's database structure","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2007-09-04T16:31:57Z","receivedAt":"2007-09-04T16:31:57Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Jon Smirl wrote:\n> Another way of looking at the problem,\n> \n> Let's build a full-text index for git. You put a string into the index\n> and it returns the SHAs of all the file nodes that contain the string.\n> How do I recover the path names of these SHAs?\n> \n\nI wouldn't know, but presumably any table can have more than one column.\n\nIs this a problem you face with git so often that it requires a complete\nre-design of its very core?\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"52485","messageId":"9e4733910709040947ia32bda4i6e30efb2d7848308@mail.gmail.com","threadId":"9778","inReplyTo":"46DD887D.3090508@op5.se","subject":"Re: Git's database structure","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-09-04T16:47:16Z","receivedAt":"2007-09-04T16:47:16Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/4/07, Andreas Ericsson wrote:\n> Jon Smirl wrote:\n> > Another way of looking at the problem,\n> >\n> > Let's build a full-text index for git. You put a string into the index\n> > and it returns the SHAs of all the file nodes that contain the string.\n> > How do I recover the path names of these SHAs?\n> >\n>\n> I wouldn't know, but presumably any table can have more than one column.\n>\n> Is this a problem you face with git so often that it requires a complete\n> re-design of its very core?\n\nThat's the whole point. We need to discuss the impact of merging a\nfield (path names) with an index (tree nodes) has on future things we\nmay want to do with the data stored in git.\n\nDatabases don't usually blend fields/indexes without also duplicating\nthe field in the table. You need all the fields in the table so that\nit is possible to create indexes on other fields.\n\n\n>\n> --\n> Andreas Ericsson andreas.ericsson@op5.se\n> OP5 AB www.op5.se\n> Tel: +46 8-230225 Fax: +46 8-230231\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"52487","messageId":"46DD8D16.9090104@op5.se","threadId":"9778","inReplyTo":"9e4733910709040947ia32bda4i6e30efb2d7848308@mail.gmail.com","subject":"Re: Git's database structure","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2007-09-04T16:51:34Z","receivedAt":"2007-09-04T16:51:34Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Jon Smirl wrote:\n> On 9/4/07, Andreas Ericsson wrote:\n>> Jon Smirl wrote:\n>>> Another way of looking at the problem,\n>>>\n>>> Let's build a full-text index for git. You put a string into the index\n>>> and it returns the SHAs of all the file nodes that contain the string.\n>>> How do I recover the path names of these SHAs?\n>>>\n>> I wouldn't know, but presumably any table can have more than one column.\n>>\n>> Is this a problem you face with git so often that it requires a complete\n>> re-design of its very core?\n> \n> That's the whole point. We need to discuss the impact of merging a\n> field (path names) with an index (tree nodes) has on future things we\n> may want to do with the data stored in git.\n> \n\nYes, but as nobody seems to know what those future things are, it feels\nrather pointless speculating about adding support to git for them. git\nis a tool. It's a great one at that, because it was built to solve a\nparticular problem, which it does an amazing job at.\n\nOther SCM's which had the potential to become amazingly good tools too\ndrowned somewhere between prototype and product in a sea of intellectual\nmasturbation, which had little to do with solving real-world problems.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"52488","messageId":"20070904170921.GA31300@coredump.intra.peff.net","threadId":"9778","inReplyTo":"9e4733910709040919u3d252b91s2785ed4d20086c88@mail.gmail.com","subject":"Re: Git's database structure","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2007-09-04T17:09:22Z","receivedAt":"2007-09-04T17:09:22Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Sep 04, 2007 at 12:19:33PM -0400, Jon Smirl wrote:\n\n> By introducing tree nodes you have blended a specific indexing scheme\n> into the data. There are many other ways the path names could be\n> indexed hash tables, binary trees, etc.\n\nThat is correct. However, given that indexing scheme, many of the common\noperations just \"fall out\" simply and efficiently, without the need to\nkeep separate indices. So yes, git is geared towards a particular set of\noperations.\n\nYour complaint seems to be two-fold:\n\n 1. there is an inelegance in the blending of data and indexing. The\n problem with changing this is:\n a. we are all already using git, and it would require completely\n re-vamping the core data structure\n b. there is some feeling that the blending is necessary for\n performance. Given the difficulty of (a), I think you would\n have to provide compelling evidence (i.e., numbers) that a\n git-like system based around set theory with separate indices\n would perform as well.\n\n 2. you want perform some operations to which the hierarchy is not\n well-suited. In this case, I think you can get by with the same\n solution you have proposed already: indices external to the data\n structure (in fact, this is exactly what Google is doing: taking\n hierarchical URLs and indexing them in different ways).\n\n Have you taken a look at the pack v4 work by Shawn and Nicolas? It\n is an attempt to build such indices at pack time (but keeping the\n core git data structure intact).\n\n-Peff\n"},{"id":"52490","messageId":"Pine.LNX.4.64.0709041816340.29009@reaper.quantumfyre.co.uk","threadId":"9778","inReplyTo":"9e4733910709040823k731f0ffchba1f93bdb4a8373d@mail.gmail.com","subject":"Re: Git's database structure","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2007-09-04T17:19:35Z","receivedAt":"2007-09-04T17:19:35Z","isPatch":false,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"On Tue, 4 Sep 2007, Jon Smirl wrote:\n\n> Let's back up a little bit from \"Caclulating tree node\". What are the\n> elements of git's data structures?\n>\n> Right now we have an index structure (tree nodes) integrated in to a\n> base table. Integrating indexing into the data is not normally done in\n> a database. Doing a normalization analysis like this may expose flaws\n> in the way the data is structured. Of course we may also decide to\n> leave everything the way it is.\n>\n> What about the special status of a rename? In the current model we\n> effectively have three tables.\n>\n> commit - a set of all SHAs in the commit, previous commit, comment, author, etc\n> blob - a file, permissions, etc.\n> file names - name, SHA\n>\n> The file name table is encoded as an index and it has been\n> intermingled with the commit table.\n>\n> Looking at this from a set theory angle brings up the question, do we\n> really have three tables and file names are an independent variable\n> from the blobs, or should file names be an attribute of the blob?\n\nThere isn't a one-to-one mapping of file names to blobs. The blob only \ndescribes the contents of the file. In the extreme case you could have \none blob for every single file in your tree. For example:\n\n# git ls-tree -r HEAD\n100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c bar/foo\n100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo\n100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo2\n100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo3\n100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo4\n100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo5\n100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo6\n\n>\n> How this gets structured in the db is an independent question about\n> how renames get detected on a commit. The current scheme for detecting\n> renames by comparing diffs is working fine. The question is, once we\n> detect a rename how should it be stored?\n>\n> Ignoring the performance impacts and looking at the problem from the\n> set theory view point, should:\n> the pathnames be in their own table with a row for each alias\n> the pathnames be stored as an attribute of the blob\n>\n> Both of these are the same information, we're just looking at how\n> things are normalized.\n>\n>\n\n-- \nJulian\n\n ---\n\"You shouldn't make my toaster angry.\"\n-- Household security explained in \"Johnny Quest\"\n"},{"id":"52491","messageId":"7vy7fmny6y.fsf@gitster.siamese.dyndns.org","threadId":"9778","inReplyTo":"46DD7FE4.1060908@op5.se","subject":"Re: Git's database structure","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-09-04T17:21:41Z","receivedAt":"2007-09-04T17:21:41Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Andreas Ericsson writes:\n\n> Each root tree can only ever belong to a single commit, unless you\n> intentionally force git to make completely empty commits. git\n> won't complain about this, so long as you don't make two in the\n> same second, because it relies more heavily on the DAG than on\n> developer sanity.\n\nThis actually can happen without even using 'ours' strategy.\n\nIf two people independently applied the same patch on their\nbranches and later their results were merged. And \"the same\nsecond\" requirement is not even there and not interesting.\nThere are other things like developer identity, log message, and\ntheir ancestry that would make the resulting commit object\ndistinct.\n\n> Each root tree can point to multiple sub-trees. The sub-trees can be\n> linked to any number of root-trees.\n>\n> Blobs can be linked to any number of tree objects, or even multiple\n> times to the same tree object. This wouldn't be possible if the\n> blob objects had their own pathnames stored inside them, so to speak.\n\nMore importantly, in git, filenames and modes are not considered\npart of \"contents\", which git tracks. Although it is an\nentirely possible and valid alternate design to move that as\npart of \"blob\" to build a system that is different from git,\nwhich Jon seems to be aiming at, the benefit of such a design is\nunclear to me, both from theoretical point of view (now blobs\nare not about pure contents anymore) nor performance point of\nview (Linus's done flat tree object in an early stage of git,\nand it was not nice) as other people explained.\n"},{"id":"52492","messageId":"7vtzqany0z.fsf@gitster.siamese.dyndns.org","threadId":"9778","inReplyTo":"9e4733910709040928n6535e49esaf713b2c63ba0831@mail.gmail.com","subject":"Re: Git's database structure","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-09-04T17:25:16Z","receivedAt":"2007-09-04T17:25:16Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Jon Smirl\" writes:\n\n> Another way of looking at the problem,\n>\n> Let's build a full-text index for git. You put a string into the index\n> and it returns the SHAs of all the file nodes that contain the string.\n> How do I recover the path names of these SHAs?\n\nThat question does not make much sense without specifying \"which\ncommit's path you are talking about\".\n\nIf you want to encode such \"contextual information\" in addition\nto \"contents\", you could do so, but you essentially need to\nrecord commit + pathname + mode bits + contents as \"blob\" and\nhash that to come up with a name.\n"},{"id":"52495","messageId":"9e4733910709041030ye912369nd574a5f78d3f521b@mail.gmail.com","threadId":"9778","inReplyTo":"Pine.LNX.4.64.0709041816340.29009@reaper.quantumfyre.co.uk","subject":"Re: Git's database structure","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-09-04T17:30:30Z","receivedAt":"2007-09-04T17:30:30Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/4/07, Julian Phillips wrote:\n> On Tue, 4 Sep 2007, Jon Smirl wrote:\n>\n> > Let's back up a little bit from \"Caclulating tree node\". What are the\n> > elements of git's data structures?\n> >\n> > Right now we have an index structure (tree nodes) integrated in to a\n> > base table. Integrating indexing into the data is not normally done in\n> > a database. Doing a normalization analysis like this may expose flaws\n> > in the way the data is structured. Of course we may also decide to\n> > leave everything the way it is.\n> >\n> > What about the special status of a rename? In the current model we\n> > effectively have three tables.\n> >\n> > commit - a set of all SHAs in the commit, previous commit, comment, author, etc\n> > blob - a file, permissions, etc.\n> > file names - name, SHA\n> >\n> > The file name table is encoded as an index and it has been\n> > intermingled with the commit table.\n> >\n> > Looking at this from a set theory angle brings up the question, do we\n> > really have three tables and file names are an independent variable\n> > from the blobs, or should file names be an attribute of the blob?\n>\n> There isn't a one-to-one mapping of file names to blobs. The blob only\n> describes the contents of the file. In the extreme case you could have\n> one blob for every single file in your tree. For example:\n>\n> # git ls-tree -r HEAD\n> 100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c bar/foo\n> 100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo\n> 100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo2\n> 100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo3\n> 100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo4\n> 100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo5\n> 100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo6\n\nBoth schemes support aliasing. In the flat scheme you would create a\nsecond blob which contains the file and the aliased path name. When\nthe blob gets delta'd the second copy of the file will disappear.\n\nI'm not proposing a change to data being stored in git, it is a\nproposal to consider the impacts of how this data has been normalized\nin the data store.\n\n> > How this gets structured in the db is an independent question about\n> > how renames get detected on a commit. The current scheme for detecting\n> > renames by comparing diffs is working fine. The question is, once we\n> > detect a rename how should it be stored?\n> >\n> > Ignoring the performance impacts and looking at the problem from the\n> > set theory view point, should:\n> > the pathnames be in their own table with a row for each alias\n> > the pathnames be stored as an attribute of the blob\n> >\n> > Both of these are the same information, we're just looking at how\n> > things are normalized.\n> >\n> >\n>\n> --\n> Julian\n>\n> ---\n> \"You shouldn't make my toaster angry.\"\n> -- Household security explained in \"Johnny Quest\"\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"52497","messageId":"9e4733910709041044r71264346n341d178565dd0521@mail.gmail.com","threadId":"9778","inReplyTo":"7vtzqany0z.fsf@gitster.siamese.dyndns.org","subject":"Re: Git's database structure","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-09-04T17:44:47Z","receivedAt":"2007-09-04T17:44:47Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/4/07, Junio C Hamano wrote:\n> \"Jon Smirl\" writes:\n>\n> > Another way of looking at the problem,\n> >\n> > Let's build a full-text index for git. You put a string into the index\n> > and it returns the SHAs of all the file nodes that contain the string.\n> > How do I recover the path names of these SHAs?\n>\n> That question does not make much sense without specifying \"which\n> commit's path you are talking about\".\n>\n> If you want to encode such \"contextual information\" in addition\n> to \"contents\", you could do so, but you essentially need to\n> record commit + pathname + mode bits + contents as \"blob\" and\n> hash that to come up with a name.\n\nI left the details out of the full-text example to make it more\nobvious that we can't recover the path names.\n\nDoing this type of analysis may point out that even more fields are\nmissing from the blob table such as commit id.\n\nThe current data store design is not very flexible. Databases solved\nthe flexibility problem long ago. I'm just wondering if we should\nsteal some good ideas out of the database world and apply them to git.\nTen years from now we may have 100GB git databases and really wish we\nhad more flexible ways of querying them.\n\nThe reason databases don't encode the fields into the index is that\nyou can only have a single index on the table if you do that.\nDatabases do sometimes duplicate the field in both the index and the\ntable. Databases also have the property that indexes are just a cache\nand can be dropped at any time.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"52501","messageId":"20070904180429.GA626@glandium.org","threadId":"9778","inReplyTo":"9e4733910709041044r71264346n341d178565dd0521@mail.gmail.com","subject":"Re: Git's database structure","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2007-09-04T18:04:29Z","receivedAt":"2007-09-04T18:04:29Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Tue, Sep 04, 2007 at 01:44:47PM -0400, Jon Smirl wrote:\n> On 9/4/07, Junio C Hamano wrote:\n> > \"Jon Smirl\" writes:\n> >\n> > > Another way of looking at the problem,\n> > >\n> > > Let's build a full-text index for git. You put a string into the index\n> > > and it returns the SHAs of all the file nodes that contain the string.\n> > > How do I recover the path names of these SHAs?\n> >\n> > That question does not make much sense without specifying \"which\n> > commit's path you are talking about\".\n> >\n> > If you want to encode such \"contextual information\" in addition\n> > to \"contents\", you could do so, but you essentially need to\n> > record commit + pathname + mode bits + contents as \"blob\" and\n> > hash that to come up with a name.\n> \n> I left the details out of the full-text example to make it more\n> obvious that we can't recover the path names.\n> \n> Doing this type of analysis may point out that even more fields are\n> missing from the blob table such as commit id.\n> \n> The current data store design is not very flexible. Databases solved\n> the flexibility problem long ago. I'm just wondering if we should\n> steal some good ideas out of the database world and apply them to git.\n> Ten years from now we may have 100GB git databases and really wish we\n> had more flexible ways of querying them.\n> \n> The reason databases don't encode the fields into the index is that\n> you can only have a single index on the table if you do that.\n> Databases do sometimes duplicate the field in both the index and the\n> table. Databases also have the property that indexes are just a cache\n> and can be dropped at any time.\n\nThe big difference between a database and git is that a database is a\ngeneral purpose tool. git has a much more restricted scope. As such, it\ndoesn't need *that much* flexibility.\n\nMike\n"},{"id":"52502","messageId":"7v1wdenw4n.fsf@gitster.siamese.dyndns.org","threadId":"9778","inReplyTo":"9e4733910709041044r71264346n341d178565dd0521@mail.gmail.com","subject":"Re: Git's database structure","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-09-04T18:06:16Z","receivedAt":"2007-09-04T18:06:16Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Jon Smirl\" writes:\n\n> On 9/4/07, Junio C Hamano wrote:\n>> \"Jon Smirl\" writes:\n>>\n>> > Another way of looking at the problem,\n>> >\n>> > Let's build a full-text index for git. You put a string into the index\n>> > and it returns the SHAs of all the file nodes that contain the string.\n>> > How do I recover the path names of these SHAs?\n>>\n>> That question does not make much sense without specifying \"which\n>> commit's path you are talking about\".\n>>\n>> If you want to encode such \"contextual information\" in addition\n>> to \"contents\", you could do so, but you essentially need to\n>> record commit + pathname + mode bits + contents as \"blob\" and\n>> hash that to come up with a name.\n>\n> I left the details out of the full-text example to make it more\n> obvious that we can't recover the path names.\n>\n> Doing this type of analysis may point out that even more fields are\n> missing from the blob table such as commit id.\n\nQuite the contrary. You just illustrated why it is wrong to put\nanything but contents in the blob.\n\nThe specialized indexing is a different issue. If you want to\nhave a full text index to answer \"what paths in which commits\nhad this string?\", then your database table would have columns\nsuch as commit (sha-1), path (string) as values, indexed with\nthe search string.\n\nNow the current set of \"git\" operation does not need to answer\nthat query, so we do not build nor maintain such an index that\nnobody uses. But your application may benefit from such an\nindex, and as others said, nobody prevents you from building\none.\n"},{"id":"52504","messageId":"46DDA93F.7050009@op5.se","threadId":"9778","inReplyTo":"9e4733910709041030ye912369nd574a5f78d3f521b@mail.gmail.com","subject":"Re: Git's database structure","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2007-09-04T18:51:43Z","receivedAt":"2007-09-04T18:51:43Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Jon Smirl wrote:\n> \n> I'm not proposing a change to data being stored in git, it is a\n> proposal to consider the impacts of how this data has been normalized\n> in the data store.\n> \n\nBut to what end?\n\nWe all *know* the impacts:\n* Excellent performance at what it does now.\n* Currently zero capability to replace google as the #1 search engine.\n\nSince replacing google's db was never, and will never, be the goal of\ngit, what is it you wish to achieve? Seriously, I'm dying to know, so\nplease tell me. If you have already and I'm too daft to understand it,\nhumor me and reiterate :-)\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"52507","messageId":"3f4fd2640709041244s125f5988j1c2d28f06bfbe098@mail.gmail.com","threadId":"9778","inReplyTo":"20070904180429.GA626@glandium.org","subject":"Re: Git's database structure","fromName":"Reece Dunn","fromEmail":"msclrhd@googlemail.com","sentAt":"2007-09-04T19:44:49Z","receivedAt":"2007-09-04T19:44:49Z","isPatch":false,"sender":{"key":"msclrhd@googlemail.com","avatar":null},"body":"On 04/09/07, Mike Hommey wrote:\n> On Tue, Sep 04, 2007 at 01:44:47PM -0400, Jon Smirl wrote:\n> > The reason databases don't encode the fields into the index is that\n> > you can only have a single index on the table if you do that.\n> > Databases do sometimes duplicate the field in both the index and the\n> > table. Databases also have the property that indexes are just a cache\n> > and can be dropped at any time.\n>\n> The big difference between a database and git is that a database is a\n> general purpose tool. git has a much more restricted scope. As such, it\n> doesn't need *that much* flexibility.\n\nDatabases are designed to be efficient at storing and accessing large\namounts of data. The key thing about a database is that it does not\ntrack the *history* of the data it is storing. This is the main\nproblem with using a database as a metadata storage facility.\n\nModern source control systems such as Perforce (and possibly\nSubversion), use a database to track metadata such as branch/merge\nhistory, user data and so on. This, IMHO is a huge weakness of these\nSCM systems. It is impossible to fully roll back to a given point in\ntime, because that metadata is stored independently of the file\ncontent tracking.\n\nGit *is not a database*. This is fundamental to understanding how git\nworks. Git stores *all* of its data in a Directed Acyclic Graph (with\nthe exception of the pointers to tag and the current head of each\nbranch, that it stores locally in the .git directory). Read\nhttp://eagain.net/articles/git-for-computer-scientists/ for more\ninformation on this.\n\nWhat this means is that for any commit, git has all the information it\nneeds about the repository at that point in time. It doesn't need\nanything else. If you then store information in a database, you lose\nhaving the complete picture at any point in the history of the\nrepository.\n\n- Reece\n"},{"id":"52510","messageId":"e1dab3980709041317v35c1dab7wd5e6ac4f7292d522@mail.gmail.com","threadId":"9778","inReplyTo":"9e4733910709040919u3d252b91s2785ed4d20086c88@mail.gmail.com","subject":"Re: Git's database structure","fromName":"David Tweed","fromEmail":"david.tweed@gmail.com","sentAt":"2007-09-04T20:17:57Z","receivedAt":"2007-09-04T20:17:57Z","isPatch":false,"sender":{"key":"david.tweed@gmail.com","avatar":null},"body":"On 9/4/07, Jon Smirl wrote:\n> without building another mapping table or a brute force search. I keep\n> using Google as an example, Google is indexing hierarchical URLs but\n> they do not use a hierarchical index to do it.\n\nIt might help the discussion if you could point to a reference,\npreferably one that discusses the trade-offs in the design, with more\nconcrete details about what google or other search engines actually\ndo. It would be particularly useful if it addressed issues of\n\n1. the type of queries the representation is optimised for.\n2. consistency requirements. (Can a search engine use different data\nstructures if they improve average performance at the cost of\noccasional inconsistency/lossage?)\n\nFinally, this design space is not totally unexplored, for example,\n\nhttp://plan9.bell-labs.com/sys/doc/venti/venti.html\n\nAFAICS they only use SHA-1 for blocks within files (although this\nmight be misreading the paper) so presumably they'd have knowledge\nabout the trade-offs.\n\n-- \ncheers, dave tweed__________________________\ndavid.tweed@gmail.com\nRm 124, School of Systems Engineering, University of Reading.\n\"we had no idea that when we added templates we were adding a Turing-\ncomplete compile-time language.\" -- C++ standardisation committee\n"},{"id":"52519","messageId":"20070904212507.GA24434@thunk.org","threadId":"9778","inReplyTo":"9e4733910709041044r71264346n341d178565dd0521@mail.gmail.com","subject":"Re: Git's database structure","fromName":"Theodore Tso","fromEmail":"tytso@mit.edu","sentAt":"2007-09-04T21:25:08Z","receivedAt":"2007-09-04T21:25:08Z","isPatch":false,"sender":{"key":"tytso@mit.edu","avatar":"https://avatars.githubusercontent.com/u/51416?v=4"},"body":"On Tue, Sep 04, 2007 at 01:44:47PM -0400, Jon Smirl wrote:\n> The current data store design is not very flexible. Databases solved\n> the flexibility problem long ago. I'm just wondering if we should\n> steal some good ideas out of the database world and apply them to git.\n> Ten years from now we may have 100GB git databases and really wish we\n> had more flexible ways of querying them.\n\nDatabases solved the flexibility problem, at the cost of performance.\nAnd if you use full normalized form in your database scheme, it costs\nyou even more in performance, because of all of the joins that you\nneed in order get the information you need to do, you know, useful\nwork as opposed to database wanking.\n\nIf you take a look at the really big databases with super high\nperformance requirements, say like those used to managed airline\ntickets/reservation/fares, you will find that they are not normalized,\nand they are not relational; they can't afford to be. And if you take\na look at some of git competition that use relational databases to\nstore their SCM data, and take a look at how loooooong they they take\nto do even basic operations, I would say that the onus is on you to\nprove that normalization is actually a win in terms of real (not\ntheoretical) advantages, and that it doesn't cause performance to go\ninto the toilet.\n\nI think the fundamental disconnect here is that no one is buying your\nclaim that just because the data design is \"more flexible\" that this\nis automatically a good thing in and of itself, and we should even for\na moment, \"put performance aside\". \n\nI also don't think that attempting to force git's data structures into\ndatabase terms makes sense; it is much closer to an filesystem using\nan object based store --- and very few people except for folks like\nHans Resiers believes that Filesystems and Database should be\nunified....\n\n\t\t\t\t\t\t- Ted\n"},{"id":"52523","messageId":"9e4733910709041454i189e6629k78ddeb89797276b3@mail.gmail.com","threadId":"9778","inReplyTo":"20070904212507.GA24434@thunk.org","subject":"Re: Git's database structure","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-09-04T21:54:00Z","receivedAt":"2007-09-04T21:54:00Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/4/07, Theodore Tso wrote:\n> On Tue, Sep 04, 2007 at 01:44:47PM -0400, Jon Smirl wrote:\n> > The current data store design is not very flexible. Databases solved\n> > the flexibility problem long ago. I'm just wondering if we should\n> > steal some good ideas out of the database world and apply them to git.\n> > Ten years from now we may have 100GB git databases and really wish we\n> > had more flexible ways of querying them.\n>\n> Databases solved the flexibility problem, at the cost of performance.\n> And if you use full normalized form in your database scheme, it costs\n> you even more in performance, because of all of the joins that you\n> need in order get the information you need to do, you know, useful\n> work as opposed to database wanking.\n>\n> If you take a look at the really big databases with super high\n> performance requirements, say like those used to managed airline\n> tickets/reservation/fares, you will find that they are not normalized,\n> and they are not relational; they can't afford to be. And if you take\n> a look at some of git competition that use relational databases to\n> store their SCM data, and take a look at how loooooong they they take\n> to do even basic operations, I would say that the onus is on you to\n> prove that normalization is actually a win in terms of real (not\n> theoretical) advantages, and that it doesn't cause performance to go\n> into the toilet.\n>\n> I think the fundamental disconnect here is that no one is buying your\n> claim that just because the data design is \"more flexible\" that this\n> is automatically a good thing in and of itself, and we should even for\n> a moment, \"put performance aside\".\n\nIt is very easy to get bogged down in performance arguments on\ndatabase design when the correct answer is that there are always lots\nof different ways to achieve the same goal. I wanted to defer debating\nperformance until we closely looked at the relationships between the\ndata at an abstract level.\n\nSince git hasn't stored all of the fields in the object table (the\npath is encoded in the index) we are never going to be able to build\nan alternative way of indexing the object table. Not being able to\nbuild alternative indexes is likely to cause problems when the\ndatabase starts getting really big. Without an index every query that\ncan't use the path name index is reduced to doing full table scans.\n\nA few things that could benefit from alternative indexing, blame,\nfull-text search, automating the Maintainers file, etc.\n\nI'm just asking if we really want to make full table scans the only\npossible way to implement these types of queries. If the answer is no,\nthen let's first explore how to fix things at an abstract level before\ndiving into the performance arguments.\n\nAn obvious parallel from the file system world is the locate database\nand how it is forced to continuously rescan the file system and store\nfull path names.\n\n\n>\n> I also don't think that attempting to force git's data structures into\n> database terms makes sense; it is much closer to an filesystem using\n> an object based store --- and very few people except for folks like\n> Hans Resiers believes that Filesystems and Database should be\n> unified....\n>\n> - Ted\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"52545","messageId":"46DE5861.4050201@op5.se","threadId":"9778","inReplyTo":"9e4733910709041454i189e6629k78ddeb89797276b3@mail.gmail.com","subject":"Re: Git's database structure","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2007-09-05T07:18:57Z","receivedAt":"2007-09-05T07:18:57Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Jon Smirl wrote:\n> On 9/4/07, Theodore Tso wrote:\n>> On Tue, Sep 04, 2007 at 01:44:47PM -0400, Jon Smirl wrote:\n>>> The current data store design is not very flexible. Databases solved\n>>> the flexibility problem long ago. I'm just wondering if we should\n>>> steal some good ideas out of the database world and apply them to git.\n>>> Ten years from now we may have 100GB git databases and really wish we\n>>> had more flexible ways of querying them.\n>> Databases solved the flexibility problem, at the cost of performance.\n>> And if you use full normalized form in your database scheme, it costs\n>> you even more in performance, because of all of the joins that you\n>> need in order get the information you need to do, you know, useful\n>> work as opposed to database wanking.\n>>\n>> If you take a look at the really big databases with super high\n>> performance requirements, say like those used to managed airline\n>> tickets/reservation/fares, you will find that they are not normalized,\n>> and they are not relational; they can't afford to be. And if you take\n>> a look at some of git competition that use relational databases to\n>> store their SCM data, and take a look at how loooooong they they take\n>> to do even basic operations, I would say that the onus is on you to\n>> prove that normalization is actually a win in terms of real (not\n>> theoretical) advantages, and that it doesn't cause performance to go\n>> into the toilet.\n>>\n>> I think the fundamental disconnect here is that no one is buying your\n>> claim that just because the data design is \"more flexible\" that this\n>> is automatically a good thing in and of itself, and we should even for\n>> a moment, \"put performance aside\".\n> \n> It is very easy to get bogged down in performance arguments on\n> database design when the correct answer is that there are always lots\n> of different ways to achieve the same goal. I wanted to defer debating\n> performance until we closely looked at the relationships between the\n> data at an abstract level.\n> \n\nBut you cannot. Git is performance-critical, for the same reason every\nother performance-critical application is: It's a tool to save human\ntime. Linux development *could* be done using patchfiles by the bundle\nand masses of tarballs. It's just not the fastest way to do it, so enter\ngit, and lots of problems just go away. It's not the only way of doing\nit, but it saves time. If you were to add 2 seconds to each commit,\nthat's several months of developer time that is lost every day!\n\n\n> Since git hasn't stored all of the fields in the object table (the\n> path is encoded in the index) we are never going to be able to build\n> an alternative way of indexing the object table.\n\nWe can still build alternative indexes. They just have to be separate\nfrom the DAG and the current indexing scheme. Junio has pointed out\nways of doing this already.\n\n> Not being able to\n> build alternative indexes is likely to cause problems when the\n> database starts getting really big. Without an index every query that\n> can't use the path name index is reduced to doing full table scans.\n> \n\nI've said it before; The most common delimiter used today is paths. It's\na behaviour git was designed to handle well, because it *is* the most\ncommon way of limiting and separating content. It's not some random\nfluke that has made git perform very well on actions that commonly\nperformed in large scale software projects; Linus designed it that way\nfrom the start, and kudos to him for a job well done.\n\n> A few things that could benefit from alternative indexing, blame,\n> full-text search, automating the Maintainers file, etc.\n> \n\nYes, but getting rid of the tree objects and storing pathnames in\nblob objects would penalize log-viewing, diffs and merges, which\nare far more common operations than full-text searches in a software\nproject.\n\n> I'm just asking if we really want to make full table scans the only\n> possible way to implement these types of queries. If the answer is no,\n> then let's first explore how to fix things at an abstract level before\n> diving into the performance arguments.\n> \n\nPersonally, I really don't care. But you should really have read Junio's\nmail a bit more carefully. He explained about 'notes' that can be attached\nto commits and contain arbitrary data. By all means, create your indexes\nthere and use them for whatever you like, but leave the foundation on which\ngit was built *alone*. The design hasn't changed since April 2006 (subtrees\nwere introduced April 26, I think), because it's a *good* design.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"52582","messageId":"9e4733910709050641j34d58683ra72caa52c56cdf0f@mail.gmail.com","threadId":"9778","inReplyTo":"46DE5861.4050201@op5.se","subject":"Re: Git's database structure","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-09-05T13:41:26Z","receivedAt":"2007-09-05T13:41:26Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/5/07, Andreas Ericsson wrote:\n> Jon Smirl wrote:\n> > On 9/4/07, Theodore Tso wrote:\n> >> On Tue, Sep 04, 2007 at 01:44:47PM -0400, Jon Smirl wrote:\n> >>> The current data store design is not very flexible. Databases solved\n> >>> the flexibility problem long ago. I'm just wondering if we should\n> >>> steal some good ideas out of the database world and apply them to git.\n> >>> Ten years from now we may have 100GB git databases and really wish we\n> >>> had more flexible ways of querying them.\n> >> Databases solved the flexibility problem, at the cost of performance.\n> >> And if you use full normalized form in your database scheme, it costs\n> >> you even more in performance, because of all of the joins that you\n> >> need in order get the information you need to do, you know, useful\n> >> work as opposed to database wanking.\n> >>\n> >> If you take a look at the really big databases with super high\n> >> performance requirements, say like those used to managed airline\n> >> tickets/reservation/fares, you will find that they are not normalized,\n> >> and they are not relational; they can't afford to be. And if you take\n> >> a look at some of git competition that use relational databases to\n> >> store their SCM data, and take a look at how loooooong they they take\n> >> to do even basic operations, I would say that the onus is on you to\n> >> prove that normalization is actually a win in terms of real (not\n> >> theoretical) advantages, and that it doesn't cause performance to go\n> >> into the toilet.\n> >>\n> >> I think the fundamental disconnect here is that no one is buying your\n> >> claim that just because the data design is \"more flexible\" that this\n> >> is automatically a good thing in and of itself, and we should even for\n> >> a moment, \"put performance aside\".\n> >\n> > It is very easy to get bogged down in performance arguments on\n> > database design when the correct answer is that there are always lots\n> > of different ways to achieve the same goal. I wanted to defer debating\n> > performance until we closely looked at the relationships between the\n> > data at an abstract level.\n> >\n>\n> But you cannot. Git is performance-critical, for the same reason every\n> other performance-critical application is: It's a tool to save human\n> time. Linux development *could* be done using patchfiles by the bundle\n> and masses of tarballs. It's just not the fastest way to do it, so enter\n> git, and lots of problems just go away. It's not the only way of doing\n> it, but it saves time. If you were to add 2 seconds to each commit,\n> that's several months of developer time that is lost every day!\n>\n>\n> > Since git hasn't stored all of the fields in the object table (the\n> > path is encoded in the index) we are never going to be able to build\n> > an alternative way of indexing the object table.\n>\n> We can still build alternative indexes. They just have to be separate\n> from the DAG and the current indexing scheme. Junio has pointed out\n> ways of doing this already.\n>\n> > Not being able to\n> > build alternative indexes is likely to cause problems when the\n> > database starts getting really big. Without an index every query that\n> > can't use the path name index is reduced to doing full table scans.\n> >\n>\n> I've said it before; The most common delimiter used today is paths. It's\n> a behaviour git was designed to handle well, because it *is* the most\n> common way of limiting and separating content. It's not some random\n> fluke that has made git perform very well on actions that commonly\n> performed in large scale software projects; Linus designed it that way\n> from the start, and kudos to him for a job well done.\n\n\nThis is why I wanted to separate the abstract data structure design\ndiscussion from the performance one. In the flat design indexes are\nlike caches and can be created and destroyed. There will definitely be\nan index created on the the paths. This index will work like the\ncurrent tree nodes. The difference is that this index is a cache\nunlike the current tree nodes which are an immutable part of the the\ndata base.\n\nThe path name field needs to be moved back into the blobs to support\nalternative indexes. For example I want an index on the Signed-off-by\nfield. I use this index to give me the SHAs for the blobs\nSigned-off-by a particular person. In the current design I have no way\nof recovering the path name for these blobs other than a brute force\nsearch following every path looking for the right SHA.\n\n\n\n>\n> > A few things that could benefit from alternative indexing, blame,\n> > full-text search, automating the Maintainers file, etc.\n> >\n>\n> Yes, but getting rid of the tree objects and storing pathnames in\n> blob objects would penalize log-viewing, diffs and merges, which\n> are far more common operations than full-text searches in a software\n> project.\n>\n> > I'm just asking if we really want to make full table scans the only\n> > possible way to implement these types of queries. If the answer is no,\n> > then let's first explore how to fix things at an abstract level before\n> > diving into the performance arguments.\n> >\n>\n> Personally, I really don't care. But you should really have read Junio's\n> mail a bit more carefully. He explained about 'notes' that can be attached\n> to commits and contain arbitrary data. By all means, create your indexes\n> there and use them for whatever you like, but leave the foundation on which\n> git was built *alone*. The design hasn't changed since April 2006 (subtrees\n> were introduced April 26, I think), because it's a *good* design.\n>\n> --\n> Andreas Ericsson andreas.ericsson@op5.se\n> OP5 AB www.op5.se\n> Tel: +46 8-230225 Fax: +46 8-230231\n>\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"52585","messageId":"46DEC26E.7030809@op5.se","threadId":"9778","inReplyTo":"9e4733910709050641j34d58683ra72caa52c56cdf0f@mail.gmail.com","subject":"Re: Git's database structure","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2007-09-05T14:51:26Z","receivedAt":"2007-09-05T14:51:26Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Jon Smirl wrote:\n> \n> The path name field needs to be moved back into the blobs to support\n> alternative indexes. For example I want an index on the Signed-off-by\n> field. I use this index to give me the SHAs for the blobs\n> Signed-off-by a particular person. In the current design I have no way\n> of recovering the path name for these blobs other than a brute force\n> search following every path looking for the right SHA.\n> \n\nAh, there we go. A use-case at last :)\n\nSo now we have a concrete problem that we can formulate thus:\n\"How can one create a database listing the relationship between 'signers'\nand blobs?\"\n\nSo the second question: Do you seriously argue that git should take a\nhuge performance loss on its common operations to accommodate a need that\nI suspect very few people have?\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"52587","messageId":"9e4733910709050837o61a2dedfpc5f72a239b1cb8e3@mail.gmail.com","threadId":"9778","inReplyTo":"46DEC26E.7030809@op5.se","subject":"Re: Git's database structure","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-09-05T15:37:28Z","receivedAt":"2007-09-05T15:37:28Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/5/07, Andreas Ericsson wrote:\n> Jon Smirl wrote:\n> >\n> > The path name field needs to be moved back into the blobs to support\n> > alternative indexes. For example I want an index on the Signed-off-by\n> > field. I use this index to give me the SHAs for the blobs\n> > Signed-off-by a particular person. In the current design I have no way\n> > of recovering the path name for these blobs other than a brute force\n> > search following every path looking for the right SHA.\n> >\n>\n> Ah, there we go. A use-case at last :)\n>\n> So now we have a concrete problem that we can formulate thus:\n> \"How can one create a database listing the relationship between 'signers'\n> and blobs?\"\n>\n> So the second question: Do you seriously argue that git should take a\n> huge performance loss on its common operations to accommodate a need that\n> I suspect very few people have?\n\nWhy do you keep jumping to a performance loss? Both schemes will have\nan index based on paths. The problem is how those indexes are\nconstructed, not the existence of the index. Moving the paths into the\nblobs in no way prevents you from creating an index on that field.\n\nThe problem is that the SHAs have been intertwined with the tree\nnodes. This blending has made it impossible to create other indexes on\nthe blobs.\n\nThe path index in the flat scheme will probably look just like tree\nnodes do today but these new tree nodes won't be intertwined with the\nSHAs.\n\n\n>\n> --\n> Andreas Ericsson andreas.ericsson@op5.se\n> OP5 AB www.op5.se\n> Tel: +46 8-230225 Fax: +46 8-230231\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"52588","messageId":"Pine.LNX.4.64.0709051648400.3189@reaper.quantumfyre.co.uk","threadId":"9778","inReplyTo":"9e4733910709050837o61a2dedfpc5f72a239b1cb8e3@mail.gmail.com","subject":"Re: Git's database structure","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2007-09-05T15:54:50Z","receivedAt":"2007-09-05T15:54:50Z","isPatch":false,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"On Wed, 5 Sep 2007, Jon Smirl wrote:\n\n> On 9/5/07, Andreas Ericsson wrote:\n>> Jon Smirl wrote:\n>>>\n>>> The path name field needs to be moved back into the blobs to support\n>>> alternative indexes. For example I want an index on the Signed-off-by\n>>> field. I use this index to give me the SHAs for the blobs\n>>> Signed-off-by a particular person. In the current design I have no way\n>>> of recovering the path name for these blobs other than a brute force\n>>> search following every path looking for the right SHA.\n>>>\n>>\n>> Ah, there we go. A use-case at last :)\n\nBut not a brilliant one. You sign off on commits not blobs. So you go\nfrom the sign-off to paths, then to blobs. There is no need to go from\nblob to path unless you deliberately introduce such a need.\n\n>>\n>> So now we have a concrete problem that we can formulate thus:\n>> \"How can one create a database listing the relationship between 'signers'\n>> and blobs?\"\n>>\n>> So the second question: Do you seriously argue that git should take a\n>> huge performance loss on its common operations to accommodate a need that\n>> I suspect very few people have?\n>\n> Why do you keep jumping to a performance loss? Both schemes will have\n> an index based on paths. The problem is how those indexes are\n> constructed, not the existence of the index. Moving the paths into the\n> blobs in no way prevents you from creating an index on that field.\n\nBut moving the path into the blob _IS_ the perfomance hit. You lose the \nability to tell the two files have the same content _without even looking \nat the blob_. This is one of the core parts of making git operations \nblindingly fast. You can't throw that out, and then say that there is no \nperformance hit.\n\nYou keep talking about abstract database performance - but git is not an \nabstract database. It has very specific common usage patterns, and is \noptomisied to handle them.\n\n>\n> The problem is that the SHAs have been intertwined with the tree\n> nodes. This blending has made it impossible to create other indexes on\n> the blobs.\n>\n> The path index in the flat scheme will probably look just like tree\n> nodes do today but these new tree nodes won't be intertwined with the\n> SHAs.\n\nAnd you will have to prove that diff/merge etc. don't become very much \nslower before you get buy in.\n\n-- \nJulian\n\n ---\nMany receive advice, few profit by it.\n \t\t-- Publilius Syrus\n"},{"id":"52590","messageId":"9e4733910709050912i57ed7137o6abb02ee741d394b@mail.gmail.com","threadId":"9778","inReplyTo":"Pine.LNX.4.64.0709051648400.3189@reaper.quantumfyre.co.uk","subject":"Re: Git's database structure","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-09-05T16:12:28Z","receivedAt":"2007-09-05T16:12:28Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 9/5/07, Julian Phillips wrote:\n> On Wed, 5 Sep 2007, Jon Smirl wrote:\n>\n> > On 9/5/07, Andreas Ericsson wrote:\n> >> Jon Smirl wrote:\n> >>>\n> >>> The path name field needs to be moved back into the blobs to support\n> >>> alternative indexes. For example I want an index on the Signed-off-by\n> >>> field. I use this index to give me the SHAs for the blobs\n> >>> Signed-off-by a particular person. In the current design I have no way\n> >>> of recovering the path name for these blobs other than a brute force\n> >>> search following every path looking for the right SHA.\n> >>>\n> >>\n> >> Ah, there we go. A use-case at last :)\n>\n> But not a brilliant one. You sign off on commits not blobs. So you go\n> from the sign-off to paths, then to blobs. There is no need to go from\n> blob to path unless you deliberately introduce such a need.\n\nUse blame for an example. Blame has to crawl every commit to see if it\ntouched the file. It keeps doing this until it figures out the last\nauthor for every line in the file. Worse case blame has to crawl every\ncommit in the data store.\n\n> >>\n> >> So now we have a concrete problem that we can formulate thus:\n> >> \"How can one create a database listing the relationship between 'signers'\n> >> and blobs?\"\n> >>\n> >> So the second question: Do you seriously argue that git should take a\n> >> huge performance loss on its common operations to accommodate a need that\n> >> I suspect very few people have?\n> >\n> > Why do you keep jumping to a performance loss? Both schemes will have\n> > an index based on paths. The problem is how those indexes are\n> > constructed, not the existence of the index. Moving the paths into the\n> > blobs in no way prevents you from creating an index on that field.\n>\n> But moving the path into the blob _IS_ the perfomance hit. You lose the\n> ability to tell the two files have the same content _without even looking\n> at the blob_. This is one of the core parts of making git operations\n> blindingly fast. You can't throw that out, and then say that there is no\n> performance hit.\n>\n> You keep talking about abstract database performance - but git is not an\n> abstract database. It has very specific common usage patterns, and is\n> optomisied to handle them.\n>\n> >\n> > The problem is that the SHAs have been intertwined with the tree\n> > nodes. This blending has made it impossible to create other indexes on\n> > the blobs.\n> >\n> > The path index in the flat scheme will probably look just like tree\n> > nodes do today but these new tree nodes won't be intertwined with the\n> > SHAs.\n>\n> And you will have to prove that diff/merge etc. don't become very much\n> slower before you get buy in.\n>\n> --\n> Julian\n>\n> ---\n> Many receive advice, few profit by it.\n> -- Publilius Syrus\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"52595","messageId":"Pine.LNX.4.64.0709051823470.26016@reaper.quantumfyre.co.uk","threadId":"9778","inReplyTo":"9e4733910709050912i57ed7137o6abb02ee741d394b@mail.gmail.com","subject":"Re: Git's database structure","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2007-09-05T17:31:43Z","receivedAt":"2007-09-05T17:31:43Z","isPatch":false,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"On Wed, 5 Sep 2007, Jon Smirl wrote:\n\n> On 9/5/07, Julian Phillips wrote:\n>> On Wed, 5 Sep 2007, Jon Smirl wrote:\n>>\n>>> On 9/5/07, Andreas Ericsson wrote:\n>>>> Jon Smirl wrote:\n>>>>>\n>>>>> The path name field needs to be moved back into the blobs to support\n>>>>> alternative indexes. For example I want an index on the Signed-off-by\n>>>>> field. I use this index to give me the SHAs for the blobs\n>>>>> Signed-off-by a particular person. In the current design I have no way\n>>>>> of recovering the path name for these blobs other than a brute force\n>>>>> search following every path looking for the right SHA.\n>>>>>\n>>>>\n>>>> Ah, there we go. A use-case at last :)\n>>\n>> But not a brilliant one. You sign off on commits not blobs. So you go\n>> from the sign-off to paths, then to blobs. There is no need to go from\n>> blob to path unless you deliberately introduce such a need.\n>\n> Use blame for an example. Blame has to crawl every commit to see if it\n> touched the file. It keeps doing this until it figures out the last\n> author for every line in the file. Worse case blame has to crawl every\n> commit in the data store.\n\nAnd this is advantaged by having the path in the blob how? The important \ninformation here is knowing which commits touched the file - this \ninformation is expensive in git because it is snapshot based. You have to \ngo back through all the commits looking for changes to the given path. \nThe information you might want to cache is which commits touched the file, \nwhich you could do without changing the current data storage. Presumably \nyou are suggesting that such a cache would be cleaner with the filename in \nthe blob? Or do you think that it would somehow be faster to create? If \nso, how?\n\n-- \nJulian\n\n ---\nHumor in the Court:\nQ: (Showing man picture.) That's you?\nA: Yes, sir.\nQ: And you were present when the picture was taken, right?\n"},{"id":"52598","messageId":"20070905173912.GB3396@glandium.org","threadId":"9778","inReplyTo":"9e4733910709050912i57ed7137o6abb02ee741d394b@mail.gmail.com","subject":"Re: Git's database structure","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2007-09-05T17:39:12Z","receivedAt":"2007-09-05T17:39:12Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Wed, Sep 05, 2007 at 12:12:28PM -0400, Jon Smirl wrote:\n> On 9/5/07, Julian Phillips wrote:\n> > On Wed, 5 Sep 2007, Jon Smirl wrote:\n> >\n> > > On 9/5/07, Andreas Ericsson wrote:\n> > >> Jon Smirl wrote:\n> > >>>\n> > >>> The path name field needs to be moved back into the blobs to support\n> > >>> alternative indexes. For example I want an index on the Signed-off-by\n> > >>> field. I use this index to give me the SHAs for the blobs\n> > >>> Signed-off-by a particular person. In the current design I have no way\n> > >>> of recovering the path name for these blobs other than a brute force\n> > >>> search following every path looking for the right SHA.\n> > >>>\n> > >>\n> > >> Ah, there we go. A use-case at last :)\n> >\n> > But not a brilliant one. You sign off on commits not blobs. So you go\n> > from the sign-off to paths, then to blobs. There is no need to go from\n> > blob to path unless you deliberately introduce such a need.\n> \n> Use blame for an example. Blame has to crawl every commit to see if it\n> touched the file. It keeps doing this until it figures out the last\n> author for every line in the file. Worse case blame has to crawl every\n> commit in the data store.\n\nAnd why exactly would you need to change blobs to contain path for blame\nto be faster ?\n\nOr more generally, what, in the current way of git doing things,\nprevents you from adding an index to $THE_DATA_YOU_LIKE, exactly ?\n\n>From the very few use cases you've given, I see nothing preventing to\ncreate an additional index from the data git currently uses.\n\nMike\n"},{"id":"52627","messageId":"200709052052.07597.andyparkins@gmail.com","threadId":"9778","inReplyTo":"9e4733910709050641j34d58683ra72caa52c56cdf0f@mail.gmail.com","subject":"Re: Git's database structure","fromName":"Andy Parkins","fromEmail":"andyparkins@gmail.com","sentAt":"2007-09-05T19:52:06Z","receivedAt":"2007-09-05T19:52:06Z","isPatch":false,"sender":{"key":"andyparkins@gmail.com","avatar":null},"body":"On Wednesday 2007, September 05, Jon Smirl wrote:\n\n> The path name field needs to be moved back into the blobs to support\n> alternative indexes. For example I want an index on the Signed-off-by\n> field. I use this index to give me the SHAs for the blobs\n> Signed-off-by a particular person. In the current design I have no way\n> of recovering the path name for these blobs other than a brute force\n> search following every path looking for the right SHA.\n\nErm, if that's your only way then you designed your index incorrectly.\n\n 1. Signed-Off-By lines appear in commits, so your index should be an index\n of SOB name against commit hash\n 2. Lookup the commit for that commit hash. As usual this is blindlingly\n git-fastic.\n 3. That commit blob contains a tree hash. Look it up. As usual this is \n blindingly git-fastic\n 4. Start gathering blobs for that tree. Fast, fast, fast.\n 5. Any subtree objects you come across, goto 4.\n\nThis is not a brute force lookup and it's stuff that git is really good at \nanyway.\n\nI'm really not sure I see what problem you're trying to solve. Whatever \nindex you want, you could keep and maintain if you wanted to without \nimpacting git's core storage at all.\n\n\n\nAndy\n\n-- \nDr Andy Parkins, M Eng (hons), MIET\nandyparkins@gmail.com\n"},{"id":"52666","messageId":"ED15F422-C83D-4749-8B0A-24F862AB1940@mac.com","threadId":"9778","inReplyTo":"Pine.LNX.4.64.0709051823470.26016@reaper.quantumfyre.co.uk","subject":"Re: Git's database structure","fromName":"Kyle Moffett","fromEmail":"mrmacman_g4@mac.com","sentAt":"2007-09-06T01:27:20Z","receivedAt":"2007-09-06T01:27:20Z","isPatch":false,"sender":{"key":"mrmacman_g4@mac.com","avatar":null},"body":"On Sep 05, 2007, at 13:31:43, Julian Phillips wrote:\n> And this is advantaged by having the path in the blob how? The \n> important information here is knowing which commits touched the \n> file - this information is expensive in git because it is snapshot \n> based. You have to go back through all the commits looking for \n> changes to the given path. The information you might want to cache \n> is which commits touched the file, which you could do without \n> changing the current data storage. Presumably you are suggesting \n> that such a cache would be cleaner with the filename in the blob? \n> Or do you think that it would somehow be faster to create? If so, \n> how?\n\nThe only possible reason I can think of for moving data into the blob \nwould be to make a POSIX-compliant git-like filesystem, and EVEN THEN \nyou would NOT move the path out of the tree objects. In order to \nhave somewhat consistent inodes (and also for performance when \nchanging 4 bytes in a 40GB file) you would want to have 3 different \ntypes of \"inode\" objects:\n\n1) 4-64k of (metadata + filedata)\n2) 4-64k of (metadata + list of 4-64k filedata blobs)\n3) 4-64k of (metadata + list of 4-64k lists of filedata blobs)\n\nOn the other hand... that isn't GIT, it's something completely \ndifferent with a very different usage pattern and set of \nrequirements. And you still don't put the path name in the objects, \njust the permissions and other attributes/metadata.\n\n\nYou would of course want to better define those 4-64k limits for \nallocation and performance reasons, but a double-indirect table of \nSHA128s with 64kb chunks lets you address up to 1TB of file data, and \nfor each additional power-of-two increase in the chunk size you get 8 \ntimes the storage space. Furthermore, the actual double-indirect \ntables for an 8TB file using 128k chunks would be all of 64MB, for a \nmore reasonable 4GB file with 32k tables (max of 128GB) it would be \nmaybe 128kB of indirect SHA1 hash tables.\n\n\nCheers,\nKyle Moffett\n"},{"id":"52712","messageId":"46DFBF13.9040109@op5.se","threadId":"9778","inReplyTo":"9e4733910709050912i57ed7137o6abb02ee741d394b@mail.gmail.com","subject":"Re: Git's database structure","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2007-09-06T08:49:23Z","receivedAt":"2007-09-06T08:49:23Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Jon Smirl wrote:\n> On 9/5/07, Julian Phillips wrote:\n>> On Wed, 5 Sep 2007, Jon Smirl wrote:\n>>\n>>> On 9/5/07, Andreas Ericsson wrote:\n>>>> Jon Smirl wrote:\n>>>>> The path name field needs to be moved back into the blobs to support\n>>>>> alternative indexes. For example I want an index on the Signed-off-by\n>>>>> field. I use this index to give me the SHAs for the blobs\n>>>>> Signed-off-by a particular person. In the current design I have no way\n>>>>> of recovering the path name for these blobs other than a brute force\n>>>>> search following every path looking for the right SHA.\n>>>>>\n>>>> Ah, there we go. A use-case at last :)\n>> But not a brilliant one. You sign off on commits not blobs. So you go\n>> from the sign-off to paths, then to blobs. There is no need to go from\n>> blob to path unless you deliberately introduce such a need.\n> \n> Use blame for an example. Blame has to crawl every commit to see if it\n> touched the file. It keeps doing this until it figures out the last\n> author for every line in the file. Worse case blame has to crawl every\n> commit in the data store.\n> \n\nEstimated daily uses of git-blame, world-wide: few\nEstimated daily uses of git-{merge,diff}, worldwide: lots\n\nCode and benchmarks, or I'm not buying it.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"52716","messageId":"7vsl5sb1nd.fsf@gitster.siamese.dyndns.org","threadId":"9778","inReplyTo":"46DFBF13.9040109@op5.se","subject":"Re: Git's database structure","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-09-06T09:09:58Z","receivedAt":"2007-09-06T09:09:58Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Andreas Ericsson writes:\n\n> Estimated daily uses of git-blame, world-wide: few\n> Estimated daily uses of git-{merge,diff}, worldwide: lots\n\nWhich makes the author of git-blame weep X-<.\n\nThe real issue is that embedding pathname in blob does _not_\nhelp \"git blame\" but would actively hurt it. A file with the\nidentical contents moved between the parent to child commit\nshares the same blob object and same object name in the real\ngit. Jon's modified system that hashes pathname together with\nthe contents would have them as two completely unrelated objects\nwith different object names, which only means that even 100%\nsimilarity rename case becomes as expensive to find as renames\nof lower similarity, which needs to expand and look into blob\ncontents.\n"},{"id":"52732","messageId":"541BD0C7-3D71-4C60-A501-7055283635F2@wincent.com","threadId":"9778","inReplyTo":"7vsl5sb1nd.fsf@gitster.siamese.dyndns.org","subject":"Re: Git's database structure","fromName":"Wincent Colaiuta","fromEmail":"win@wincent.com","sentAt":"2007-09-06T11:03:16Z","receivedAt":"2007-09-06T11:03:16Z","isPatch":false,"sender":{"key":"greg@hurrell.net","avatar":"https://avatars.githubusercontent.com/u/7074?v=4"},"body":"El 6/9/2007, a las 11:09, Junio C Hamano escribió:\n\n> Andreas Ericsson writes:\n>\n>> Estimated daily uses of git-blame, world-wide: few\n>> Estimated daily uses of git-{merge,diff}, worldwide: lots\n>\n> Which makes the author of git-blame weep X-<.\n\nBut the few times when you do use git-blame (apart from when you use \nit out of sheer curiosity) it usually saves you backside (ie. when \nyou've located a problem in the code and you want to know the who/ \nwhat/when/why of the offending commit).\n\nCheers,\nWincent\n"},{"id":"52745","messageId":"Pine.LNX.4.64.0709061354180.28586@racer.site","threadId":"9778","inReplyTo":"9e4733910709050912i57ed7137o6abb02ee741d394b@mail.gmail.com","subject":"Re: Git's database structure","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-09-06T12:56:36Z","receivedAt":"2007-09-06T12:56:36Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 5 Sep 2007, Jon Smirl wrote:\n\n> On 9/5/07, Julian Phillips wrote:\n> > On Wed, 5 Sep 2007, Jon Smirl wrote:\n> >\n> > >> Ah, there we go. A use-case at last :)\n> >\n> > But not a brilliant one. You sign off on commits not blobs. So you \n> > go from the sign-off to paths, then to blobs. There is no need to go \n> > from blob to path unless you deliberately introduce such a need.\n> \n> Use blame for an example. Blame has to crawl every commit to see if it \n> touched the file. It keeps doing this until it figures out the last \n> author for every line in the file. Worse case blame has to crawl every \n> commit in the data store.\n\nBut you can add _yet another_ index to it, which can be generated on the \nfly, so that Git only has to generate the information once, and then reuse \nit later. As a benefit of this method, the underlying well-tested \nstructure needs no change at all.\n\nBTW could you please, please, please cut the quoted message that you are \n_not_ responding to? It really _wastes_ my time.\n\nCiao,\nDscho\n"},{"id":"52792","messageId":"46E0436E.9030504@midwinter.com","threadId":"9778","inReplyTo":"Pine.LNX.4.64.0709061354180.28586@racer.site","subject":"Re: Git's database structure","fromName":"Steven Grimm","fromEmail":"koreth@midwinter.com","sentAt":"2007-09-06T18:14:06Z","receivedAt":"2007-09-06T18:14:06Z","isPatch":false,"sender":{"key":"koreth@midwinter.com","avatar":"https://gravatar.com/avatar/71b4d2e8b62f168bdc9e9205341159e3567003b4f9e2127c617c5fa0a1f5bad2?d=mp&s=160"},"body":"Johannes Schindelin wrote:\n> But you can add _yet another_ index to it, which can be generated on the \n> fly, so that Git only has to generate the information once, and then reuse \n> it later. As a benefit of this method, the underlying well-tested \n> structure needs no change at all.\n> \n\nAnd in fact, you can do this today, without modifying git-blame at all, \nby (ab)using its \"-S\" option (which lets you specify a custom ancestry \nchain to search). By coincidence, I was just showing some people at my \noffice how to do this yesterday. I'll cut-and-paste from the email I \nsent them. I am not claiming this is nearly as desirable as a built-in, \nauto-updated secondary index, but it proves the concept, anyway.\n\nFast-to-generate version:\n\ngit-rev-list HEAD -- main.c | awk '{if (last) print last \" \" $0; \nlast=$0;}' > /tmp/revlist\n\nThis speeds things up a lot, because git blame doesn't have to examine \nother revisions:\n\ntime git blame main.c\n 1.56s user 0.30s system 99% cpu 1.868 total\ntime git blame -S /tmp/revlist main.c\n 0.21s user 0.03s system 96% cpu 0.249 total\n\nThe bad news is that generating that revision list is a bit slow, and if \nyou do it the naive way I suggested above, you can't use the rev list \nwith the -M option (to follow renames). The good news is that it's \npossible to have that too if you generate a list of revisions that \nincludes the renames:\n\n# Generate a list of all revisions in the right order (only need to do \nthis once, not once per file)\ngit rev-list HEAD > /tmp/all-revs\n# Generate a list of the revisions that touched this file, following \ncopies/renames.\n# Could do this in fewer commands but this is hopefully easier to follow.\ngit blame --porcelain -M main.c | \\\n egrep '^[0-9a-f]{40}' | \\\n cut -d' ' -f1 | \\\n fgrep -f - /tmp/all-revs | \\\n awk '{if (last) print last \" \" $0; last=$0;}' > /tmp/revlist\n\nThen -M is fast too:\n\ntime git blame -M main.c\n 1.72s user 0.27s system 89% cpu 2.219 total\ntime git blame -M -S /tmp/revlist main.c\n 0.29s user 0.03s system 93% cpu 0.341 total\n\nOddly, if you use the -S option, \"git blame -C\" actually gets \nsignificantly *slower*. I am not sure why.\n\n-Steve\n"},{"id":"52826","messageId":"46a038f90709061733s3b8f15b7se3e4002c1f69a04d@mail.gmail.com","threadId":"9778","inReplyTo":"9e4733910709050912i57ed7137o6abb02ee741d394b@mail.gmail.com","subject":"Re: Git's database structure","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2007-09-07T00:33:57Z","receivedAt":"2007-09-07T00:33:57Z","isPatch":false,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"On 9/6/07, Jon Smirl wrote:\n> Use blame for an example. Blame has to crawl every commit to see if it\n\nSure. Build a quick dedicated index for that and measure\n\n - cost (size and commit/fetch costs)\n - benefit\n - frequency of usage\n\ngit is a special-purpouse DB that does great for certain access\npatterns. Have a look at monotone for a design that looks a lot like\ngit but is backed by a general purpouse DB and does equally poorly for\nall access patterns ;-)\n\n> It keeps doing this until it figures out the last\n> author for every line in the file. Worse case blame has to crawl every\n> commit in the data store.\n\nYep. Can we get a minimal-cost index with just enough hints that can\nspeed up blame, and perhaps git log with/very/deep/path? Probably!\n\nThat's worth pursuing sure.\n\n\nmartin\n"}]}