Improving performance of sql query

The nested IN business in the second and third queries doesn't look very good. It might be personal preference over anything else but I have seen cases where the optimizer can't create an optimal plan because of nested IN operators. Especially if your DISTINCT gets in the way - I'm not sure whether this will be dutifully ignored or actually executed, when all you really need is a single EXISTS (see the bottom of this answer). Without seeing the generated plan I can't say too much more though.

In fact the way you have written the subquery is redundant - you are using both WHERE given_Id IN and a correlation WHERE rec.given_Id = tbl.given_Id. This is probably the real problem. We only want one of these.

What would I do? First of all, I would pull the correlated subquery stuff out as a join:

select tbl.given_id, tbl.name, tbl.message, tbl.emplid, tbl.category, tbl.created_date
from dbo.myTable tbl
join dbo.Recipient r on tbl.given_Id = r.given_Id
where created_date >= @dtFrom
and created_date < @dtTo
and r.emplid IN ( ... )

Second of all, in the "both" case I would run away from UNION in favor of OR. The duplicate elimination is unnecessary and costly:

select tbl.given_id, tbl.name, tbl.message, tbl.emplid, tbl.category, tbl.created_date
from dbo.myTable tbl
join dbo.Recipient r on tbl.given_Id = r.given_Id
where created_date >= @dtFrom
and created_date < @dtTo
and (r.emplid IN ( ... ) or tbl.emplid IN ( ... ))

Note I am assuming your sb.ToString() is safe, which is probably a bad idea. In my book, dynamic SQL is an ultimate last resort. You could write this into a stored procedure; instead of the IN, you would pass a table-valued parameter then join against it.

I'm also assuming some things about your schema; you may indeed want a single DISTINCT on that last query. Or frankly you can change it to an EXISTS:

select tbl.given_id, tbl.name, tbl.message, tbl.emplid, tbl.category, tbl.created_date
from dbo.myTable tbl
where created_date >= @dtFrom
and created_date < @dtTo
and (tbl.emplid IN ( ... ) or exists (
    select 1
    from dbo.Recipient r
    where r.given_Id = tbl.given_Id
    and r.emplid IN ( ... )))

Why not write a single query along the lines of:

SELECT <stuff in first query>
WHERE ... 
AND @Challenge in (1,3)
UNION
SELECT <stuff in second query>
WHERE ...
AND @Challenge in (2,3)

And let the query optimizer do the hard work for you.

I don't like concatenated SQL queries. Prefer to have separate query for each condition or one query which operates this condition. Depending on difficulty.

As there are only two separate conditions and one else combining it - we could use boolean logic.

SELECT
    tbl.given_id, 
    name, 
    [message], 
    tbl.emplid, 
    category, 
    created_date
FROM
    dbo.myTable tbl             
WHERE 
    created_date >= @dtFrom
    AND created_date < @dtTo
    AND ((@challenge <> 2 AND tbl.emplid IN (@lst_emplids)) 
      OR (@challenge <> 1 AND given_Id IN (SELECT DISTINCT rec.given_Id  from dbo.Recipient rec WHERE rec.given_Id = tbl.given_Id AND rec.emplid IN (@lst_emplids)))

If @challenge = 1 or 3 will be filtered all items tbl.emplid IN (@lst_emplids)
If @challenge = 2 or 3 will be filtered all items given_Id IN (...)
So if @challenge is 3 - will be extracted all items, but if 1 or 2 - only one subset.

A more sensible solution would be to call this code from a stored procedure and use dynamic sql in that to build your query , and use parameterised query rather then concatenating values from the UI, it makes your code prone to sql-injection.

I would do it something like......

CREATE PROCEDURE my_SP
   @dtFrom      DATE
 , @dtTo        DATE
 , @Sb          VARCHAR(8000)
 , @challenge   INT
 AS
 BEGIN
   SET NOCOUNT ON;
DECLARE @Sql NVARCHAR(MAX);

SET @Sql = N'  declare @xml xml = N''<root><r>'' + replace(@Sb,'','',''</r><r>'') + ''</r></root>'';
SELECT tbl.given_id, name, message, tbl.emplid, category, created_date
FROM  dbo.myTable tbl
WHERE created_date >= @dtFrom
 AND  created_date < @dtTo'

+ CASE WHEN (@challenge = 0)
         THEN N'AND emplid IN ( select r.value(''.'',''varchar(max)'') as item
                                from @xml.nodes(''//root/r'') as records(r))' 
       WHEN  (@challenge = 1)
         THEN N'AND given_Id IN (SELECT rec.given_Id  
                                from dbo.Recipient rec 
                                WHERE rec.given_Id = tbl.given_Id 
                                AND rec.emplid IN ( select r.value(''.'',''varchar(max)'') as item
                                                    from @xml.nodes(''//root/r'') as records(r))
                                )'
        WHEN (@challenge = 2)
          THEN 'AND 
                    ( emplid IN ( select r.value(''.'',''varchar(max)'') as item
                                  from @xml.nodes(''//root/r'') as records(r))
                      OR 
                      given_Id IN (SELECT rec.given_Id  
                                from dbo.Recipient rec 
                                WHERE rec.given_Id = tbl.given_Id 
                                AND rec.emplid IN ( select r.value(''.'',''varchar(max)'') as item
                                                    from @xml.nodes(''//root/r'') as records(r))
                                )
                     )'
         ELSE N'' END

Exec sp_executesql @Sql 
                  ,N'@dtFrom DATE, @dtTo DATE, @Sb VARCHAR(8000)'
                  ,@dtFrom 
                  ,@dtTo 
                  ,@Sb 
END