Find minimum adjustment cost of an array

Given an array of positive integers, replace each element in the array such that the difference between adjacent elements in the array is less than or equal to a given target. We need to minimize the adjustment cost, that is the sum of differences between new and old values. We basically need to minimize ∑|A[i] – A_new[i]| where 0 <= i <= n-1, n is size of A[] and A_new[] is the array with adjacent difference less that or equal to target.
Assume all elements of the array is less than constant M = 100.
Examples:

Input: arr = [1, 3, 0, 3], target = 1
Output: Minimum adjustment cost is 3
Explanation: One of the possible solutions 
is [2, 3, 2, 3]

Input: arr = [2, 3, 2, 3], target = 1
Output: Minimum adjustment cost is 0
Explanation:  All adjacent elements in the input 
array are already less than equal to given target

Input: arr = [55, 77, 52, 61, 39, 6, 
             25, 60, 49, 47], target = 10
Output: Minimum adjustment cost is 75
Explanation: One of the possible solutions is 
[55, 62, 52, 49, 39, 29, 30, 40, 49, 47]

We strongly recommend you to minimize your browser and try this yourself first.

In order to minimize the adjustment cost ∑|A[i] – A_new[i]| for all index i in the array, |A[i] – A_new[i]| should be as close to zero as possible. Also, |A[i] – A_new[i+1] ]| <= Target.
This problem can be solved by dynamic programming.
Let dp[i][j] defines minimal adjustment cost on changing A[i] to j, then the DP relation is defined by –

dp[i][j] = min{dp[i - 1][k]} + |j - A[i]|
           for all k's such that |k - j| <= target

Here, 0 <= i < n and 0 <= j <= M where n is number of elements in the array and M = 100. We have to consider all k such that max(j – target, 0) <= k <= min(M, j + target)
Finally, the minimum adjustment cost of the array will be min{dp[n – 1][j]} for all 0 <= j <= M.
Below is C++ implementation of above idea –

// C++ program to find minimum adjustment cost of an array #include <bits/stdc++.h> using namespace std;   #define M 100   // Function to find minimum adjustment cost of an array int minAdjustmentCost(int A[], int n, int target) {     // dp[i][j] stores minimal adjustment cost on changing     // A[i] to j     int dp[n][M + 1];       // handle first element of array seperately     for (int j = 0; j <= M; j++)         dp[0][j] = abs(j - A[0]);       // do for rest elements of the array     for (int i = 1; i < n; i++)     {         // replace A[i] to j and calculate minimal adjustment         // cost dp[i][j]         for (int j = 0; j <= M; j++)         {           // initialize minimal adjustment cost to INT_MAX           dp[i][j] = INT_MAX;             // consider all k such that k >= max(j - target, 0) and           // k <= min(M, j + target) and take minimum           for (int k = max(j-target,0); k <= min(M,j+target); k++)              dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(A[i] - j));         }     }          // return minimum value from last row of dp table     int res = INT_MAX;     for (int j = 0; j <= M; j++)         res = min(res, dp[n - 1][j]);       return res; }   // Driver Program to test above functions int main() {     int arr[] = {55, 77, 52, 61, 39, 6, 25, 60, 49, 47};     int n = sizeof(arr) / sizeof(arr[0]);     int target = 10;       cout << "Minimum adjustment cost is "          << minAdjustmentCost(arr, n, target) << endl;       return 0; }

Output:

Minimum adjustment cost is 75

Replace every element with the least greater element on its right

Given an array of integers, replace every element with the least greater element on its right side in the array. If there are no greater element on right side, replace it with -1.
Examples:

Input: [8, 58, 71, 18, 31, 32, 63, 92, 
         43, 3, 91, 93, 25, 80, 28]
Output: [18, 63, 80, 25, 32, 43, 80, 93, 
         80, 25, 93, -1, 28, -1, -1]

We strongly recommend you to minimize your browser and try this yourself first.

A naive method is to run two loops. The outer loop will one by one pick array elements from left to right. The inner loop will find the smallest element greater than the picked element on its right side. Finally the outer loop will replace the picked element with the element found by inner loop. The time complexity of this method will be O(n²).
A tricky solution would be to use Binary Search Trees. We start scanning the array from right to left and insert each element into the BST. For each inserted element, we replace it in the array by its inorder successor in BST. If the element inserted is the maximum so far (i.e. its inorder successor doesn’t exists), we replace it by -1.
Below is C++ implementation of above idea –

