From: Jon Smirl <hidden> Date: 2016-06-15 22:43:33
Let's back up a little bit from "Caclulating tree node". What are the
elements of git's data structures?
Right now we have an index structure (tree nodes) integrated in to a
base table. Integrating indexing into the data is not normally done in
a database. Doing a normalization analysis like this may expose flaws
in the way the data is structured. Of course we may also decide to
leave everything the way it is.
What about the special status of a rename? In the current model we
effectively have three tables.
commit - a set of all SHAs in the commit, previous commit, comment, author, etc
blob - a file, permissions, etc.
file names - name, SHA
The file name table is encoded as an index and it has been
intermingled with the commit table.
Looking at this from a set theory angle brings up the question, do we
really have three tables and file names are an independent variable
from the blobs, or should file names be an attribute of the blob?
How this gets structured in the db is an independent question about
how renames get detected on a commit. The current scheme for detecting
renames by comparing diffs is working fine. The question is, once we
detect a rename how should it be stored?
Ignoring the performance impacts and looking at the problem from the
set theory view point, should:
the pathnames be in their own table with a row for each alias
the pathnames be stored as an attribute of the blob
Both of these are the same information, we're just looking at how
things are normalized.
--
Jon Smirl
jonsmirl@gmail.com
From: Andreas Ericsson <hidden> Date: 2016-06-15 22:43:33
Jon Smirl wrote:
Let's back up a little bit from "Caclulating tree node". What are the
elements of git's data structures?
Right now we have an index structure (tree nodes) integrated in to a
base table. Integrating indexing into the data is not normally done in
a database. Doing a normalization analysis like this may expose flaws
in the way the data is structured. Of course we may also decide to
leave everything the way it is.
What about the special status of a rename? In the current model we
effectively have three tables.
commit - a set of all SHAs in the commit, previous commit, comment, author, etc
blob - a file, permissions, etc.
file names - name, SHA
commit - SHA1 of its parent(s) and its root-tree, along with
author info and a free-form field
blob - content addressable by *multiple trees*
file names - List of path-names inside a tree object.
To draw some sort of relationship model here, you'd have
commit 1<->M roottree
tree M<->M tree
tree M<->M blob
Assuming SHA1 never collides (collisions rule out any form of storage,
so we might as well hope it never happens), that leaves us with this:
Each root tree can only ever belong to a single commit, unless you
intentionally force git to make completely empty commits. git
won't complain about this, so long as you don't make two in the
same second, because it relies more heavily on the DAG than on
developer sanity.
Each root tree can point to multiple sub-trees. The sub-trees can be
linked to any number of root-trees.
Blobs can be linked to any number of tree objects, or even multiple
times to the same tree object. This wouldn't be possible if the
blob objects had their own pathnames stored inside them, so to speak.
The file name table is encoded as an index and it has been
intermingled with the commit table.
Looking at this from a set theory angle brings up the question, do we
really have three tables and file names are an independent variable
from the blobs, or should file names be an attribute of the blob?
File names are not independant variables. They belong inside the
table created for them, which is the tree objects.
How this gets structured in the db is an independent question about
how renames get detected on a commit. The current scheme for detecting
renames by comparing diffs is working fine. The question is, once we
detect a rename how should it be stored?
Do you realize that you're contradicting yourself in two upon each
other following sentences here?
Detecting renames after the fashion works fine. Not storing them
is part of the "detect them by comparing diffs".
Ignoring the performance impacts and looking at the problem from the
set theory view point, should:
the pathnames be in their own table with a row for each alias
the pathnames be stored as an attribute of the blob
Both of these are the same information, we're just looking at how
things are normalized.
Except that
git init
echo foo > a
cp -a a b
git add .
git commit -m testing
git count-objects
yields 3 objects at the moment; A commit-object, a tree object and *one*
blob object. With your scheme the 2 blob objects would differ, and there
would be 4 of them. If you propose to ignore the path-name you have
effectively broken support for having two identical files with different
names in the same directory.
Now, can you please tell me what gains you're hoping to see with this
new layout of yours?
--
Andreas Ericsson andreas.ericsson@op5.se
OP5 AB www.op5.se
Tel: +46 8-230225 Fax: +46 8-230231
From: Mike Hommey <hidden> Date: 2016-06-15 22:43:33
On Tue, Sep 04, 2007 at 05:55:16PM +0200, Andreas Ericsson [off-list ref] wrote:
Each root tree can only ever belong to a single commit, unless you
intentionally force git to make completely empty commits. git
won't complain about this, so long as you don't make two in the
same second, because it relies more heavily on the DAG than on
developer sanity.
Actually, you don't need to be insane to have multiple commits pointing
at the same root tree. It is actually very easy:
- git clone
- do some stuff on your master branch and commit
- send your changes upstream
- upstream applies as is
- git pull
You now have everything merged, and the last commit on your master branch,
while being a different commit object due to its parenting, has the same
root tree as the tip of the remote branch.
Mike
From: Andreas Ericsson <hidden> Date: 2016-06-15 22:43:33
Mike Hommey wrote:
On Tue, Sep 04, 2007 at 05:55:16PM +0200, Andreas Ericsson [off-list ref] wrote:
quoted
Each root tree can only ever belong to a single commit, unless you
intentionally force git to make completely empty commits. git
won't complain about this, so long as you don't make two in the
same second, because it relies more heavily on the DAG than on
developer sanity.
Actually, you don't need to be insane to have multiple commits pointing
at the same root tree. It is actually very easy:
- git clone
- do some stuff on your master branch and commit
- send your changes upstream
- upstream applies as is
- git pull
You now have everything merged, and the last commit on your master branch,
while being a different commit object due to its parenting, has the same
root tree as the tip of the remote branch.
That explains why it felt so awkward writing that sentence. :)
Thanks for correcting me. Even so, one more M<->M relation-ship
certainly speaks for rather than against the current model.
--
Andreas Ericsson andreas.ericsson@op5.se
OP5 AB www.op5.se
Tel: +46 8-230225 Fax: +46 8-230231
From: Jon Smirl <hidden> Date: 2016-06-15 22:43:33
On 9/4/07, Andreas Ericsson [off-list ref] wrote:
Jon Smirl wrote:
quoted
Let's back up a little bit from "Caclulating tree node". What are the
elements of git's data structures?
Right now we have an index structure (tree nodes) integrated in to a
base table. Integrating indexing into the data is not normally done in
a database. Doing a normalization analysis like this may expose flaws
in the way the data is structured. Of course we may also decide to
leave everything the way it is.
What about the special status of a rename? In the current model we
effectively have three tables.
commit - a set of all SHAs in the commit, previous commit, comment, author, etc
quoted
blob - a file, permissions, etc.
file names - name, SHA
commit - SHA1 of its parent(s) and its root-tree, along with
author info and a free-form field
blob - content addressable by *multiple trees*
file names - List of path-names inside a tree object.
To draw some sort of relationship model here, you'd have
commit 1<->M roottree
tree M<->M tree
tree M<->M blob
By introducing tree nodes you have blended a specific indexing scheme
into the data. There are many other ways the path names could be
indexed hash tables, binary trees, etc.
This problem exists in files systems. Since the path names have been
encoded into the directory structures there is no way to query
something like "all files created yesterday" from a file system
without building another mapping table or a brute force search. I keep
using Google as an example, Google is indexing hierarchical URLs but
they do not use a hierarchical index to do it.
Databases keep the knowledge of how things are indexed out of the
data. A data structure analysis of git should remove the blended index
and start from the set theory.
Assuming SHA1 never collides (collisions rule out any form of storage,
so we might as well hope it never happens), that leaves us with this:
Each root tree can only ever belong to a single commit, unless you
intentionally force git to make completely empty commits. git
won't complain about this, so long as you don't make two in the
same second, because it relies more heavily on the DAG than on
developer sanity.
Each root tree can point to multiple sub-trees. The sub-trees can be
linked to any number of root-trees.
Blobs can be linked to any number of tree objects, or even multiple
times to the same tree object. This wouldn't be possible if the
blob objects had their own pathnames stored inside them, so to speak.
quoted
The file name table is encoded as an index and it has been
intermingled with the commit table.
Looking at this from a set theory angle brings up the question, do we
really have three tables and file names are an independent variable
from the blobs, or should file names be an attribute of the blob?
File names are not independant variables. They belong inside the
table created for them, which is the tree objects.
quoted
How this gets structured in the db is an independent question about
how renames get detected on a commit. The current scheme for detecting
renames by comparing diffs is working fine. The question is, once we
detect a rename how should it be stored?
Do you realize that you're contradicting yourself in two upon each
other following sentences here?
Detecting renames after the fashion works fine. Not storing them
is part of the "detect them by comparing diffs".
quoted
Ignoring the performance impacts and looking at the problem from the
set theory view point, should:
the pathnames be in their own table with a row for each alias
the pathnames be stored as an attribute of the blob
Both of these are the same information, we're just looking at how
things are normalized.
Except that
git init
echo foo > a
cp -a a b
git add .
git commit -m testing
git count-objects
yields 3 objects at the moment; A commit-object, a tree object and *one*
blob object. With your scheme the 2 blob objects would differ, and there
would be 4 of them. If you propose to ignore the path-name you have
effectively broken support for having two identical files with different
names in the same directory.
Now, can you please tell me what gains you're hoping to see with this
new layout of yours?
--
Andreas Ericsson andreas.ericsson@op5.se
OP5 AB www.op5.se
Tel: +46 8-230225 Fax: +46 8-230231
From: Jon Smirl <hidden> Date: 2016-06-15 22:43:33
Another way of looking at the problem,
Let's build a full-text index for git. You put a string into the index
and it returns the SHAs of all the file nodes that contain the string.
How do I recover the path names of these SHAs?
--
Jon Smirl
jonsmirl@gmail.com
From: Andreas Ericsson <hidden> Date: 2016-06-15 22:43:33
Jon Smirl wrote:
On 9/4/07, Andreas Ericsson [off-list ref] wrote:
quoted
Jon Smirl wrote:
quoted
Let's back up a little bit from "Caclulating tree node". What are the
elements of git's data structures?
Right now we have an index structure (tree nodes) integrated in to a
base table. Integrating indexing into the data is not normally done in
a database. Doing a normalization analysis like this may expose flaws
in the way the data is structured. Of course we may also decide to
leave everything the way it is.
What about the special status of a rename? In the current model we
effectively have three tables.
commit - a set of all SHAs in the commit, previous commit, comment, author, etc
blob - a file, permissions, etc.
file names - name, SHA
commit - SHA1 of its parent(s) and its root-tree, along with
author info and a free-form field
blob - content addressable by *multiple trees*
file names - List of path-names inside a tree object.
To draw some sort of relationship model here, you'd have
commit 1<->M roottree
tree M<->M tree
tree M<->M blob
By introducing tree nodes you have blended a specific indexing scheme
into the data. There are many other ways the path names could be
indexed hash tables, binary trees, etc.
This problem exists in files systems. Since the path names have been
encoded into the directory structures there is no way to query
something like "all files created yesterday" from a file system
without building another mapping table or a brute force search. I keep
using Google as an example, Google is indexing hierarchical URLs but
they do not use a hierarchical index to do it.
Pathnames are by far the most common search-/delimiting criteria for
git though, so I fail to see why this is a problem for you.
Databases keep the knowledge of how things are indexed out of the
data. A data structure analysis of git should remove the blended index
and start from the set theory.
Why? This is the core of the problem, really. You haven't specified a
single, real-life reason *why* it should be any other way than it
already is. It sounds a bit to me as if you've been to a really
inspiring seminar about "how database-like things *should* be done"
and then decided to go berserk on your favourite database-like thing,
which is git.
Code and benchmarks or bust. In the meantime, I'll settle for a recount
of what problems you're having with the current layout, or what gains
you're hoping to achieve with the new one. As it's the 3rd time I'm
asking, this'll be the last.
--
Andreas Ericsson andreas.ericsson@op5.se
OP5 AB www.op5.se
Tel: +46 8-230225 Fax: +46 8-230231
From: Andreas Ericsson <hidden> Date: 2016-06-15 22:43:33
Jon Smirl wrote:
Another way of looking at the problem,
Let's build a full-text index for git. You put a string into the index
and it returns the SHAs of all the file nodes that contain the string.
How do I recover the path names of these SHAs?
I wouldn't know, but presumably any table can have more than one column.
Is this a problem you face with git so often that it requires a complete
re-design of its very core?
--
Andreas Ericsson andreas.ericsson@op5.se
OP5 AB www.op5.se
Tel: +46 8-230225 Fax: +46 8-230231
From: Jon Smirl <hidden> Date: 2016-06-15 22:43:33
On 9/4/07, Andreas Ericsson [off-list ref] wrote:
Jon Smirl wrote:
quoted
Another way of looking at the problem,
Let's build a full-text index for git. You put a string into the index
and it returns the SHAs of all the file nodes that contain the string.
How do I recover the path names of these SHAs?
I wouldn't know, but presumably any table can have more than one column.
Is this a problem you face with git so often that it requires a complete
re-design of its very core?
That's the whole point. We need to discuss the impact of merging a
field (path names) with an index (tree nodes) has on future things we
may want to do with the data stored in git.
Databases don't usually blend fields/indexes without also duplicating
the field in the table. You need all the fields in the table so that
it is possible to create indexes on other fields.
--
Andreas Ericsson andreas.ericsson@op5.se
OP5 AB www.op5.se
Tel: +46 8-230225 Fax: +46 8-230231
From: Andreas Ericsson <hidden> Date: 2016-06-15 22:43:33
Jon Smirl wrote:
On 9/4/07, Andreas Ericsson [off-list ref] wrote:
quoted
Jon Smirl wrote:
quoted
Another way of looking at the problem,
Let's build a full-text index for git. You put a string into the index
and it returns the SHAs of all the file nodes that contain the string.
How do I recover the path names of these SHAs?
I wouldn't know, but presumably any table can have more than one column.
Is this a problem you face with git so often that it requires a complete
re-design of its very core?
That's the whole point. We need to discuss the impact of merging a
field (path names) with an index (tree nodes) has on future things we
may want to do with the data stored in git.
Yes, but as nobody seems to know what those future things are, it feels
rather pointless speculating about adding support to git for them. git
is a tool. It's a great one at that, because it was built to solve a
particular problem, which it does an amazing job at.
Other SCM's which had the potential to become amazingly good tools too
drowned somewhere between prototype and product in a sea of intellectual
masturbation, which had little to do with solving real-world problems.
--
Andreas Ericsson andreas.ericsson@op5.se
OP5 AB www.op5.se
Tel: +46 8-230225 Fax: +46 8-230231
From: Jeff King <hidden> Date: 2016-06-15 22:43:33
On Tue, Sep 04, 2007 at 12:19:33PM -0400, Jon Smirl wrote:
By introducing tree nodes you have blended a specific indexing scheme
into the data. There are many other ways the path names could be
indexed hash tables, binary trees, etc.
That is correct. However, given that indexing scheme, many of the common
operations just "fall out" simply and efficiently, without the need to
keep separate indices. So yes, git is geared towards a particular set of
operations.
Your complaint seems to be two-fold:
1. there is an inelegance in the blending of data and indexing. The
problem with changing this is:
a. we are all already using git, and it would require completely
re-vamping the core data structure
b. there is some feeling that the blending is necessary for
performance. Given the difficulty of (a), I think you would
have to provide compelling evidence (i.e., numbers) that a
git-like system based around set theory with separate indices
would perform as well.
2. you want perform some operations to which the hierarchy is not
well-suited. In this case, I think you can get by with the same
solution you have proposed already: indices external to the data
structure (in fact, this is exactly what Google is doing: taking
hierarchical URLs and indexing them in different ways).
Have you taken a look at the pack v4 work by Shawn and Nicolas? It
is an attempt to build such indices at pack time (but keeping the
core git data structure intact).
-Peff
Let's back up a little bit from "Caclulating tree node". What are the
elements of git's data structures?
Right now we have an index structure (tree nodes) integrated in to a
base table. Integrating indexing into the data is not normally done in
a database. Doing a normalization analysis like this may expose flaws
in the way the data is structured. Of course we may also decide to
leave everything the way it is.
What about the special status of a rename? In the current model we
effectively have three tables.
commit - a set of all SHAs in the commit, previous commit, comment, author, etc
blob - a file, permissions, etc.
file names - name, SHA
The file name table is encoded as an index and it has been
intermingled with the commit table.
Looking at this from a set theory angle brings up the question, do we
really have three tables and file names are an independent variable
from the blobs, or should file names be an attribute of the blob?
There isn't a one-to-one mapping of file names to blobs. The blob only
describes the contents of the file. In the extreme case you could have
one blob for every single file in your tree. For example:
# git ls-tree -r HEAD
100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c bar/foo
100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo
100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo2
100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo3
100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo4
100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo5
100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo6
How this gets structured in the db is an independent question about
how renames get detected on a commit. The current scheme for detecting
renames by comparing diffs is working fine. The question is, once we
detect a rename how should it be stored?
Ignoring the performance impacts and looking at the problem from the
set theory view point, should:
the pathnames be in their own table with a row for each alias
the pathnames be stored as an attribute of the blob
Both of these are the same information, we're just looking at how
things are normalized.
--
Julian
---
"You shouldn't make my toaster angry."
-- Household security explained in "Johnny Quest"
From: Jon Smirl <hidden> Date: 2016-06-15 22:43:33
On 9/4/07, Julian Phillips [off-list ref] wrote:
On Tue, 4 Sep 2007, Jon Smirl wrote:
quoted
Let's back up a little bit from "Caclulating tree node". What are the
elements of git's data structures?
Right now we have an index structure (tree nodes) integrated in to a
base table. Integrating indexing into the data is not normally done in
a database. Doing a normalization analysis like this may expose flaws
in the way the data is structured. Of course we may also decide to
leave everything the way it is.
What about the special status of a rename? In the current model we
effectively have three tables.
commit - a set of all SHAs in the commit, previous commit, comment, author, etc
blob - a file, permissions, etc.
file names - name, SHA
The file name table is encoded as an index and it has been
intermingled with the commit table.
Looking at this from a set theory angle brings up the question, do we
really have three tables and file names are an independent variable
from the blobs, or should file names be an attribute of the blob?
There isn't a one-to-one mapping of file names to blobs. The blob only
describes the contents of the file. In the extreme case you could have
one blob for every single file in your tree. For example:
# git ls-tree -r HEAD
100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c bar/foo
100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo
100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo2
100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo3
100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo4
100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo5
100644 blob 05303ef858aeeb01ca40590dd6fe65928096ee6c foo6
Both schemes support aliasing. In the flat scheme you would create a
second blob which contains the file and the aliased path name. When
the blob gets delta'd the second copy of the file will disappear.
I'm not proposing a change to data being stored in git, it is a
proposal to consider the impacts of how this data has been normalized
in the data store.
quoted
How this gets structured in the db is an independent question about
how renames get detected on a commit. The current scheme for detecting
renames by comparing diffs is working fine. The question is, once we
detect a rename how should it be stored?
Ignoring the performance impacts and looking at the problem from the
set theory view point, should:
the pathnames be in their own table with a row for each alias
the pathnames be stored as an attribute of the blob
Both of these are the same information, we're just looking at how
things are normalized.
--
Julian
---
"You shouldn't make my toaster angry."
-- Household security explained in "Johnny Quest"
From: Andreas Ericsson <hidden> Date: 2016-06-15 22:43:33
Jon Smirl wrote:
I'm not proposing a change to data being stored in git, it is a
proposal to consider the impacts of how this data has been normalized
in the data store.
But to what end?
We all *know* the impacts:
* Excellent performance at what it does now.
* Currently zero capability to replace google as the #1 search engine.
Since replacing google's db was never, and will never, be the goal of
git, what is it you wish to achieve? Seriously, I'm dying to know, so
please tell me. If you have already and I'm too daft to understand it,
humor me and reiterate :-)
--
Andreas Ericsson andreas.ericsson@op5.se
OP5 AB www.op5.se
Tel: +46 8-230225 Fax: +46 8-230231
From: David Tweed <hidden> Date: 2016-06-15 22:43:33
On 9/4/07, Jon Smirl [off-list ref] wrote:
without building another mapping table or a brute force search. I keep
using Google as an example, Google is indexing hierarchical URLs but
they do not use a hierarchical index to do it.
It might help the discussion if you could point to a reference,
preferably one that discusses the trade-offs in the design, with more
concrete details about what google or other search engines actually
do. It would be particularly useful if it addressed issues of
1. the type of queries the representation is optimised for.
2. consistency requirements. (Can a search engine use different data
structures if they improve average performance at the cost of
occasional inconsistency/lossage?)
Finally, this design space is not totally unexplored, for example,
http://plan9.bell-labs.com/sys/doc/venti/venti.html
AFAICS they only use SHA-1 for blocks within files (although this
might be misreading the paper) so presumably they'd have knowledge
about the trade-offs.
--
cheers, dave tweed__________________________
david.tweed@gmail.com
Rm 124, School of Systems Engineering, University of Reading.
"we had no idea that when we added templates we were adding a Turing-
complete compile-time language." -- C++ standardisation committee