Self anti-join - failed to obtain optimal exectuion plan on a 9i database

I continued to study the query I described in the previous post on Jan 18. I realized that the first part of the query is essentially a self anti-join.

The column statistics of the table BM in the production is as follows:

 COLUMN_NAME       LOW_VAL        HIGH_VAL   NUM_DISTINCT  NUM_NULLS
 ------------- ------------- --------------  -----------   ----------
 BID               3             598219339    314914980          0
 BSCI              B             S                    2          0
 BSC               1             7                    7          0
 VP_BID            0             598218162     25905093          0

I thus constructed a baseline test case as following:

create table bm
as
select
   rownum    bid,
   trunc(dbms_random.value(1,500))          vp_bid,
   mod(rownum, 7)  + 1                  bsc,
   decode(mod(rownum,2),
          0, 'A',
          1, 'S')     bsci
from all_objects 
where rownum <= 6500;  
  
create index bm_fk5 on bm(vp_bid);     

begin        
dbms_stats.gather_table_stats( user,  'bm',  cascade => true); 
end; 
/  

set autotrace traceonly  
SELECT *   FROM bm  
WHERE bm.bsc = 3    
AND bm.bsci = 'S'    
AND NOT EXISTS (           
          SELECT  1             
            FROM bm bm1            
           WHERE bm.vp_bid = bm1.vp_bid              
             AND bm1.bsci = 'S'              
             AND bm1.bsc NOT IN (3, 4)); 
set autotrace off  

Here are the results of Autotrace

1. When executed the baseline test case in a 9.2.0.8 database:

Execution Plan
-------------------------------------------------------
0      SELECT STATEMENT Optimizer=CHOOSE (Cost=14 Card=1 Bytes=12)
1    0   FILTER
2    1     TABLE ACCESS (FULL) OF 'BM' (Cost=4 Card=1 Bytes=12)
3    1     TABLE ACCESS (BY INDEX ROWID) OF 'BM' (Cost=10 Card=1 Bytes=12)
4    3       INDEX (RANGE SCAN) OF 'BM_FK5' (NON-UNIQUE) (Cost=1 Card=13)


Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
       1508  consistent gets
          0  physical reads
          0  redo size
        278  bytes sent via SQL*Net to client
        234  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed

2. When executed the baseline test case in a 10.2.0.1 database:

---------------------------------------------------------------------------
 Id   Operation           Name  Rows   Bytes  Cost (%CPU) Time  
---------------------------------------------------------------------------
   0  SELECT STATEMENT              1     21     14  (15) 00:00:01
*  1   HASH JOIN ANTI               1     21     14  (15) 00:00:01
*  2    TABLE ACCESS FULL BM      464   5568      7  (15) 00:00:01
*  3    TABLE ACCESS FULL BM     2388  21492      7  (15) 00:00:01
---------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - access("BM"."VP_BID"="BM1"."VP_BID")
   2 - filter("BM"."BSC"=3 AND "BM"."BSCI"='S')
   3 - filter("BM1"."BSCI"='S' AND "BM1"."BSC"<>3 AND "BM1"."BSC"<>4)


Statistics
----------------------------------------------------------
        166  recursive calls
          0  db block gets
         55  consistent gets
          0  physical reads
          0  redo size
        689  bytes sent via SQL*Net to client
        381  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          4  sorts (memory)
          0  sorts (disk)
          8  rows processed

Note: 10g picked up hash join anti acccess path and the consistent gets is only 55 vs 1508 in the case of 9i.

3. Drop the index BM_FK5, and run the baseline test case in the 9.2.0.8 database

   Execution Plan
   ----------------------------------------------------------
      0      SELECT STATEMENT Optimizer=CHOOSE (Cost=9 Card=1 Bytes=21)
      1    0   HASH JOIN (ANTI) (Cost=9 Card=1 Bytes=21)
      2    1     TABLE ACCESS (FULL) OF 'BM' (Cost=4 Card=464 Bytes=5568)
      3    1     TABLE ACCESS (FULL) OF 'BM' (Cost=4 Card=2388 Bytes=21492)


   Statistics
   ----------------------------------------------------------
           153  recursive calls
             0  db block gets
            54  consistent gets
             0  physical reads
             0  redo size
           389  bytes sent via SQL*Net to client
           234  bytes received via SQL*Net from client
             2  SQL*Net roundtrips to/from client
             3  sorts (memory)
             0  sorts (disk)
             8  rows processed

Note: without that index, 9i can choose right executin plan.

I then tested different ways in order to get 9.2.0.8 database to pick up the good execution plan when the index is present.

I tried:

1. NO_INDEX hint
2. collect histogram on the indexed column
3. rewrite the SQL to use NOT IN
4. NOT IN with HASH_AJ hint
5. HASH_AJ hint
6. Not analyzing the table, using dynamic sampling feaure

None of above succeeded. After playing with it the whole afternoon. I decided to move on and document it here for reference.