// C++ program to replace every element with the // least greater element on its right #include <iostream> using namespace std;   // A binary Tree node struct Node {     int data;     Node *left, *right; };   // A utility function to create a new BST node Node* newNode(int item) {     Node* temp = new Node;     temp->data = item;     temp->left = temp->right = NULL;       return temp; }   /* A utility function to insert a new node with    given data in BST and find its successor */ void insert(Node*& node, int data, Node*& succ) {     /* If the tree is empty, return a new node */     if (node == NULL)         node = newNode(data);       // If key is smaller than root's key, go to left     // subtree and set successor as current node     if (data < node->data)     {         succ = node;         insert(node->left, data, succ);     }       // go to right subtree     else if (data > node->data)         insert(node->right, data, succ); }   // Function to replace every element with the // least greater element on its right void replace(int arr[], int n) {     Node* root = NULL;       // start from right to left     for (int i = n - 1; i >= 0; i--)     {         Node* succ = NULL;           // insert current element into BST and         // find its inorder successor         insert(root, arr[i], succ);           // replace element by its inorder         // successor in BST         if (succ)             arr[i] = succ->data;         else    // No inorder successor             arr[i] = -1;     } }   // Driver Program to test above functions int main() {     int arr[] = { 8, 58, 71, 18, 31, 32, 63, 92,                   43, 3, 91, 93, 25, 80, 28 };     int n = sizeof(arr)/ sizeof(arr[0]);       replace(arr, n);       for (int i = 0; i < n; i++)         cout << arr[i] << " ";       return 0; }

Output:

18 63 80 25 32 43 80 93 80 25 93 -1 28 -1 -1

Worst case time complexity of above solution is also O(n²) as it uses BST. The worst case will happen when array is sorted in ascending or descending order. The complexity can easily be reduced to O(nlogn) by using balanced trees like red-black trees.

Palindromic Primes

A palindromic prime (sometimes called a palprime) is a prime number that is also a palindromic number.

Given a number n, print all palindromic primes smaller than or equal to n. For example, If n is 10, the output should be “2, 3, 5, 7′. And if n is 20, the output should be “2, 3, 5, 7, 11′.
Idea is to generate all prime numbers smaller than or equal to given number n and checking every prime number whether it is palindromic or not.
Methods used

• To find if a given number is prime or not.
• To check whether the given number is palindromic number or not.

Below is the C++ implementation of above algorithm:

// C++ Program to print all palindromic primes // smaller than or equal to n. #include<bits/stdc++.h> using namespace std;   // A function that reurns true only if num // contains one digit int oneDigit(int num) {     // comparison operation is faster than     // division operation. So using following     // instead of "return num / 10 == 0;"     return (num >= 0 && num < 10); }   // A recursive function to find out whether // num is palindrome or not. Initially, dupNum // contains address of a copy of num. bool isPalUtil(int num, int* dupNum) {     // Base case (needed for recursion termination):     // This statement/ mainly compares the first     // digit with the last digit     if (oneDigit(num))         return (num == (*dupNum) % 10);       // This is the key line in this method. Note     // that all recursive/ calls have a separate     // copy of num, but they all share same copy     // of *dupNum. We divide num while moving up     // the recursion tree     if (!isPalUtil(num/10, dupNum))         return false;       // The following statements are executed when     // we move up the recursion call tree     *dupNum /= 10;       // At this point, if num%10 contains i'th     // digit from beiginning, then (*dupNum)%10     // contains i'th digit from end     return (num % 10 == (*dupNum) % 10); }   // The main function that uses recursive function // isPalUtil() to find out whether num is palindrome // or not int isPal(int num) {     // If num is negative, make it positive     if (num < 0)        num = -num;       // Create a separate copy of num, so that     // modifications made to address dupNum don't     // change the input number.     int *dupNum = new int(num); // *dupNum = num       return isPalUtil(num, dupNum); }   // Function to generate all primes and checking // whether number is palindromic or not void printPalPrimesLessThanN(int n) {     // Create a boolean array "prime[0..n]" and     // initialize all entries it as true. A value     // in prime[i] will finally be false if i is     // Not a prime, else true.     bool prime[n+1];     memset(prime, true, sizeof(prime));       for (int p=2; p*p<=n; p++)     {         // If prime[p] is not changed, then it is         // a prime         if (prime[p] == true)         {             // Update all multiples of p             for (int i=p*2; i<=n; i += p)                 prime[i] = false;         }     }       // Print all palindromic prime numbers     for (int p=2; p<=n; p++)          // checking whether the given number is        // prime palindromic or not        if (prime[p] && isPal(p))           cout << p << " "; }   // Driver Program int main() {     int n = 200;     printf("Palindromic primes smaller than or "            "equal to %d are :\n", n);     printPalPrimesLessThanN(n); }

