When does SQL Server determine to use a new index?

I have been performing some maintenance on a server that runs some software the company bought, so I can't really change how the queries have been written. I have used some tools to determine some of the missing indexes on the server. Using my tools, though, I didn't see which queries were indicating these. I do, however, monitor how much the indexes are being written and read.

So, my question is, when adding new indexes that have been determined as missing, when does SQL Server notice the new indexes and determines whether they actually help the query? Is it immediately after the index is created and the query is ran again, or is it more complicated?

when does SQL Server notice the new indexes and determines whether they actually help the query?

Immediately. Creating an index causes a recompile because of a schema change.

Here's an illustration of this. First to setup the objects in the test database:

use TestDatabase;
go

if exists (select 1 from sys.tables where object_id = object_id('dbo.TestTable1'))
    drop table dbo.TestTable1;
create table dbo.TestTable1
(
    Id int identity(1, 1) not null
);
go

insert into dbo.TestTable1
default values;
go 1000

if exists (select 1 from sys.procedures where object_id = object_id('dbo.GetIdFromTestTable1'))
    drop proc dbo.GetIdFromTestTable1;
go
create proc dbo.GetIdFromTestTable1
    @Id int
as
    select Id
    from dbo.TestTable1
    where Id = @Id;
go

As you would expect, running this stored procedure would result in a table scan:

exec dbo.GetIdFromTestTable1 500;
go

Now let's create an index that we know this query can benefit from:

create unique index IX_TestTable1_Id
on dbo.TestTable1 (Id);
go

Re-execute the stored procedure and take a look at the post-execution plan:

exec dbo.GetIdFromTestTable1 500;
go

We can see that our table scan turned into an index seek. This shows that a new plan was generated.

Why?

We can trace this behavior with an XEvents session:

if exists (select 1 from sys.server_event_sessions where name = N'RecompileTracing')
    drop event session RecompileTracing
    on server;
go
create event session RecompileTracing
on server
add event sqlserver.sql_statement_recompile
(
    set
        collect_statement = 1,
        collect_object_name = 1
)
add target package0.event_file
(
    set
        filename = N'RecompileTracing.xel'
);
go

alter event session RecompileTracing
on server
state = start;
go

/*
alter event session RecompileTracing
on server
state = stop;
go

drop event session RecompileTracing
on server;
go
*/

The output we get from the above illustration/repro is that we had a sql_statement_recompile on the statement select Id from dbo.TestTable1 where Id = @Id; (condensed with removed whitespaces/tabs/newlines) and the recompile_cause is Schema changed.

StackExchange Database Administrators Q#89213, answer score: 8