SQL - Optimizing complex paged search querys

I'm currently developing a stored procedure for a complex search in a big database. Because there are many thousand entries, that could be returned I want to use paging. Although it is working, I think it's too slow. I read a lot of posts and articles regarding pagination of SQL queries and optimizing performance. But most 'optimizations' were only helpful for very basic requests like 'give items 20-30 from table x'.

Since our world is not that simple and there are more complex queries to make I would like to get some help optimizing the following query:

CREATE PROCEDURE [SearchItems]
@SAttr1 BIT = 0,
@SAttr2 BIT = 0,
@SAttr3 BIT = 0,
@Flag1 BIT = 0,
@Flag2 BIT = 0,
@Param1 VARCHAR(20),
@Param2 VARCHAR(10),
@SkipCount BIGINT,
@TakeCount BIGINT,
@SearchStrings NVARCHAR(1000)    
AS
    DECLARE @SearchStringsT TABLE(
        Val NVARCHAR(30)
    )

    INSERT INTO @SearchStringsT 
    SELECT * FROM dbo.Split(@SearchStrings,',');

WITH ResultTable AS (
    SELECT  Table1.*, ROW_NUMBER() OVER(ORDER BY Table1.ID ASC) AS [!ROWNUM!]
    FROM Table1
    INNER JOIN Table2 ON Table1.ID = Table2.FK1
    INNER JOIN Table3 ON Table2.ID = Table3.FK2
    INNER JOIN Table4 ON Table3.XX = Table4.FKX
    WHERE Table1.X1 = @Parameter1
    AND
        (@Flag1 = 0 OR Table1.X2 = 1) AND
        (@Flag2 = 0 OR Table2.X4 = @Parameter2) AND
        (@Flag3 = 0 OR EXISTS(SELECT * FROM Table5 WHERE Table5.ID = Table3.X1)) 
    AND
    (                   
        (@SAttr1 = 0 OR EXISTS(SELECT * FROM @SearchStringsT WHERE Table1.X1 LIKE Val)) OR
        (@SAttr2 = 0 OR EXISTS(SELECT * FROM @SearchStringsT WHERE Table2.X1 LIKE Val)) OR
        (@SAttr3 = 0 OR EXISTS(SELECT * FROM @SearchStringsT WHERE Table3.X1 LIKE Val)) OR
        (@SAttr4 = 0 OR EXISTS(SELECT * FROM @SearchStringsT WHERE Table4.X1 LIKE Val))
    )
)
SELECT TOP(@TakeCount) * FROM ResultTable
WHERE [!ROWNUM!] BETWEEN (@SkipCount + 1) AND (@SkipCount + @TakeCount)
RETURN

The @SAttr parameters are bit parameters to specify whether to search a field or not , the @Flag parameters are turning on/off checking of some boolean expressions, @SkipCount and @TakeCount are used for paging. @SearchString is a comma separated list of search keywords, already including the wild cards.

I hope someone can help me optimizing this, because a single search in a database with 20.000 entries in the main table lasts 800ms and its increasing with entry count. The final application needs to deal with over 100.000 entries.

I thank you very much for every help. Marks

While I agree with Tom H. that this may be a case where dynamic SQL is best (and I'm a stored proc kinds girl, so I don't say that very often), it may be that you don't have good indexing on your tables. Are all the possible search fields indexed? Are all the FKs indexed?

I mean 20,000 is a tiny, tiny table and 100,000 is too, so it really seems as if you might not have indexed yet.

Check your execution plan to see if indexes are being used.