I need to speed up a query that lists transactions from BillingInfo joined to site/customer tables. Users filter by CustomerName (first + last). Data volume: BillingInfo ≈ 3.1M rows

CREATE TABLE [dbo].[BillingInfo] (
    [Id]               INT            IDENTITY (1, 1) NOT NULL,
    [TransactionId]    INT            NOT NULL,
    [SiteId]           INT            NULL,
    [CbId]             NVARCHAR (20)  NOT NULL,
    [ConnectorNumber]  INT            NOT NULL,
    [CustomerId]       INT            NULL,
    [IdTag]            NVARCHAR (50)  NULL,
    [StartTime]        DATETIME       NOT NULL,
    [StopTime]         DATETIME       NOT NULL,
    [StopReason]       NVARCHAR (250) NULL,
    [TotalConsumption] NVARCHAR (200) NULL,
    [TotalConsumption1] DECIMAL(18, 3) NULL,
    [TarrifId]         INT     NOT NULL,
    [StartMeter] NVARCHAR(20) NULL, 
    [StopMeter] NVARCHAR(20) NULL, 
    [StartSOC] NVARCHAR(20) NULL, 
    [StopSOC] NVARCHAR(20) NULL, 
    [AuthValid] BIT NOT NULL DEFAULT 1, 
    [ChargeBoxSerialNumber] NVARCHAR(100) NULL, 
    [OverrideChargePlan] BIT NOT NULL DEFAULT 0 , 
    [ChargespotType] NVARCHAR(50) NULL, 
    [ChargerType] NVARCHAR(50) NULL, 
    CONSTRAINT [PK__BillingI__3214EC07EDB3B6E8] PRIMARY KEY CLUSTERED ([Id] ASC),
    CONSTRAINT [FK_BillingInfo_OfficeCustomers_CustomerId] FOREIGN KEY ([CustomerId]) REFERENCES [dbo].[OfficeCustomers] ([Id]) ON DELETE SET NULL,
    CONSTRAINT [FK_BillingInfo_OfficeRFIDs_IdTag] FOREIGN KEY ([IdTag]) REFERENCES [dbo].[OfficeRFIDs] ([RFID]) ON DELETE SET NULL,
    CONSTRAINT [FK_BillingInfo_Site_SiteId] FOREIGN KEY ([SiteId]) REFERENCES [dbo].[Site] ([Id]) ON DELETE SET NULL,
    CONSTRAINT [UQ__BillingI__55433A6ABEA4CD28] UNIQUE NONCLUSTERED ([TransactionId] ASC)
);
GO

CREATE NONCLUSTERED INDEX [IDX_BillingInfo_CustomerId]
    ON [dbo].[BillingInfo]([CustomerId] ASC);

GO
CREATE UNIQUE NONCLUSTERED INDEX [IDX_BillingInfo_TransactionId]
    ON [dbo].[BillingInfo]([TransactionId] ASC);
GO

CREATE NONCLUSTERED INDEX [IX_BillingInfo_SiteId_CustomerId]
    ON [dbo].[BillingInfo]([SiteId] ASC, [CustomerId] ASC);

CREATE TABLE [dbo].[CustomerContact] (
    [Id]        INT             IDENTITY (1, 1) NOT NULL,
    [MobileId]  INT             NOT NULL,
    [EmailId]   INT             NULL,
    [AddressId] INT             NOT NULL,
    [FirstName] NVARCHAR (250)  NOT NULL,
    [LastName]  NVARCHAR (250)  NOT NULL,
    [Title]     NVARCHAR (250)  NULL,
    [Company]   NVARCHAR (250)  NULL,
    [Birthday]  DATETIME        NULL,
    [Note]      NVARCHAR (1000) NULL,
    PRIMARY KEY CLUSTERED ([Id] ASC),
    CONSTRAINT [FK_CustomerContact_ContactAddress_AddressId] FOREIGN KEY ([AddressId]) REFERENCES [dbo].[ContactAddress] ([Id]),
    CONSTRAINT [FK_CustomerContact_ContactEmail_EmailId] FOREIGN KEY ([EmailId]) REFERENCES [dbo].[ContactEmail] ([Id]),
    CONSTRAINT [FK_CustomerContact_ContactMobile_MobileId] FOREIGN KEY ([MobileId]) REFERENCES [dbo].[ContactMobile] ([Id])
);
GO

