Hash join anti vs Nested loop join anti

This post shows you details about a specific case where 'hash anti join' is defeated by 'nested loop anti join'.
The initial problem came to light in a very large BW system running on Oracle 11.2.0.4 when several BW loads (making use of older data in the BW system) reported missing dimension ids in the dimension tables.

In some BW systems much of the data is stored using fact tables (E-fact and F-fact tables).
The first 16 (differs) fields in these fact tables (both E and F) typically are number fields.
They are known as dimension key fields and each have a corresponding dimension table or view where the 16 fields become the unique primary key for that dimension.
In the E- and F-fact table they are all part of the unique primary key.

Example of a E-fact table /BIC/EYDMA025A:

Field Name     K Type Length Data Elem.       Short Text
KEY_YDMA025AP  X INT4     10 RSDIMID          Dimension Table Key
KEY_YDMA025AT  X INT4     10 RSDIMID          Dimension Table Key
KEY_YDMA025AU  X INT4     10 RSDIMID          Dimension Table Key
KEY_YDMA025A1  X INT4     10 RSDIMID          Dimension Table Key
KEY_YDMA025A2  X INT4     10 RSDIMID          Dimension Table Key
KEY_YDMA025A3  X INT4     10 RSDIMID          Dimension Table Key
KEY_YDMA025A4  X INT4     10 RSDIMID          Dimension Table Key
KEY_YDMA025A5  X INT4     10 RSDIMID          Dimension Table Key
KEY_YDMA025A6  X INT4     10 RSDIMID          Dimension Table Key
KEY_YDMA025A7  X INT4     10 RSDIMID          Dimension Table Key
KEY_YDMA025A8  X INT4     10 RSDIMID          Dimension Table Key
KEY_YDMA025A9  X INT4     10 RSDIMID          Dimension Table Key
KEY_YDMA025AA  X INT4     10 RSDIMID          Dimension Table Key
KEY_YDMA025AB  X INT4     10 RSDIMID          Dimension Table Key
KEY_YDMA025AC  X INT4     10 RSSID            Master data ID
KEY_YDMA025AD  X INT4     10 RSSID            Master data ID
SID_0FISCPER     INT4     10 RSSID            Master data ID
QUANTITY         QUAN     17 /BI0/OIQUANTITY  Quantity
/BIC/ZCOSA_VAR   CURR     17 /BIC/OIZCOSA_VAR COSA_VAR
/BIC/ZGIQTY      QUAN     17 /BIC/OIZGIQTY    Goods Issued_QTY
/BIC/ZGI_CCS     CURR     17 /BIC/OIZGI_CCS   Goods Issued_CCS
/BIC/ZGL_CCS     CURR     17 /BIC/OIZGL_CCS   Gain & Losses_CCS
/BIC/ZGL_QTY     QUAN     17 /BIC/OIZGL_QTY   Gain & Losses_Qty
/BIC/ZGRM_CCS    CURR     17 /BIC/OIZGRM_CCS  Gross Refinery Margin_CCS
/BIC/ZINTK_CCS   CURR     17 /BIC/OIZINTK_CCS Intake_CCS
/BIC/ZINTK_QTY   QUAN     17 /BIC/OIZINTK_QTY Intake_Qty
/BIC/ZOTHCSABS   CURR     17 /BIC/OIZOTHCSABS Other Movements
/BIC/ZOTHR_CCS   CURR     17 /BIC/OIZOTHR_CCS Other Movements_CCS

Example of the dimension table of dimension 9 (for the same E-fact table) called /BIC/DYDMA025A9:

Field Name      K Type Length Data Elem. Short Text]/b]
DIMID           X INT4     10 RSDIMID    Dimension Table Key
SID_0OI_EXGNUM    INT4     10 RSSID      Master data ID
SID_ZEXCHGIND     INT4     10 RSSID      Master data ID
SID_0OI_EXGTYP    INT4     10 RSSID      Master data ID
SID_ZMGRP         INT4     10 RSSID      Master data ID
SID_0MOVETYPE     INT4     10 RSSID      Master data ID
SID_0OI_MOT       INT4     10 RSSID      Master data ID
SID_0CONTRACT     INT4     10 RSSID      Master data ID
SID_0CONT_ITEM    INT4     10 RSSID      Master data ID
SID_0REFER_DOC    INT4     10 RSSID      Master data ID
SID_0REFER_ITM    INT4     10 RSSID      Master data ID
SID_0REF_DOC_NR   INT4     10 RSSID      Master data ID
SID_ZBOLNUM       INT4     10 RSSID      Master data ID
SID_ZCONTRACT     INT4     10 RSSID      Master data ID
SID_ZSMARTNR      INT4     10 RSSID      Master data ID
SID_ZSTIREFNO     INT4     10 RSSID      Master data ID
SID_ZSTIRFITM     INT4     10 RSSID      Master data ID