Output:

Palindromic primes smaller than or equal to 100 are :
2 3 5 7 11 

To Generate a One Time Password or Unique Identification URL

A one-time password (OTP) is a password that is valid for only one login session or transaction, on a computer system or other digital device.

Applications

• OTPs are widely used in websites like- Facebook, Google Sign-in, Wifi – accessing, Railways Portal Login etc.

How it gets generated ?
Well it is a great possibility that they uses the same algorithm as an OTP is generated. If by chance (very rare) the unique string generated is already been generated before and has been associated with a different code then another random string is used.
As per now it seems that only six character strings are generated randomly for a unique identification of all codes. A time will come when all the possible six character strings may get exhausted. So yes, even the web-related stuffs also heavily relies on randomness.
Probability of collision of two OTPs

• The length of OTP is 6 and the set size of all possible characters in the OTP is 62. So the total number of possible sets of the pair of OTPs are 62¹².
• Some of them are – [{aaaaaa, aaaaaa}, {aaaaaa, aaaaab},…..{456789, 456788}, {456789, 456789}]
• But the possible sets of equal pair of OTPs are:62⁶. Some of them are – [{aaaaaa, aaaaaa}, {aaaaab, aaaaab},…..{456788, 456788}, {456789, 456789}]
• Hence the probability of collision of two OTPs is:
  62⁶ / 62¹² = 1 / 62⁶ = 1 / 56800235584 = 1.7605561^-11

So the probability of two OTPs colliding are as less probable as the existence of your life on earth (Ratio of the number of years you will live to the number of years from the start of the universe and everything in existence).So yes,OTPs are way more secure than static passwords !


Implementation

// A C/C++ Program to generate OTP (One Time Password) #include<bits/stdc++.h> using namespace std;   // A Function to generate a unique OTP everytime string generateOTP(int len) {     // All possible characters of my OTP     string str = "abcdefghijklmnopqrstuvwxyzABCD"                "EFGHIJKLMNOPQRSTUVWXYZ0123456789";     int n = str.length();       // String to hold my OTP     string OTP;       for (int i=1; i<=len; i++)         OTP.push_back(str[rand() % n]);       return(OTP); }   // Driver Program to test above functions int main() {     // For different values each time we run the code     srand(time(NULL));       // Delare the length of OTP     int len = 6;     printf("Your OTP is - %s", generateOTP(len).c_str());       return(0); }

Output (May be different for every run):

Your OTP is - 8qOtzy

Time Complexity: O(N), where N = number of characters in our OTP
Auxiliary Space: Apart from the string having all possible characters we require O(N) space to hold the OTP, where N = number of characters in our OTP.


Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Using EXPLAIN PLAN in ORACLE

table, EMP_RANGE, partitioned by range on HIREDATE to illustrate how pruning is displayed. Assume that the tables EMP and DEPT from a standard Oracle schema exist.

   CREATE TABLE EMP_RANGE 
    PARTITION BY RANGE(HIREDATE) 
    ( 
    PARTITION EMP_P1 VALUES LESS THAN (TO_DATE('1-JAN-1981','DD-MON-YYYY')),
    PARTITION EMP_P2 VALUES LESS THAN (TO_DATE('1-JAN-1983','DD-MON-YYYY')),
    PARTITION EMP_P3 VALUES LESS THAN (TO_DATE('1-JAN-1985','DD-MON-YYYY')),
    PARTITION EMP_P4 VALUES LESS THAN (TO_DATE('1-JAN-1987','DD-MON-YYYY')),
    PARTITION EMP_P5 VALUES LESS THAN (TO_DATE('1-JAN-1989','DD-MON-YYYY')) 
    ) 
    AS SELECT * FROM EMP; 

Example 1:

   EXPLAIN PLAN FOR SELECT * FROM EMP_RANGE; 

Then enter the following to display the EXPLAIN PLAN output:

        @?/RDBMS/ADMIN/UTLXPLS 

Oracle displays something similar to:

Plan Table 
-------------------------------------------------------------------------------
| Operation               |  Name    |  Rows | Bytes|  Cost  | Pstart |  Pstop|
-------------------------------------------------------------------------------
| SELECT STATEMENT        |          |   105 |    8K|      1 |        |       |
|  PARTITION RANGE ALL    |          |       |      |        |     1  |     5 |
|   TABLE ACCESS FULL     |EMP_RANGE |   105 |    8K|      1 |     1  |     5 |
-------------------------------------------------------------------------------
6 rows selected. 

