Charlotte Webb wrote:

On 2/5/08, Tim Starling tstarling@wikimedia.org wrote:

...

Another way to find a previous revision is to order by rev_id. But rev_id is not monotonic with respect to time, due to various accidents of history. There are step discontinuities, such as those introduced by undeletion or the conversion script. It is however used by the older/newer links on the old revision views. This algorithm is chosen over the timestamp algorithm because at the time the revision is fetched, the timestamp is not known, only the rev_id is known. Finding out the timestamp would require an extra query.

I'm guessing a one-time re-assignment of rev_id's for edits older than [timestamp of most recent discontinuity] is out of the question :-)

Yes. :)

To summarize, there are several sources of discontinuity:

1) The old schema

Originally, all current revisions sat in the 'cur' table. Revision IDs were only assigned once another edit kicked it out of the current slot and moved it to the 'old' table.

As a result, revision IDs between _different_ pages from 2002-2005 have no clear time relationship.

Later merging of multiple pages could then make the order within a page's history inconsistent.

2) The double import from UseMod

Wikipedia originally ran on the perl-based UseModWiki software until the predecessor to MediaWiki went live in January 2002. The initial conversion only kept the *current* version of each page; older revisions were added some months later on another pass reading from an old backup.

As a result, revisions from before the conversion got revision IDs from the time of the later import.

They also would have no clear time relationship across multiple pages, as the convertor's progression was sorted first by page, then by revisions within each page.

3) Undeletion

Until 2006, revision IDs were not maintained across delete+undelete; undeleted revisions would be given fresh new IDs, regardless of their original timestamp.

4) Transwiki import

Pages moved across wikis through Special:Import or bulk imports (such as when moving pages off Incubator) are given fresh new local revision IDs, which do not relate to their timestamps.

5) Clock skew

Timestamps saved on revisions are made from the local clock on the web server front end. It sometimes happens that some machines have incorrectly set clocks; sometimes by a few seconds, sometimes by years (there was an incident with bad BIOS backing batteries and clocks that reset themselves to 2003).

In these rarer cases, the timestamp is "wrong" whereas the revision ID may be seen to show a more accurate picture of where in the sequence it belongs.

Some of these have been detected and cleaned up, but others will have incorrect timestamps in the logs forever.

This is really the only one that's *wrong* as such, and we may want to better protect against it in the future. One possible protection could be to use the database server's timestamp for things instead of the web front-end's, though that may complicate various things.

-- brion vibber (brion @ wikimedia.org)

Roan Kattouw wrote:

On this whole revid vs. timestamp thing: I think I read something a while ago (don't remember where) about adding rev_previd and rev_nextid fields, each pointing to the previous/next revision ID (unless of course it doesn't exist, in which case it would be NULL; does MySQL distinguish between NULL and 0, anyway?). This would make the prev/next links less expensive to generate (only one DB query rather than 3), but would cause an extra UPDATE when adding revisions; also, merging histories could become a nightmare: in a worst-case scenario, merging N revisions into a history of 2N revisions would cause all rows to be changed (3 times as many as is currently the case). Also, filling these fields for existing revisions would be a huge operation (maybe this could be done on the fly?).

There's been occasional talk, and at one point some code went in and I think got taken back out temporarily.

One thing to consider is that we could actually *indicate* those non-contiguous merged sections in some useful way, like a (shudder) tree view....... maybe.... sort of. :D

Everything gets horrifyingly ugly when you try to do anything other than straight timelines, though.

-- brion

Right now they're just inserted chronologically, which might not always make sense.

You're being kind (something I've never been accused of)... it never makes any sense at all... it's far easier than any of the alternatives, so I understand why it's done that way, but it doesn't make sense.

Magnus Manske wrote:

Just thinking out loud here...

If timestamps are not unique, and revisions might not be ordered, wouldn't ORDER BY revision GROUP BY timestamp order it by timestamp, and then by revision number if two or more identical timestamps are found?

That would get around the two-query issue. Or is that too expensive?

That should work reasonably well in theory, if there was an index for it; without an index I'm not convinced it'll sort efficiently. In theory it'd be simple as you'd only have to reorder small bits here and there in the stream, but the database may not know that. :)

-- brion

On Feb 5, 2008 2:29 PM, Roan Kattouw roan.kattouw@home.nl wrote:

does MySQL distinguish between NULL and 0, anyway?

Yes. Everything except Oracle does, as far as I know (and for Oracle maybe it's only empty strings that are NULL, I can't remember).

This would make the prev/next links less expensive to generate (only one DB query rather than 3), but would cause an extra UPDATE when adding revisions

Three very cheap selects versus one (since when do we need three selects for this anyway?) is not a big difference. Nor is an extra update in the extremely rare case of adding a new revision.

Also, filling these fields for existing revisions would be a huge operation (maybe this could be done on the fly?).

Probably not as big a deal as altering the table in the first place. :)

On Feb 5, 2008 2:51 PM, Brion Vibber brion@wikimedia.org wrote:

Everything gets horrifyingly ugly when you try to do anything other than straight timelines, though.

That's exactly what I always said to David about LQT. He's sticking to trees, and look where that's gotten. :P

On Feb 5, 2008 4:45 PM, Magnus Manske magnusmanske@googlemail.com wrote:

If timestamps are not unique, and revisions might not be ordered, wouldn't ORDER BY revision GROUP BY timestamp order it by timestamp, and then by revision number if two or more identical timestamps are found?

GROUP BY x ORDER BY y is a filesort in MySQL, always. No index use is possible for the sorting, in any version to date. You could, however, do ORDER BY rev_timestamp, rev_id. That would work with an appropriate index, one beginning with the columns needed for retrieval and ending with (rev_timestamp, rev_id), *if* the retrieval condition were appropriate -- no range scan on anything but rev_timestamp, and no range scan on rev_timestamp other than comparison, like no IN( ... ). Something of the pattern SELECT ... WHERE rev_page = X AND rev_timestamp >= Y ORDER BY rev_timestamp, rev_id would work as desired with an index on (rev_page, rev_timestamp, rev_id).

Note that I'm not sure if we want rev_timestamp > Y or rev_timestamp

= Y. Either one is, I think, actually wrong, in a case where you

have three values of (rev_id, rev_timestamp) like (1, 20080205000000), (2, 20080205000000), (3, 20080205000000), and are trying to find the revision before or after revision 2. I guess you would need WHERE rev_page = X AND (rev_timestamp > Y OR (rev_timestamp = Y AND rev_id > Z)). That would have to be rewritten as a UNION to permit index use before 5.0ish (and in 5.0ish still, unless you feel lucky), and I *think* the UNION would be perfectly efficient using the same index, but this is getting kind of hairy. :)

On Feb 5, 2008 5:26 PM, Thomas Dalton thomas.dalton@gmail.com wrote:

Can you not create a new index for it?

Every extra index means slower inserts and slower deletes. Unneeded indexes should be avoided. In this case, I wonder if it's not best to just do the logic in PHP in the extremely rare case where two revisions have the same timestamp, rather than adding what amounts to a penalty on *every single query on the revision table* of a particular form.