title: Search from Multiple columns in Where clause for SQL Server
body: <p>We have a stored procedure that is used to allow users to search in a table with 20 million records and 40 columns wide. There are about 20 different columns they can search on (any combination) from and all those columns are in the <code>WHERE</code> clause. </p>
  
  <p>Furthermore each columns is checked for Null and needs to be able to search with just part of the data.</p>
  
  <p>Here is an example</p>
  
  <pre><code>(
      @FirstName IS NULL
      OR (RTRIM(UPPER(FirstName)) LIKE RTRIM(UPPER(@FirstName)) + '%')
  )
  AND (@LastName IS NULL)
  </code></pre>
  
  <p>What is a best way to rewrite this stored procedure? Should I break this stored procedure into multiple small stored procedures? If so how? I will need to allow user to search  </p>
  
  <p>When I look at the execution plan, regardless of what columns are passed, it always does the index scan</p>