O plano de execução da consulta é horrível até que as estatísticas sejam atualizadas

Espero que vocês possam me ajudar aqui. Nosso aplicativo pesquisa uma tabela de mensagens a cada 3 segundos procurando notificações para enviar. Isso funciona bem em todos os nossos clientes (DB de locatário único), exceto um. Eles não terão atividade por 23 horas por dia e, em seguida, carregarão milhares de mensagens de uma só vez (mais de 3000). Em outros casos, esse volume não é nada e podemos lidar com ele facilmente, exceto que neste caso, a consulta SQL abaixo leva aproximadamente 30 segundos para ser executada e piora à medida que a fila faz backup enquanto faz uma atualização, exige um bloqueio exclusivo e portanto, bloqueando todas as outras consultas e, portanto, os problemas causam todos os tipos de estragos. Isso tudo é devido a um plano de consulta ruim.

Temos reindexação diária que é executada todas as manhãs às 5 da manhã (reorganizar < 30%, reconstruir > 30%, ignorar <5%), bem como atualizar estatísticas. Ambos são da solução de manutenção Ola Hallengren. Também estamos no SQL Server 2016 e totalmente atualizados (13.0.5492.2)

Eu não tenho os 2 planos à mão, mas basicamente o plano ruim vai e faz uma varredura completa da tabela MessagesSent (3,5 milhões de linhas).

Minha teoria é que, como a consulta não retorna nada o dia todo, certas partes não são executadas e, portanto, a consulta ruim é a consulta mais eficiente para SQL.

Isso continuará depois de liberar o plano para a consulta, pois apenas gera o mesmo plano, no entanto, quando eu ATUALIZAR STATISTICS na tabela MessagesSent, o bom plano é criado e tudo está íntegro, com a consulta sendo executada em cerca de 10-30ms.

Alguém sabe como posso ajustar isso para sempre usar o melhor plano, mesmo que não existam dados para a consulta retornar? Como um hotfix, adicionamos a opção recompilar ao aplicativo, mas não acho que seja a solução ideal para uma consulta que está sendo executada a cada 3 segundos.

Aqui está a consulta:

WITH TopMessage
    AS
    (
        SELECT TOP 1 ID, BatchID FROM MessagesSent 
        JOIN Units ON Unit = idUnit 
        WHERE   MessageDate <= GETDATE() 
          AND         Active = 'True' 
          AND         Status = 'Queued' 
          AND NOT(DialString = 'null') 
          AND           Unit = ('29') 
          AND System in ('SystemName', 'Q1', '') 
        ORDER BY 
            CASE 
                WHEN QPriority IS NULL 
                    THEN 
                        CASE 
                            WHEN DefaultPriority IS NULL 
                                THEN 999999 
                                ELSE DefaultPriority 
                        END
                 ELSE QPriority 
            END ASC,
            Retries ASC, 
            MessageDate ASC, 
            ID ASC
    ),
    BatchCalls
    AS
    (
        SELECT * FROM MessagesSent 
        WHERE (
                 (LEN(BatchID) > 0 
                  AND BatchID = (SELECT TOP 1 BatchID FROM TopMessage)
                 ) 
        OR ID = (SELECT TOP 1 ID FROM TopMessage)
        )
        AND Status = 'Queued' AND Active = 'True'
    )

    UPDATE BatchCalls
    SET LastUpdated = @dtNow
    OUTPUT INSERTED.*
    WHERE Status = 'Queued'

Muito obrigado pelo seu tempo e por procurar.