ryandotsmith/queue_classic — Issue #19: optimizing lock_head: avoiding random offsets
Author: fdr
Created: 2011-11-11 00:22:58+00:00
State: open

LIMIT/OFFSET still has to scan all the tuples being skipped by OFFSET. That means read-only locks are taken (but those can be blocked by a concurrent UPDATE that touches the index) and additional tuples are scanned. This still is helpful because there's a good chance a worker will perform UPDATE on a tuple that is fairly "deep", but we could be much better.

My suggestion is to try using modulus and qualifying against the index. Unlike LIMIT/OFFSET, swathes of tuples can be skipped as those index pages will never be accessed. It has better concurrency characteristics and fetches fewer tuples, too. This requires each worker have a 'clock' value that increments, and ideally those clock numbers are well-distributed. As a degenerate case, consider the modulus of 1, which will always result in all workers always trying to lock the first element.

I suggest instead of using centralized coordination of the workers to parcel out their seed clock numbers to instead choose a random number in a large space (even, say a full uint32 range) and then do a random restart every few jobs to prevent systemic issues. The modulus can be tuned the same way the limit/offset can be, trading ordering for better concurrency.

It's hard to for me to foresee a metric -- besides some implementation complexity -- whereby this is not superior to random LIMIT/OFFSET in every way. (That doesn't mean such a trade-off does not exist, I just cannot predict it)