A partition row source is created on top of the table access row source. It iterates over the set of partitions to be accessed.

In example 1, the partition iterator covers all partitions (option ALL) because a predicate was not used for pruning. The PARTITION_START and PARTITION STOP columns of the plan table show access to all partitions from 1 to 5.

Example 2:

   EXPLAIN PLAN FOR SELECT * FROM EMP_RANGE 
   WHERE HIREDATE >= TO_DATE('1-JAN-1985','DD-MON-YYYY'); 

Plan Table 
--------------------------------------------------------------------------------
| Operation                 | Name    |  Rows  | Bytes|  Cost  | Pstart| Pstop |
--------------------------------------------------------------------------------
| SELECT STATEMENT          |          |     3 |   54 |      1 |       |       |
|  PARTITION RANGE ITERATOR |          |       |      |        |     4 |     5 |
|   TABLE ACCESS FULL       |EMP_RANGE |     3 |   54 |      1 |     4 |     5 |
--------------------------------------------------------------------------------
6 rows selected. 

In example 2, the partition row source iterates from partition 4 to 5 because we prune the other partitions using a predicate on HIREDATE.

Example 3:

   EXPLAIN PLAN FOR SELECT * FROM EMP_RANGE 
   WHERE HIREDATE < TO_DATE('1-JAN-1981','DD-MON-YYYY'); 

Plan Table 
--------------------------------------------------------------------------------
| Operation                 |  Name    |  Rows | Bytes|  Cost  | Pstart| Pstop |
--------------------------------------------------------------------------------
| SELECT STATEMENT          |          |     2 |   36 |      1 |       |       |
|  TABLE ACCESS FULL        |EMP_RANGE |     2 |   36 |      1 |     1 |     1 |
--------------------------------------------------------------------------------
5 rows selected. 

In example 3, only partition 1 is accessed and known at compile time, thus there is no need for a partition row source.

Plans for Hash Partitioning

Oracle displays the same information for hash partitioned objects except that the partition row source name is "PARTITION HASH" instead of "PARTITION RANGE". Also, with hash partitioning, pruning is only possible using equality or in-list predicates.

Pruning Information with Composite Partitioned Objects

To illustrate how Oracle displays pruning information for composite partitioned objects, consider the table EMP_COMP that is range partitioned on HIREDATE and subpartitioned by hash on DEPTNO.

 CREATE TABLE EMP_COMP PARTITION BY RANGE(HIREDATE) SUBPARTITION BY HASH(DEPTNO) 
  SUBPARTITIONS 3 
  ( 
  PARTITION EMP_P1 VALUES LESS THAN (TO_DATE('1-JAN-1981','DD-MON-YYYY')),
  PARTITION EMP_P2 VALUES LESS THAN (TO_DATE('1-JAN-1983','DD-MON-YYYY')),
  PARTITION EMP_P3 VALUES LESS THAN (TO_DATE('1-JAN-1985','DD-MON-YYYY')),
  PARTITION EMP_P4 VALUES LESS THAN (TO_DATE('1-JAN-1987','DD-MON-YYYY')),
  PARTITION EMP_P5 VALUES LESS THAN (TO_DATE('1-JAN-1989','DD-MON-YYYY')) 
   ) 
  AS SELECT * FROM EMP; 

Example 1:

   EXPLAIN PLAN FOR SELECT * FROM EMP_COMP; 

Plan Table 
--------------------------------------------------------------------------------
| Operation                 |  Name   |  Rows | Bytes|  Cost  | Pstart | Pstop |
--------------------------------------------------------------------------------
| SELECT STATEMENT          |         |   105 |    8K|      1 |        |       |
|  PARTITION RANGE ALL      |         |       |      |        |     1  |     5 |
|   PARTITION HASH ALL      |         |       |      |        |     1  |     3 |
|    TABLE ACCESS FULL      |EMP_COMP |   105 |    8K|      1 |     1  |     15|
--------------------------------------------------------------------------------
7 rows selected. 

Example 1 shows the explain plan when Oracle accesses all subpartitions of all partitions of a composite object. Two partition row sources are used for that purpose: a range partition row source to iterate over the partitions and a hash partition row source to iterate over the subpartitions of each accessed partition.

In this example, since no pruning is performed, the range partition row source iterates from partition 1 to 5. Within each partition, the hash partition row source iterates over subpartitions 1 to 3 of the current partition. As a result, the table access row source accesses subpartitions 1 to 15. In other words, it accesses all subpartitions of the composite object.

