high requests in large table

Dear Tobias Bäthge
Thank you for your awesome plugins. I really appreciate your work on this plugin.
one thing that one of my client asked to fix for him was the large amount of requests that takes time when his page load big table with more that 4000 rows of their company phone numbers. it is so important to search between data and find exact match of search query but one thing that he suffer from is the first loading time before pagination become active. I mean before everything would be ready for search and pagination his page takes time to load all 4000 rows then pagination start to change UI and page is ready to use. I was wondering to ask you is there any way to make the amount of requests less than what it is and let user ask for next page then the next 10 rows would be load? (but searching would work through all data?)
I told the client that as the table apply ajax search all his data must load first so it needs that much request to load all 4000 rows. and if he want the high performance in search and filtering so he need to wait for table rows to be fully load and then pagination to become visible. he didn’t accept and ask me to make the request to be less than what it is. I told him he must reduce the size of data but i will work on it.
my question is: is there a way to make request less than what it is? is there a way to not load whole data before pagination requests? (for example the third 10rows only loads when the user click on the page 3 but searching through whole database would work as usual?)
tnx for your respond