In the above example, field KEY_YDMA025A9 of table /BIC/EYDMA025A corresponds to field DIMID of dimension table /BIC/DYDMA025A9.
In this case the dimension again contains numbers which in this case are pointers to the actual data stored in again different tables.
The first 16 fields of this E-fact table are followed by a couple of fields that contain data that is not really suitable for storing in dimensions. Like amounts and quantities.
YDMA025A in the name of the objects is the name of the infocube.

Furthermore the E-fact table has one unique primary index which consists of all fields starting with KEY in the order of the table definition. So in this case 1st field in the index is KEY_YDMA025AP and last field is KEY_YDMA025AD.
Then there are bitmap indexes all with one field for all fields starting with KEY except for KEY_YDMA025AP and KEY_YDMA025AU.
Field KEY_YDMA025AU is the only dimension that does not have an index in any fact table which i believe to be a design problem.
So in total for this E-fact table 15 indexes. 14 bitmap and one normal index.
The F-fact table has no normal indexes. All are bitmap and they exist for all dimension fields (KEY*) except KEY_YDMA025AU. In addition bitmap index can exist for other fields in the F-fact table.

Back to the problem and using the example above.
What happened was that dimension ids present in the E-fact table /BIC/EYDMA025A were missing in dimension table /BIC/DYDMA025A9 which qualifies as a logical inconsistency and can, and in this case did, prevent successful execution of month end critical reports.
At first this problem seemed limited to a couple of tables but it was considered serious enough to start checking if this problem was present in other tables too. Tables for which the problem simply had not occurred yet.
After some initial runs it turned out several important infocubes were also missing records in the dimension tables.
So a decision was made to start checking all dimensions off all infocubes for both E- and F-fact tables.
An immense task since there are several thousands of infocubes all with 10-16 dimensions and both and E- and f-fact table had to be checked.
Not only would the check have to be executed several ten thousands times but the amount of data that needs to be read ranges from 10-20Tb depending on how the CBO executes the query.

The supplier of the BW system recommended to perform a consistency check once to track down all problems and to perform checks every month which would not prevent the problem but at least allowed early notification and follow-up action.
A very comprehensive tool is offered in this BW system to check for many inconsistencies and part of that is the consistency check between fact tables and their dimensions.
A dynamic SELECT located in one of the main pieces of code in this check is responsible for the actual check.
The SELECT uses a 'WHERE NOT EXISTS' which the CBO translates into a 'HASH JOIN RIGHT ANTI'.
Output of such a SELECT are dimension ids that are present in the fact table but missing in the dimensions table. If there are any.
When such a situation occurs the tool reports a red light and actions needs to be undertaken to correct the problem.

This is an example of how the code for the check in SQL looks like:

SELECT 
T_00."KEY_YDMA025A9",COUNT(T_00."KEY_YDMA025A9") "COUNT"
FROM "/BIC/EYDMA025A" T_00 WHERE NOT EXISTS (
SELECT T_100.DIMID FROM "/BIC/DYDMA025A9" T_100 WHERE T_100.DIMID=T_00."KEY_YDMA025A9")
GROUP BY T_00."KEY_YDMA025A9"

This is how the execution plan looks:

------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                       | Name               | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     | Pstart| Pstop |
------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                |                    |  1415K|    14M|       |   184K  (1)| 00:49:18 |       |       |
|   1 |  HASH GROUP BY                  |                    |  1415K|    14M|    27M|   184K  (1)| 00:49:18 |       |       |
|*  2 |   HASH JOIN RIGHT ANTI          |                    |  1415K|    14M|    84M|   178K  (1)| 00:47:43 |       |       |
|   3 |    INDEX FAST FULL SCAN         | /BIC/DYDMA025A9~0  |  4939K|    28M|       |  2908   (1)| 00:00:47 |       |       |
|   4 |    PARTITION RANGE ALL          |                    |   141M|   674M|       | 81396   (1)| 00:21:43 |     1 |   121 |
|   5 |     BITMAP CONVERSION TO ROWIDS |                    |   141M|   674M|       | 81396   (1)| 00:21:43 |       |       |
|   6 |      BITMAP INDEX FAST FULL SCAN| /BIC/EYDMA025A~120 |       |       |       |            |          |     1 |   121 |
------------------------------------------------------------------------------------------------------------------------------