Example 2:

   EXPLAIN PLAN FOR SELECT * FROM EMP_COMP WHERE HIREDATE = 
   TO_DATE('15-FEB-1987', 'DD-MON-YYYY'); 

Plan Table 
--------------------------------------------------------------------------------
| Operation                 |  Name    |  Rows | Bytes|  Cost  | Pstart| Pstop |
--------------------------------------------------------------------------------
| SELECT STATEMENT          |          |     1 |   96 |      1 |       |       |
|  PARTITION HASH ALL       |          |       |      |        |     1 |     3 |
|   TABLE ACCESS FULL       |EMP_COMP  |     1 |   96 |      1 |    13 |    15 |
--------------------------------------------------------------------------------
6 rows selected. 
 

In example 2, only the last partition, partition 5, is accessed. This partition is known at compile time so we do not need to show it in the plan. The hash partition row source shows accessing of all subpartitions within that partition, that is, subpartitions 1 to 3, which translates into subpartitions 13 to 15 of the EMP_COMP table.

Example 3:

   EXPLAIN PLAN FOR SELECT * FROM EMP_COMP WHERE DEPTNO = 20; 

Plan Table 
--------------------------------------------------------------------------------
| Operation                 |  Name    |  Rows | Bytes|  Cost  | Pstart| Pstop |
--------------------------------------------------------------------------------
| SELECT STATEMENT          |          |     2 |  200 |      1 |       |       |
|  PARTITION RANGE ALL      |          |       |      |        |     1 |     5 |
|   TABLE ACCESS FULL       |EMP_COMP  |     2 |  200 |      1 |       |       |
--------------------------------------------------------------------------------
6 rows selected. 

In this example, the predicate "DEPTNO = 20" enables pruning on the hash dimension within each partition, so Oracle only needs to access a single subpartition. The number of that subpartition is known at compile time so the hash partition row source is not needed.

Example 4:

   VARIABLE DNO NUMBER; 
   EXPLAIN PLAN FOR SELECT * FROM EMP_COMP WHERE DEPTNO = :DNO; 

Plan Table 
--------------------------------------------------------------------------------
| Operation                 |  Name    |  Rows | Bytes|  Cost  | Pstart| Pstop |
--------------------------------------------------------------------------------
| SELECT STATEMENT          |          |     2 |  200 |      1 |       |       |
|  PARTITION RANGE ALL      |          |       |      |        |     1 |     5 |
|   PARTITION HASH SINGLE   |          |       |      |        |   KEY |   KEY |
|    TABLE ACCESS FULL      |EMP_COMP  |     2 |  200 |      1 |       |       |
--------------------------------------------------------------------------------
 7 rows selected. 

Example 4 is the same as example 3 except that "DEPTNO = 20" has been replaced by "DEPTNO = :DNO". In this case, the subpartition number is unknown at compile time and a hash partition row source is allocated. The option is SINGLE for that row source because Oracle accesses only one subpartition within each partition. The PARTITION START and PARTITION STOP is set to "KEY". This means Oracle will determine the number of the subpartition at run time.

Partial Partition-wise Joins

Example 1:

In the following example, EMP_RANGE is joined on the partitioning column and is parallelized. This enables use of partial partition-wise join because the DEPT table is not partitioned. Oracle dynamically partitions the DEPT table before the join.

   ALTER TABLE EMP PARALLEL 2; 
      STATEMENT PROCESSED.
   ALTER TABLE DEPT PARALLEL 2; 
      STATEMENT PROCESSED. 

To show the plan for the query, enter:

   EXPLAIN PLAN FOR SELECT /*+ ORDERED USE_HASH(D) */ ENAME, DNAME 
     FROM EMP_RANGE E, DEPT D 
     WHERE E.DEPTNO = D.DEPTNO 
     AND E.HIREDATE > TO_DATE('29-JUN-1986','DD-MON-YYYY'); 

    
Plan Table 
------------------------------------------------------------------------------------------------------------ 
| Operation                  |  Name    |  Rows | Bytes|  Cost  |  TQ  |IN-OUT| PQ Distrib | Pstart| Pstop | 
------------------------------------------------------------------------------------------------------------ 
| SELECT STATEMENT           |          |     1 |   51 |      3 |      |      |            |       |       | 
|  HASH JOIN                 |          |     1 |   51 |      3 | 2,02 | P->S | QC (RANDOM)|       |       | 
|   PARTITION RANGE ITERATOR |          |       |      |        | 2,02 | PCWP |            |     4 |     5 | 
|    TABLE ACCESS FULL       |EMP_RANGE |     3 |   87 |      1 | 2,00 | PCWP |            |     4 |     5 | 
|    TABLE ACCESS FULL       |DEPT      |    21 |  462 |      1 | 2,01 | P->P |PART (KEY)  |       |       | 
------------------------------------------------------------------------------------------------------------ 
8 rows selected.

