Database : SQL Server 12.0.5207

I have several queries which are exactly the same in all ways except for the value of one of the filter terms. Same table (not a copy of the schema on another server), therefor same indexes, resources, etc. Everything is absolutely IDENTICAL.


    This Query runs in under one second … 
    
    SELECT 
             MAX(MessageID) AS [MaxID]
    FROM BoothComm.UniversalMessageQueue
    WHERE 
           MessagePlatform = 'linux'
    
    
    
    This Query runs in under one second … 
    
    SELECT 
             MAX(MessageID) AS [MaxID]
    FROM BoothComm.UniversalMessageQueue
    WHERE 
           MessagePlatform = 'linux'
           AND
           MessageCategory = 'accounting'
    
    
    
    This Query runs in under one second … 
    
    SELECT 
             MAX(MessageID) AS [MaxID]
    FROM BoothComm.UniversalMessageQueue
    WHERE 
           MessagePlatform = 'windows'
    
    
    
    So why does THIS one take nearly 30 seconds to run?
    
    SELECT 
             MAX(MessageID) AS [MaxID]
    FROM BoothComm.UniversalMessageQueue
    WHERE 
           MessagePlatform = 'windows'
           AND
           MessageCategory = 'accounting'

 
A colleague of mine added another index to the table which resolved the *business* problem of latency. This index reduced 30 seconds to a FULL second while speeding the other queries up to instantaneous. Again, execution plans are exactly the same ... 

https://www.brentozar.com/pastetheplan/?id=r1rVxaCqZ

(Index Scan should be 100%). I have taken advice from other forums and made sure that the column order in the query matched the order that they are stored in the index...

    CREATE NONCLUSTERED INDEX [MessageID and Platform and Category] ON [BoothComm].[UniversalMessageQueue]
    (
    	[MessageID] ASC,
    	[MessagePlatform] ASC,
    	[MessageCategory] ASC
    )WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
    GO

 I am also providing the table schema in the event that that is helpful. 

    CREATE TABLE [BoothComm].[UniversalMessageQueue](
    	[MessageQueueId] [bigint] IDENTITY(1,1) NOT NULL,
    	[MessageID] [bigint] NOT NULL,
    	[MessagePlatform] [nvarchar](50) NULL,
    	[AssetNumber] [nvarchar](50) NOT NULL,
    	[MessageState] [int] NULL,
    	[MessageStateLabel] [nvarchar](50) NULL,
    	[MessageType] [int] NULL,
    	[MessageTypeLabel] [nvarchar](50) NULL,
    	[MessageCategory] [nvarchar](50) NULL,
    	[MessageSource] [int] NULL,
    	[MessageSourceLabel] [nvarchar](50) NULL,
    	[MessageSourceSerialNumber] [nvarchar](50) NULL,
    	[MessageCreateDate] [datetime] NULL,
    	[MessageTransmitDate] [datetime] NULL,
    	[MessageReceivedDate] [datetime] NULL,
    	[MessageStoredDate] [datetime] NULL,
    	[XMLPayload] [nvarchar](max) NULL,
    	[JSONPayload] [nvarchar](max) NULL,
    	[SemanticXML] [nvarchar](max) NULL,
    	[SemanticJSON] [nvarchar](max) NULL,
    	[MessageSequenceNumber] [int] NULL,
    	[ERPImportDate] [datetime] NULL,
    	[ERPImportStatus] [int] NULL,
    	[ERPMsg] [nvarchar](max) NULL,
    	[NormalizationDate] [datetime] NULL,
    	[NormalizationStatus] [int] NULL,
    	[NormalizationDesc] [nvarchar](max) NULL,
    	[SemanticDate] [datetime] NULL,
    	[SemanticStatus] [int] NULL,
    	[SemanticDesc] [nvarchar](max) NULL,
    	[CreatedDate] [datetime] NOT NULL DEFAULT (getdate()),
    	[CreatedBy] [nvarchar](50) NOT NULL DEFAULT ('ETL'),
    	[UpdatedDate] [datetime] NOT NULL DEFAULT (getdate()),
    	[UpdatedBy] [nvarchar](50) NOT NULL DEFAULT ('ETL'),
    	[ETL_ID] [uniqueidentifier] NULL,
    PRIMARY KEY CLUSTERED 
    (
    	[MessageQueueId] ASC
    )WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY],
     CONSTRAINT [CK_ETL_Unique_MessageID_Platform] UNIQUE NONCLUSTERED 
    (
    	[MessageID] ASC,
    	[MessagePlatform] ASC,
    	[MessageType] ASC
    )WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
    ) ON [PRIMARY] TEXTIMAGE_ON [PRIMARY]
    
    GO


This should provide you with enough code to reproduce the problem ... just fill the table with about 11 million records and you can see the problem!