Topic: Load Set at Once or Delay?

Hi - I've got a quick question on what the best way of doing this may be...

I have a few index pages with a search table.  What I used to do is take all 700+ records and load them with the page load.  Then, filter thru everything using jQuery.   The result was an initial load that would take a few extra seconds, but the searching was incredibly fast. 

Our App is on Heroku, so to make the requests take less time (as we have 10+ constant users) I only load the first 12 and with some ajax calls call up the data.  This has the opposite result (our index page loads super fast but each key down brings up a loading screen and the requests take a while).

What is the best way to fix this?

I'm thinking that I should just load the table once, cacheing each generated row (per the record) and then only update the cache when a record is created/updated/deleted.  Then I can just use the existing jQuery table search.  Is this going to be faster or will checking if the cache is expired for each row cause the same slow down?  What's the best way to speed this up?