(Using Oracle)

I have a table with key/value pairs like this:

create table MESSAGE_INDEX
(
  KEY               VARCHAR2(256) not null,
  VALUE             VARCHAR2(4000) not null,
  MESSAGE_ID        NUMBER not null
)

I now want to find all the messages where key = 'someKey' and value is 'val1', 'val2' or 'val3' - OR value is null in which case there will be no entry in the table at all. This is to save space; there would be a large number of keys with null values if I stored them all.

I think this works:

SELECT message_id
FROM message_index idx
WHERE ((key = 'someKey' AND value IN ('val1', 'val2', 'val3'))
      OR NOT EXISTS (SELECT 1 FROM message_index WHERE key = 'someKey'
      AND idx.message_id = message_id))

But is is extremely slow. Takes 8 seconds with 700K records in message_index and there will be many more records and more search criteria when moving outside of my test environment.

Primary key is key, value, message_id:

  add constraint PK_KEY_VALUE primary key (KEY, VALUE, MESSAGE_ID)

And I added another index for message_id, to speed up searching for missing keys:

create index IDX_MESSAGE_ID on MESSAGE_INDEX (MESSAGE_ID)

I will be doing several of these key/value lookups in every search, not just one as shown above. So far I am doing them nested, where output id's of one level is the input to the next. E.g.:

SELECT message_id from message_index
WHERE (key/value compare)
AND message_id IN
  (
    SELECT ... and so on
  )

What can I do to speed this up?