Can a binary search be done in a database in SQL?

Question

OK. I am using the C# programming language to access a simple database (on Microsoft SQL Server)

Currently, I am using the DataReader object to access the database. So here is my question: is it possible to do a binary search (in C#) for a particular piece of data so that i can make the search faster?

Currently, I'm using a simple while loop to search the contents of the database. I believe this is done sequentially.

while (pReader.Read())
{
   if ((String)pReader["theData"] == "The_thing_im_searching_for")
   break;
}

So is there any way to do a binary search?

Answer 1

If you're using a database anyways, you should write a select statement to search for what you're looking for instead of iterating through the database manually. There's no reason to reinvent the wheel.

Answer 2

As Donnie points out, if you express your predicate in SQL, the database will select the most efficient way of extracting your data automatically.

Try this:

string sql = "SELECT * FROM Foo WHERE theData = 'The_thing_im_searching_for'"
SqlDataAdapter adapter = new SqlDataAdapter(sql);
DataTable table = new DataTable();
adapter.Fill(table);

foreach(DataRow row in table.Rows) {
    // Do whatever you want here
}

Answer 3

Daniel and Donnie's responses here telling you this is a bad idea are very correct.

However, a more direct answer to your question is that yes you can search binary data, though I'm not sure this is what you are looking for.

MSSQL can store data in the varbinary format, and you can do searches on this varbinary data. In fact you can find more information on doing so in this post: http://stackoverflow.com/questions/976761/dealing-with-a-varbinary-field-in-vb-net

Here's an example of a query doing just that.

byteArrayToken = StringToByteArray(stringToken)
scSelectThing.CommandText = "select thing from table where token=@token"
Dim param As SqlParameter = scSelectThing.Parameters.Add("@token", SqlDbType.VarBinary)
param.Value = byteArrayToken
lbOutput2.Text = scSelectThing.ExecuteScalar()

Answer 4

In the spirit of Donnies answer, I've provided a simple SQL example of how to retrieve what you're after using a more securable mechanism than dynamically constructed SQL (as others have advised you)

In the simple case, you should create a stored procedure for each Create, Read, Update, Delete operation available to the application, per entity in the database. (This isn't 100% true in large production systems, but it's better than dynamically generated SQL constructed in the application)

Now for the READ, this lists all if no parameter is provided. This is a simplified version of an approach a database architect at my job has lectured on -- here we don't separate the retrieve stored procedure from the listing procedure, they are effectively the same operation. This will pay out in less SQL code to maintain in the long run.

CREATE PROCEDURE usp_ReadName 
 @name_id bigint=NULL
AS
BEGIN
 SET NOCOUNT ON;
 if (@name_id IS NULL)
  SELECT name_id,name,description 
            from name with(nolock)
 else
  select name_id,name,description 
            from name with(nolock) 
            where name_id = @name_id  
END
GO

Now for the C# side. To hold the results we define a data transfer entity. Generally speaking these are lighter weight than a datatable faster and more efficient to use. If speed, large volumes of data or limited memory are not a concern just go with a datatable. (On average you'll save roughly 40%+ memory, and about 10% speed - 100K records of the structure above peaks memory use at 140MB with a datatable while the DTE peaks at 78MB)

/// <summary>
/// A simple data transfer entity
/// </summary>
public struct name_data
{
    public long name_id;
    public string name;
    public string description;
    public name_data(long id, string n, string d)
    {
        name_id = id;
        name = n;
        description = d;
    }
}

Now we capture the results in C# using the nullable parameter syntax. This code assumes you've already opened the sql connection

conn.Open();
using (SqlCommand cmd = new SqlCommand("usp_ReadName",conn))
{
    cmd.CommandType = CommandType.StoredProcedure;
    if (id.HasValue)
        cmd.Parameters.Add("@name_id", SqlDbType.BigInt).Value = id.Value;
    using (SqlDataReader reader = cmd.ExecuteReader())
    {

        if (reader.HasRows)
        {
            while (reader.Read())
            {
                dte.name_data item = new dte.name_data(
                    (long)reader["name_id"],
                    reader["name"].ToString(),
                    reader["description"].ToString());
                items.Add(item);
            }
        }
    }
}

Answer 5

So is there any way to do a binary search?

The problem with a straight SELECT on the SQL Server side is that the DB will do a linear search through the table unless the column you're working with has an index on it; then the DB can be smarter.

If you need to read the entire table anyway (for example, so you can search it again a short time later), then you might consider using ArrayList.BinarySearch(). Of course, for that to work, the data will need to be in sorted order in the ArrayList.

Answer 6

Thanks for all the Information (Jay Here again). I believe i have my question answered.

The thing is, I have a lot of information in the database. Searching for a particular item would take a lot of time. So i was interested in doing a binary search.

When i do a SELECT command to find something, i do not know whether or not MSSQL (in the back ground) does a binary search. But if what RickNZ (above) says is true

The problem with a straight SELECT on the SQL Server side is that the DB will do a linear search through the table unless the column you're working with has an index on it; then the DB can be smarter.

Then the database will do the search most effeciently (a binary search) if i had the information "indexed".