Planos instáveis ​​quando duas primeiras colunas de índice têm valores NULL em todas as linhas

Tenho um caso estranho de uma consulta que demora para ser executada, apesar de ter um bom índice de correspondência. O problema é que os valores das 2 primeiras colunas em um índice não clusterizado são NULL em todas as linhas. (Para contexto, ficou assim depois de arquivar dados antigos de processos de negócios antigos). A consulta tem cláusula WHERE nessas 2 colunas usando igualdade e valores não NULL, portanto, deve ser fácil para o SQL Server preparar um bom plano usando index seek+lookup, especialmente porque os dados que estão sendo procurados não existem, então as estimativas são 0 ou 1 linha.

Infelizmente, a consulta é muito sensível a alterações na tabela, nem mesmo à atualização automática de estatísticas ou distorção de dados. Suspeito que pode ser um bug no otimizador, onde ele não pode fazer uso de histogramas de estatísticas de etapa única, onde NULL é o único valor no intervalo. Não tenho certeza se explorei todas as opções, portanto, gostaria que alguém desse uma olhada. O servidor de produção é 2017, mas preparei esta reprodução em 2022, e o comportamento é idêntico nessas 2 versões.

A tabela em produção contém 35 milhões de linhas e cerca de 60 colunas e está sendo atualizada (principalmente inserção+atualização) em cerca de 3.000 linhas em 1 hora, portanto, não há muito tráfego de gravação, principalmente leituras.

Tem alguma coisa que eu esqueci? Ou é um bug real?

Agradeço antecipadamente.

use tempdb;
go

-- The simplest repro of the issue.

-- Just in case you wondered if it's enabled. It's not needed, but included for your reference.
alter database tempdb set auto_create_statistics on;
alter database tempdb set auto_update_statistics on;

drop table if exists t1;

create table t1 (
  ID int identity(1,1) not null
      primary key clustered,
  c2 int null,
  c3 varchar(16) null,
  c4 int null,
  c5 varchar(128) null,
  -- in prod there are ~50 more columns
);


-- The actual prod index has 4 columns with explicit ID PK at the end.
create index ix_test on t1 (c2, c3, c4, ID);

-- The prod table contains ~35 million rows. The issue occurs with much smaller
-- number of rows so I only use 1 million here to not waste your time playing with it.
--
-- It happens that in prod all rows have NULL values in c2 and c3.
insert into t1 (c4, c5)
select top (1000*1000) crypt_gen_random(2), 'a'
from sys.all_columns ac1, sys.all_columns ac2;

-- At this point the query uses the index (see the plan).
declare @0 int = 100;      -- value that may or may not exist
select ID, c2, c3, c4, c5  -- and all remaining columns in prod
from t1
where c2 = @0 and c3 = 'x' -- 'x' is a value that may or may not exist
order by c2, c3, c4, ID;   -- this is the exact order of the index
go

-- But with "option (recompile)" it does the full scan of the clustered index
-- and has awful estimates.
declare @0 int = 100;
select ID, c2, c3, c4, c5
from t1
where c2 = @0 and c3 = 'x'
order by c2, c3, c4, ID
option (recompile);
go

-- The same issue also occurs when not using parameters.
select ID, c2, c3, c4, c5
from t1
where c2 = 100 and c3 = 'x'
order by c2, c3, c4, ID
option (recompile);

-- Now let's update statistics to be as great as possible.
update statistics t1 with fullscan, maxdop=1;

-- After which it picks the right index and have great estimates with or
-- without "option (recompile)".
declare @0 int = 100;
select ID, c2, c3, c4, c5
from t1
where c2 = @0 and c3 = 'x'
order by c2, c3, c4, ID
option (recompile);

-- Insert only a tiny bit of more data. It does not trigger auto update of the
-- statistics.
insert into t1 (c4, c5)
select top (10) 1, crypt_gen_random(2)
from sys.all_columns ac1, sys.all_columns ac2;

-- And now it again does the full scan even when not using the hint nor the
-- @parameter.
select ID, c2, c3, c4, c5
from t1
where c2 = 100 and c3 = 'x'
order by c2, c3, c4, ID;
go

-- If the above gave you seek+lookup, this one will not:
declare @0 int = 100;
select ID, c2, c3, c4, c5
from t1
where c2 = @0 and c3 = 'x'
order by c2, c3, c4, ID
option (recompile);

-- When using the index hint it works fine, but has awful estimates.
select ID, c2, c3, c4, c5
from t1
where c2 = 100 and c3 = 'x'
order by c2, c3, c4, ID
option (table hint (t1, index (ix_test)));

-- I would expect it to just always use the index seek + lookup. The query
-- should always be fast. It's easy to determine that there's no data
-- satisfying the filter.

-- When you check the stats histogram, there's none.
declare @stats_id int = (
  select stats_id from sys.stats
  where [object_id] = object_id('t1') and name = 'ix_test');
select * from sys.dm_db_stats_histogram(object_id('t1'), @stats_id);

/* In SSMS you can see that there's only 1 step:
Statistics for INDEX 'ix_test'.
-------------------------------------------------------------------------------------------------------------------
   Name             Updated     Rows   Rows Sampled   Steps  Density  Average Key Length  String Index
-------------------------------------------------------------------------------------------------------------------
ix_test   Sep 9 2024 4:59PM  1000000        1000000       1        0                   8            NO  1000000  0

 All Density  Average Length         Columns
--------------------------------------------
           1               0              c2
           1               0          c2, c3
1.525879E-05               4      c2, c3, c4
       1E-06               8  c2, c3, c4, ID

Histogram Steps
RANGE_HI_KEY  RANGE_ROWS  EQ_ROWS  DISTINCT_RANGE_ROWS  AVG_RANGE_ROWS
----------------------------------------------------------------------
                       0  1000000                    0               1

so the optimizer has the knowledge that all rows have NULL values, and
that there's nothing else in the table, it just is unable to use that
information in some cases.
*/

EDIT: Este é o plano de consulta ao usar OPTION (RECOMPILE):

e esse é o plano sem a dica. Eu perdi o fato de que ele foi parametrizado apesar de passar o valor literal na string: