Selecting id's where all rows match

Question

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 ?

Answer 1

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' 

Answer 2

Oracle Setup:

CREATE TYPE KEY_VALUE_PAIR IS OBJECT (
  KEY   VARCHAR2(50),
  VALUE VARCHAR2(50)
);
/

CREATE TYPE KEY_VALUE_TABLE IS TABLE OF KEY_VALUE_PAIR;
/

CREATE TABLE meta_data ( meta_key, meta_value, meta_document_id ) AS
SELECT 'Firstname',   'Chris',    1 FROM DUAL UNION ALL
SELECT 'Lastname',    'Doe',      1 FROM DUAL UNION ALL
SELECT 'Phonenumber', '555-2368', 1 FROM DUAL UNION ALL
SELECT 'Firstname',   'Chris',    2 FROM DUAL UNION ALL
SELECT 'Lastname',    'Moe',      2 FROM DUAL UNION ALL
SELECT 'Phonenumber', '555-0001', 2 FROM DUAL;

Query:

SELECT meta_document_id
FROM   (
  SELECT meta_document_id,
         CAST(
           COLLECT(
             KEY_VALUE_PAIR( meta_key, meta_value )
           ) AS KEY_VALUE_TABLE
         ) AS key_values
  FROM   meta_data
  GROUP BY meta_document_id
)
WHERE  KEY_VALUE_TABLE(
         -- Your values here:
         KEY_VALUE_PAIR( 'Firstname', 'Chris' ),
         KEY_VALUE_PAIR( 'Lastname',  'Doe' )
       )
       SUBMULTISET OF key_values;

Output:

 META_DOCUMENT_ID
------------------
                1

Update - Reimplementing the meta data table using a nested table:

Oracle Setup:

CREATE TYPE KEY_VALUE_PAIR IS OBJECT (
  META_KEY   VARCHAR2(50),
  META_VALUE VARCHAR2(50)
);
/

CREATE TYPE KEY_VALUE_TABLE IS TABLE OF KEY_VALUE_PAIR;
/

CREATE TABLE meta_data (
  meta_document_id INT,
  key_values       KEY_VALUE_TABLE
) NESTED TABLE key_values STORE AS meta_data_key_values;

CREATE UNIQUE INDEX META_DATA_KEY_VALUES_IDX ON META_DATA_KEY_VALUES (
  NESTED_TABLE_ID,
  META_KEY,
  META_VALUE
);
/

-- Insert everything in one go:
INSERT INTO META_DATA VALUES(
  1,
  KEY_VALUE_TABLE(
    KEY_VALUE_PAIR( 'Firstname',   'Chris' ),
    KEY_VALUE_PAIR( 'Lastname',    'Doe' ),
    KEY_VALUE_PAIR( 'Phonenumber', '555-2368' )
  )
);

-- Insert everything in bits:
INSERT INTO meta_data VALUE ( 2, KEY_VALUE_TABLE() );

INSERT INTO TABLE( SELECT key_values FROM meta_data WHERE meta_document_id = 2 )
  ( meta_key, meta_value ) VALUES( 'Firstname', 'Chris' );
INSERT INTO TABLE( SELECT key_values FROM meta_data WHERE meta_document_id = 2 )
  ( meta_key, meta_value ) VALUES( 'Lastname', 'Moe' );
INSERT INTO TABLE( SELECT key_values FROM meta_data WHERE meta_document_id = 2 )
  ( meta_key, meta_value ) VALUES( 'Phonenumber', '555-0001' );

--Select all the key-value pairs:
SELECT META_DOCUMENT_ID,
       META_KEY,
       META_VALUE
FROM   META_DATA md,
       TABLE( md.KEY_VALUES );

Query:

The changes above let you simplify the query a lot:

SELECT META_DOCUMENT_ID
FROM   meta_data
WHERE  KEY_VALUE_TABLE(
         -- Your values here:
         KEY_VALUE_PAIR( 'Firstname', 'Chris' ),
         KEY_VALUE_PAIR( 'Lastname',  'Doe' )
       )
       SUBMULTISET OF key_values;

Answer 3

If you know in advance all the possible TAGS, an approach could be with some PIVOT:

with METADATA (META_KEY, META_VALUE, META_DOCUMENT_ID) as
(
select 'Firstname', 'Chris',1 from dual union all
select 'Lastname', 'Doe',1 from dual union all
select 'Firstname', 'Chris',2 from dual union all
select 'Lastname', 'Moe',2 from dual
)
select *
from metadata
PIVOT  ( max (META_VALUE ) FOR (META_KEY) IN ('Firstname' AS Firstname, 'Lastname' AS Lastname))
where Firstname = 'Chris' /* and Lastname ='Doe' ...*/