Mejorar cola de trabajos

Saludos lista

Tengo una implementación de una cola de trabajos en postgres muy similar a
https://www.pgcon.org/2016/schedule/track/Applications/929.en.html

La cola está dividida en dos partes

1. Tabla cola_cliente
2. Tabla cola_trabajo_cliente

create table cola_cliente
(
id bigserial not null,
id_cliente bigint not null,
prioridad int not null,
tomado timestamp,
ultima timestamp not null,
primary key(id),
UNIQUE (id_cliente)
);

create table cola_trabajo_cliente
(
id bigserial not null,
id_cliente bigint not null,
id_ticket int not null,
prioridad int not null,
intentos int not null,
tomado timestamp,
primary key(id),
UNIQUE (id_ticket)
);

El funcionamiento es el siguiente, tengo aprox. 5000 clientes donde cada
uno crea un trabajo (id_ticket), esos trabajos se realizan las siguientes
operaciones (validar, almacenar y enviar a un ente EXTERNO), se hace una
cola ya que ese ente EXTERNO(gobierno) demora su ejecución. Los clientes se
les informa que está listo su trabajo cuando complete las operaciones
(validar, almacenar).

cliente1 -> trab1_1 -> trab1_2 -> trab1_3
cliente2 -> trab2_1 -> trab2_2 -> trab2_2 -> trab2_3
cliente3 -> trab3_1 -> trab3_2

Los trabajos de los clientes deben enviarse uno a uno, porque hay
dependencias entre ellos, pero entre clientes se pueden enviar en paralelo.

Actualmente funciona con 100 workers, es decir, se puede procesar hasta 100
trabajos (de distintos clientes) al mismo tiempo.

Para evitar que dos o más workers tomen el mismo cliente y quieran procesar
el mismo trabajo, inicialmente hacía un bloqueo completo de la
*cola_trabajo_cliente*, buscaba cual tenía el campo tomado IS NULL y que
ese id_cliente no tuviese un trabajo en ejecución, generando unos terribles
tiempos de ejecución ya que para tener un acceso exclusivo a esa tabla
podría tomar hasta 20 seg.

Además hay días que pueden generarse hasta 200mil trabajos y la tabla
*cola_trabajo_cliente
*crecía mucho (500mil).

Tenía que usar estrictamente un bloqueo exclusivo ya que si usaba el modelo
de SELECT FOR UPDATE según el url inicialmente, me devolvía el siguiente
trabajo y ocurría que dos o más workers trabajaban sobre el mismo cliente.

Así que decidí usar un modelo con dos tablas. Donde si podía usar el SELECT
FOR UPDATE pero ahora en la tabla *cola_cliente*, tomo un cliente donde
tomado IS NULL lo cual se bloquea, y otro worker puede tomar otro cliente
donde tomado IS NULL haciendo un FOR UPDATE, para evitar el bloqueo
exclusivo uso SKIP LOCKED, donde me retorna el siguiente registro de un
cliente no bloqueado.

SELECT id_cliente INTO idcliente FROM *cola_cliente* where tomado IS NULL
ORDER BY prioridad DESC, ultima, id FOR UPDATE SKIP LOCKED;

Luego actualizo el cliente para asignar tomado con la fecha hora actual

UPDATE *cola_cliente* SET tomado=now(), ultima=now() WHERE
id_cliente=idcliente;

y tomo el siguiente trabajo de ese cliente de su cola.

SELECT id_ticket INTO idticket FROM *cola_trabajo_cliente* WHERE
id_cliente=idcliente AND tomado IS NULL ORDER BY prioridad DESC, id_ticket
LIMIT 1;

hay clientes que envían hasta 20mil trabajos, así que ellos tienen
prioridad sobre el resto, y también puede existir un trabajo prioritario
que no dependa de otros.

Cuando se pudo enviar al entre EXTERNO, se elimina de la *cola_trabajo_cliente
*y se libera el cliente

DELETE FROM *cola_trabajo_cliente* WHERE id_ticket=idticket;

UPDATE *cola_cliente* SET tomado=null where id_cliente=idcliente;

Pueden observar que la tabla *cola_cliente *se asigna tomado y última con
la fecha y hora actual, pero al liberar al cliente sólo se coloca NULL
sobre tomado, se hizo así para cuando se ordenen los clientes, primero son
los prioritarios y después por el campo última, así que un cliente atendido
es colocado al final para que el sistema tome otro cliente que lleva tiempo
sin atender.

Un poco largo pero fueron varias semanas de trabajo y ahora funciona con
mayor fluidez, no hay bloqueos exclusivos de las tablas y la cola permanece
en promedio 50mil registros en el día y el resto se procesa en la noche
donde no hay clientes enviando trabajos.

Necesito su ayuda para mejorar el modelo ya como menciona el el url,
soluciones como RabbitMQ / Redis no se adapta a los requerimientos.

he observado que al ejecutar los siguientes comandos se cancela porque
genera deadlock

UPDATE *cola_cliente *SET prioridad=0;

o
with prioritarios as
(select count(*) as cuantos, id_cliente from *cola_trabajo_cliente* group
by id_cliente*)*
update cola_cliente set prioridad=1 where id_cliente in (select id from
prioritarios where cuantos > 5000);

Día a día puedo cambiar la prioridad de un cliente, dependiendo de la
cantidad de trabajos en su cola

y por último

SELECT id_ticket INTO idticket FROM *cola_trabajo_cliente* WHERE
id_cliente=idcliente AND tomado IS NULL ORDER BY prioridad DESC, id_ticket
LIMIT 1;

cada vez que consulto el siguiente trabajo tengo que ordenar, en el peor de
los casos 20mil trabajos para devolver uno sólo.

Gracias.