SQL Server - Update with Output not working in Parallel environment I know that the output parameter does not guarantees parallelism logic.
And the logic I want to implement is failing in a multi thread environment.

To test this, just open 2 windows and execute them side by side as fast as you can. Then compare the Ids, some will be duplicated.

declare @id int 
select @id = 1
while @id &gt;=1 and @id &lt;= 100
begin
    UPDATE sys_QueueJob
    SET StartedOn = GETDATE()
    OUTPUT DELETED.Id as Result
    WHERE Id = (select top 1 qj.Id 
                    from sys_QueueJob qj
                    where qj.ProcessedOn is null AND qj.StartedOn is null                                                   
                    order by CreatedOn asc)
    print 'Count: ' + convert(nvarchar(max), @id)
    select @id = @id + 1
end


I just want to get the oldest entry from the qeueJob table that has not yet being started and at the same time tell that now it has. And the same code needs to provide me 100% certainty that the next execution will give me the next correct Id.

How can I do this?
While I agree that "the sp_getapplock/sp_releaseapplock approach [is] the most straight forward and least dirty way to manage explicit semaphore logic."

There is a reason that's not working and a way to fix it directly, and enable multiple, concurrent transactions to simultaneously fetch disjoint rows:

This should fix it:

UPDATE sys_QueueJob
    SET StartedOn = GETDATE()
    OUTPUT DELETED.Id as Result
    WHERE Id = (select top 1 qj.Id 
                    from sys_QueueJob qj with (rowlock, updlock, readpast)
                    where qj.ProcessedOn is null AND qj.StartedOn is null                                                   
                    order by CreatedOn asc)


See Using Tables as Queues