How a search function searches

I've beeing giving a thought about a search function upon related list.
My app has an incremental search by extending an original android incremetanl search, so you can find a record easily with typing prefix keywords on the search box.

My app's stance when downloading data from salesforce server, basically child-to-parent relationship is respected. For instance, when an Event that has a contact and an opportunity, the app is trying to retrieve the event and then the contact and the opportunity, and then Accounts of the contact and the opportunity programatically. However when it comes to parent-to-child like account-to-opportunity, the app does not try to download. Now Event and Task objects are root objects now.

So going back to this topic - how a search function searches - especially for related lists, there should be 3 options as the followings.

1. show records stored in the local database only (such as the image below)
2. add online search function and download them into the local database
3. baciacaly respects #1 and improve data sync mechanism for retrieving parent-to-child.

Which one is the best? #2 or #3 seem good to be implemented but data volume would be an issue if a user has lots of events and tasks.

Possible to improve the incremental search box that tries to search every users input something words? API calls would be increased radically.