Como você não tem uma chave única, use
ctid
:update medias m
set sort_order = new_sort_order
from (
select
ctid,
owner_user_id,
sort_order,
row_number() over w as new_sort_order
from medias
where visible
window w as (partition by owner_user_id order by sort_order asc, created_at asc)
) s
where m.ctid = s.ctid;
Observe,
row_number()
pode ser melhor que rank()
como o primeiro nunca dá duplicatas.