I think it's more likely to be the UDFs (assuming they are scalar) that are the problem with many rows, since UDFs are calculated for each row, effectively making the query incur a cursor-like performance penalty. This is a problem I frequently run into when investigating slow queries on large numbers of rows.

You can reduce ore eliminate the negative effect either by persisting and indexing the computed column (assuming the UDF is deterministic) or by using a different method. Using a view won't help if the view contains the same scalar UDF as the computed column.

Duncan