The plan shows that the optimizer select partition-wise join because the DIST column contains the text "PART (KEY)", or, partition key.

Example 2:

In example 2, EMP_COMP is joined on its hash partitioning column, DEPTNO, and is parallelized. This enables use of partial partition-wise join because the DEPT table is not partitioned. Again, Oracle dynamically partitions the DEPT table.

   ALTER TABLE EMP_COMP PARALLEL 2; 
     STATEMENT PROCESSED. 
   EXPLAIN PLAN FOR SELECT /*+ ORDERED USE_HASH(D) */ ENAME, DNAME 
     FROM EMP_COMP E, DEPT D 
     WHERE E.DEPTNO = D.DEPTNO 
     AND E.HIREDATE > TO_DATE('13-MAR-1985','DD-MON-YYYY'); 

    
Plan Table
------------------------------------------------------------------------------------------------------------ 
| Operation                  |  Name    |  Rows | Bytes|  Cost  |  TQ  |IN-OUT| PQ Distrib | Pstart| Pstop | 
------------------------------------------------------------------------------------------------------------ 
| SELECT STATEMENT           |          |    1  |  51  |      3 |      |      |            |       |       |
|  HASH JOIN                 |          |     1 |   51 |      3 | 0,01 | P->S | QC (RANDOM)|       |       | 
|   PARTITION RANGE ITERATOR |          |       |      |        | 0,01 | PCWP |            |     4 |     5 | 
|    PARTITION HASH ALL      |          |       |      |        | 0,01 | PCWP |            |     1 |     3 | 
|     TABLE ACCESS FULL      |EMP_COMP  |     3 |   87 |      1 | 0,01 | PCWP |            |    10 |    15 | 
|   TABLE ACCESS FULL        |DEPT      |    21 |  462 |      1 | 0,00 | P->P | PART (KEY) |       |       | 
------------------------------------------------------------------------------------------------------------ 
9 rows selected.

Full Partition-wise Joins

In the following example, EMP_COMP and DEPT_HASH are joined on their hash partitioning columns. This enables use of full partition-wise join. The "PARTITION HASH" row source appears on top of the join row source in the plan table output.

To create the table DEPT_HASH, enter:

   CREATE TABLE DEPT_HASH 
     PARTITION BY HASH(deptno) 
     PARTITIONS 3 
     PARALLEL 
     AS SELECT * FROM DEPT; 

To show the plan for the query, enter:

   EXPLAIN PLAN FOR SELECT /*+ ORDERED USE_HASH(D) */ ENAME, DNAME 
     FROM EMP_COMP E, DEPT_HASH D 
     WHERE E.DEPTNO = D.DEPTNO 
     AND E.HIREDATE > TO_DATE('29-JUN-1986','DD-MON-YYYY'); 

    
Plan Table 
------------------------------------------------------------------------------------------------------------ 
| Operation                   |  Name    |  Rows | Bytes|  Cost  |  TQ |IN-OUT| PQ Distrib | Pstart| Pstop | 
------------------------------------------------------------------------------------------------------------ 
| SELECT STATEMENT            |          |     2 |   102|      2 |     |      |            |       |       |
|  PARTITION HASH ALL         |          |       |      |        | 4,00| PCWP |            |     1 |     3 | 
|   HASH JOIN                 |          |     2 |  102 |      2 | 4,00| P->S | QC (RANDOM)|       |       | 
|    PARTITION RANGE ITERATOR |          |       |      |        | 4,00| PCWP |            |     4 |     5 | 
|     TABLE ACCESS FULL       |EMP_COMP  |     3 |   87 |      1 | 4,00| PCWP |            |    10 |    15 | 
|    TABLE ACCESS FULL        |DEPT_HASH |    63 |    1K|      1 | 4,00| PCWP |            |     1 |     3 | 
------------------------------------------------------------------------------------------------------------ 
9 rows selected. 

INLIST ITERATOR and EXPLAIN PLAN

An INLIST ITERATOR operation appears in the EXPLAIN PLAN output if an index implements an IN list predicate. For example, for the query:

   SELECT * FROM EMP WHERE EMPNO IN (7876, 7900, 7902); 

The EXPLAIN PLAN output appears as follows:

   OPERATION          OPTIONS           OBJECT_NAME
   ----------------   ---------------   -------------- 
   SELECT STATEMENT
   INLIST ITERATOR
   TABLE ACCESS       BY ROWID          EMP
   INDEX              RANGE SCAN        EMP_EMPNO

