Porque no usas alguno de los tantos paginadores y buscadores que existen con jQuery, son excelentes y salvo que tu aplicación sea muy grande el funcionamiento tambien lo es, como por ejemplo
http://datatables.net/ ahi te ahorras de ir a la base de datos tanto para paginar como para realizar las busquedas!!
Saludos!!
Nico.