CREATE NONCLUSTERED INDEX [IDX_CustomerContact_FirstName]
    ON [dbo].[CustomerContact]([FirstName] ASC);
GO

CREATE NONCLUSTERED INDEX [IDX_CustomerContact_LastName]
    ON [dbo].[CustomerContact]([LastName] ASC);
GO

CREATE TABLE [dbo].[OfficeCustomers] (
    [Id]                 INT            IDENTITY (1, 1) NOT NULL,
    [AppUserId]          INT            NULL,
    [ContactId]          INT            NULL,
    [ServicePack]        NVARCHAR (50)  NULL,
    [Status]             NVARCHAR (50)  NULL,
    [DefaultMailAddress] NVARCHAR (50)  NULL,
    [LastUpdate]         DATETIME       NULL,
    [RegisterDate]       DATETIME       NULL,
    [Comments]           NVARCHAR (MAX) NULL,
    [CreatedBy]          INT            NULL,
    [IsActive]           BIT            NULL,
    [IsGnrgySubscribed]  BIT            NULL,
    [PriorityId]         NVARCHAR (30)  NULL,
    [CustomerType]       INT   NULL DEFAULT 0, 
    [CompanyNumber]      NVARCHAR(20)   NULL, 
    [VendorId]           INT   NOT NULL DEFAULT 2, 
    [IsAddressManagedBuilding] BIT NULL,
    [FixedMonthlyCharge] DECIMAL(10,2) NULL,
    CONSTRAINT [PK_OfficeCustomers] PRIMARY KEY CLUSTERED ([Id] ASC),
    CONSTRAINT [FK_OfficeCustomers_CustomerContact_ContactId] FOREIGN KEY ([ContactId]) REFERENCES [dbo].[CustomerContact] ([Id])
);
GO

CREATE NONCLUSTERED INDEX [_dta_index_OfficeCustomers_6_98099390__K2_K1_4_8_11]
    ON [dbo].[OfficeCustomers]([ContactId] ASC, [Id] ASC)
    INCLUDE([Status], [Comments], [IsGnrgySubscribed]);
GO

CREATE NONCLUSTERED INDEX [IDX_OfficeCustomers_ContactId]
    ON [dbo].[OfficeCustomers]([ContactId] ASC);
GO

--  CREATE UNIQUE NONCLUSTERED INDEX [idx_appuserid_notnull]
--      ON [dbo].[OfficeCustomers]([AppUserId] ASC) WHERE ([AppUserId] IS NOT NULL);
--  GO

CREATE UNIQUE NONCLUSTERED INDEX [idx_appuserid_notnull]
    ON [dbo].[OfficeCustomers]([AppUserId] ASC) WHERE ([AppUserId] IS NOT NULL);

CREATE TABLE [dbo].[Site] (
    [Id]              INT             IDENTITY (1, 1) NOT NULL,
    [Code]            NVARCHAR (50)   DEFAULT (NULL) NULL,
    [OperationStatus] INT             NULL,
    [Zipcode]         NVARCHAR (8)    DEFAULT (NULL) NULL,
    [CountryId]       SMALLINT        NULL,
    [CustomerId]      INT             DEFAULT (NULL) NULL,
    [SiteTypeId]      SMALLINT        NOT NULL,
    [ContactId]       INT             NULL,
    [OwnerId]         INT             NULL,
    [LocationTypeid]  TINYINT         DEFAULT (NULL) NULL,
    [PublishToApp]    BIT             DEFAULT(0)   NULL,
    [IsRoaming]       BIT             DEFAULT(0)   NULL,
    [Lat]             DECIMAL (11, 8) DEFAULT (NULL) NULL,
    [Lon]             DECIMAL (11, 8) DEFAULT (NULL) NULL,
    [Details]         NVARCHAR (250)  DEFAULT (NULL) NULL,
    [Sla]             NVARCHAR (32)   DEFAULT (NULL) NULL,
    [CreatedOn]       DATETIME        DEFAULT (getdate()) NOT NULL,
    [UpdatedOn]       DATETIME        DEFAULT (getdate()) NOT NULL,
    [OldSiteTypeId]   SMALLINT        CONSTRAINT [DF_Site_OldSiteTypeId_3] DEFAULT ((3)) NOT NULL,
    [VendorId]        INT             CONSTRAINT [DF_Site_VendorId_2] DEFAULT ((2)) NOT NULL,
    [IsRestricted] BIT NOT NULL default 0, 
    [IsUpcoming] BIT NOT NULL DEFAULT 0,
    [ChargePlanId] INT,
    [ManagedSite] BIT DEFAULT (0) NULL,
    [LimitUnit] VARCHAR (2),
    [MaxPower] INT,
    [CanOverride] BIT NOT NULL DEFAULT (0),
    [PriorityChargingType] INT   NULL,
    [QueueSize]            INT   NULL,
    [QueueDispatchType]    INT   NULL,
    [MidLevelSoc] INT NULL, 
    [StopSoc] INT NULL,
    PRIMARY KEY CLUSTERED ([Id] ASC),
    CONSTRAINT [Fk_Site_Country_CountryId] FOREIGN KEY ([CountryId]) REFERENCES [dbo].[Country] ([Id]) ON DELETE SET NULL,
    CONSTRAINT [FK_Site_CustomerContact_ContactId] FOREIGN KEY ([ContactId]) REFERENCES [dbo].[CustomerContact] ([Id]),
    CONSTRAINT [FK_Site_CustomerContact_OwnerId] FOREIGN KEY ([OwnerId]) REFERENCES [dbo].[CustomerContact] ([Id]),
    CONSTRAINT [Fk_Site_OfficeCustomers_CustomerId] FOREIGN KEY ([CustomerId]) REFERENCES [dbo].[OfficeCustomers] ([Id]) ON DELETE SET NULL,
    CONSTRAINT [Fk_Site_SiteOperationStatus_OperationStatus] FOREIGN KEY ([OperationStatus]) REFERENCES [dbo].[SiteOperationStatus] ([Id]) ON DELETE SET NULL
);
GO

CREATE NONCLUSTERED INDEX [IX_Site_SiteTypeId]
    ON [dbo].[Site]([SiteTypeId] ASC);
GO

CREATE NONCLUSTERED INDEX [IX_Site_CustomerId]
    ON [dbo].[Site]([CustomerId] ASC);

CREATE TABLE [dbo].[OfficeRFIDs] (
    [Id]           INT            IDENTITY (1, 1) NOT NULL,
    [RFID]         NVARCHAR (50)  NOT NULL,
    [Type]         NVARCHAR (MAX) NULL,
    [RFIDName]     NVARCHAR (MAX) NULL,
    [CustomerId]   INT            NULL,
    [RegisterDate] DATETIME       NULL,
    [LastUpdate]   DATETIME       NULL,
    [IsActive]     BIT            NULL,
    [IsDefault]    BIT            NULL,
    [IsExpired]    BIT            NULL,
    [CardId]       NVARCHAR (MAX) NULL,
    [DateExpired]  DATETIME       NULL,
    [Comment]      NVARCHAR (MAX) NULL,
    [VendorId]     INT            CONSTRAINT[Rfid_VendorId] NULL,
    [Remarks]      NVARCHAR (100) NULL,
    [BilledToId]     INT NULL, 
    [OwnerId]        INT NULL, 
    CONSTRAINT [PK_OfficeRFIDs] PRIMARY KEY CLUSTERED ([Id] ASC),
    CONSTRAINT [UQ_OfficeRFIDs_RFID] UNIQUE NONCLUSTERED ([RFID] ASC)   
);