The INLIST ITERATOR operation iterates over the operation below it for each value in the IN list predicate. For partitioned tables and indexes, the three possible types of IN list columns are described in the following sections.

Index Column

If the IN list column EMPNO is an index column but not a partition column, then the plan is as follows (the IN list operator appears above the table operation but below the partition operation):

 OPERATION         OPTIONS        OBJECT_NAME   PARTITION_START   PARTITION_STOP
 ----------------  ------------   -----------   ---------------   --------------
 SELECT STATEMENT 
 PARTITION         INLIST                       KEY(INLIST)       KEY(INLIST)
 INLIST ITERATOR
 TABLE ACCESS      BY ROWID       EMP           KEY(INLIST)       KEY(INLIST)
 INDEX             RANGE SCAN     EMP_EMPNO     KEY(INLIST)       KEY(INLIST)

The KEY(INLIST) designation for the partition start and stop keys specifies that an IN list predicate appears on the index start/stop keys.

Index and Partition Column

If EMPNO is an indexed and a partition column, then the plan contains an INLIST ITERATOR operation above the partition operation:

 OPERATION         OPTIONS        OBJECT_NAME   PARTITION_START   PARTITION_STOP
 ----------------  ------------   -----------   ---------------   --------------
 SELECT STATEMENT
 INLIST ITERATOR
 PARTITION         ITERATOR                     KEY(INLIST)       KEY(INLIST)
 TABLE ACCESS      BY ROWID       EMP           KEY(INLIST)       KEY(INLIST)
 INDEX             RANGE SCAN     EMP_EMPNO     KEY(INLIST)       KEY(INLIST)

Partition Column

If EMPNO is a partition column and there are no indexes, then no INLIST ITERATOR operation is allocated:

 OPERATION         OPTIONS        OBJECT_NAME   PARTITION_START   PARTITION_STOP
 ----------------  ------------   -----------   ---------------   --------------
 SELECT STATEMENT
 PARTITION                                      KEY(INLIST)       KEY(INLIST)
 TABLE ACCESS      BY ROWID       EMP           KEY(INLIST)       KEY(INLIST)
 INDEX             RANGE SCAN     EMP_EMPNO     KEY(INLIST)       KEY(INLIST)

If EMP_EMPNO is a bitmap index, then the plan is as follows:

 OPERATION          OPTIONS           OBJECT_NAME
 ----------------   ---------------   -------------- 
 SELECT STATEMENT
 INLIST ITERATOR
 TABLE ACCESS       BY INDEX ROWID    EMP
 BITMAP CONVERSION  TO ROWIDS
 BITMAP INDEX       SINGLE VALUE      EMP_EMPNO

DOMAIN INDEX and EXPLAIN PLAN

You can also use EXPLAIN PLAN to derive user-defined CPU and I/O costs for domain indexes. EXPLAIN PLAN displays these statistics in the "OTHER" column of PLAN_TABLE.

For example, assume table EMP has user-defined operator CONTAINS with a domain index EMP_RESUME on the RESUME column and the index type of EMP_RESUME supports the operator CONTAINS. Then the query:

 SELECT * from EMP where Contains(resume, 'Oracle') = 1 

might display the following plan:

  OPERATION            OPTIONS      OBJECT_NAME     OTHER 
 -----------------    -----------  ------------    ----------------
 SELECT STATEMENT 
 TABLE ACCESS         BY ROWID     EMP
 DOMAIN INDEX                      EMP_RESUME      CPU: 300, I/O: 4

Formatting EXPLAIN PLAN Output

This section shows options for formatting EXPLAIN PLAN output

• Using the EXPLAIN PLAN Statement
• Selecting PLAN_TABLE Output in Table Format
• Selecting PLAN_TABLE Output in Nested Format
  

  Note: The output of the EXPLAIN PLAN statement reflects the behavior of the Oracle optimizer. As the optimizer evolves between releases of the Oracle server, output from the EXPLAIN PLAN statement is also likely to evolve.

Using the EXPLAIN PLAN Statement

The following example shows a SQL statement and its corresponding execution plan generated by EXPLAIN PLAN. The sample query retrieves names and related information for employees whose salary is not within any range of the SALGRADE table:

 SELECT ename, job, sal, dname
   FROM emp, dept
   WHERE emp.deptno = dept.deptno
      AND NOT EXISTS
         (SELECT *
            FROM salgrade
            WHERE emp.sal BETWEEN losal AND hisal);

