You can make one large query, many small ones (joining data in memory in PHP), or you can do a different concept:
- Each genre has it's own unique bit (1, 2, 4, 8, 16, ...)
- A search checks for bitwise AND of those genres vs your search mask.
A similar system (if bitwise AND not supported) would be to use a char field and compare with a regex. E.g. to be "metal" and "progressive", could be "YY", while "metal" without "progressive" would be "YN". Then regex could match only Y's.