The current search functionality only attempts a 'contains' search on activity descriptions - As a result, SQL Timeouts are common if the user searches the description field for a string.
It would be helpful if the application would allow fields to utilize a full-text index if available. - This could be automatic if the app could identify when an index is available and use it - or if needed, an option to configuration an attribute to 'Leverage existing full-text index' and then the DBA could create / manage the indexes that are appropriate for their environment.
Good news! Microsoft Dynamics CRM 2015 provides Full Text indexing for On Premise organizations. Enhanced search experience with improved query performance can be achieved using this new feature. Refer this link for more details https://technet.microsoft.com/en-us/library/dn919650.aspx