Visual Basic - Saber num. registros sin recordset

Hay alguna manera de saber el numero de registros que tienen las tablas de una base de datos sin tener que crear un recordset para cada una de ellas y luego hacer un recordcount?. El problema haciendo un recordset es que si la tabla tiene muchos registros me tarda mucho tiempo en darme esa información.

Gracias.

Por cierto, las tablas están en una base de datos de access

Fijate con: SELECT COUNT(*) AS CantRegistros FROM MiTabla

Gracias Cecilia, esto ha solucionado mi problema. Añado un poco más de código por si a alguien le interesa:

rs.open("SELECT COUNT(*) FROM " & miTabla,cnn,1,4)