How simultaneous queries are handled in a MySQL database?
Queries are always handled in parallel between multiple sessions (i.e. client connections). All queries on a single connections are run one-after-another. The level of parallelism between multiple connections can be configured depending on your available server resources.
Generally, some operations are guarded between individual query sessions (called transactions). These are supported by InnoDB backends, but not MyISAM tables (but it supports a concept called atomic operations). There are various level of isolation which differ in which operations are guarded from each other (and thus how operations in one parallel transactions affect another) and in their performance impact.
Each connection can run a maximum of one query at once, and does it in a single thread. The server opens one thread per query.
Normally, hopefully, queries don't block each other. Depending on the engine and the queries however, they may. There is a lot of locking in MySQL which is discussed in some detail in the manual.
However, if they don't block each other, they can still slow each other down by consuming resources. IO operations are a particular source of these slow-downs. If your data don't fit in memory, you should really limit the number of parallel queries to what your IO subsystem can handle, or things will get really bad. Measurement is the key.
I would normally say that if 500 queries are running at once (and NOT waiting on locks), you may not be getting best value from your hardware (do you have 500 cores? How many threads are waiting for IO?)
Normally all queries will be run in parallel.
But... there are some exceptions to that. Depending on your transaction isolation level a row can be locked while updating. Read more about that over here: http://dev.mysql.com/doc/refman/5.1/en/dynindex-isolevel.html