Es probable que la tabla tenga triggers que sean los que relentizan el sistema. Para comprobarlo, desactivá los triggers asociados y cronometrá nuevamente.
Es probable también que haya una relación que no esté soportada con un índice. Interbase/Firebird crea automáticamente los índices necesarios cuando declaras un foreign key, pero recuerdo que es posible borrar estos, lo que obliga al sistema a hacer un full scan de la tabla cada vez que se comprueba la integridad.
Hasta luego.