Sql server index for parameterized query

Question

I want to create best index for sql query. User can pick options on UI, from which query is built. Here are table and query:

CREATE TABLE [dbo].[MyTable](
    [Id] [nvarchar](32) NOT NULL,
    [SomeKey] [int] NOT NULL,
    [Col1] [nvarchar](max) NULL,
    [Col2] [nvarchar](max) NULL,
    [NumCol1] [int] NOT NULL,
    [NumCol2] [int] NOT NULL,
    [BitCol1] [bit] NOT NULL,
    [BitCol2] [bit] NOT NULL,
    [Created] [datetime] NOT NULL
CONSTRAINT [PK_dbo.MyTable] PRIMARY KEY CLUSTERED 
(
    [Id] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY] TEXTIMAGE_ON [PRIMARY]

and the query is here (SP):

ALTER PROCEDURE [dbo].[MyTable] 
@SomeKey INT,@Col1 BIT,@Col2 BIT,@BitCol1 BIT,@BitCol2 BIT,
@NumCol1 INT,@NumCol2 INT,@offset INT,@take INT
AS
DECLARE @sql NVARCHAR(MAX), @paramlist  nvarchar(4000) 
SET @sql = 'SELECT [Id],[SomeKey],[Col1],[Col2],[NumCol1],[NumCol2],[BitCol1],[BitCol2], FROM MyTable WHERE SomeKey = @SomeKey'
IF @NumCol1 IS NOT NULL SELECT @sql = @sql + ' AND NumCol1 = @NumCol1'
IF @NumCol2 IS NOT NULL SELECT @sql = @sql + ' AND (NumCol2 > @NumCol2)'
IF @Col1 IS NOT NULL SELECT @sql = @sql + ' AND (Col1 = '''' OR Col1 IS NULL)'
IF @Col2 IS NOT NULL SELECT @sql = @sql + ' AND (Col2 = '''' OR Col2 IS NULL)'
IF @BitCol1 IS NOT NULL SELECT @sql = @sql + ' AND BitCol1 = 1'
IF @BitCol2 IS NOT NULL SELECT @sql = @sql + ' AND BitCol2 = 1'
SELECT @sql = @sql + ' ORDER BY Created OFFSET @offset ROWS FETCH NEXT @take ROWS ONLY'
SELECT @paramlist = '@SomeKey INT, @Col1 INT, ....'
EXEC sp_executesql @sql, @paramlist, @SomeKey, @Col1, @Col2, ...

hope you get the point. I'm building query string in db, and executing it. If I send param Col1 = true, that means I want all empty Col1 from db. From app i make sure that I prepare all params. Rest is self-explanatory i hope (but please feel free to ask any question in comment)!

How to make index for this table/query, to avoid index scan or similar 'slow' searches? And, I'm just a web developer, so this (advanced) indexing is something new for me! Db is SQL Server 2012.

UPDATE: usage scenario
Table will have from 100k to 10m-20m rows max. Rows will not be updated. Insert will be done in bulk of 500 (sqlbulkcopy c# class), every 5-10mins or more, when app is running (its not running always). Once every week-two some rows will be deleted (based on SomeKey col).
App will not have many users (maybe few in same time, 10 at most), so don't expect many queries/sec (1 query every 5-10 sec?), but i would like it to be fast (measured in ms, not sec).

Answer 1

Index is a trade off. It must be updated on data changes in the table, so be careful with tables with lots of INSERT and UPDATE.

In SQL Server Management Studio you can see execution play for Your query. There are options for that under Query menu. You will be able to see what takes most time during Your query execution.

Other option is Tuning advisor accessible from menu Tools > Database Engine Tuning Advisor. It will propose indexes to create.

Whatever variable You have in searches like WHERE is a good candidate to be indexed.

Index is not something that will kill You. You can play with it to find best solution and You can make changes during production without major problems. Unfortunately decision if You need index is not only based on table design, but also on amount of data in this table, data diversity and nature of operations You perform on the table.

Update:

What may help You:

MSDN Query Performance

MSDN Query Tuning

Referring to Your execution plan I recommend You to read part about Understanding Nested Loops Joins

Index scan is usually result of retrieving big percentage of data from given column.