Database table size did not decrease proportionately

Question

I am working with a PostgreSQL 8.4.13 database.
Recently I had around around 86.5 million records in a table. I deleted almost all of them - only 5000 records are left. I ran

reindex

and

vacuum analyze

after deleting the rows. But I still see that the table is occupying a large disk space:

jbossql=> SELECT pg_size_pretty(pg_total_relation_size('my_table'));
pg_size_pretty 
----------------
7673 MB

Also, the index value of the remaining rows are pretty high still - like in the million range. I thought after vacuuming and re-indexing, the index of the remaining rows would start from 1.

I read the documentation and it's pretty clear that my understanding of re-indexing was skewed.

But nonetheless, my intention is to reduce the table size after delete operation and bring down the index values so that the read operations (SELECT) from the table does not take that long - currently it's taking me around 40 seconds to retrieve just one record from my table.

Update

Thanks Erwin. I have corrected the pg version number.

vacuum full

worked for me. I have one follow up question here:
Restart primary key numbers of existing rows after deleting most of a big table

Answer 1

To actually return disk space to the OS, run VACUUM FULL.

A lot more details in this closely related recent answer on dba.SE.