CREATE TABLE [dbo].[SiteType] (
    [Id]        SMALLINT      IDENTITY (1, 1) NOT NULL,
    [Type]      NVARCHAR (32) NOT NULL,
    [CreatedOn] DATETIME      DEFAULT (getdate()) NOT NULL,
    [UpdatedOn] DATETIME      DEFAULT (getdate()) NOT NULL,
    [SiteIcon] NVARCHAR(MAX) NULL, 
    [SiteTypeId] INT NOT NULL DEFAULT 0, 
    [LanguageCode] NVARCHAR(10) NOT NULL DEFAULT 'en', 
    PRIMARY KEY CLUSTERED ([Id] ASC),
    CONSTRAINT [UQ_SiteType_SiteTypeId_LanguageCode] UNIQUE NONCLUSTERED ([SiteTypeId] ASC, [LanguageCode] ASC)
);
 
CREATE TABLE [dbo].[Vendors] (
    [Id]                    INT            IDENTITY (1, 1) NOT NULL,
    [VID]                   NVARCHAR (MAX) NULL,
    [VendorConfigurationId] INT            NULL,
    [PayingVendorId]        INT            NULL,
    [RootGridElementId]     INT            NULL,
    [ImageFile]             NVARCHAR (MAX) NULL,
    [ParentVendorId]        INT            NULL,
    [TypeId]                INT            NULL,
    [MapFilterId]           INT            NULL,
    [Name]                  NVARCHAR (MAX) NULL,
    CONSTRAINT [PK_Vendor] PRIMARY KEY CLUSTERED ([Id] ASC)
);

CREATE TABLE [dbo].[SiteTranslation] (
    [Id]             INT            IDENTITY (1, 1) NOT NULL,
    [SiteId]         INT            NOT NULL,
    [LanguageCode]   NVARCHAR (2)   NOT NULL,
    [Name]           NVARCHAR (50)  NOT NULL,
    [Housenumber]    NVARCHAR (12)  NULL,
    [Street]         NVARCHAR (30)  NOT NULL,
    [City]           NVARCHAR (30)  NOT NULL,
    [Openinghours]   NVARCHAR (250) NULL,
    [Hotline]        NVARCHAR (250) NULL,
    [Additionalinfo] NVARCHAR (250) NULL,
    [Paymentstring]  NVARCHAR (250) NULL,
    [Notes]          NVARCHAR (250) NULL,
    [RestrictedMessage ] NVARCHAR(500) NULL, 
    PRIMARY KEY CLUSTERED ([Id] ASC),
    CONSTRAINT [FK_SiteTranslation_Site_SiteId] FOREIGN KEY ([SiteId]) REFERENCES [dbo].[Site] ([Id]) ON DELETE CASCADE,
    CONSTRAINT [UQ_SiteTranslation_SiteId_LanguageCode] UNIQUE NONCLUSTERED ([SiteId] ASC, [LanguageCode] ASC)
);

New Approach Query

