How can I speed up this linq function for sql?

I have a function (called "powersearch", ironic!) That searches a set of rows through a bunch of (~ 5) fields. Words enter as one line and are separated by spaces.
Some fields may be exact matches, others must contain "contains".

(Filmed for brevity)

//Start with all colors
IQueryable<Color> q = db.Colors;
//Filter by powersearch
if (!string.IsNullOrEmpty(searchBag.PowerSearchKeys)){
    foreach (string key in searchBag.SplitSearchKeys(searchBag.PowerSearchKeys)
                                    .Where(k=> !string.IsNullOrEmpty(k))){
        //Make a local copy of the var, otherwise it gets overwritten
        string myKey = key;
        int year;
        if (int.TryParse(myKey, out year) && year > 999){
            q = q.Where(c => c.Company.Name.Contains(myKey)
                || c.StockCode.Contains(myKey)                                
                || c.PaintCodes.Any(p => p.Code.Equals(myKey))
                || c.Names.Any(n => n.Label.Contains(myKey))
                || c.Company.CompanyModels.Any(m => m.Model.Name.Contains(myKey))
                || c.UseYears.Any(y => y.Year.Equals(year))
            );
        }
        else{
            q = q.Where(c => c.Company.Name.Contains(myKey)
                || c.StockCode.Contains(myKey)
                || c.PaintCodes.Any(p => p.Code.Contains(myKey))
                || c.Names.Any(n => n.Label.Contains(myKey))                                
                || c.Company.CompanyModels.Any(m => m.Model.Name.Equals(myKey))
            );
        }
    }
}

      

        
        
        
      

    

Since the amount of using Year is quite large, I tried to test it as little as possible by dropping all numbers that could never be a number, which does it in this case. Similar checks are not possible in other fields as they can contain many conceivable strings.

This query currently takes about 15 seconds for a single non-annual row. It's too much. Anything I can do to improve this?

- Edit - The
profiler shows me the following information for the part where the string is not a year:

exec sp_reset_connection Login Audit

exec sp_executesql N'
SELECT COUNT(*) AS [value]
FROM [dbo].[CLR] AS [t0]
INNER JOIN [dbo].[CO] AS [t1] ON [t1].[CO_ID] = [t0].[CO_ID]
WHERE 
    ([t1].[LONG_NM] LIKE @p0)
    OR ([t0].[EUR_STK_CD] LIKE @p1)
    OR (EXISTS(
        SELECT NULL AS [EMPTY]
        FROM [dbo].[PAINT_CD] AS [t2]
        WHERE ([t2].[PAINT_CD] LIKE @p2)
            AND ([t2].[CLR_ID] = [t0].[CLR_ID])
            AND ([t2].[CUSTOM_ID] = [t0].[CUSTOM_ID])
        )
    )OR (EXISTS(
        SELECT NULL AS [EMPTY]
        FROM [dbo].[CLR_NM] AS [t3]
        WHERE ([t3].[CLR_NM] LIKE @p3)
            AND ([t3].[CLR_ID] = [t0].[CLR_ID])
            AND ([t3].[CUSTOM_ID] = [t0].[CUSTOM_ID])
        )
    ) OR (EXISTS(
        SELECT NULL AS [EMPTY]
        FROM [dbo].[CO_MODL] AS [t4]
        INNER JOIN [dbo].[MODL] AS [t5] ON [t5].[MODL_ID] = [t4].[MODL_ID]
        WHERE ([t5].[MODL_NM] = @p4)
            AND ([t4].[CO_ID] = [t1].[CO_ID])
        )
    )
',N'@p0 varchar(10),@p1 varchar(10),@p2 varchar(10),@p3 varchar(10),@p4 varchar(8)',@p0='%mercedes%',@p1='%mercedes%',@p2='%mercedes%',@p3='%mercedes%',@p4='mercedes'

      

        
        
        
      

    

(took 3626ms) Audit Login (3673ms) exec sp_reset_connection (0ms) Audit Login

exec sp_executesql N'
SELECT TOP (30) 
[t0].[CLR_ID] AS [Id],
[t0].[CUSTOM_ID] AS [CustomId],
[t0].[CO_ID] AS [CompanyId], 
[t0].[EUR_STK_CD] AS [StockCode], 
[t0].[SPCL_USE_CD] AS [UseCode], 
[t0].[EFF_IND] AS [EffectIndicator]
FROM [dbo].[CLR] AS [t0]
INNER JOIN [dbo].[CO] AS [t1] ON [t1].[CO_ID] = [t0].[CO_ID]
WHERE 
    ([t1].[LONG_NM] LIKE @p0)
    OR ([t0].[EUR_STK_CD] LIKE @p1)
    OR (EXISTS(
        SELECT NULL AS [EMPTY]
        FROM [dbo].[PAINT_CD] AS [t2]
        WHERE ([t2].[PAINT_CD] LIKE @p2)
            AND ([t2].[CLR_ID] = [t0].[CLR_ID])
            AND ([t2].[CUSTOM_ID] = [t0].[CUSTOM_ID])
        )
    )
    OR (EXISTS(
        SELECT NULL AS [EMPTY]
        FROM [dbo].[CLR_NM] AS [t3]
        WHERE ([t3].[CLR_NM] LIKE @p3)
            AND ([t3].[CLR_ID] = [t0].[CLR_ID])
            AND ([t3].[CUSTOM_ID] = [t0].[CUSTOM_ID])
        )
    )
    OR (EXISTS(
        SELECT NULL AS [EMPTY]
        FROM [dbo].[CO_MODL] AS [t4]
        INNER JOIN [dbo].[MODL] AS [t5] ON [t5].[MODL_ID] = [t4].[MODL_ID]
        WHERE ([t5].[MODL_NM] = @p4)
            AND ([t4].[CO_ID] = [t1].[CO_ID])
        )
    )'
,N'@p0 varchar(10),@p1 varchar(10),@p2 varchar(10),@p3 varchar(10),@p4 varchar(8)',@p0='%mercedes%',@p1='%mercedes%',@p2='%mercedes%',@p3='%mercedes%',@p4='mercedes'

      

        
        
        
      

    

(took 3368 msec)

The database structure is unfortunately not under my control. It comes from the US and should remain in the same format for compatibility reasons. While most of the important fields are indeed indexed, they are indexed into (unnecessary) clustered primary keys. I can do little about it.