I think that 4,000,000 pales into insignificance compared to the Google version :)
Seriously more important to consider are the number of records returned each time and how often you're querying, the Pro Ajax book example has a built-in delay to stop too many requests.
Which database you are using as well as the server spec will obviously matter too.
--
Joe (
Microsoft MVP - XML)