SELECT b.Id, vendor.Name AS Vendor, ST.Name AS SiteName, stype.Type AS Sitetype, 
                S.Code AS ReferenceCode, b.CbId AS CbId, b.ConnectorNumber, 
                CONCAT(offCon.FirstName, '' '', offCon.LastName) AS CustomerName, 
                RFID.RFIDName AS IdTagLabel, RFID.CardId, b.StartTime, b.StopTime, 
                FORMAT(DATEADD(SECOND, CASE WHEN b.StopTime < b.StartTime THEN 0 ELSE DATEDIFF(SECOND, b.StartTime, b.StopTime) END, 0), ''H\h m\m s\s'') AS Duration,
                CASE WHEN b.StopTime < b.StartTime THEN 0 ELSE DATEDIFF(MINUTE, b.StartTime, b.StopTime) END AS DurationMins,
                FORMAT(b.StartTime, ''yyyy-MM-ddTHH:mm:ss.fffZ'') AS strStartTimeInUTC, 
                FORMAT(b.StopTime, ''yyyy-MM-ddTHH:mm:ss.fffZ'') AS strStopTimeInUTC, 
                b.TotalConsumption1 AS Consumption, b.StartMeter, b.StopMeter, 
                b.StartSOC, b.StopSOC, b.AuthValid, 
                CONCAT(
                    ISNULL(st.HouseNumber + '', '', ''''), 
                    ISNULL(NULLIF(st.Street, '''') + '', '', ''''), 
                    ISNULL(NULLIF(st.City, '''') + '' - '', ''''), 
                    ISNULL(NULLIF(S.ZipCode, '''') + '', '', ''''), 
                    ISNULL(CT.Name, '''')
                ) AS SiteAddress, 
                b.SiteId, S.VendorId, CONVERT(VARCHAR, b.StopTime, 103) AS Date, 
                b.TransactionId AS TxId, b.ChargerType, b.StopReason, b.ChargeBoxSerialNumber as ChargerSerial
            FROM BillingInfo b
            INNER JOIN Site S ON S.Id = b.SiteId
            INNER JOIN SiteTranslation ST     ON ST.SiteId = S.Id AND ST.LanguageCode = @lang
            LEFT JOIN OfficeRFIDs RFID ON RFID.RFID = b.IdTag
            LEFT JOIN [GN.eMobility].dbo.Vendors V ON RFID.VendorId = V.Id
            LEFT JOIN [GN.eMobility].dbo.Vendors vendor ON S.VendorId = vendor.Id
            INNER JOIN SiteType stype ON S.SiteTypeId = stype.SiteTypeId AND stype.LanguageCode = @lang
            LEFT JOIN Country country ON S.CountryId = country.Id
            LEFT  JOIN CountryTranslation CT  ON country.Id = CT.CountryId AND CT.LanguageCode = @lang
            INNER JOIN OfficeCustomers offCus ON offCus.Id = b.CustomerId
            INNER JOIN CustomerContact offCon ON offCon.Id = offCus.ContactId
            WHERE 1=1 AND st.LanguageCode = @lang AND CT.LanguageCode = @lang AND stype.LanguageCode= @lang AND (REPLACE(CONCAT(offCon.FirstName, offCon.LastName), '' '', '''') 
       LIKE REPLACE(@CustomerName, '' '', '''') or REPLACE(CONCAT(offCon.LastName, offCon.FirstName), '' '', '''') 
       LIKE REPLACE(@CustomerName, '' '', '''')) order by  b.TransactionId desc OFFSET (0) ROWS FETCH NEXT (50) ROWS ONLY',N'@VendorId int,@CustomerId int,
            @lang nvarchar(4000),@ReferenceCode nvarchar(4000),@SiteName nvarchar(4000),@ChargerSerial nvarchar(4000),@CbId nvarchar(4000),
            @AuthValid nvarchar(4000),@CustomerName nvarchar(4000),@IdTagLabel nvarchar(4000),@Id int',@VendorId=0,@CustomerId=0,@lang=N'en',@ReferenceCode=N'',
            @SiteName=N'%',@ChargerSerial=N'%%',@CbId=N'%%',@AuthValid=NULL,@CustomerName=N'%סומך עומר עובד מלם גמל ופנסיה%',@IdTagLabel=N'%',@Id=0

What we've tried

1. Added indexes on CustomerContact.FirstName, LastName
2. Tried "Starts with" pattern (LIKE @CustomerName +'%'
3. Moved to Space-stripped REPLACE(CONCAT(...)) to support "full name" typing (no space)

Actual Execution Plan: https://www.brentozar.com/pastetheplan/?id=ae3T7DUgYC

Expected Result / Goal

I want this query to return the first 50 matching transactions in under 1–2 seconds even when filtering by CustomerName, regardless of whether the name is in English or Hebrew, or whether the user types it as:

• "First Last"
• "Last First"
• or without spaces ("FirstLast")

Specifically, I want to improve:

1. Query execution time – it currently takes around 20–35 seconds for some names.
2. Scalability – it should continue to perform well as data grows (currently ~3.1M rows in BillingInfo).
3. Multilingual support – the solution should correctly handle Hebrew and English text (collation-aware).
4. Top N performance – since we only show the latest 50 records (ORDER BY TransactionId DESC OFFSET 0 FETCH NEXT 50 ROWS), the plan should take advantage of that limit.