Tabla con búsqueda con ajax

Hola todos de antemano muchas gracias. Esta vez tengo una duda conceptual. Verán, tengo una tabla de clientes que tiene el nombre y el teléfono del cliente. Y quiero tener un campo arriba para buscar el cliente pero que a medida que escribo el nombre filtre las filas de la tabla que están debajo de la tabla.

Se hacer esto con ajax, es decir capturando el evento key up.

Sin embargo me parece que hacer una consulta por cada vez que el usuario presiona la letra para ir filtrando podría saturar mucho la base de datos.

Estuve viendo librerías jquery y js que ya hacen esto pero lo que entiendo es que uno les pasa toda la lista de datos. Es decir si tengo 5000 clientes tengo que hacer la consulta de los 5000 clientes y pasársela y ya la librera hace la paginación y demás cosas mediante js.

Sin embargo también me parece poco óptimo hacer una consulta para 5000 clientes cuando en realidad se página por cada 10.

Me pueden ayudar con ideas por favor?

Gracias!

Buenas.

Es q no es lo muy funcional hacerlo en el keyup. Hazlo en el blur.

Un saludo.