When you call SEARCH on a TABLE file, Easytrieve does not read every row until it finds a match. The product loads table data into memory, builds an internal structure over ascending ARG keys, and applies binary search—halving the candidate set on each comparison until the key is found or proven absent. That algorithm is why TABLE lookup stays fast for batch jobs that decode codes millions of times per night. It is also why table maintenance is strict: one out-of-order ARG row or one duplicate key can make binary search return wrong results without a compile error. This page explains binary search as Easytrieve implements it: ascending sort requirements, duplicate rules, step-by-step intuition, complexity compared to sequential scan, numeric versus alphanumeric ARG ordering, validation practices after external file updates, and symptoms when production lookups suddenly fail after a reference data change.
Reference tables exist to answer the same question repeatedly: given this code, what is the description? A payroll run with two hundred thousand employees and twelve decode tables per row could invoke millions of lookups. Scanning every table row linearly for each lookup would multiply CPU cost by table size. Binary search reduces average comparisons from n to log₂(n). A five-hundred-row department table needs at most nine comparisons per SEARCH instead of up to five hundred. The trade-off is preparation: table data must be sorted and unique on ARG before load.
Imagine ARG keys 100, 200, 417, 903, 950 in a five-row table. SEARCH WITH 417 compares against the middle key 417—immediate match. SEARCH WITH 800 compares against middle 417; 800 is greater, so search continues in the upper half [903, 950]. Middle of upper half is 903; 800 is less, so search continues between 417 and 903—only 903 remains as candidate; no equal key, IF NOT table-file. Easytrieve performs this internally; you only supply sorted data and correct field lengths.
1234567891011FILE DEPTTAB TABLE INSTREAM ARG 1 3 N DESC 5 20 A 100 FINANCE 200 LEGAL 417 DATA CENTER 903 OPERATIONS 950 EXECUTIVE ENDTABLE SEARCH DEPTTAB WITH EMP-DEPT GIVING DEPT-NAME
Keys ascend numerically. Inserting 500 between 417 and 903 without maintaining order—say maintenance appends 500 after 950—breaks binary search. EMP-DEPT 500 might return NOT FOUND even though a row exists because midpoint logic examines wrong partitions.
| Rule | Reason | If violated |
|---|---|---|
| ARG ascending | Binary partition assumes low left, high right | Missed matches |
| No duplicate ARG | Single match point per key | Undefined which DESC wins |
| Consistent type | Numeric versus alpha compare differently | Wrong ordering if types mixed |
| Fixed length keys | Compare uses declared ARG length | Truncation or padding mismatches |
Numeric ARG fields sort by numeric value: 2 before 10. Alphanumeric ARG sorts character by character—'10' before '2' because '1' precedes '2' in collating sequence. Choose ARG type to match input key representation. Zip codes stored as five-digit numeric ARG need numeric DEFINE on input WITH field; state codes as two-character alphanumeric need consistent padding. Mixed maintenance—sometimes 'CA', sometimes 'C A'—creates ordering and match failures invisible until production reports show blank descriptions.
| Method | Per lookup cost | In Easytrieve |
|---|---|---|
| Binary search | O(log n) comparisons | SEARCH on TABLE files |
| Sequential scan | O(n) comparisons worst case | Manual GET loop—not recommended |
| Indexed Db2 | Index seek plus SQL overhead | SQL FILE |
For n equals 10,000 rows, binary search needs at most fourteen comparisons; sequential scan may need 10,000. Multiply by five million input records and the difference separates sub-minute CPU from unacceptable batch windows.
INSTREAM rows in source must be typed in ascending ARG order before compile. External sequential files must be sorted before JOB initiation load. Easytrieve does not verify full sort order at compile time for every instream row in all releases—teams rely on code review and optional validation programs that read maintenance files and flag order violations. Add a SORT step in table-generation JCL as insurance.
Compare failing key against maintenance file row order. Dump ARG values in sequence; one inversion often explains dozens of false negatives. Re-sort, reload, rerun.
FILE TABLE max-entries reserves memory for external load; it does not change search algorithm. Binary search runs over loaded entries regardless of whether count is fifty or five thousand. Undersizing max-entries truncates load—rows beyond limit never participate in search, appearing as permanent NOT FOUND for high keys.
No statement selects linear search for small tables. No hash-table option appears in Language Reference for TABLE files. SEARCH always uses binary search on sorted ARG. Optimization focus belongs on table size, call frequency, consolidating tables, and correct maintenance—not on alternate search modes inside Easytrieve.
Binary search is finding a name in a phone book by opening to the middle instead of reading every page from the start. The book must be in alphabetical order or the middle trick fails. Easytrieve keeps the phone book sorted on ARG and uses the middle-page trick every time you SEARCH.
1. Easytrieve SEARCH on TABLE files uses:
2. Duplicate ARG values in a table cause:
3. A table with 1,024 rows needs at most about:
4. ARG sort order must be:
5. Out-of-order ARG after maintenance causes: