Hi!
I dont know very much about cursors, so, if I was in your place, I would try to nails the problem.

> The thing is sometime it will take 40 seconds to go through a 1 >million record table and sometime 5 minutes to go through 20 000 >records, that does not make sense.
> Any idea why the performance differ so much?

this could be by many things, including missuse of index, even in a select that show only one row (o.Ô). Are this tables in two distincts databases? if yes, can you provide gstat -h of both? (preffer of a working in progress) Also what is the version of your FB server/Clients?

>
> DECLARE STATUS_UPDATE CURSOR FOR (

Like I said, I don't understand many about cursors, but seems for me that you will do it throught all the table.

>
> SELECT (...)
> FROM FNDY_THRESHOLDS

this is a only one row table?

>...
> :T_ENSEMBLE;
> END
> CLOSE STATUS_UPDATE;
> EXECUTE PROCEDURE COUNT_RULE;

Hey!! theres another procedure here!! what it does? can you disable it and test again against the tables??

> DUMMY = GEN_ID(GEN_FNDY_NL,1);

why this all DUMMY? Does it do something in any place of the code?

> END^
> SET TERM ; ^

After reading your SP, i don't figured out why you dont used a UPDATE or a FOR SELECT loop.
I should change all your procedure by this update below, except by: I dont get why did you used CURSORS, why no a FOR SELECT?; I dont know why the dummy things; and what that procedure COUNT_RULE realy does?.
Said that, this UPDATE below should do the trick.

begin
SELECT FNDY_THRESHOLDS.CUTOFF_THRESHOLD,
FNDY_THRESHOLDS.LOWER_THRESHOLD,
FNDY_THRESHOLDS.UPPER_THRESHOLD
FROM FNDY_THRESHOLDS
INTO :T_CUTOFF_THRESHOLD,
:T_LOWER_THRESHOLD,
:T_UPPER_THRESHOLD;

UPDATE FNDY_LINK
SET STATUS =(case when (ENSEMBLE = 'N') THEN 'N'
when (TOTWGHT < T_LOWER_THRESHOLD) THEN 'R'
when (T_LOWER_THRESHOLD <= TOTWGHT AND TOTWGHT < T_UPPER_THRESHOLD) THEN 'P'
ELSE 'D'
end),
SOURCE='R';

end^

PS.: I haven't sure about what you are trying to get with this procedure, so maybe my code is not that usefull for you. And I don't tested the code above by now. Anyway, that kind of update could let you try it even out of the SP and see the plan that it use for any update. This may let you nails the problem.

WTH
regards,