COBOL Binary search

We had a situation where we loaded a large VSAM file into memory to be searched by online CICS application. We encountered problems trying to emulate the VSAM START verb using COBOL SEARCH ALL verb when the key does not exist in the array. To get around this we had to write our own BINARY SEARCH in COBOL. 

The array which we are searching contains about 240,000 entries. 

We found that the hand coded BINARY SEARCH was significantly more efficient in terms of CPU usage than the COBOL "SEARCH ALL" verb. 

The code was modeled after KNUTH's binary search, see this link 

http://www.z390.org/contest/p21/P21DW1.TXT 

the key to maximizing the performance of the code below was to use PIC S9(8) COMP for all the binary fields. This avoids the check for binary overflow in the generated code. Also we used the compiler option TRUNC(OPT) to avoid the code generated to check for truncation. 

Note --> the IF statement after the PERFORM loop is to check for a "not found" condition. To emulate the VSAM START command we need to position the INDEX to the first row which is >= the search key. 

           MOVE +1                     TO BIN-LOW. 

           MOVE BCNTR-TCA1-ENTRIES-USED 

                                       TO BIN-HIGH. 

           PERFORM WITH TEST AFTER 

               UNTIL BIN-LOW > BIN-HIGH 

               COMPUTE BIN-RANGE = BIN-HIGH - BIN-LOW 

               COMPUTE BIN-MID = (BIN-RANGE / 2) + BIN-LOW 

               SET TCA1-INDEX          TO BIN-MID 

               EVALUATE TRUE 

                   WHEN TCA1-KEY (TCA1-INDEX) = SRCH-TCA1-KEY 

                       MOVE 1          TO BIN-RANGE 

                       COMPUTE BIN-LOW = BIN-HIGH + 1 

                   WHEN TCA1-KEY (TCA1-INDEX) < SRCH-TCA1-KEY 

                       COMPUTE BIN-LOW  = BIN-MID + 1 

                   WHEN OTHER 

                       COMPUTE BIN-HIGH  = BIN-MID - 1 

               END-EVALUATE 

           END-PERFORM. 

           IF TCA1-KEY (TCA1-INDEX) < SRCH-TCA1-KEY 

               SET TCA1-INDEX          UP BY +1 

           END-IF. 

Row-Value-Expression and Quantified Predicates in Db2

Row-Value-Expression in Db2

A row-value-expression allows you to compare multiple columns (or values) at once as a tuple. Instead of writing separate conditions for each column, you can group them together.

General Syntax

(COL1, COL2, COL3) operator (Value1, Value2, Value3)

·        Both sides must have the same number of values.

·        Data types must be compatible.

·        Comparisons are evaluated pair by pair.

·        If any comparison involves NULL, the result may be Unknown.

Operators Explained with Examples

1. Equality (=)

(COL1, COL2, COL3) = (100, 'X', 2000)

·       Row (100, 'X', 2000) → True

·       Row (100, 'Y', 2000) → False

·       Row (100, NULL, 2000) → Unknown

2. Inequality (<>)

(COL1, COL2, COL3) <> (100, 'B', 500)

·       Row (100, 'B', 500) → False (all equal)

·       Row (100, 'C', 500) → True (COL2 <> 'B')

·       Row (101, 'B', 500) → True (COL1 <> 100)

3. Less Than (<)

(COL1, COL2, COL3) < (100, 'B', 500)

·       Row (100, 'A', 500) → True ('A' < 'B')

·       Row (99, 'Z', 999) → True (99 < 100)

·       Row (100, 'B', 400) → True (400 < 500)

4. Greater Than (>)

(COL1, COL2, COL3) > (100, 'B', 500)

·       Row (100, 'C', 500) → True ('C' > 'B')

·       Row (101, 'A', 300) → True (101 > 100)

·       Row (100, 'B', 600) → True (600 > 500)

5. Less Than or Equal (<=)

(COL1, COL2, COL3) <= (100, 'B', 500)

·       Row (100, 'B', 500) → True (exact match)

·       Row (100, 'A', 500) → True ('A' < 'B')

·       Row (99, 'Z', 999) → True (99 < 100)

6. Greater Than or Equal (>=)

(COL1, COL2, COL3) >= (100, 'B', 500)

·       Row (100, 'B', 500) → True (exact match)

·       Row (100, 'C', 500) → True ('C' > 'B')

·       Row (101, 'A', 300) → True (101 > 100)

The detailed IBM manual can be found at the following link:

 https://www.ibm.com/docs/en/db2-for-zos/12.0.0?topic=predicates-basic-predicate#db2z_basicpredicate__fnocop

 

Quantified Predicates in Db2

A quantified predicate compares a value (or a row of values) against a set of values returned by a subquery (fullselect). It uses operators together with quantifiers like ALL, SOME, or ANY.

General Syntax

expression operator {ALL | SOME | ANY} (fullselect1)

(row-value-expression) operator {ALL | SOME | ANY} (fullselect2)

·       expression → single value compared against a column of values.

·       row-value-expression → tuple of values compared against multiple columns.

·       fullselect → subquery returning one or more values.

Behavior of Quantifiers

1. ALL

• True if the relationship holds for every value returned by the subquery.
• False if the relationship fails for at least one value.
• Unknown if no comparison is false, but at least one is unknown due to NULL.
• Special case: If the subquery returns no rows, the result is True.

2. SOME / ANY

• True if the relationship holds for at least one value returned by the subquery.
• False if the subquery is empty or the relationship fails for all values.
• Unknown if no comparison is true, but at least one is unknown due to NULL.

Examples

TBLA

COLA
1
2
3
4

TBLB

 

COLB	COLC
2	2
3	–

TBLC

COLB	COLC
2	2

Example 1: ALL

COLA > ALL (SELECT COLB FROM TBLB UNION SELECT COLB FROM TBLC)

·       Subquery returns {2, 3}.

·       Predicate is False for rows 1, 2, 3.

·       True for row 4 (4 > 2 and 4 > 3).

Example 2: ANY

COLA > ANY (SELECT COLB FROM TBLB UNION SELECT COLB FROM TBLC)

·       Subquery returns {2, 3}.

·       Predicate is False for rows 1, 2.

·       True for rows 3, 4 (3 > 2, 4 > 2 or 3).

Example 3: ALL with NULL

COLA > ALL (SELECT COLC FROM TBLB UNION SELECT COLC FROM TBLC)

·       Subquery returns {2, NULL}.

·       Predicate is False for rows 1, 2.

·       Unknown for rows 3, 4 (because of NULL).

Example 4: SOME with NULL

COLA > SOME (SELECT COLC FROM TBLB UNION SELECT COLC FROM TBLC)

·       Subquery returns {2, NULL}.

·       Predicate is Unknown for rows 1, 2.

·       True for rows 3, 4 (3 > 2, 4 > 2).

Example 5: Empty Result with ALL

COLA < ALL (SELECT COLB FROM TBLB WHERE COLB > 3

            UNION

            SELECT COLB FROM TBLC WHERE COLB > 3)

·       Subquery returns empty set.

·       Predicate is True for all rows (special case).

Example 6: Empty Result with ANY

COLA < ANY (SELECT COLB FROM TBLB WHERE COLB > 3

            UNION

            SELECT COLB FROM TBLC WHERE COLB > 3)

·       Subquery returns empty set.

·       Predicate is False for all rows.

The detailed IBM manual can be found at the following link:

https://www.ibm.com/docs/en/db2-for-zos/12.0.0?topic=predicates-quantified-predicate