68611 - store the "end of the dup chain" in the duplicates table

Status: NEW

(Bugzilla :: Bugzilla-General, enhancement, P3)

Description

[Andreas Franke (gone)]

Currently the "is-duplicate-of" relation is stored in the duplicates table,
but the transitive closure of this relation does not have a representation in
the database. This makes it impossible to query for open bugs where any bug in
the duplicate tree meets certain criteria (well, you can query for the
duplicates and then follow the duplicate chain for each bug, but that's kind of
inelegant :) 

Having the "end-of-the-chain" cached in the duplicates table would be a first
step towards fixing bug 24957 ("include duplicates in search").
Also, the following is a quote from a comment I made somewhere else:

> I think something like this would be [a better approximation for "relevant"]:
> 1.) open bugs
> 2.) recently fixed bugs (resolution=FIXED and resolution changed after ...)
> 3.) duplicates of (duplicates of) both 1.) and 2.)
> [...]
> The problem with this is obvious: Currently it seems to be impossible to 
> search for duplicates of (duplicates of) a subset of bugs (please correct me
> if I'm wrong). And even if this would be possible, I'm sure it would be dog
> slow (without doing massive changes to the database).

So why not start changing the database? 

I have thought a little how this could be done, and I'll post the results here
in a minute. Please review and comment. Thanks.

Comment 1

[Andreas Franke (gone)]

Attachment: RFC: thoughts and pseudo-code for duplicate chains etc.

Comment 2

[Matthew Tuck [:CodeMachine]]

Whoever does this would need to deal with the cache in a similar way that the
votes and keywords caches are dealt with on sanitycheck.cgi, ie check the cache
and allow it to be fixed.

Comment 3

[Dave Miller [:justdave]]

Taking all of cyeh's Bugzilla bugs.

Comment 4

[Andreas Franke (gone)]

I stronly hope that "Future" refers to the implementation of this, not to my
request for review and comments. Please confirm.

Comment 5

[Matthew Tuck [:CodeMachine]]

Yes.

Comment 6

[Dave Miller [:justdave]]

Reassigning all of my "future" targetted bugs to indicate that I'm not presently
working on them, and someone else could feel free to work on them. (sorry for
the spam if you got this twice, it didn't take right the first time)

Comment 7

[Dave Miller [:justdave]]

this needs sooner discussion than Future. grr

Comment 8

[Bradley Baetz (:bbaetz)]

Comment on attachment 25083 [details]
RFC: thoughts and pseudo-code for duplicate chains etc.

This looks really complicated, for a fairly unused use.

Plus, it also involes duplication of data, and this things can get out of sync.

Since this isn't being done as a speed issue (the chain length is one in most
places, remember), I think that the best way to handle it would be to use an
sql stored procedure to do the traversal. On dbs which support recursive
lookups (ie Oracle), we could just use that. For mysql, we could just not
support this feature, or only supportthe one level stuff. This is because its a
_lot_ of effort to do this, and more importantly to it correctly, for a minor
gain.

Comment 9

[Bradley Baetz (:bbaetz)]

Note, of course, that doing it via a stored proc means that for whatever side is
the 'end' of teh proc reqlly shouldn't have query qualifiers put against it,
only because if there are no predicates against the argument, then you'd run
this for every single bug in the db. If you do it the other way arround, then
perf should be fine.

Comment 10

[Myk Melez [:myk] [@mykmelez]]

Note bug 24957, which I think would be better off if this were fixed (see bug
24957, comment 30 in particular).  Note also bug 204209 about storing duplicates
in the bugs table.

Comment 11

[Stephen Lee]

Comment on attachment 25083 [details]
RFC: thoughts and pseudo-code for duplicate chains etc.

Just happened upon this while browsing....

... it seems to me the pseudo-code for deletion could be:

a)
DELETE FROM duplicates
WHERE duplicate=Dupe;

b)
push Dupe into DupeList

do
{
  SELECT duplicate FROM duplicates
  WHERE duplicate-of IN DupeList
    AND duplicate NOT IN DupeList;

  push all returned results into DupeList
} while (results were returned);

UPDATE duplicates
SET end-of-chain = Dupe
WHERE duplicate IN DupeList;


This does not require any additional column besides the end-of-chain, and would
seem to me to be pretty fast.

Comment 12

[Stephen Lee]

To initialise the end-of-chain column on an existing installation when 
upgrading, the code needs to cope with any existing duplicate loops...

suggest something like:

UPDATE duplicates
SET end-of-chain = duplicate-of;

followed by a loop like:

do
{
  SELECT d1.duplicate Dupe, d2.duplicate-of NextInChain
  FROM duplicates d1, duplicates d2
  WHERE d1.end-of-chain = d2.duplicate
    AND d2.duplicate != d2.end-of-chain;

  for each item returned:
    UPDATE duplicates
    SET end-of-chain = NextInChain
    WHERE duplicate = Dupe;

} while (at least one item was returned.)


This will result in end-of-chain = self for bugs in a dupe loop, giving a nice 
easy way to check for such loops! :-)


Bugs which are marked as a duplicate of a bug in a dupe loop will have end-of-
chain equal to one of the bugs in the loop, but it is not well defined which 
one.

This would all get fixed up by the pseudo-code in comment 11 when one of the 
bugs in the dupe loop was reopened.

Comment 13

[Matthew Tuck [:CodeMachine]]

Don't we already do transitive closure for group inheritance?  I imagine that
one set of code for transitive closure caches could reduce the sync problems
somewhat, since one lot of code means only one lot of bugs.

Sure, transitive lookup would definitely be great if it's supported, but what
would the performance be like?

Comment 14

[Matthew Tuck [:CodeMachine]]

I had a brief skim over the pseudo code cause it's a bit too late at night to do
anything more in depth.

Storing a whole chain to handle deletion (reopening) probably makes your SQL
easier, but it probably won't make your performance much better.  Given you need
to use a contains search, you're not going to be able to use an index and hence
it's still going to be slow.

A separate table would be better than that, since you can do searches faster.  I
don't know, but if you maintain an entire transitive closure rather than just
end-of-chain data you might be able to rebuild it faster (and it might well be
useful for other things too).  But I have to read further as to the techniques
being proposed.  My head hurts ...

Comment 15

[Stephen Lee]

The premise for the over-complicated designs involving storing the entire chain 
is in the section:

:   b) other rows will have to be updated:
:   Unfortunately, with this design we 
:   would have to re-compute all (!) 
:   duplicate-chains now in order to know 
:   which rows are affected. 


... which I believe to be incorrect, as per my comment 11. Did I miss something 
important here?

Comment 16

[Dave Miller [:justdave]]

Bugzilla 2.20 feature set is now frozen as of 15 Sept 2004.  Anything flagged
enhancement that hasn't already landed is being pushed out.  If this bug is
otherwise ready to land, we'll handle it on a case-by-case basis, please set the
blocking2.20 flag to '?' if you think it qualifies.

Comment 17

[Dave Miller [:justdave]]

Comment on attachment 25083 [details]
RFC: thoughts and pseudo-code for duplicate chains etc.

Several people appear to have reviewed this already based on the comments on
the bug, just not the named people.  We shouldn't let that hold it up.	We have
lots of smart people around these days ;)

Comment 18

[Frédéric Buclin]

The trunk is now frozen to prepare Bugzilla 2.22. Enhancement bugs are retargetted to 2.24.

Comment 19

[Frédéric Buclin]

We are freezing the code for 3.0 in two weeks and we don't expect this bug to be fixed on time.