Did you look at the query plan? How big is the table? Is r_lock_owner a
string? Is it indexed? Doing a not equals search on unindexed string columns can be very expensive.
Is workflow_id indexed? Which criteria is more selective? If you have unindexed columns, it might be cheaper to put the more selective criteria before the less selective criteria if you just look at the individual criteria, which criteria will return more rows. The criteria that returns less rows is more selective.
I would look at the query plan on a database populated with data first. The query plan will tell you what the database is doing. You can tweak your query.
Also, do you have a large number of lock owners on a workflow? It might be better to do a select count(r_lock_owner) than select r_lock_owner. It will reduce the network latency