Is it normal for it to take up to a minute for an execution plan to be generated (even an estimated one) on simple queries?

Question

Once in a while (but uncommonly) my SQL server will take what seems like an odd amount of time to generate an execution plan. It just took 37 seconds to generate an estimated execution plan for the following fairly simple query:

SELECT *
FROM Table1
WHERE IndexedIntField1 = 12345
    AND NonIndexedVarcharField IN ('Value1', 'Value2', 'Value3')

The number of results from this query were roughly 500 rows (from a table that holds about 10 billion rows) and the execution plan was essentially a nonclustered index seek with a key look up.

Is this normal?

Edit:

• Table1 is an actual materialized regular disk-based table (nothing special going on here).
• It's about 30 columns wide.
• There's the 1 clustered index and 4 nonclustered indexes on it.
• The "IndexedIntField1" in my example is part of the index key in 2 of the nonclustered indexes, and is an included column on a third nonclustered index.
• "NonIndexedVarcharField" is not a key nor included on any of the indexes.
• We update statistics on the table and indexes at least once a week (and sometimes as much as once a day or more)
• No fancy calculated columns are on this table
• The indexes on the table are pretty simple, only a couple of fields in the key columns / included columns EXCEPT one of the indexes that have "IndexedIntField1" as a key column does include about 15 columns on it (so it's a rather unusually big index).

Answer 1

To process a query of this form:

SELECT *
FROM Table1
WHERE IndexedIntField1 = 12345
    AND NonIndexedVarcharField IN ('Value1', 'Value2', 'Value3')

The basic choices are to scan the whole table or to seek on IndexedIntField1, and then perform lookups for each row to see if the other predicate obtains. If there a lots of rows IndexedIntField1 = 12345 then the table scan will be much cheaper, and if there are very few then the index seek + bookmark lookup will be much cheaper.

If the statistics necessary to decide which plan to use don't exist or are out-of-date, then, by default, SQL Server will create or update the statistics before picking a query plan.

The Query Optimizer creates statistics for single columns in query predicates when AUTO_CREATE_STATISTICS is on.

https://learn.microsoft.com/en-us/sql/relational-databases/statistics/statistics?view=sql-server-ver15#CreateStatistics

and

AUTO_UPDATE_STATISTICS { ON | OFF } ON Specifies that Query Optimizer updates statistics when they're used by a query and when they might be out-of-date.

https://learn.microsoft.com/en-us/sql/t-sql/statements/alter-database-transact-sql-set-options?view=sql-server-ver15#auto_update_statistics

You can see the existing statistics and when they were updated like this:

select *, stats_date(s.object_id, s.stats_id) stats_date
from sys.stats s
where object_id = object_id('sales.salesorderdetail')