Da minha perspectiva, seu servidor tem um sério problema de desempenho. Mesmo se assumirmos que nenhum dos registros na consulta
select some_col with (nolock) where id_col between 57000000 and 57001000
estava na memória, não deve demorar 21 segundos para ler as poucas páginas sequencialmente do disco (seu índice clusterizado no id_col não deve ser fragmentado se for uma identidade automática e você não fez algo estúpido como adicionar um "desc" para a definição de índice).
Mas se você não pode / não vai consertar isso, meu conselho seria fazer a atualização em pequenos pacotes como 100-1000 registros por vez (dependendo de quanto tempo a função de pesquisa consome). Uma atualização/transação não deve demorar mais de 30 segundos.
Você vê que cada atualização mantém um bloqueio exclusivo em todos os registros modificados até que a transação seja concluída. Se você não usar uma transação explícita, cada instrução será executada em um único contexto de transação automática, de modo que os bloqueios sejam liberados quando a instrução de atualização for concluída.
Mas você ainda pode encontrar deadlocks dessa maneira, dependendo do que os outros processos fazem. Se eles também modificarem mais de um registro por vez, ou mesmo se reunirem e manterem bloqueios de leitura em várias linhas, você poderá obter impasses.
Para evitar os deadlocks, sua instrução de atualização precisa bloquear todos os registros que ela modificará de uma só vez. A maneira de fazer isso é colocar a única instrução de atualização (com apenas algumas linhas limitadas pelo id_col) em uma transação serializável como
IF @@TRANCOUNT > 0
-- Error: You are in a transaction context already
SET NOCOUNT ON
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
-- Insert Loop here to work "x" through the id range
BEGIN TRANSACTION
UPDATE SOMETABLE
SET [some_col] = dbo.ufn_SomeFunction(CONVERT(NVARCHAR(500), another_column))
WHERE [some_col] = 243 AND id_col BETWEEN x AND x+500 -- or whatever keeps the update in the small timerange
COMMIT
-- Next loop
-- Get all new records while you where running the loop. If these are too many you may have to paginate this also:
BEGIN TRANSACTION
UPDATE SOMETABLE
SET [some_col] = dbo.ufn_SomeFunction(CONVERT(NVARCHAR(500), another_column))
WHERE [some_col] = 243 AND id_col >= x
COMMIT
Para cada atualização, isso exigirá um bloqueio de intervalo de chave de atualização/exclusivo nos registros fornecidos (mas apenas neles, porque você limita a atualização por meio da chave de índice clusterizado). Ele aguardará que quaisquer outras atualizações nos mesmos registros terminem, então obterá seu bloqueio (causando bloqueio para todas as outras transações, mas ainda apenas para os registros fornecidos), então atualizará os registros e liberará o bloqueio.
A última instrução extra é importante, porque levará um bloqueio de intervalo de chaves até "infinito" e, portanto, impedirá inserções uniformes no final do intervalo enquanto a instrução de atualização for executada.
