Re: [Monotone-devel] Suspend certs...

[Nathaniel Smith]

On Sun, Aug 12, 2007 at 10:27:02PM +1000, William Uther wrote:
> At the moment when erasing ancestry, we grab revisions in random  
> order, and find all their ancestors.  For most n.v.m branches, this  
> is going to mean traversing the entire n.v.m.* ancestry graph back to  
> the root.
> 
> My first thought was that we should use something like this sql I  
> posted before:
> 
> >SELECT revision_certs.id FROM revision_certs,
> >revision_ancestry                      // get the id of revs
> >   WHERE revision_certs.id =
> >revision_ancestry.child                                  // that  
> >are children in the ancestry table
> >   AND revision_certs.name = ? AND revision_certs.value
> >= ?                           // and are in the branch we're  
> >looking for
> >   AND revision_ancestry.child NOT
> >IN                                                 // and are not
> >      (SELECT revision_ancestry.parent FROM revision_ancestry,
> >revision_certs WHERE   // parents in the ancestry table
> >          revision_ancestry.child = revision_certs.id
> >AND                             // where the corresponding child's
> >branch
> >          revision_certs.name = ? AND revision_certs.value
> >= ?                        // is the branch we're looking for
> >      )
> 
> which tries to use SQL to find heads ignoring trust.  Once you have  
> those, search back from them to the first trusted rev in the  
> appropriate branch.  I think that should give you the heads, and in  
> most cases be quite efficient.  I couldn't convince myself that it  
> was 100% correct though (I could sorta prove it to myself, but it was  
> more complex than I wanted to trust).

What about discontiguous branches?  If you have A1 -> B1 -> A2, then
the above SQL will report both A1 and A2 as heads for branch A.

Dealing with that requires doing actual history traversal in any case,
and I don't know that history traversal is any slower than SQL tricks
will be anyway; remember that SQL is not magic, the database will just
convert it into some loops anyway.  (The big exception: when it can
take advantage of indexes.  I don't see that here.)

> The next thought was to use heights (as suggested in the comment).   
> That would stop short branches from iterating over the entire  
> ancestry.  I have a fairly busy week, and mtn ls branches is not  
> horrendous any more.  I'll look at it when I have time.

Yeah, I can see heights helping in the find-heads-of-everything case
for sure...

-- Nathaniel

-- 
So let us espouse a less contested notion of truth and falsehood, even
if it is philosophically debatable (if we listen to philosophers, we
must debate everything, and there would be no end to the discussion).
  -- Serendipities, Umberto Eco