Need advice to avoid ORDER BY

Hello,

I have one query in my postgresql 9.2.3 that took 137 ms to me executed
and looking a way
what I can do to optimize it. I have one table generated numbers from 1
to 1 000 000 and
I need to get first free id, meanwhile id's when is taken can be free
(deleted data and id
is free for next job). Table is simple:

id serial,
jobid text,
valids int default 0

(Yes, I have index).

my query is: SELECT jobid FROM mytable WHERE valids = 0 ORDER BY id ASC
LIMIT 1

I need the first id only.

My question is: Is there a way how I can avoid using ORDER BY to
receive the first
free id from mytable ?

Cheers,
Condor