>> * You forgot to use
>> ORDER BY Column1, Column2
>> clause.
>>
>
> I've tried that already but it doesn't help much. I even tried forcing
> the plan by adding PLAN(my_table index my_index_name).

It is not question whether it helps much or not. Without ORDER BY
the query does not make sense at all.

Ivan