I have the following query:

SELECT z303_rec_key FROM z303
WHERE z303_rec_key NOT IN
(SELECT z308_id FROM z308
WHERE substr(z308_rec_key,1,2) = '01');

This looks at two tables: z303 and z308
The only part of z303 I want to use is:

Z303_REC_KEY...............................NOT NULL CHAR(12)

and the description of z308 is this:

Z308_REC_KEY...............................NOT NULL CHAR(22)
Z308_VERIFICATION........................VARCHAR2( 20)
Z308_VERIFICATION_TYPE................CHAR(2)
Z308_ID........................................VAR CHAR2(12)
Z308_STATUS................................CHAR(2)
Z308_ENCRYPTION..........................CHAR(1)

The first 2 characters of z308_rec_key denote a type e.g. 00 or 01 etc.

The z308_id matches the z303_rec_key.

I wish to return a list of z303_rec_key's where there is no '01' type z308_rec_key.

Seems simple enough in my head...but when I run this query I have to abort. When run, it just sits there for ages and doesnt return any results. The tables are big and I think that the size of these table coupled with the query I have used means that it will take forever and a day to run. [z308 is a table with about 20,000 '01' type rec_key's and so is z303]

Is there any other way I can acheive this?

I use oracle pl/sql but posted here since it seems like a basic sql question...

You could do it this way:
But your own query may work OK if you remove the unwanted reference to z308 from the top line:
Or you could rewrite with NOT EXISTS instead of NOT IN.

oops, typo there