AFAIK telegram dont have any super-advanced search features neither it instantly return you results for all these years. Also if you search less common terms it's usually take longer than less than second.
And if you just run client on device without a lot of this history cached search wouldn't be anywhere as fast as you expect. So I pretty sure there no server-side magic there, but instead very good UX.
Also I can tell for certain that with right index grepping tons of JSONs can be very effective on any modern devices.