2 ms·
> but the worry here is with how sparse the id's might be, and the fact it might have to occasionally retry 20 times -- unpredictable performance characteristic
by gwern 3y ago
> but the worry here is with how sparse the id's might be, and the fact it might have to occasionally retry 20 times -- unpredictable performance characteristics like that aren't ideal.
Is this really a big deal? Surely for a SQL database, looking up the existence of a few IDs, just about the simplest possible set operation, is an operation measured in a fraction of a millisecond. Wikipedia is not that sparse, and a lookup of a few IDs in a call would easily bound it to a worst case of <10 calls and still just a millisecond or two.
- hddqsb 3y agoIt's not a big deal because there is no need to retry 20 times. The probability of getting a deleted article several times in a row is very low, so you could limit to e.g. 5 tries, and if all are deleted fall back to the next non-deleted article (or even a hard-coded article). The bias would be negligible assuming the proportion of deleted articles is low; to guarantee that it is low, one can periodically renumber to eliminated deleted articles (this can be done efficiently using the trick suggested by @munificent; but the naive O(n) approach would probably be good enough).