Creating efficient indexes on SQL Server with a big WHERE clause

I have a database that contains two tables, containing these columns (some irrelevant columns have been omitted): 1. Containers table - Id nvarchar(20) NOT NULL primary key, value generated before insert - Category nvarchar(5) NOT NULL A category with around 5 possible values - Status int NOT NULL Value between 0 and 3. 2. Items table - Id uniqueidentifier NOT NULL primary key - ContainerId nvarchar(20) NOT NULL FK to the Containers table. Containers contain 1-n Items - PartId uniqueidentifier NULL A part ID OR a part category must be provided. They are mutually exclusive. There are ~15000 unique part ids - PartCategory nvarchar(50) NULL ~1000 unique part categories - CustomerId uniqueidentifier NULL A customer ID, category or area must be provided. They are mutually exclusive. There are ~2000 unique customer ids - CustomerCategory nvarchar(10) NULL ~50 unique values - CustomerArea nvarchar(10) NULL ~30 unique values - StartDate date NOT NULL - EndDate date NOT NULL - MinQuantity int NOT NULL - MaxQuantity int NULL Currently my Containers table contains 9000 rows, and my Items table contains 800000 rows. I now need to create a query that retrieves all Items matching a set of criterias : the container category, the container status (I always need those with a value of 3), the items part (through its ID or category), the items customer (through its ID, category or area), with a valid date (current date must be between StartDate and EndDate), and a valid quantity (a provided quantity must be between MinQuantity and MaxQuantity if not null). I naively wrote the following query:

select Items.ColumnA, Items.ColumnB -- actually I project 13 columns here
from Items
inner join Containers on Items.ContainerId=Containers.Id
where
Containers.Category = 'Category1' and
Containers.Status = 3 and -- always 3 (not parametrized)
(Items.PartId = 'some guid' or Items.PartCategory = 'PartCategory') and
(Items.CustomerId = 'some other guid' or Items.CustomerCategory = 'CustCategory' or Items.CustomerArea='area') and
Items.StartDate = 'some date' and
Items.MinQuantity = 10)

This works and runs in around 200ms on our staging server. Not great, but that was acceptable for single queries. Now, my problem is that we want to prepare catalogs to send to every customer. This means calling this query for hundreds of customers multiplied by around 70000 parts. And that, of course, takes a very long time. We have tried creating an index suggested by Management Studio in the Live Query Statistics, but while it did bring some improvement, we are still trying to improve. Question : 1. Are there any obvious pointers about what can be done to optimize this specific query? I have a developer background and I'm feeling overwhelmed by all the different indexing possibilities. 2. I'm also trying to think of a way to group all my queries into one call to the database, but even if I use things like a stored procedure to loop on inputs and execute my query 1000 times, I fear that the gain will also be small as the database will still have to seek on large indexes, which will still take the most time. Is there any stragegy to optimize grouping calls to this query? *Addendum*: The index that we created after Management Studio's suggestion looks like this:

CREATE NONCLUSTERED INDEX [IX_SomeIndex] ON Items (
  MinQuantity ASC,
  MaxQuantity ASC,
  StartDate ASC,
  EndDate ASC
)
INCLUDE PartId, PartCategory, CustomerId, CustomerCategory, CustomerArea, ContainerId, Column1, Column2