The consistency check provided by the supplier can execute this for all dimensions (or a subset) for both E- en F-fact tables with the exception of 1 dimension which is only checked for the F-fact table.
This means that 31 checks are executed for infocube YDMA025A in the examples used.
The E- and F-fact all have bitmap indexes for each of the dimensions.
YDMA025A has 8.6 million rows in the F-fact table and >140 million in the E-fact table.
The number of rows in the dimension tables for this infocube ranges from 10 to over 4.9 million. Dimension 9 used in the example has 4.9 million rows.
The total time it took to check this infocube was 22m2s.
Purely judging on the numbers and the amount of work that has to be performed by Oracle and the fact that one index (U dimension is missing) you could argue that a response time of 22m2s to check all 16 dimensions against both fact tables is fast.
In fact no one would ever even bothered to complain about the performance if this issue was limited to 1 or several infocubes.

But the reality was that there were between 1500 and 2000 infocubes in play all with 16 dimensions and with a combined total size of 10-20Tb.
The total estimated runtime to complete the checks for all infocubes was over to a month. Not really helped by the fact this can only be executed manually from within the application.
Absolutely not workable not all and with the supplier offering no other solution i attempted to find out if the already fast 'hash join right anti' could be boosted.
First thing to do is to create the missing U dimension index for all infocubes for both E- and F-fact tables.
Next, before realizing it was the 'hash' itself that caused the problem, i tried to increase the speed of reading the fact and dimension data.
This turned out to be a failure because no significant improvement in speed was noticeable.
But because i could not achieve a good improvement by speeding up I/O i thought the only other option was to improve the 'hash' activity.
I should have realized this way earlier because Oracle simply shows where the bulk of the time is spent for these queries namely in the CPU.

Still thinking it is maybe not so bad to check billions of entries against billions of entries in 7h34m but also thinking hash joining this many entries against so many other entries maybe not the best way to do it.
Would a 'nested loop anti join' for instance in combination with parallelism not perform faster?
And so i first changed the SQL to this:

SELECT 
T_00."KEY_YDMA025A9",COUNT(T_00."KEY_YDMA025A9") "COUNT"
FROM "/BIC/EYDMA025A" T_00 WHERE NOT EXISTS (
SELECT /*+ NL_AJ */ T_100.DIMID FROM "/BIC/DYDMA025A9" T_100 WHERE T_100.DIMID=T_00."KEY_YDMA025A9")
GROUP BY T_00."KEY_YDMA025A9".

This is how the execution plan looks then:

------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                       | Name               | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     | Pstart| Pstop |
------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                |                    |       |       |       |   141M(100)|          |       |       |
|   1 |  HASH GROUP BY                  |                    |  1415K|    14M|    27M|   141M  (1)|629:38:24 |       |       |
|   2 |   NESTED LOOPS ANTI             |                    |  1415K|    14M|       |   141M  (1)|629:36:49 |       |       |
|   3 |    PARTITION RANGE ALL          |                    |   141M|   674M|       | 81396   (1)| 00:21:43 |     1 |   121 |
|   4 |     BITMAP CONVERSION TO ROWIDS |                    |   141M|   674M|       | 81396   (1)| 00:21:43 |       |       |
|   5 |      BITMAP INDEX FAST FULL SCAN| /BIC/EYDMA025A~120 |       |       |       |            |          |     1 |   121 |
|*  6 |    INDEX UNIQUE SCAN            | /BIC/DYDMA025A9~0  |  4938K|    28M|       |     1   (0)| 00:00:01 |       |       |
------------------------------------------------------------------------------------------------------------------------------

But i also changed the SQL to this:

SELECT /*+ INDEX_FFS(T_00 "/BIC/EYDMA025A~120") PARALLEL_INDEX(T_00 "/BIC/EYDMA025A~120",16) */
T_00."KEY_YDMA025A9",COUNT(T_00."KEY_YDMA025A9") "COUNT"
FROM "/BIC/EYDMA025A" T_00 WHERE NOT EXISTS (
SELECT /*+ NL_AJ */ T_100.DIMID FROM "/BIC/DYDMA025A9" T_100 WHERE T_100.DIMID=T_00."KEY_YDMA025A9")
GROUP BY T_00."KEY_YDMA025A9".

With this execution plan:

----------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                           | Name               | Rows  | Bytes |TempSpc| Cost (%CPU)| Time     | Pstart| Pstop |
----------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                    |                    |       |       |       |   141M(100)|          |       |       |
|   1 |  PX COORDINATOR                     |                    |       |       |       |            |          |       |       |
|   2 |   PX SEND QC (RANDOM)               | :TQ10001           |  1415K|    14M|       |   141M  (1)|629:38:24 |       |       |
|   3 |    HASH GROUP BY                    |                    |  1415K|    14M|    27M|   141M  (1)|629:38:24 |       |       |
|   4 |     PX RECEIVE                      |                    |  1415K|    14M|       |   141M  (1)|629:36:49 |       |       |
|   5 |      PX SEND HASH                   | :TQ10000           |  1415K|    14M|       |   141M  (1)|629:36:49 |       |       |
|   6 |       NESTED LOOPS ANTI             |                    |  1415K|    14M|       |   141M  (1)|629:36:49 |       |       |
|   7 |        PX BLOCK ITERATOR            |                    |   141M|   674M|       | 81396   (1)| 00:21:43 |     1 |   121 |
|   8 |         BITMAP CONVERSION TO ROWIDS |                    |   141M|   674M|       | 81396   (1)| 00:21:43 |       |       |
|*  9 |          BITMAP INDEX FAST FULL SCAN| /BIC/EYDMA025A~120 |       |       |       |            |          |     1 |   121 |
|* 10 |        INDEX UNIQUE SCAN            | /BIC/DYDMA025A9~0  |  4938K|    28M|       |     1   (0)| 00:00:01 |       |       |
----------------------------------------------------------------------------------------------------------------------------------

The execution plan for both look ugly. Real ugly. But the actual execution showed a completely different picture.

Results for checking dimension 9 of infocube YDMA025A are:
- 10 executions of the standard method so without U dimension indexes, INDEX_FFS, PARALLEL_INDEX and NL_AJ took 6m15s
- 10 executions of the enhanced method with U dimension indexes and NL_AJ took 3m18s
- 10 executions of the enhanced method with U dimension indexes, INDEX_FFS, PARALLEL_INDEX and NL_AJ took 39s

Results for complete YDMA025A infocube checking both E- and F-fact tables against 16 dimension are:
- Standard method so without U dimension indexes, INDEX_FFS, PARALLEL_INDEX and NL_AJ took 22m2s
- Enhanced method with U dimension indexes, INDEX_FFS, PARALLEL_INDEX and NL_AJ took 1m28s
- Improvement for dimension U checks is dropping from 11m43s to 4s
- Improvement for the 15 other dimensions is dropping from 10m19s to 1m24s

It appeared the 'nested loop anti join' was already brings a considerable improvement but the addition of the parallelism really changes things for the better.

Next step was to prove this on a larger scale.
The test set consisted of 10 big infocubes all with 16 dimensions.
- A total of 4.2 billion fact table entries checked against a billion of dimension table entries lasted 7h34m using the standard method.
- The method i used so with INDEX_FFS,PARALLEL_INDEX and NL_AJ and indexes for the U dimension only took 23m.
- For 20 U dimension checks (10 infocubes with 2 fact tables) the improvement is a drop from 2h23m to 1m13s.
- The improvement for the 290 other dimensions is a drop from 5h11m to 21m47s.

As a result of the tests i considered the problem solved.
The only thing that was needed now was making a few simple changes in the dynamic code of the supplier so that the NL_AJ, INDEX_FSS and PARALLEL_INDEX hints would be included and adjusted per dimension per infocube.
But the supplier stated there is no intention to further improve the check tool they have provided so far. Oops.

So i decided to go even further and write a program myself that includes the Oracle hints but also allows batch scheduling, multiple infocubes being checked at the same and extensive logging.
Took me about a week to write the code. It was not that hard and works pretty good and very fast.
I have checked the results of the standard method against this program and they are identical so both reporting the same errors.
This program can achieve what the standard method can achieve only a hundred times faster. Because apart from the boost of nested loops anti join you now the the parallel execution of check on multiple cubes.
Plus no risk of duplication, no accidental skipping of infocubes and no hard labour for the person(s) responsible for the checks.

But to my surprise the company with the problems decided to totally abort the path of performing checks and so there was no need for the hints or the program or the U dimension indexes. Again oops.
I have no clue why the checks are no longer needed.

So hopefully this information can be used by someone facing the same problem but not liking standard method or performance.

Peter van der Woude.

Comments

A very scholarly exposition of and interesting problem and solution, Peter. I have very little experience of working with SAP, but your article explains some of the problems that I have seen. Simply, SAP does not use foreign key constraints. Googling around, it seems that their proprietary database does not support FK constraints, and they have propagated that limitation into deployments on Oracle databases. To any relational engineer, this is awful! To an Oracle DBA, it is even worse because FK constraints do not only help with data integrity (your problem) but also assist the optimizer with devleoping efficient plans.

My immediate reaction was "declare FK contraints on those dimension columns, and the problem will never re-occur. The DB might run better, too". But perhaps you aren't allowed to do that.

Thanks for your reply John.

Lack of foreign key relationships is a great example of how sub-optimal Oracle functionality is used in SAP environments.
Sometimes i just wonder whether the whole design of a SAP BW system (or ECC system for that matter) is a deliberate attempt to make Oracle look bad.
Indeed i cannot make changes like that and even the most trivial changes grow to large complex ones induced by the red tape that has become a fact of life for me.