>Naomi,
>If you have correct indexes, then
> the problem is in the backstage.
>Have you RI code that is performed ?

I re-indexed all tables yesterday and I switched from UPDATE to REPLACE WHILE. I have lots of RI, but they are executed only when I'm doing tableupdate (and that's why my tableupdate took ~ 1min. for 15K records in ~7 tables). The total execution time is now down to ~4 minutes for 15K records, which I think is good enough and can be accepted.