Hi Vitaly and thanks for the idea.
The table contains 3.5M rows

create table test as select row_status from <src>
create bitmap index test_row_status_idx on test(row_status)

select top 10 ID from test where row_status in ('U','I') order by ID

0.579s

So most probably you are right and the table indeed has some issues with indexes

Done. Neither `collect statistics` nor `tune table` help. 

By the way, how normal is this? Index usage = 0 everywhere

Two times :( First this index, then the whole table too. Then I recreated the index as bitmap, rebuilt all indexes again - doesn't work