SqlParameter causes slow MSSQL queries

Hi,

I'm currently creating a frontend for searching information in a MSSQL database and I'm facing the problem that it is so slow when I use a statement with placeholders and SqlParameter, that it runs into a timeout. Using the variable directly (string.Format, which is of course prone to SQL-Injection attacks) is fast, so I'm guessing it has to do with the SqlParameter.

The database has the following format and contains about 115.000.000 entries:

Code:

CREATE TABLE ExampleTable (
	ID INT NOT NULL,
	Name VARCHAR(128) NOT NULL DEFAULT '',
	Class CHAR(1) NOT NULL DEFAULT 'M',
	PRIMARY KEY (ID)
);

The tips I found while browsing the Internet basically consisted of those two things:

Set ArithAbort ON
Use explicit datatypes for the SqlParameter

So my code currently looks like this (simplified):

Code:

string searchName = "%SomeValue%";

SqlConnection connection = new SqlConnection(string.Format("Data Source={0};Database={1};Trusted_Connection=true", CONNECTION_SERVER, CONNECTION_DATABASE));
connection.Open();
new SqlCommand("SET ARITHABORT ON;", connection).ExecuteNonQuery();

using (SqlCommand command = new SqlCommand("SELECT TOP 100 ID, Name FROM dbo.ExampleTable WHERE Name LIKE [at]Name;", connection)) // Replace [at] with @, Elitepvpers replaces it with some [mention] tag
{
	command.Parameters.Add(new SqlParameter("Name", SqlDbType.VarChar, 128)).Value = searchName;
	List<ExampleClass> names = new List<ExampleClass>();
	using (SqlDataReader reader = command.ExecuteReader()) // This is where the timeout occurs.
	{
		while (reader.Read())
		{
			names.Add(new ExampleClass((int)reader[0], (string)reader[1]));
		}
	}
	// Do something with List<ExampleClass> names.
}

But if I do the following instead it is fast:

Code:

// ...
using (SqlCommand command = new SqlCommand(string.Format("SELECT TOP 100 ID, Name FROM dbo.ExampleTable WHERE Name LIKE '{0}';", searchName), connection))
// ...

I also tried setting all the other variables a SqlCommand can be constructed with with no change to the outcome.

Do you have any more tips what I can do?
Thanks in advance,
Mi4uric3