Q:

How to implement a search system in a database for an iphone application

This is pretty wide question, but I'm hoping to get a push in the right direction (technologies and methodology).
Ok, I have an iphone app (which I am developing) that works with a web service (c#) through http requests. The web service connects to the underlying database, extracts the necessary data depending on the request and feeds it back to the application. 
Now, I need to implement a search system in the app. The user searches for some words, and I need to provide the most relevant results. The search must be performed on different tables in the database.  Each table can be searched in a number of columns. For example, when searching through the people table I need to search in the first name, lastname, company, and other fields. Other tables have other important columns.
I have so many questions that I don't even know where to start.  
How do I make my sql queries to make the search, but still be fast enough. Do I need to make some extra tables with indexed content somehow?
How should I add relevance factor to the results so I can ultimately filter only the most relevant results? For example, if an user searches for Smith, maybe there is a person named Smith or even a Company. They should be displayed before any other content that can have smith in the description.
I know the question is a little vague/wide but I can explain more if somebody desires.
Thank you

A:

In the end I have decided to use Lucene. It's a wonderful piece of technology and even if I had some doubts in the beginning, after reading 3/4 of the book called "Lucene in Action" it was clear to me that it had everything I needed (and much more). 
I know it's not a fully-functional searching system (with all the elements needed), but merely a library handling the core of a search system. It will need some work to integrate it with my application/webservice/database. I will let you know how it goes :)
Thanks for your input!

