Multi column indexing question

[Yu-Hwei Chou]

Hi everyone,
I am building a database of songs with various attributes to each song. Originally had all attributes attached to the songName in one big table. Then realized that all my select queries would not be indexable because of this rather inconvenient Prefix problem:

It says in the documentation that multi column indexes will only work if your select statement involves the leftmost prefixes in your table. How can that possibly be done? Here's my take on it:

1) Normally the first column of any table is the Primary key (it has to be) and it's usually a unique auto increment int. Any select statement construed will never be concerned with such a column since it is not useful. I don't ever want to write "SELECT songName FROM table WHERE col1 BETWEEN 1 AND 65;" for example. What I would like to do is say "SELECT songName where bandname='Nora Jones" or something like that. So how do I write a SELECT that can use a multicolumn index while bypassing the useless column for Primary key? the only thing I thought up was something like :
"SELECT songName FROM table WHERE col1 IS NOT NULL AND col2='Nora Jones AND col3='piano';. (Assuming I have a 3 column "Multi index" of col1, col2 and col3).

But my question is" Am I nullifying the efficiency of my index by selecting for all non null rows for col1?"

Thanks for your advice.