CREATE TABLE #Item (
 id INT PRIMARY KEY NOT NULL
 ,Name VARCHAR(50) NULL
 )

 CREATE TABLE #Attribute (
 id INT PRIMARY KEY NOT NULL
 ,Name VARCHAR(50) NULL
 )

 CREATE TABLE #ItemAttribute (
 itemid INT NOT NULL,
 attrid INT NOT NULL
 ,Desk VARCHAR(50) NULL
 )
go

INSERT #Item ( id ,Name )
select top (500000)
 row_number() over (order by 1/0),
 'Item-' + cast(newid() as varchar(36))
from
 master.dbo.spt_values a cross join
 master.dbo.spt_values b;

 INSERT #Attribute ( id ,Name )
VALUES ( 1 ,'Attribute1' )
 ,( 2 ,'Attribute2' )
 ,( 3 ,'Attribute3' )
 ,( 4 ,'Attribute4' )
 ,( 5 ,'Attribute5' )

 INSERT #ItemAttribute ( itemid , attrid , Desk  )
 select
  i.id, a.id, 
 'Desc-' + cast(newid() as varchar(36))
 from
  #Item i cross apply
  (select top (cast(rand(checksum(i.id, i.Name)) * 5 + 1 as int)) id from #Attribute order by newid()) a

create index IX_#ItemAttribute on #ItemAttribute (itemid, attrid);
go

declare @itemid int;

set statistics xml, time on;

select
 @itemid = itemid
from 
(
SELECT t1.Itemid, (  SELECT '#' + ltrim(str(attrid))  FROM #ItemAttribute WHERE itemid=t1.Itemid FOR XML PATH('') ) + '#'  as attrs
FROM #ItemAttribute  t1
group by t1.Itemid
) as tt
WHERE (  (attrs LIKE '%#1#%')  OR (attrs LIKE '%#2#%')  )  AND (  (attrs LIKE '%#3#%')  OR (attrs LIKE '%#4#%')  )
option
 (maxdop 1);

select
 @itemid = i.id
from #Item i
where 
  (
    exists(
      SELECT *
      FROM #ItemAttribute  ia
      where ia.itemid = i.id
        and (ia.attrid = 1)
    )
    or exists(
      SELECT *
      FROM #ItemAttribute  ia
      where ia.itemid = i.id
        and (ia.attrid = 2)
    )
  )
  and
  (
    exists(
      SELECT *
      FROM #ItemAttribute  ia
      where ia.itemid = i.id
        and (ia.attrid = 3)
    )
    or exists(
      SELECT *
      FROM #ItemAttribute  ia
      where ia.itemid = i.id
        and (ia.attrid = 4)
  )
)
option
 (maxdop 1);

with t as
(
 select
  itemid,
  sum(distinct case when attrid = 1 then 1 when attrid = 2 then 2 when attrid = 3 then 4 when attrid = 4 then 8 else 0 end) s
 from
  #ItemAttribute
 group by
  itemid
)
select
 @itemid = itemid
from
 t
where
 s & 3 > 0 and s & 12 > 0
option
 (maxdop 1);

set statistics xml, time off;
go

drop table #ItemAttribute, #Attribute, #Item;
go

(1 row affected)

 SQL Server Execution Times:
   CPU time = 4391 ms,  elapsed time = 4476 ms.
SQL Server parse and compile time: 
   CPU time = 182 ms, elapsed time = 182 ms.

(1 row affected)

 SQL Server Execution Times:
   CPU time = 782 ms,  elapsed time = 889 ms.
SQL Server parse and compile time: 
   CPU time = 0 ms, elapsed time = 2 ms.

(1 row affected)

 SQL Server Execution Times:
   CPU time = 1515 ms,  elapsed time = 1669 ms.