As you already know, using MySQL indexes can really improve performance dramatically. This is just a record of how dramatic that difference can be.

I had two tables that were used PHP program that someone else developed as seen below:

+---------------------------------+--------------+------+-----+---------------------+----------------+
| Field                           | Type         | Null | Key | Default             | Extra          |
+---------------------------------+--------------+------+-----+---------------------+----------------+
| customers_id                    | int(11)      | NO   | PRI | NULL                | auto_increment |
| customers_gender                | char(1)      | NO   |     |                     |                |
| customers_firstname             | varchar(32)  | NO   |     |                     |                |
| customers_lastname              | varchar(32)  | NO   |     |                     |                |
| customers_dob                   | datetime     | NO   |     | 0000-00-00 00:00:00 |                |
| customers_email_address         | varchar(96)  | NO   |     |                     |                |
| customers_default_address_id    | int(11)      | NO   |     | 0                   |                |
| customers_telephone             | varchar(32)  | NO   |     |                     |                |
| customers_fax                   | varchar(32)  | YES  |     | NULL                |                |
| customers_password              | varchar(40)  | NO   |     |                     |                |
| customers_newsletter            | char(1)      | YES  |     | NULL                |                |
| customers_group_id              | int(1)       | YES  |     | NULL                |                |
| customers_group_ra              | int(1)       | YES  |     | NULL                |                |
| customers_payment_allowed       | varchar(255) | NO   |     |                     |                |
| customers_shipment_allowed      | varchar(255) | NO   |     |                     |                |
| customers_order_total_allowed   | varchar(255) | NO   |     |                     |                |
| customers_specific_taxes_exempt | varchar(255) | NO   |     |                     |                |
| entry_company_tax_id            | varchar(32)  | YES  |     | NULL                |                |
+---------------------------------+--------------+------+-----+---------------------+----------------+
+-----------------------------------+-------------+------+-----+---------+----------------+
| Field                             | Type        | Null | Key | Default | Extra          |
+-----------------------------------+-------------+------+-----+---------+----------------+
| membership_id                     | int(7)      | NO   | PRI | NULL    | auto_increment |
| customers_id                      | int(11)     | YES  |     | NULL    |                |
| membership_number                 | varchar(6)  | YES  |     | NULL    |                |
| membership_month_join             | char(2)     | YES  |     | NULL    |                |
| membership_year_join              | varchar(4)  | YES  |     | NULL    |                |
| membership_renewal                | varchar(8)  | YES  |     | NULL    |                |
| membership_comments               | varchar(64) | YES  |     | NULL    |                |
| membership_status                 | char(1)     | YES  |     | NULL    |                |
| membership_type_id                | int(2)      | YES  |     | NULL    |                |
| membership_since                  | varchar(7)  | YES  |     | NULL    |                |
| gs_number                         | varchar(6)  | YES  |     | NULL    |                |
| membership_firstname              | varchar(32) | YES  |     | NULL    |                |
| membership_lastname               | varchar(32) | YES  |     | NULL    |                |
| membership_reinstatement_comments | varchar(65) | YES  |     | NULL    |                |
| membership_day_original_join      | char(2)     | YES  |     | NULL    |                |
| membership_month_original_join    | char(2)     | YES  |     | NULL    |                |
| membership_year_original_join     | varchar(4)  | YES  |     | NULL    |                |
+-----------------------------------+-------------+------+-----+---------+----------------+

They had the following sizes, which did not seem that big to me.

mysql> select count(*) from customers;
+----------+
| count(*) |
+----------+
|     6484 |
+----------+
1 row in set (0.13 sec)

mysql> select count(*) from membership;
+----------+
| count(*) |
+----------+
|     5863 |
+----------+
1 row in set (0.13 sec)

The software was taking too long to load a simple web form. This was looking up some information to populate a data field. With some debugging I found a select with a left join took a really long time to complete.

mysql> select c.customers_id, c.customers_firstname, c.customers_lastname from customers as c left join membership as m on c.customers_id = m.customers_id where m.customers_id IS NULL order by c.customers_lastname;
...
2155 rows in set (8 min 16.99 sec)

The solution was simple, just alter the join id to be an indexed column.

mysql> alter table membership add key(customers_id);
Query OK, 5863 rows affected (0.40 sec)
Records: 5863  Duplicates: 0  Warnings: 0
2155 rows in set (0.66 sec)

After that the selects became as fast as you would expect.

mysql> select c.customers_id, c.customers_firstname, c.customers_lastname from customers as c left join membership as m on c.customers_id = m.customers_id where m.customers_id IS NULL order by c.customers_lastname;
...
2155 rows in set (0.12 sec)