SELECT WHERE 'NOT LOCKED'?

In a very volatile table I have a list of actions which need to be
completed by external systems -- somewhat like a queue.  I'd like the
action row to be locked until it's completed so that multiple
processes chewing away at it won't try to complete the same external
action (easy enough -- exclusive lock on the row).

Now, ORDER BY random() requires a full sort on the table -- even with
LIMIT 1 in place which makes this operation quite heavy.  A plain
select attempts to grab the same row each time as the row is always at
the top.  Doing an update (to flag it) shouldn't be necessary and
isn't effective.

Ideally in my case, I could do:  SELECT * FROM junk WHERE 'ROW NOT
LOCKED' LIMIT 1

Anyway to fake this type of thing?  I've thought about SET TRANSACTION
ISOLATION LEVEL READ UNCOMMITTED (does that exist?), and doing an
update to a flag while it's locked.  Of course, I remove the row after
using it so that doesn't really affect anything.  What I do want
though is the action to become available again if something doesn't
complete.
--
Rod Taylor  BarChord Entertainment Inc.