Q:

Selecting id's where all rows match

I have two tables : DOCUMENT and METADATA. DOCUMENT stores an ID and some informations we're not interested in, METADATA stores "tags" for those documents. A tag is composed of a key and a value.
So for one document, there is only one entry in the DOCUMENT table, but possibly many in the METADATA table.
Now what I need is to pass a set of keys/values, and retrieve from the METADATA table only the documents that match ALL the keys/values. Which means inspecting different rows "at the same time", well, I don't really know how to do it.
Quick example:
META_KEY | META_VALUE | META_DOCUMENT_ID
----------------------------------------
Firstname| Chris      | 1
Lastname | Doe        | 1
Firstname| Chris      | 2
Lastname | Moe        | 2

So if I query with the following tags : "Firstname"="Chris", "Lastname"="Doe", I want 1 as result. If I only specify "Firstname"="Chris" I want both 1 and 2 as results.
Thanks a lot for any help !

EDIT :
How about something where I count the number of tags that have to match ? 
Like this :
select meta_document_id, count(*) from metadata where (meta_key = 'Firstname' and meta_value = 'Chris') or (meta_key = 'Lastname' and meta_value = 'Doe') group by meta_document_id
With the count(*) I can easily find out if all the input key/value pairs have matched. How would that run performance-wise ?

A:

Well, you are employing a database model named "key-value" or "Entity-attributte-value".
This is usually not a best choice, you can read more on this in these questions:

Key/Value pairs in a database table
Key value pairs in relational database

You need two separate queries for these two cases like this:
SELECT distinct META_DOCUMENT_ID
FROM METADATA 
WHERE meta_key = 'Firstname' and meta_value = 'Chris'

SELECT distinct m1.META_DOCUMENT_ID
FROM METADATA m1
JOIN METADATA m2
ON m1.META_DOCUMENT_ID = m2.META_DOCUMENT_ID
WHERE m1.meta_key = 'Firstname' and m1.meta_value = 'Chris'
  AND m2.meta_key = 'Lastname' and m2.meta_value = 'Doe'

EDIT:

I suppose I'll have to join N times the table for N key/value pairs ?

This could be done without a join, for example like below (assuming that each id has no more than 1 meta_key value):
SELECT META_DOCUMENT_ID
FROM METADATA 
WHERE (meta_key, meta_value) IN
   ( ('Firstname' ,'Chris'), ('Lastname', 'Doe' ) )
GROUP BY META_DOCUMENT_ID
HAVING COUNT(*) = 2 /* 2 means that we are looking for 2 meta keys */

How is that going to run performance-wise ?

Terribly. See an explanation from links above about this model.
This query must in many cases do a full table scan (especially when a number of attributes/keys we are looking for is more than a few), count values for each id, then pick these id that have count = 2.
In a normalized model this is a simple query that can use indexes to quickly pick only these few rows with firstname = 'Chris'
SELECT *
FROM table 
WHERE firstname = 'Chris' and lastname = 'Doe' 

