Dois grandes problemas de desempenho:

1. Sua função de divisor de CSV é um grande assassino de desempenho. Troque-o pela função DelimitedSplit8k de Jeff Moden. Você pode ler tudo sobre isso aqui . Ou melhor ainda, troque-o pela função CLR ou um parâmetro com valor de tabela se você estiver em 2008+. Confira os testes de desempenho de Aaron Bertrand para as várias funções do divisor CSV . CLR é o vencedor geral.
2. A variável de tabela pode ser um grande assassino de desempenho, mesmo que tenha apenas 1 linha. Mude para uma tabela temporária e adicione um índice clusterizado a ela.

Em seus planos de execução agora fornecidos, a função mostra um custo de 0%, mas não é o caso. O custo da função é maior, mas você não verá o custo real no plano de execução, a menos que seja uma função com valor de tabela embutida.

Infelizmente, embora uma vez eu tenha tido um tempo de execução de 1 segundo, alterando o SP e voltando novamente, leva 6 segundos novamente.

Isso cheira a cheirar parâmetros .

Como você compartilhou a imagem, não posso detalhar seu problema em profundidade. Marquei a principal diferença entre dois planos de execução.

No primeiro plano, o SQL Server criou um plano de execução para a consulta e usou o Non Clustered Index Seek, mas no segundo, usou o Index Scan. Este é o principal culpado que aumenta o tempo total de execução.

Index Seek:- Toca apenas nas linhas que se qualificam e nas páginas que contêm essas linhas qualificadas.

Varredura de índice:- Toca cada linha na tabela/índice, seja ela qualificada ou não.

Quando você manipula dados (coluna) (usando função ou instrução case) na condição where, primeiro o SQL Server verifica o índice/tabela completo e, em seguida, realiza a manipulação de dados e corresponde à sua condição. Este processo aumenta a utilização de memória, disco IO e aumenta o tempo de execução.

Incluindo a sugestão de Tara Kizer, gostaria de sugerir

1. Adicione uma coluna na tabela e faça alterações nos SPs que você usa para inserir dados na tabela com base na lógica que você está usando na condição WHERE com a instrução CASE e crie um índice nela. Isso resolverá seu problema.

Ou

2. Puxe todos os registros em uma tabela temporária, crie um índice nela e insira dados nela, incluindo a instrução CASE e recupere dados da tabela temporária.

   CREATE TABLE #TEMP
   (
   Location DataType(LENGTH), --Estimated Length
   Start DataType(LENGTH),
   STOP DataType(LENGTH),
   WCondition DataType(LENGTH)
   );
   CREATE NONCLUSTERED INDEX IDXTMP ON #TEMP(WCONDITION);
   
   INSERT INTO #TEMP
   SELECT
           D.Location,
           MIN(D.Start) as Start,
           MAX(D.[Stop]) as Stop,
           CASE
           WHEN D.Stop IS NULL THEN 0
           WHEN @Locations IS NULL THEN 1 -- full list, so binding to another list doesn't do us any good.
           WHEN EXISTS (SELECT 1 from (SELECT Location from @loclist as l where l.Location=D.Location) as ll) THEN 1 END AS Wcondition
       FROM
           Deployments as D
   
   SELECT * FROM #TEMP WHERE W Condition --Put Condition
   

   Obrigado

Resumo

Depois de implementar algumas das sugestões nas respostas fornecidas, todo o SP parece ser executado em 0-1 segundo, independentemente dos valores dos parâmetros usados. Muito obrigado a todos que ajudaram.

Se isso parecer afetar o desempenho no futuro (ou vincular os resultados disso a outra tabela), analisarei a sugestão de Rajesh de armazenar um valor "condicional" em uma tabela temporária.

Questões não resolvidas

Não sei por que está usando uma verificação de índice clusterizado em vez de uma busca pelo seguinte:

