La query più veloce per verificare l'esistenza di una riga in Oracle?

Usare COUNT(*) va bene se usi anche rownum=1:

declare
   l_cnt integer;
begin
   select count(*)
   into   l_cnt
   from   x
   where  x.col_a = value_a 
   and    x.col_b = value_b
   and    rownum = 1;
end;

Questo restituirà sempre una riga, quindi non è necessario gestire alcuna eccezione NO_DATA_FOUND. Il valore di l_cnt sarà 0 (nessuna riga) o 1 (esiste almeno 1 riga).