This EXPLAIN PLAN statement generates an execution plan and places the output in PLAN_TABLE:

 EXPLAIN PLAN
   SET STATEMENT_ID = 'Emp_Sal'
   FOR SELECT ename, job, sal, dname
      FROM emp, dept
      WHERE emp.deptno = dept.deptno
         AND NOT EXISTS
            (SELECT *
               FROM salgrade
               WHERE emp.sal BETWEEN losal AND hisal);

Selecting PLAN_TABLE Output in Table Format

This SELECT statement:

            SELECT operation, options, object_name, id, parent_id, position, cost, cardinality,
            other_tag, optimizer 
               FROM plan_table
               WHERE statement_id = 'Emp_Sal'
               ORDER BY id;

Generates this output:

  OPERATION  OPTIONS OBJECT_NAME ID PARENT_ID POSITION COST CARDINALITY BYTES OTHER_TAG 
OPTIMIZER
  
-----------------------------------------------------------------------------------------------
  SELECT STATEMENT                    0                    2    2            1    62       
CHOOSE
  FILTER                              1          0         1
  NESTED LOOPS                        2          1         1    2            1    62
  TABLE ACCESS FULL    EMP            3          2         1    1            1    40     
ANALYZED
  TABLE ACCESS FULL    DEPT           4          2         2                 4    88     
ANALYZED
  TABLE ACCESS FULL    SALGRADE       5          1         2    1            1    13     
ANALYZED

The ORDER BY clause returns the steps of the execution plan sequentially by ID value. However, Oracle does not perform the steps in this order. PARENT_ID receives information from ID, yet more than one ID step fed into PARENT_ID.

For example, step 2, a merge join, and step 6, a table access, both fed into step 1. A nested, visual representation of the processing sequence is shown in the next section.

The value of the POSITION column for the first row of output indicates the optimizer's estimated cost of executing the statement with this plan to be 5. For the other rows, it indicates the position relative to the other children of the same parent.

Note: A CONNECT BY does not preserve ordering. To have rows come out in the correct order in this example, you must either truncate the table first, or else create a view and select from the view. For example:

CREATE VIEW test AS
SELECT id, parent_id,
lpad(' ', 2*(level-1))||operation||' '||options||' '||object_name||' '||
       decode(id, 0, 'Cost = '||position) "Query Plan"
FROM plan_table
START WITH id = 0 and statement_id = 'TST'
CONNECT BY prior id = parent_id and statement_id = 'TST';
SELECT * FROM foo ORDER BY id, parent_id;

This yields results as follows:

 ID  PAR Query Plan
 --- --- --------------------------------------------------
  0     Select Statement   Cost = 69602
  1   0   Nested Loops
  2   1     Nested Loops
  3   2       Merge Join
  4   3         Sort Join
  5   4           Table Access Full T3
  6   3         Sort Join
  7   6           Table Access Full T4
  8   2       Index Unique Scan T2
  9   1     Table Access Full T1
10 rows selected.

Selecting PLAN_TABLE Output in Nested Format

This type of SELECT statement generates a nested representation of the output that more closely depicts the processing order used for the SQL statement.

 SELECT LPAD(' ',2*(LEVEL-1))||operation||' '||options
   ||' '||object_name
   ||' '||DECODE(id, 0, 'Cost = '||position) "Query Plan"
   FROM plan_table
   START WITH id = 0 AND statement_id = 'Emp_Sal'
   CONNECT BY PRIOR id = parent_id AND statement_id ='Emp_Sal';
 
 Query Plan
 ------------------------------
 SELECT STATEMENT   Cost = 5
   FILTER
      NESTED LOOPS
         TABLE ACCESS FULL EMP
         TABLE ACCESS FULL DEPT
      TABLE ACCESS FULL SALGRADE  

The order resembles a tree structure, as illustrated in Figure 13-1.

Figure 13-1 Tree Structure of an Execution Plan

Tree structures illustrate how SQL statement execution operations feed one another. Oracle assigns each step in the execution plan a number representing the ID column of the PLAN_TABLE. Each step is depicted by a "node". The result of each node's operation passes to its parent node, which uses it as input.

EXPLAIN PLAN Restrictions

Oracle does not support EXPLAIN PLAN for statements performing implicit type conversion of date bind variables. With bind variables in general, the EXPLAIN PLAN output may not represent the real execution plan.

From the text of a SQL statement, TKPROF cannot determine the types of the bind variables. It assumes that the type is CHARACTER, and gives an error message if this is not the case. You can avoid this limitation by putting appropriate type conversions in the SQL statement.