WHERE 
    CASE
        WHEN D.Stop IS NULL THEN NULL
        WHEN @Locations IS NULL THEN 1 -- full list, so binding to another list doesn't do us any good.
        WHEN Location IN (SELECT Location from #loclist) THEN 1 --does clustered index scan
--alternate: EXISTS (SELECT 1 from (SELECT Location from #loclist as l where l.Location=D.Location) as ll) THEN 1 --does clustered index scan
    END is not null

Considerando que, isso faz uma busca

WHERE 
    D.Stop is not NULL AND 
      EXISTS (SELECT 1 from (SELECT Location from #loclist as l where l.Location=D.Location) as ll).

Além disso, no fim de semana, eu estava investigando se a indexação de texto completo seria benéfica para minha LIKE x+'[_]%'junção, mas não consegui descobrir quais são os divisores de palavras padrão (o '_'idioma 1033 separa tokens de palavras? Ou apenas caracteres de espaço em branco verdadeiros?) E Parece que não tenho a indexação de texto completo instalada ( SELECT * from sys.fulltext_languagesretorna um conjunto de resultados vazio, assim como EXEC sp_help_fulltext_system_components). Como não tenho mídia de instalação, precisaria esperar que a TI reinstalasse o SQL Server 2008 R2 para adicionar capacidade de texto completo, o que pode nem me beneficiar.

Mas, como eu disse, toda a bagunça leva 0-1 s para ser executada, então estou satisfeito por enquanto.

Procedimento armazenado inteiro

ALTER PROCEDURE [dbo].[dev_Tech@Locs2b] ( --CREATE or ALTER
     @Locations as nvarchar(MAX) = NULL -- = 'GG1,BenBr14,BenBr00,YB_ToeDrain_Base,SR_AbvTisdale_E1,GG5,Elephant'
    ,@rangeStart as DateTime = '1970-01-01'
    ,@rangeEnd as DateTime = '2099-12-31'
) AS BEGIN
SET NOCOUNT ON; --otherwise concrete5 chokes for multi-table returns.
CREATE TABLE #loclist (
    Location nvarchar(50) PRIMARY KEY CLUSTERED
)
IF @Locations is NULL
    INSERT INTO #loclist(Location)
        SELECT Location from Monitor_Locations-- order by Location
ELSE 
    INSERT INTO #loclist(Location)
        SELECT
            ML.Location
        FROM Monitor_Locations as ML join
                clr_splitString_delim(@Locations,',') as ss ON
                ML.Location=ss.substr OR 
                ML.Location like ss.substr+'[_]%'
--      ORDER BY ML.Location
        ;
With subsitelist as (
    SELECT
        ML.Location as intxt,
        CASE
            WHEN UPPER(t.substr) NOT IN ('RT','180RT','RT180','180','J','JST','JSAT','JSATS') 
                THEN LEFT(ML.Location,MAX(t.sEnd)) -- or MAX(t.leng+t.pos?) --look at 1167
                ELSE LEFT(ML.Location,COALESCE(MIN(t.sEnd-1),1))
        END as baseTxt,
        case WHEN UPPER(t.substr) IN ('RT','180RT','RT180') THEN '_'+t.substr END as sRT, --ELSE NULL
        case WHEN UPPER(t.substr) IN ('180','180RT','RT180') THEN '_'+t.substr END as s180,
        case WHEN UPPER(t.substr) IN ('J','JST','JSAT','JSATS') THEN '_'+t.substr END as sJ
    from 
        #loclist /*Monitor_Locations*/ as ML CROSS APPLY 
        clr_splitString_delim(ML.Location, '_') as t
    group by 
        ML.Location, t.substr
),  deploys as (
    SELECT
        D.Location,
        MIN(D.Start) as Start,
        MAX(D.[Stop]) as Stop
    FROM
        Deployments as D 
    WHERE 
-- tSQL does not use traditional short-circiting in a WHERE clause with ANDs or ORs, so no guarantee that the join to the larger list won't happen when Stop is set.
-- CASE is a way of getting around this. Unfortunately the execution plan is showing clustered index scans, rather than the optimal seeks for the CASEd version
        CASE
            WHEN D.Stop IS NULL THEN NULL
            WHEN @Locations IS NULL THEN 1 -- full list, so binding to another list doesn't do us any good.
            WHEN Location in (SELECT Location from #loclist) THEN 1 -- does clustered index SCAN
--Alternate:  EXISTS (SELECT 1 from (SELECT Location from #loclist as l where l.Location=D.Location) as ll) THEN 1 -- does clustered index SCAN
        END is NOT NULL
--      D.Stop is NOT NULL AND EXISTS (SELECT 1 from (SELECT Location from #loclist as l where l.Location=D.Location) as ll) -- does clustered index SEEK
    GROUP BY
        D.Location
--      CASE WHEN D.Stop IS NULL THEN 1 END  --groups all terminating deployments together and seperates out the non-terminating deployment of that series.
), shortestBaseSiteName as (
    SELECT
        sl.intxt,
        CASE WHEN MAX(COALESCE(sl.sRT,sl.s180,sl.sJ)) IS NOT NULL THEN MIN(sl.basetxt) ELSE sl.intxt END as baseName,
        MAX(sl.sRT) as sRT,
        MAX(sl.s180) as s180,
        MAX(sl.sJ) as sJ
    FROM
        subsitelist as sl
    GROUP BY
        sl.intxt
), longestSubSiteName as (
    SELECT 
        sbs.baseName,
        MAX(sbs.intxt) as longestSS,
        MAX(sbs.sRT) as sRT,
        MAX(sbs.s180) as s180,
        MAX(sbs.sJ) as sJ
    FROM
        shortestBaseSiteName as sbs
    GROUP by sbs.baseName
), baseNames as (
    SELECT 
        intxt,
        MAX(baseTxt) as baseName
    FROM 
        subsitelist
    GROUP BY
        intxt, sRT, s180, sJ
    HAVING 
        MIN(COALESCE(sRT,s180,sJ)) is NULL
), subSiteTally as (
    SELECT
        intxt,
        MAX(sRT) as sRT,
        MAX(s180) as s180,
        MAX(sJ) as sJ
    FROM
        subsitelist
    GROUP BY
        intxt
), bigList as (
    SELECT 
        bn.baseName,
        MAX(sst.sRT) as sRT,
        MAX(sst.s180) as s180,
        MAX(sst.sJ) as sJ
    FROM
        subSiteTally as sst INNER JOIN 
            baseNames as bn on bn.intxt=sst.intxt
    GROUP BY
        bn.baseName
), smat as (
    SELECT 
        baseName as Location,
        CASE WHEN baseName in (ML.Location) THEN baseName END as l69,
        baseName+s180 as l180,
        baseName+sJ as lJ,
        baseName+sRT as lRT69,
        baseName+sRT+s180 as lRT180,
        baseName+sRT+sJ as lRTJ
    FROM
        bigList as bl inner join 
        --LEFT OUTER gives all site names, regardless if in the short list or not. RIGHT will return an all-null entry for "donkey" (which is not a site)
            #loclist as ML on bl.baseName=ML.Location
), depWithDets as (
    SELECT 
        smat.Location,
        CASE Dep.Location WHEN l69 THEN 1 END as d69,
        CASE Dep.Location WHEN l180 THEN 1 END as d180,
        CASE Dep.Location WHEN lJ then 1 END as dJ,
        CASE Dep.Location WHEN lRT69 THEN 1 END as dRT69,
        CASE Dep.Location WHEN lRT180 THEN 1 END as dRT180,
        CASE Dep.Location WHEN lRTJ THEN 1 END as dRTJ
        ,smat.l69
        ,smat.l180
        ,smat.lJ
        ,smat.lRT69
        ,smat.lRT180
        ,smat.lRTJ
    FROM
        smat INNER JOIN
            deploys as Dep ON (Dep.Location in (l69,l180,lJ,lRT69,lRT180,lRTJ))
    WHERE
        (Dep.Start > @rangeStart AND Dep.Start < @rangeEnd) OR 
        (Dep.Stop > @rangeStart AND Dep.Stop < @rangeEnd) OR
        (Dep.Start < @rangeStart AND Dep.Stop > @rangeEnd)
)
SELECT Location,
    count(d69) as bool_auton_69,
    count(d180) as bool_auton_180,
    count(dJ) as bool_auton_JSATS,
    count(dRT69) as bool_rtime_69,
    count(dRT180) as bool_rtime_180,
    count(dRTJ) as bool_rtime_JSATS
    ,min(l69) as name_auton_69
    ,min(l180) as name_auton_180
    ,min(lJ) as name_auton_JSATS
    ,min(lRT69) as name_rtime_69
    ,min(lRT180) as name_rtime_180
    ,min(lRTJ) as name_rtime_JSATS
from depWithDets
group by Location
Drop table #loclist
END

Gif do plano de execução

Plano final

Função C# CLR

Como nunca programei em C#, achei que seria uma boa ideia documentar minhas modificações de código em um CLR vinculado nos comentários aqui.

clr_splitString_delim (para .NET Framework 3.5) com base no SQLCLR String Splitter de Adam Machanic :

using System;
using System.Collections;
using System.Data;
using System.Data.SqlClient;
using System.Data.SqlTypes;
using Microsoft.SqlServer.Server;

/*
Code adapted from http://sqlblog.com/blogs/adam_machanic/archive/2009/04/28/sqlclr-string-splitting-part-2-even-faster-even-more-scalable.aspx (author: Adam Machanic)
alterations to the I/O of Adam's function:
1) change returned field "Item" to "substr"
2) add returned field "sIndex"
       * which position in the list is this substring. 0 indexed
3) add returned field "sStart"
       * At which character position the substring starts with respect to the input string
4) add returned field "sEnd"
       * At which character position the substring ends
*/    
public partial class UserDefinedFunctions
{
    public class SplitStringTable : object
    {
        public String item;
        public int index;
        public int start;
        //        public int length;
        public int end;
        public SplitStringTable()
        {
            item = "";
            index = 0;
            start = 0;
            end = 0;
        }
        public SplitStringTable(String i, int idx, int stp, int nd)
        {
            item = i;
            index = idx;
            start = stp;
            end = nd;
        }
        public override string ToString()
        {
            return item.ToString();
        }
    }
    private static SplitStringTable fill_result(String obj, int sp, int l)
    {
        return (new SplitStringTable { item = obj.ToString(), start = sp, end = l });
    }

    [Microsoft.SqlServer.Server.SqlFunction(
        FillRowMethodName = "FillRow_Multi",
        TableDefinition = "substr nvarchar(4000),sIndex int,sStart int,sEnd int",
        IsDeterministic =true
        )
    ]
    public static SplitStringMulti SplitString_Multi( [SqlFacet(MaxSize = -1)] SqlChars Input, [SqlFacet(MaxSize = 255)] SqlChars Delimiter )
    {
        SplitStringMulti ssm = (Input.IsNull || Delimiter.IsNull) ? new SplitStringMulti(new char[0], new char[0]) : new SplitStringMulti(Input.Value, Delimiter.Value);
        return (ssm);
    }

    public static void FillRow_Multi(object obj, out SqlString substr, out SqlInt32 sIndex, out SqlInt32 sStart, out SqlInt32 sEnd)
    {
        SplitStringTable res = (SplitStringTable)obj;
        substr = new SqlString(obj.ToString());
        sIndex = res.index;
        sStart = res.start;
        sEnd = res.end;
    }

    public class SplitStringMulti : IEnumerator
    {
        private static SplitStringTable fill_result(object obj, int idx, int sp, int l)
        {
            return (new SplitStringTable { item = obj.ToString(), index = idx, start = sp, end = l });
        }
        public SplitStringMulti(char[] TheString, char[] Delimiter)
        {
            theString = TheString;
            stringLen = TheString.Length;
            delimiter = Delimiter;
            delimiterLen = (byte)(Delimiter.Length);
            isSingleCharDelim = (delimiterLen == 1);

            lastPos = 0;
            nextPos = delimiterLen * -1;
            delimOccur = 0;
            //leng = nextPos - lastPos;
        }

        #region IEnumerator Members

            public object Current
        {
            get
        {
                var item = new string(theString, lastPos, nextPos - lastPos);
                var res = fill_result(item, delimOccur-1, lastPos, nextPos);
                return res;                     
//                return new string(theString, lastPos, nextPos - lastPos);
        }
        }
        public override String ToString() {
            return new string(theString, lastPos, nextPos - lastPos);
        }
        public bool MoveNext() {
            if (nextPos >= stringLen)
                return false;
            else {
                lastPos = nextPos + delimiterLen;
                for (int i = lastPos; i < stringLen; i++) {
                    bool matches = true;
                    //Optimize for single-character delimiters
                    if (isSingleCharDelim) {
                        if (theString[i] != delimiter[0])
                            matches = false;
                    }
                    else {
                        for (byte j = 0; j < delimiterLen; j++) {
                            if (((i + j) >= stringLen) || (theString[i + j] != delimiter[j])) {
                                matches = false;
                                break;
                            }
                        }
                    }
                    if (matches) {
                        delimOccur++;
                        nextPos = i;
                        //Deal with consecutive delimiters
                        if ((nextPos - lastPos) > 0)
                            return true;
                        else {
                            i += (delimiterLen - 1);
                            lastPos += delimiterLen;
                        }
                    }
                }
                delimOccur++;
                lastPos = nextPos + delimiterLen;
                nextPos = stringLen;
                if ((nextPos - lastPos) > 0)
                    return true;
                else
                    return false;
            }
        }

        public void Reset()
        {
            lastPos = 0;
            delimOccur = 0;
            nextPos = delimiterLen * -1;
        }

        #endregion

        public int lastPos;
        public int nextPos;
        public int delimOccur;

        private readonly char[] theString;
        private readonly char[] delimiter;
        private readonly int stringLen;
        private readonly byte delimiterLen;
        private readonly bool isSingleCharDelim;
    }
};

Montagem do CLR no banco de dados, uma vez que a DLL já foi criada no VisStudio:

DROP FUNCTION dbo.clr_splitString_delim
go

DROP ASSEMBLY CLRUtilities
GO

CREATE ASSEMBLY CLRUtilities FROM 'c:\DLLs\CLRUtilities.dll' 
  WITH PERMISSION_SET = SAFE;
GO

CREATE FUNCTION dbo.clr_splitString_delim (
   @List      NVARCHAR(MAX),
   @Delimiter NVARCHAR(255)
)
RETURNS TABLE ( substr NVARCHAR(4000), sIndex int, sStart int, sEnd int )
EXTERNAL NAME CLRUtilities.UserDefinedFunctions.SplitString_Multi;
GO