This means that you should use EXPLAIN to get hints on how to optimize your query.
If a full tablescan is required, it means that there is no index/primary key on the table; for each execution, the table has to be looked up record by record. This is time consuming and even will cause heavy activity on your harddrives. With smalls tables, this problem is less important, but if you have huge tables with thousands ore more records, your query times will be awfully slow, you might even get timeouts.
An index can speed up the query significantely and reduce disc access.
I don't know about MySql, but on Oracle DBs , full tablescns are never cached, so you start the same thing over and over again. Index queries are cached which, again, increases performance.