A PostgreSQL query causes the processor to drop to 100%. Given 90k records, is it worth 7,000 normally?

I am working on understanding how to use cost and actual time to optimize queries. My application is rails 3 with PostgreSQL 9.1 db. My request is used by Delayed_job:

EXPLAIN ANALYZE SELECT  "delayed_jobs".*
FROM "delayed_jobs"
WHERE ((run_at <= '2011-05-23 15:16:43.180810' AND (locked_at IS NULL OR locked_at < '2011-01-25 11:05:28.077144') OR locked_by = 'host:foo pid:2') AND failed_at IS NULL AND queue = 'authentication_emails')
ORDER BY priority ASC, run_at ASC LIMIT 5

Or:

EXPLAIN ANALYZE SELECT  "delayed_jobs".*
FROM "delayed_jobs"
WHERE ((run_at <= '2011-05-23 15:16:43.180810' AND (locked_at IS NULL OR locked_at < '2011-01-25 11:05:28.077144') OR locked_by = 'host:foo pid:2') AND failed_at IS NULL )
ORDER BY priority ASC, run_at ASC LIMIT 5

For the first request, the output is:

Limit  (cost=7097.57..7097.57 rows=1 width=1008) (actual time=35.657..35.657 rows=0 loops=1)
  ->  Sort  (cost=7097.57..7097.57 rows=1 width=1008) (actual time=35.655..35.655 rows=0 loops=1)
        Sort Key: priority, run_at
        Sort Method: quicksort  Memory: 25kB
        ->  Seq Scan on delayed_jobs  (cost=0.00..7097.56 rows=1 width=1008) (actual time=35.648..35.648 rows=0 loops=1)
              Filter: ((failed_at IS NULL) AND ((queue)::text = 'authentication_emails'::text) AND (((run_at <= '2011-05-23 15:16:43.18081'::timestamp without time zone) AND ((locked_at IS NULL) OR (locked_at < '2011-01-25 11:05:28.077144'::timestamp without time zone))) OR (locked_by = 'host:foo pid:2'::text)))
Total runtime: 35.695 ms

Currently, the table contains 90 thousand records and can vary from 0 to 200 thousand. We notice that this query causes the CPU to open and cause bottlenecks. What can be learned from the above information. Where should indexes be added, if any? Thanks

Database schema. The table has 0 indexes.

  create_table "delayed_jobs", :force => true do |t|
    t.integer  "priority",   :default => 0
    t.integer  "attempts",   :default => 0
    t.text     "handler"
    t.text     "last_error"
    t.datetime "run_at"
    t.datetime "locked_at"
    t.datetime "failed_at"
    t.text     "locked_by"
    t.datetime "created_at",                :null => false
    t.datetime "updated_at",                :null => false
    t.string   "queue"
  end