>In one particular situation, once I scan my dataset to show the records, I need to lookup for a particular record inside of it. So, basically, for each record, I also need to search into that same dataset for another record to see if it is present. This is based on a condition and all the required fields are part of the dataset. Given the fact that I can have up to 1000 records, will this be still as fast and how can I accomplish this?

Are you looking up a record based on the PK of the record, and is it a typed dataset?
If so there is a method created FindByYourPKHere() that you can use.