It's normal to take 3 mins 4 seconds when you are running a
large database on a machine that doesn't have enough RAM to
store the entire database in RAM. You're actually having to
access the disk, which is *much* slower than RAM.
If you want faster access times then the best thing you
could do is increase RAM. (Personally I wouldn't have considered
using anything less than 512MB.)
Have you tuned the MySQL variables? Do a 'show variables;' to
see them. What table type are you using? Do a 'show create
table <some_table_name>;' to see what type of tables you are
using. Some MySQL variables are tuned differently depending on
the table type you are using.
At the very least, you should be setting 'key_buffer_size'.
If you are using innodb tables, you should also be setting
'innodb_buffer_pool_size'. Those are the two biggies.
If you are using innodb
tables, then innodb_buffer_pool_size (for a 256MB machine)
should be about 128MB. Key_buffer_size should probably be
set to around 64MB. There are a host of other variables you
can be tuning, too.
Finally, is 500MB too big for a database of 750,000 records?
It depends on how much info is stored in each record.
500MB/750,000 records = 666 bytes/record (max, not taking
into account indexes and empty buffers). If your tables hold only a few
integers in each record then, yes, 666 bytes/record is excessive and
something is wrong. But if these tables have a dozen or more
fields with some of them being text then, no, this would be
reasonable.