COMPILATION LISTING OF SEGMENT mrds_dsl_permute Compiled by: Multics PL/I Compiler, Release 33e, of October 6, 1992 Compiled at: CGI Compiled on: 2000-04-18_1115.46_Tue_mdt Options: optimize map 1 /****^ *********************************************************** 2* * * 3* * Copyright, (C) Honeywell Bull Inc., 1988 * 4* * * 5* * Copyright, (C) Honeywell Information Systems Inc., 1981 * 6* * * 7* * Copyright (c) 1972 by Massachusetts Institute of * 8* * Technology and Honeywell Information Systems, Inc. * 9* * * 10* *********************************************************** */ 11 12 13 14 15 /****^ HISTORY COMMENTS: 16* 1) change(87-01-22,Hergert), approve(88-07-11,MCR7903), 17* audit(88-07-07,Dupuis), install(88-08-01,MR12.2-1073): 18* For new parser, modified the way that the range and select list pointers 19* are set. 20* END HISTORY COMMENTS */ 21 22 23 24 mrds_dsl_permute: 25 proc (dbcb_ptr, ag_ptr, pvp, cost, code); 26 27 /* 28* BEGIN_DESCRIPTION 29* INPUT: 30* 31* dbcb_ptr - points to a valid dbcb in which dbcb.pred_ptr points to a valid 32* predicate tree. 33* 34* ag_ptr - points to an and_group list to be used in finding a search path. 35* 36* 37* 38* OUTPUT: 39* 40* pvp - points to a search path with the last variable being the first 41* variable in the list. 42* 43* cost - the calculated cost of this search path. 44* 45* code - may be 0 or any of the codes returned by mu_get_rel_size. 46* END_DESCRIPTION 47* 48* 49* MRDS_DEBUG_TOOL SWITCH DEFINITIONS: 50* 51* bit 1 = display each new low cost path as it is determinied. 52* 53* bit 2 = display each permutation step. 54* 55* bit 3 = use the path defined by the order of the range clause. 56* 57* bit 4 = display the access method cost calculation details 58* 59* bit 5 = display details of final lowest cost path 60* 61* bits 6 thru 9 = not used. 62* 63* NOTES for mrds_debug_tool 64* 65* bit 1 displays paths starting with the last variable to be 66* determined and working back to the first variable to be 67* determined. 68* 69* bit 2 displays partial paths starting with the first path to be 70* determined and working forward to the variable currently being 71* looked at. 72* 73* bit 3 causes the order of the range clause to be use as the order 74* of searching of relations for tuples satisfying the selection 75* expression when it is turned on. 76* 77* bit 4 causes the results of the calc_sub_path_cost subroutine to 78* be output. This includes the cost of doing each type of useable 79* access method, plus the low cost access method chosen, and it's 80* resulting partial path cost. 81* 82* bit 5 causes the details of all the conditions, and details for 83* the final path determined as the lowest cost path to be 84* displayed. 85* 86* 87* 88* 89* HISTORY: 90* 91* 79-10-01 Rickie E. Brinegar: Initially written using large portions of code 92* from mrds_dsl_calc_cost. 93* 94* 79-12-01 Rickie E. Brinegar: Modified to handle the case where the number 95* of variables in the range clause is greater than the number of variables in 96* the and group. 97* 98* 79-12-10 Rickie E. Brinegar: Modified to make the proper transfers when 99* using rev_ops. 100* 101* 79-12-11 Rickie E. Brinegar: Modified to make proper use of the op_code 102* variable when adding a condition to a range variable list. 103* 104* 80-01-14 Rickie E. Brinegar: Modified to keep conditions on attributes in 105* the same relation. 106* 107* 80-01-18 Rickie E. Brinegar: Modified to look at all the conditions on the 108* primary key when deciding if short_key may be used. 109* 110* 80-01-23 Rickie E. Brinegar: Modified to properly determine sequential 111* paths for tuple variables not found in the and group. 112* 113* 80-01-25 Rickie E. Brinegar: Modified to add the range variables not in 114* this and group to the end of the search path as a sequential search. 115* 116* 80-02-08 Rickie E. Brinegar: Modified to properly determine when a 117* expression should be evaluated in a search path. 118* 119* 80-02-09 Jim Gray: Modified to remove bad coding in while clause of 120* add_to_attr_list, so that both a null ptr, and a structure value depending 121* on that value on not in the same if statement. 122* 123* 80-02-11 Rickie E. Brinegar: Modified to correct the same problem that Jim 124* Gray corrected, only through out the rest of the code. 125* 126* 80-07-08 Rickie E. Brinegar: Modified to add the ability to generate only 127* the search path defined by the order of the attributes in the range clause 128* of the selection expresssion. This is done by setting mrds_debug_switch bit 129* 3. 130* 131* 80-08-14 Davids: answered tr7173 fixed as suggested in tr. problem occured 132* when mrds reversed the order of A op B as it appeared in the where clause 133* and B was an expression. Operator sense was reversed ok but it was still 134* connected to A rather than B. 135* 136* 80-10-17 Rickie E. Brinegar: Modified add_to_expr_list to properly 137* subscript expr_list.info.op_code. This was in response to TR7908. 138* 139* 81-01-13 Rickie E. Brinegar: Modified to reuse the structures allocated. 140* These include path_var, attr_list, expr_list, cond. This was in response to 141* TR8567. 142* 143* 81-02-24 Rickie E. Brinegar: Commented out the calling of code that has to 144* do only with blocked file structures. 145* 146* 81-03-27 Jim Gray : added dbcb_ptr parameter to mu_get_rel_size 147* as part of getting rid of mus_ptr_man module. 148* 149* 81-06-01 Jim Gray : changed to use new resultant structure, thus 150* blocked file code deleted. 151* 152* 81-06-29 Roger Lackey : added the use of dbcb.no_optimize flag q 153* 154* 81-07-02 Jim Gray : changed getting of relation tuple count from 155* a call to mu_get_rel_size, to getting it from the statistics now 156* kept in the rm_rel_info structure for that relation. 157* 158* 81-07-07 Jim Gray : made changes to allow correct calculation of 159* path cost, done via multiplying number of times that a particular 160* I/O cost will be incurred. These changes involved: 1) re-write 161* calc_sub_path_cost to take into account the currently available 162* access methods, compute the expected number of tuples retrieved 163* for that access method, compute the access cost based on times it 164* will be incurred 2) change the interface to what used to be 165* unique_index (now long_key) and index_range (now short_key) to 166* allow needed info to be passed back, this included the addition 167* of recognition of long key head access. 3) added the unordered 168* sequential type of access method 4) changed the interface to 169* find_attributes and permutations to include a multiplier 170* paramater, to be used in properly calculating sub_path costs 5) 171* Changed handling of not_in_and_group tuple variables, so that the 172* implied cross product is done in the fastest manner. This 173* involves forcing a sequential access method for not in and_group 174* tuple variables, and considering them just as the other tuple 175* variables are. 6) Also added many comments to help clarify the 176* logic and purpose of the major internal procedures. 7) Added the 177* debug switch 4, to display the results of the changed 178* calc_sub_path_cost routine. 8) added count_conditions subroutine, 179* and changes to long_key/short_key to take into account the number 180* of conditions, and the condition types, in estimating the number 181* of tuples selected by an access method. 182* 183* 81-07-14 Jim Gray : made some adjustments to the changes of 184* 07-07. 1) expanded the long_key subroutine to allow > 1 185* condition, along with the = conditions for primary keys, and key 186* heads, and renamed the routine equal_key. 2) changed short_key 187* not to have to consider the = condition, now that equal_key 188* handles 1st key attr for this case 3) improved the info returned 189* for the condition against a tuple variable, or a particular key. 190* 4) improved the formulas for conditions costing, and tuples 191* selected 5) changed the key head formula to the exponential form 192* for better behavior close to a fraction of 1/1. 6) added info to 193* path_var structure to force gen_srch_prog to use the access 194* method chosen by permute 195* 196* 81-07-16 Jim Gray : had to modify copy_attr_list to put pointer 197* to new copy of the cond structure in the path_var, now that it is 198* saved there in order to pass info to gen_srch_prog. 199* 200* 81-07-17 Jim Gray : added a debug switch option to display all 201* the details for the final lowest cost path found. Also changed 202* logic dealing with attr_list entries, so that array elements are 203* addressed on an attribute definition order basis. 204* 205* 81-07-18 Jim Gray : removed logic referring to cost = 0 as a 206* control in the permutations program. This was done for two 207* reasons. First this control was part of the old not in and group 208* logic that was thrown away, and second, the most efficient path 209* was not being found for the case of one of the tuple variables 210* having a zero population. In the last case the 0 tuple rel should 211* go first always, and result in an and group cost of 0.0 Also 212* changed calc_sub_path_cost to not do un-needed work in the case 213* of unpopulated relations. 214* 215* 81-07-19 Jim Gray : added logic to handle tuple variables with no 216* effect on the select set. They are dropped from further 217* consideration in the low cost path, but passed back to optimize 218* for further no tuple effect checks. 219* 220* 81-07-21 Jim Gray : added the ability to favor a range of values 221* specified against a short key head or indexed attr, and to 222* remember the details for gen srch prog. 223* 224* 81-08-03 Jim Gray : fixed problem introduced by last change, the 225* = condition was not being favored over >, <=, etc. conditions if 226* it came first in the condition list. 227* 228* 81-09-21 Rickie E. Brinegar: Changed the assignment of two expr_list 229* structures to each other to be done using an unspec to avoid subscript 230* ranged conditions. 231* 232* 82-06-04 Mike Kubicar : Added fix for TR phx12306. The problem was 233* that permute would sometimes change its mind in the middle of a 234* selection's where clause and decide that an equals comparison is better 235* than the range one it was working on. Unfortunately, it would not 236* completely change it's internal representation to reflect this fact. 237* 238* 82-07-20 Ronald B. Harvey: Made fix for TR phx12925. This involved fixing 239* an improperly constructed do statement in get_attr_list. A test could not 240* be generated, but it was clear that the statement was in error. 241* 242* 82-09-16 Davids: Modified the way that the best condition for an indexed 243* attribute is choosen, created the find_index_attr internal 244* procedure. This takes into account not only the precedence 245* order of the equal, range, inequality and not-equal 246* operations but the number of duplicates for each index 247* (obtained from rm_attr_info.number_of_dups). The one with 248* the fewest duplicates will be chosen, if two or more have 249* the same number of dups the one defined first within the 250* relation will be chosen. Note that the number of dups for 251* a vfile type database is an estimate and equal for all 252* of the indices. 253* 254* Modified the internal proc calc_sub_path_cost tono longer 255* assume the equal distribution of dups throughout all 256* indices in a relation but to use the number of dups 257* returned from the call to the internal proc short_key 258* (which ends up calling find_index_attr). 259* 260* Removed references to the constant cost values for the 261* different access methods and replaced them with references 262* to elements in the dbcb structure. Costs will be dependent 263* on the type of database, i.e. vfile or page_file. 264* 265*82-12-15 Davids: Modified the copy_expr_list procedure by explicitly setting 266*the number of expressions in the copy_to_ptr -> path_var.elp -> expr_list to 267*the original number it was allocated with. The number of expressions recorded 268*is reduced from the number the structure was allocated with since the original 269*number is based on a maximum possible number while the number in the structure 270*is the actual number of expressions. This was needed because it is possible 271*to get a string size condition when different and-groups have different 272*numbers of expressions and the expr_list structures and being copied and 273*re-used. Fixes TR 14382 274* 275* 83-04-04 Mike Kubicar : Removed code to generate an unordered sequential 276* search. vfile_relmgr_ can now handle all searches on a record collection 277* cursor correctly. 278* 279* 83-10-01 Bert Moberg: Added code to the permutations subroutine to not 280* try all possible permutations if the number of tuple variables is very 281* large (=> ENOUGH_TUPLE_VARIABLES_TO_NOT_TRY_ALL_POSSIBLE_PERMUTATIONS, 282* currently = 5). The current path must be predicted to select <= 1 tuple 283* (<= PATH_DOES_NOT_EXPAND) at every level where permutations are skipped. 284* If this true, it implies that the exact order is not as important, since 285* the levels will be executed the same number of times. In all cases, all 286* permutations will be tried for the first 287* NUMBER_OF_LEVELS_THAT_MUST_BE_PERMUTED (currently 2). 288* 289*83-10-24 Roger Lackey : Changed the dcl for index_attr_number_of_dups from 290* fixed bin to fixed bin (35). 291**/ 292 1 1 /* BEGIN mrds_dbcb.incl.pl1 -- jaw, 11/7/78 */ 1 2 1 3 1 4 1 5 /****^ HISTORY COMMENTS: 1 6* 1) change(85-11-17,Dupuis), approve(85-12-16,MCR7314), 1 7* audit(86-02-04,Brunelle), install(86-02-05,MR12.0-1013): 1 8* This entry is being made to cover the change made on 85-07-01 by Thanh 1 9* Nguyen. The scopes_changed flag was added to make checking for this 1 10* more efficient (mrds error list #137). 1 11* 2) change(86-06-10,Blair), approve(86-08-07,MCR7491), 1 12* audit(86-08-07,Gilcrease), install(86-08-15,MR12.0-1127): 1 13* Add a bit called dont_check_txn_id to indicate whether or not we should 1 14* care if multiple txns use the same selection_expression. (mrds #156) 1 15* 3) change(87-11-23,Hergert), approve(88-06-28,MCR7903), 1 16* audit(88-06-28,Dupuis), install(88-08-01,MR12.2-1073): 1 17* Added parser_work_area_ptr and mrds_se_info_ptr for new parser. 1 18* END HISTORY COMMENTS */ 1 19 1 20 1 21 /* WARNING 1 22* If the dbcb structure is changed then the mrds_data_ 1 23* item saved_res_version MUST be incremented to invalidate all 1 24* existing saved resultants 1 25**/ 1 26 1 27 /* HISTORY : 1 28* 1 29* modified by Jim Gray - - 80-10-24, to add new_select_expr bit for 1 30* tid_list management 1 31* 1 32* 81-1-9 Jim Gray : added like reference for ease in making the 1 33* phony resultant in mu_database_index, without having the area dcl 1 34* included. 1 35* 1 36* 81-06-17 Roger Lackey : added last_store_rel_name for use by 1 37* mrds_dsl_store 1 38* 1 39* 81-06-26 Roger Lackey : Added no_optimize and print_search_order 1 40* switches 1 41* 1 42* 81-07-06 Jim Gray : added identifier for the current selection 1 43* expression, so that relation statistics can be updated relative 1 44* to number of selection expressions seem. Also removed init for 1 45* last_store_rel_name, as this iw now properly done in 1 46* mrds_dsl_init_res. 1 47* 1 48* 81-07-17 Roger Lackey : added pred_ptr and unused_ptrs. 1 49* 1 50* 82-08-19 Mike Kubicar : added store_vector field. This is needed 1 51* for the conversion to the relation manager. 1 52* 1 53* 82-08-23 Davids: added the relmgr_entries and access_costs 1 54* substructures so that the entries and costs can change 1 55* depending on the type of database that is opened. 1 56* 1 57* 82-09-09 Mike Kubicar : added modify_vector field. This is needed 1 58* since modify uses a different vector type (general) than does store. 1 59* 1 60* 82-09-20 Davids: changed names of (store modify)_vector to 1 61* (store modify)_vector_ptr. Also (delete modify)_tuple_by_id to 1 62* (delete modify)_tuples_by_id. added the element cursor_storage_ptr 1 63* which should be inited to null and will be set by mu_cursor_manager_$get 1 64* during the first call. 1 65* 1 66* 82-09-21 Davids: renamed cursor_storage_ptr to cursor_ptrs_storage_ptr 1 67* since it deals with the pointers to the cursors and not the cursors 1 68* themelves and added the element cursor_storage_area_ptr which points 1 69* to the area where the cursors are kept. 1 70* 1 71* 82-09-22 Davids: renamed the transact_ctl_seg to transactions_needed. 1 72* the transact_ctl_seg always had a value of 0 and really didn't mean 1 73* anything. 1 74* 1 75* 82-09-22 Mike Kubicar : added create_relation, create_index and 1 76* destroy_relation_by_opening to relmgr_entries. They are needed 1 77* by mrds_dsl_define_temp_rel. 1 78* 1 79* 82-09-24 Donna Woodka : added put_tuple to relmgr_entries. It 1 80* is needed by mu_store. 1 81* 1 82* 82-11-12 Davids: changed the declaration of the access_costs from fixed 1 83* bin to float bin since the values are not integers. 1 84* 1 85* 83-02-02 Davids: added the dbc_uid element. This will allow mrds to make 1 86* sure that the dbc_ptr still points to the correct segment. Element was 1 87* added to the end of the structure to allow modules that don't use 1 88* the element to continue to reference the dbcb structure without recompiling. 1 89* 1 90* 83-02-25 Davids: added the concurrency_on and rollback_on elements. These 1 91* are needed so that temp rels can be created with the same file attributes 1 92* as the permanent relations. 1 93* 1 94* 83-05-02 Mike Kubicar : Deleted get_next_search_specification_ptr and 1 95* added the resultant_in_pdir bit. 1 96* 1 97* 83-05-18 Davids: reduced the number of reserved bits to 14 (from 15) and 1 98* added the res_already_made element. 1 99* 1 100* 83-05-24 Mike Kubicar : Updated the relation manager calling sequences. 1 101* 1 102* 83-08-03 Mike Kubicar : Added the element_id_list_segment_ptr and removed 1 103* one of the unused pointers. 1 104* 1 105* 83-09-20 Ron Harvey: Added relmgr_entries.get_population. 1 106* 1 107* 84-08-27 John Hergert: Created compiled_se_info_ptr from unused_ptrs(2) 1 108* leaving unused_ptrs(1). 1 109* 1 110* 85-01-15 Thanh Nguyen: Added the work_area_ptr and removed the last 1 111* unused_ptrs (1). 1 112* 1 113* 85-04-12 Thanh Nguyen: Added user_started_transaction and 1 114* non_shared_to_shared flags. Also added se_transaction_id and some more 1 115* spare ptrs, entries and reserved storages for future enhancement, since 1 116* we changed the saved_res_version from rslt0001 to rslt0002. 1 117* 1 118* 85-07-01 Thanh Nguyen: Added scopes_changed flag. This flag is set by 1 119* common routine of mrds_dsl_set_scope, reset by mrds_dsl_optimize and 1 120* mrds_dsl_gen_srch_prog when building of a new search_vars. 1 121**/ 1 122 1 123 1 124 /* this structure is based on the {unique_name}.mrds.dbcb segment 1 125* that constitutes the non-secure portion of the resultant model that is 1 126* created during the opening of a database. it contains variables that 1 127* are used during the runtime access of the database, and an area 1 128* for evaluation of requests. it points to four other 1 129* segments in the resultant model, {unique_name}.mrds.rdbi, the secure 1 130* portion of the resultant(see mdbm_rm_db_info.incl.pl1), 1 131* {unique_name}.mrds.select, an area for selection expression evaluation, 1 132* {unique_name}.mrds.curdat, and {unique_name}.mrds.stadat, two segments 1 133* used in the elimination of duplicate tuples during a retrieve. 1 134* the dbcb area holds the structure in mdbm_scope_info.incl.pl1 1 135* that is used when the database is using the file scope mechanism 1 136* for concurrency control over file readying. the segment overlayed via 1 137* mrds_dbc.incl.pl1 structure is pointed to and also handles concurrency control, 1 138* across database openings. the pointer to this dbcb structure is kept in a table 1 139* which associates database indexes(returned from a call to dsl_$open), with particular 1 140* opening instances of resultant models. (see mu_database_index routine) */ 1 141 1 142 dcl 1 dbcb aligned based (dbcb_ptr), /* DBCB -- non-secure portion */ 1 143 2 data like dbcb_data, 1 144 2 static_area area (sys_info$max_seg_size - fixed (rel (addr (dbcb.static_area)))); 1 145 1 146 dcl dbcb_ptr ptr; 1 147 1 148 declare 1 dbcb_data based, /* info part of dbcb, separated out so that 1 149* like references can avoid getting the area declaration */ 1 150 2 rdbi_ptr ptr, /* pointer to write protected mdbm_util_ info. */ 1 151 2 range_ptr ptr, /* ptr to range structure, or null */ 1 152 2 select_ptr ptr, /* ptr to select list, or null */ 1 153 2 sv_ptr ptr, /* pointer to search variables */ 1 154 2 so_ptr ptr, /* pointer to search operators */ 1 155 2 ti_ptr ptr, /* pointer to tuple info */ 1 156 2 lit_ptr ptr, /* pointer to the literal area, or null */ 1 157 2 current_ptr ptr, /* ptr to select list resulting from -current clause */ 1 158 2 ss_ptr ptr, /* ptr to select sets block if not simple s.e. */ 1 159 2 retr_info_ptr ptr, /* ptr to retrieve info area */ 1 160 2 trel_info_ptr ptr, /* ptr to retrieve info area */ 1 161 2 sti_ptr ptr, /* pointer to store info */ 1 162 2 dbc_ptr ptr, /* pointer to the data base control segment */ 1 163 2 sfi_ptr ptr, /* points to head of scalar function list */ 1 164 2 scope_ptr ptr, /* points to array of scope tuples */ 1 165 2 select_area_ptr ptr, /* ptr to area for current selection expression allocations */ 1 166 2 current_data_ptr ptr, /* ptr to one of 2 segments used by mrds_dsl_retrieve 1 167* for eliminating duplicate tuples. */ 1 168 2 static_data_ptr ptr, /* ptr to one of 2 segments used by mrds_dsl_retrieve 1 169* for eliminating duplicate tuples. */ 1 170 2 store_area_ptr ptr, /* temp storage area for dsl_$store */ 1 171 2 retrieve_area_ptr ptr, /* temp storage for dsl_$retrieve */ 1 172 2 modify_area_ptr ptr, /* temp storage area for dsl_$modify */ 1 173 2 delete_area_ptr ptr, /* temp storage area for dsl_$delete */ 1 174 2 def_temp_rel_area_ptr ptr, /* temp storage area for dsl_$define_temp_rel */ 1 175 2 pred_ptr ptr, /* Pointer to pred_array */ 1 176 2 store_vector_ptr ptr, /* Vector structure used during store operations */ 1 177 2 modify_vector_ptr ptr, /* Used during modifies */ 1 178 2 element_id_list_segment_ptr ptr, /* Points to the segment used to hold element_id_list structures */ 1 179 2 compiled_se_info_ptr ptr, /* points to the segment containing all info on compiled sexs */ 1 180 2 work_area_ptr ptr, /* Work area for encode/decode value allocations in mu_retrieve */ 1 181 2 se_info_ptr ptr, /* Points to se_info struct. Primarily for error reports */ 1 182 2 parser_work_area_ptr ptr, /* work area for parser */ 1 183 2 reserved_ptrs (4) ptr, /* Reserved for future use */ 1 184 2 another_flag bit (1) unal, /* on if predicate was -another */ 1 185 2 current_flag bit (1) unal, /* on if predicate was -current clause */ 1 186 2 dbc_incr bit (1) unal, /* on if dbc open mode has been incremented for this user */ 1 187 2 delete_flag bit (1) unal, /* On if search was called from mrds_dsl_sec_delete */ 1 188 2 dup_retain bit (1) unaligned, /* On if dup tuples allowed for retrieval */ 1 189 2 prev_select bit (1) unal, /* on if prev. select block processed in this s.e. */ 1 190 2 possible_op bit (1) unal, /* on of arith op. allowed */ 1 191 2 sel_clause bit (1) unal, /* on if currently in select clause */ 1 192 2 dsm_sw bit (1) unal, /* on if data base was opened via data submodel */ 1 193 2 val_rtrv bit (1) unal, /* if s.e. valid for retrieve */ 1 194 2 val_mod bit (1) unal, /* for modify */ 1 195 2 val_del bit (1) unal, /* for delete */ 1 196 2 val_dtr bit (1) unal, /* for define temp rel */ 1 197 2 transactions_needed bit (1) unal, /* On => transaction must be started or in progress does 1 198* not imply that the database is of type page_file */ 1 199 2 open_mode bit (3) unal, /* 0=>unknown, 1=>r, 2=>u, 3=>er, 4=>eu, >4=>bad */ 1 200 2 new_select_expr bit (1) unal, /* on => starting a new tid list management period */ 1 201 2 no_optimize bit (1) unal, /* On => no optimize */ 1 202 2 print_search_order bit (1) unal, /* On => print the search order */ 1 203 2 resultant_in_pdir bit (1) unal, /* On => Temp segments are in the process dir */ 1 204 2 res_already_made bit (1) unal, /* On => resultant has been made based on a saved copy */ 1 205 2 user_started_transaction bit (1) unal, /* On => user already started his own transaction. */ 1 206 2 non_shared_to_shared bit (1) unal, /* On => user changed the scope from non shared to shared 1 207* inside a sequence of -another selection expression. */ 1 208 2 scopes_changed bit (1) unal, /* On => scopes had been changed by set_scopes or delete_scopes */ 1 209 2 dont_check_txn_id bit (1) unal, /* On => cpmd needs same selection exp across multiple txns */ 1 210 2 reserved bit (10) unal, /* reserved for future use */ 1 211 2 nseq_sch fixed bin (35), /* no. tuples located via sequential search */ 1 212 2 nind_sch fixed bin (35), /* no. tuples located via index search */ 1 213 2 nhash_sch fixed bin (35), /* no. tuples located via hash search */ 1 214 2 nlk_sch fixed bin (35), /* no tuples located via link search */ 1 215 2 cur_lit_offset fixed bin (35), /* current bit offset in literal string */ 1 216 2 dbi fixed bin (35), /* database index for this opening */ 1 217 2 last_s_e_id_num fixed bin (35), /* identifying number for last selection expression seen */ 1 218 2 se_transaction_id bit (36) aligned, /* transaction id from beginning of select expression */ 1 219 2 last_store_rel_name char (32), /* Name of relation last used for store */ 1 220 2 cursor_ptrs_storage_ptr ptr, /* pointer to space where cursor ptrs are stored */ 1 221 2 cursor_storage_area_ptr ptr, /* pointer to area where the cursors are kept */ 1 222 2 reserved_words (10) fixed bin (35), /* Reserved for future use */ 1 223 2 relmgr_entries, /* relation manager entries */ 1 224 3 open entry (char (*), char (*), bit (36) aligned, fixed bin (35)), 1 225 3 close entry (bit (36) aligned, fixed bin (35)), 1 226 3 create_cursor entry (bit (36) aligned, ptr, ptr, fixed bin (35)), 1 227 3 destroy_cursor entry (ptr, ptr, fixed bin (35)), 1 228 3 set_scope entry (bit (36) aligned, bit (2) aligned, bit (2) aligned, fixed bin (35)), 1 229 3 delete_tuples_by_id entry (ptr, ptr, fixed bin (35), fixed bin (35)), 1 230 3 modify_tuples_by_id entry (ptr, ptr, ptr, fixed bin (35), fixed bin (35)), 1 231 3 get_tuple_by_id entry (ptr, bit (36) aligned, ptr, ptr, ptr, fixed bin (35)), 1 232 3 get_tuples_by_spec entry (ptr, ptr, ptr, ptr, ptr, fixed bin (35)), 1 233 3 get_tuple_id entry (ptr, ptr, ptr, ptr, fixed bin (35)), 1 234 3 put_tuple entry (ptr, ptr, bit (36) aligned, fixed bin (35)), 1 235 3 get_count entry (ptr, ptr, fixed bin (35), fixed bin (35)), 1 236 3 get_duplicate_key_count entry (ptr, bit (36) aligned, fixed bin (17), fixed bin (35), fixed bin (35)), 1 237 3 get_population entry (ptr, fixed bin (35), fixed bin (35)), 1 238 3 create_relation entry (char (*), char (*), ptr, ptr, bit (36) aligned, bit (36) aligned, fixed bin (35)), 1 239 3 create_index entry (bit (36) aligned, ptr, bit (36) aligned, fixed bin (17), bit (36) aligned, fixed bin (35)), 1 240 3 destroy_relation_by_path entry (char (*), char (*), fixed bin (35)), 1 241 3 reserved_entries (5) entry (), 1 242 2 access_costs, /* access costs for permute */ 1 243 3 total_primary_key_cost float bin, 1 244 3 access_cost float bin, 1 245 3 access_overhead float bin, 1 246 3 us_access_cost float bin, 1 247 3 os_access_cost float bin, 1 248 2 dbc_uid bit (36) aligned, /* uid of the segment containing the dbc structure */ 1 249 2 concurrency_on bit (1) unal, /* "1"b implies dmfile concurrency is being used */ 1 250 2 rollback_on bit (1) unal; /* "1"b iomplies before journaling is to be done */ 1 251 1 252 /* END mrds_dbcb.incl.pl1 */ 1 253 1 254 293 294 2 1 /* BEGIN mrds_range.incl.pl1 -- jaw, 10/20/78 */ 2 2 2 3 /* Modified 83-04-22 by R. Harvey to add needed_bits */ 2 4 2 5 dcl 1 range aligned based (range_ptr), 2 6 2 num_vars fixed bin, /* number of tuple variables */ 2 7 2 tup_var (mrds_data_$max_tup_var refer (range.num_vars)), /* info for each tuple variable */ 2 8 3 name char (mrds_data_$max_id_len), /* name of tuple variable */ 2 9 3 temp_rel bit (1) unal, /* on if temporary relation */ 2 10 3 used bit (1) unal, /* 1 => this tuple variable is referenced by 2 11* a -select clause. */ 2 12 3 whole_tuple_selected bit (1) unal, /* the whole tuple variable is referenced in the select clause */ 2 13 3 copy_for_current bit (1) unal, /* -current requests attributes not previously retrieved */ 2 14 3 copied_for_current bit (1) unal, /* tuple copied during previous -current */ 2 15 3 reserved bit (31) unal, /* reserved for future use */ 2 16 3 rel_index fixed bin, /* index to assoc. relation */ 2 17 3 stv_ptr ptr, /* simple typed vector */ 2 18 3 idl_ptr ptr, /* id_list ptr */ 2 19 3 needed_bits aligned, 2 20 4 attr (mrds_data_$max_attributes) bit (1) unal, 2 21 3 ri_ptr ptr; /* pointer to rel info for assoc. relation */ 2 22 2 23 dcl range_ptr ptr; 2 24 2 25 /* END mrds_range.incl.pl1 */ 2 26 295 296 3 1 /* BEGIN mrds_predicate_tree.incl.pl1 -- jaw, 2/14/79 */ 3 2 3 3 /* HISTORY: 3 4* 3 5* 81-06-01 Jim Gray : removed assn type and len, now that 3 6* mu_convert is being used. 3 7* 3 8* 3 9**/ 3 10 3 11 3 12 dcl 1 pred_node based (pn_ptr), /* structure of predicate tree node */ 3 13 2 type fixed bin, /* indicates if node or leaf */ 3 14 2 id unal, /* id for node */ 3 15 3 lleaf_id like pred_leaf.id, /* id for left leaf */ 3 16 3 op_code bit (6) unal, /* operator code for this node */ 3 17 3 rleaf_id like pred_leaf.id, /* id for right leaf */ 3 18 2 term_type fixed bin (5) unal, /* if term, indicates type of term */ 3 19 2 root bit (1) unal, /* on if root node */ 3 20 2 term bit (1) unal, /* on if node is term */ 3 21 2 determined bit (1) unal, /* on if term is "determined" independent of other terms */ 3 22 2 reserved bit (21) unal, /* reserved for future use */ 3 23 2 parent ptr, /* pointer to parent node */ 3 24 2 lbr ptr, /* pointer to left branch */ 3 25 2 rbr ptr; /* pointer to right branch */ 3 26 3 27 dcl pn_ptr ptr; 3 28 3 29 dcl 1 pred_array based (pred_ptr), /* list representation of pred. */ 3 30 2 type fixed bin, /* indicates array, rather than node or leaf */ 3 31 2 num_ands fixed bin, /* is the number of and groups */ 3 32 2 and_ptr (num_ands_init refer (pred_array.num_ands)) ptr; /* pointers to the and groups */ 3 33 3 34 dcl pred_ptr ptr; 3 35 3 36 dcl 1 and_group based (ag_ptr), /* list of pointers to all terms in and group */ 3 37 2 num_terms fixed bin, /* number of terms in list */ 3 38 2 term_ptr (num_terms_init refer (and_group.num_terms)) ptr; /* point to terms in this and group */ 3 39 3 40 dcl ag_ptr ptr; 3 41 dcl (num_ands_init, 3 42 num_terms_init) fixed bin; 3 43 3 44 dcl ((CURRENT_OP init ("000001"b)), /* pred_node op_codes */ 3 45 (AND_OP init ("000010"b)), 3 46 (OR_OP init ("000011"b)), 3 47 (NOT_OP init ("000100"b)), 3 48 (EQ_OP init ("000101"b)), 3 49 (NE_OP init ("000110"b)), 3 50 (LT_OP init ("000111"b)), 3 51 (GT_OP init ("001000"b)), 3 52 (LE_OP init ("001001"b)), 3 53 (GE_OP init ("001010"b)), 3 54 (ALL_OP init ("001011"b))) bit (6) int static options (constant); 3 55 3 56 dcl ((CONST init (1)), /* pred leaf data types */ 3 57 (ATTR init (2)), 3 58 (EXPRES init (3))) fixed bin int static options (constant); 3 59 3 60 dcl ((NODE init (0)), /* type indicators */ 3 61 (LEAF init (1)), 3 62 (ARRAY init (2))) fixed bin int static options (constant); 3 63 3 64 dcl ((V_C init (1)), /* pred_node term_types */ 3 65 (V_V init (2))) fixed bin (5) int static options (constant); 3 66 3 67 dcl 1 pred_leaf based (pl_ptr), /* structure for a predicate tree leaf */ 3 68 2 type fixed bin, /* indicates if node or leaf */ 3 69 2 id, /* leaf id */ 3 70 3 var_id bit (18) unal, /* index of tuple var. */ 3 71 3 attr_id bit (18) unal, /* defn order of attr. */ 3 72 2 dummy bit (1) unal, /* on if dummy leaf for ALL_OP */ 3 73 2 reserved bit (35) unal, /* reserved for future use */ 3 74 2 data_type fixed bin, /* whether const, attr, or expr */ 3 75 2 lit_offset fixed bin (35), /* bit offset of literal or expr. result */ 3 76 2 lit_length fixed bin (35), /* bit length of literal or expr. result */ 3 77 2 rslt_desc bit (36), /* descriptor of expr. result */ 3 78 2 lit_ptr ptr, /* ptr to literal or expr. result value */ 3 79 2 lit_desc_ptr ptr, /* ptr to literal or expr. result desc. */ 3 80 2 ai_ptr ptr, /* to rm_attr_info for attribute */ 3 81 2 expr_ptr ptr, /* pointer to expr. structure if expr. leaf */ 3 82 2 parent ptr; /* pointer to parent node */ 3 83 3 84 dcl pl_ptr ptr; 3 85 3 86 /* END mrds_predicate_tree.incl.pl1 */ 3 87 297 298 4 1 /* BEGIN mrds_optimize_tables.incl.pl1 -- jaw, 2/23/79 */ 4 2 4 3 /* HISTORY: 4 4* 4 5* 81-07-06 Jim Gray : added number of tuples selected, and the 4 6* access methods currently available to the path_var structure, to 4 7* allow the cost of a search path to be properly calculated. 4 8* 4 9* 81-07-07 Jim Gray : added in_and_group and cost to path_var for 4 10* handling not in and_group tuple variables. 4 11* 4 12* 81-07-13 Jim Gray : removed calc_cost related structures that are 4 13* no longer used. Also commented the access methods available. 4 14* Added cond_ptr and attr_index to path_var to make gen_srch_prog 4 15* use access specified by permute. 4 16* 4 17* 81-07-14 Jim Gray : added condition_selected and attr_selected 4 18* bits to the cond and attr_list structures respectively, so that 4 19* the permute logic in gen_srch_prog could be removed, and the 4 20* desires of permute could be passed to gen_srch_prog. Also added 4 21* description of structures in this include file. 4 22* 4 23* 81-07-17 Jim Gray : removed unused path_array structure once used 4 24* by the discarded calc_cost routine, now replaced by permute. 4 25* 4 26* 81-07-19 Jim Gray : added in_select_clause bit to path_var for 4 27* use by optimize, gen_srch_prog and the permute display for 4 28* properly handling no_tuple_effect tuple variables, and not 4 29* producing cross products not specified by the user. 4 30* 4 31* 81-07-21 Jim Gray : added a second condition pointer to the path 4 32* var structure, so that permute could detect, make use of, and 4 33* pass on the info for doing range searches on key heads and 4 34* secondary indexes. 4 35* 4 36* 83-04-22 Mike Kubicar : removed attr_list.info.used. It is no 4 37* longer needed. 4 38* 4 39**/ 4 40 4 41 4 42 /* DESCRIPTION: 4 43* 4 44* The major structure of this include file is the path_var 4 45* structure. It is used to hold an ordered list of tuple variables 4 46* from the selection expression range clause, in the order in which 4 47* they will be used for doing I/O on the database in order to 4 48* retrieve the data necessary to evaluate the selection expression. 4 49* 4 50* The alp in this structure points to the attr_list structure which 4 51* contains a list of all attributes referenced by this particular 4 52* tuple variable in the selection expression. 4 53* 4 54* The elp in this path_var structure for this tuple variable 4 55* similarly points to the expr_list structure, which contains 4 56* information on all expressions in the selection expression which 4 57* reference the tuple variable. 4 58* 4 59* The attr_list structure in turn has a list of all conditions 4 60* (comparisons involving it) against that attribute in a linked 4 61* list of cond structures pointed to by the cond_ptr. 4 62* 4 63* The op_code encoding for thecond and expr_list structures is that 4 64* used in the pred_node structures of the predicate tree, and that 4 65* given by the named constants starting OTT_... 4 66* 4 67* The path_array structure was originally intended for use by 4 68* mrds_dsl_calc_cost, which is obsolete. Now only one element is 4 69* used to point to the path returned by permute. 4 70* 4 71**/ 4 72 4 73 dcl 1 path_var aligned based (pvp), /* info on one path through and group */ 4 74 2 var_index fixed bin, /* index of this var */ 4 75 2 in_and_group bit (1) unal, /* on => this tuple variable participates in the and group */ 4 76 2 in_select_clause bit (1), /* on => this tuple variable selected */ 4 77 2 pad bit (34) unal, /* for future use */ 4 78 2 cost float bin (63), /* partial sub path cost, or total for not in and_group */ 4 79 2 number_tuples_selected fixed bin (35), /* estimate of tuples selected by access method */ 4 80 2 access_method fixed bin, /* encoding for the method of access to this tuple variable: 4 81* 1 => unique key search 4 82* 2 => long key head search, only "=" conditions 4 83* 3 => short key head, other than "=" conditions 4 84* 4 => indexed attr 4 85* 5 => unordered sequential search 4 86* 6 => ordered sequential search */ 4 87 2 cond_ptr ptr, /* to condition on this T.V. to be used for accessing it */ 4 88 2 second_cond_ptr ptr, /* to second condition when a range is specified */ 4 89 2 attr_index fixed bin, /* attr_ptr array definition order index 4 90* of attr to be used for accessing this T.V. */ 4 91 2 lk_key_ind fixed bin, /* link index or key id */ 4 92 2 alp ptr, /* to attribute list */ 4 93 2 elp ptr, /* to expr list */ 4 94 2 fwd_thd ptr; /* to next in path */ 4 95 4 96 dcl pvp ptr; 4 97 4 98 4 99 /* ACCESS METHODS AVAILABLE TO MRDS: 4 100* 4 101* 1) any number of key attributes making up a total primary key, 4 102* with at least one "=" condition against each allows use of a 4 103* vfile seek_key, to find the 1 unique tuple referenced 4 104* 4 105* 2) any number of key head attributes with at least one "=" 4 106* condition against each allows use of vfile select, to find >1 4 107* tuples whose key has this prefix value 4 108* 4 109* 3) the first key head attribute having other than a "=" 4 110* condition, or any number of conditions against it allows use of 4 111* vfile select, to find >1 tuples whose key has this prefix 4 112* 4 113* 4) a single secondarily indexed attribute with any condition or 4 114* number of conditions against it allows use of vfile select, to 4 115* find the >= 1 tuples whose values match that of the value or 4 116* range of values given 4 117* 4 118* 5) an unordered sequential search, where no updates against the 4 119* database relation will be done allows use of mu_scan_records, 4 120* which goes through the records without touching the vfile keys 4 121* 4 122* 6) an ordered sequential search, which must touch the vfile keys 4 123* in order to get the tuple records, thus producing an in-order 4 124* retrieval 4 125* 4 126**/ 4 127 4 128 dcl ((TOTAL_PRIMARY_KEY init (1)), 4 129 (LONG_KEY_HEAD init (2)), 4 130 (SHORT_KEY_HEAD init (3)), 4 131 (INDEXED_ATTR init (4)), 4 132 (UNORDERED_SEQUENTIAL init (5)), 4 133 (ORDERED_SEQUENTIAL init (6))) fixed bin int static options (constant); 4 134 4 135 dcl 1 attr_list aligned based (alp), /* info on all ref. attr. for a t.v. */ 4 136 2 nattr fixed bin, /* number of attrs in rel */ 4 137 2 info (al_nattr_init refer (attr_list.nattr)), /* definition order array */ 4 138 3 attr_selected bit (1) unal, /* on => this attr used by access method chosed */ 4 139 3 pad bit (35) unal, 4 140 3 index fixed bin, /* definition order, same as array element number */ 4 141 3 cond_ptr ptr ; /* to list of conditions on attr. */ 4 142 4 143 dcl alp ptr; 4 144 dcl al_nattr_init fixed bin; 4 145 4 146 dcl 1 cond aligned based (condp), /* info on attr condition */ 4 147 2 op_code fixed bin, /* op code translated from pred_node */ 4 148 2 condition_selected bit (1) unal, /* on => this condition used by access method chosen */ 4 149 2 pad bit (35) unal, 4 150 2 pl_ptr ptr, /* to pred leaf of other attr */ 4 151 2 fwd_thd ptr; /* to next condition */ 4 152 4 153 dcl condp ptr; 4 154 4 155 dcl 1 expr_list aligned based (elp), /* info for expr in this var */ 4 156 2 nexprs fixed bin, 4 157 2 info (el_nexprs_init refer (expr_list.nexprs)), 4 158 3 epl_ptr ptr, /* to pred leaf for this expr */ 4 159 3 op_code fixed bin, 4 160 3 reserved bit (36) unal, /* for future use */ 4 161 3 pl_ptr ptr; /* to pred leaf of other var */ 4 162 4 163 dcl elp ptr; 4 164 dcl el_nexprs_init fixed bin; 4 165 4 166 /* COMPARISON OPERATOR NAMED CONSTANTS: 4 167* 4 168* The following named constants represent the comparison operators 4 169* "=", "^=", "<", "<=", ">", ">=". 4 170* 4 171* They are used in the predicate tree nodes, the cond and expr_list 4 172* structure, and in gen_srch_prog structures. */ 4 173 4 174 dcl ((OTT_EQ init (1)), 4 175 (OTT_NE init (2)), 4 176 (OTT_LT init (3)), 4 177 (OTT_LE init (4)), 4 178 (OTT_GT init (5)), 4 179 (OTT_GE init (6))) fixed bin int static options (constant); 4 180 4 181 /* END mrds_optimize_tables.incl.pl1 */ 4 182 299 300 5 1 /* BEGIN mdbm_rm_rel_info.incl.pl1 -- jaw, 11/16/78 */ 5 2 5 3 /* WARNING 5 4* If the rm_rel_info structure is changed then the mrds_data_ 5 5* item saved_res_version MUST be incremented to invalidate all 5 6* existing saved resultants 5 7**/ 5 8 5 9 /* HISTORY: 5 10* 5 11* Modified by Jim Gray - - May 1980, to include model number of 5 12* attributes, and varying attributes, so that partial view 5 13* submodels will have the info needed to properly set up the 5 14* varying length array headers in the tuple structure. 5 15* 5 16* Modified by Jim Gray - - 80-11-06, to rename r_perm = 5 17* status_perm, s_perm = append_tuple_perm, d_perm = 5 18* delete_tuple_perm, and make m_perm = unused_perm. 5 19* 5 20* 81-01-23 Jim Gray : added bit to indicate whether the last model 5 21* view attribute was varying character or bit, since a partial view 5 22* submodel will not have this information in the resultant, and it 5 23* is needed for determining the new tuple length in mus_mod_ubtup, 5 24* since with exact length storage of varying length attributes, 5 25* each tuple can be a different length, which is can only be 5 26* determined by examining the tuple itself. 5 27* 5 28* 81-01-29 Jim Gray : added curent tuple count, to provide for 5 29* interface to allow temp rel population to be known, and to 5 30* provide a more efficient means of finding an approx. current perm 5 31* relation population. 5 32* 5 33* 81-05-28 Jim Gray : removed structure elements referring to 5 34* blocked files, foreign keys, and ids procedures. Also set number 5 35* of files per rel to a constant of 1. 5 36* 5 37* 81-05-28 Jim Gray : combined data from rm_file_info into this 5 38* structure so that only one structure per relation is needed. 5 39* 5 40* 81-07-02 Jim Gray : added total_key and dup_key vfile statistics 5 41* counts. Also added number of operations count since last 5 42* statistics update, and a time since the statistics were last 5 43* updated. 5 44* 5 45* 81-07-06 Jim Gray : added a per selection expression update 5 46* identifier so that small relations could be updated on a per S.E. 5 47* basis 5 48* 5 49* 82-04-21 R. Lackey : Added number_selected (ri_niocbs_init refer (rm_rel_info.niocbs)) fixed bin (35) 5 50* to end of structure TR 12205 (Suggestion). 5 51* 5 52* 82-08-19 D. Woodka : Removed rm_rel_info.max_data_len field for 5 53* the DMS conversion. 5 54* 5 55* 82-08-30 Davids: added the opening_id element and removed the iocb 5 56* array and the niocb element for DMS conversion. Also removed the 5 57* number_selected array (and ri_niocbs_init) since subsets are not 5 58* going to be used. 5 59* 5 60* 82-09-20 Mike Kubicar : changed rm_rel_info.rel_id to bit (36) aligned 5 61* so that it can be used with relation manager. Also added 5 62* rm_rel_info.primary_key_index_id for relation manager. 5 63* 5 64* 82-09-22 Mike Kubicar : Removed the, now useless, fields var_attr_ptrs, 5 65* nvar_atts, model_nvar_atts. 5 66* 5 67* 82-09-24 Davids: Removed current_key_count and current_dup_key_count 5 68* since the duplicate key count for each secondary index is now being 5 69* kept in the attr_info structure and key_count was only needed to 5 70* help in calculating the average selectivity of each index which 5 71* can now be gotten directly from each index's dup key count. Also 5 72* removed the file_id element since it is no longer needed for 5 73* anything. 5 74* 5 75* 82-09-27 Mike Kubicar : removed file_id_len for the same reason file_id 5 76* was removed. 5 77* 5 78* 82-11-05 Mike Kubicar : added a pointer to an id_list structure to be 5 79* used when retrieving tuples from this relation. 5 80* 5 81* 83-04-06 Davids: Added the scope_flags_ptr which points to the scope_flags structure 5 82* for the relation. Note that this structure is part of the resultant NOT 5 83* part of the db.control structure. The scopes are duplicated in the resultant 5 84* to reduce contention for the db.control structure. Note also that the pointer 5 85* will always point to a scope_flags structure even if no scopes have been 5 86* set on the relation, the structure is allocated when the db is opened. 5 87**/ 5 88 5 89 5 90 /* DESCRIPTION: 5 91* 5 92* This structure is allocated in the area part of the structure in 5 93* mdbm_rm_db_info.incl.pl1 as part of the resultant model created 5 94* at open time for a database. There will be one of these 5 95* rm_rel_info structures for each relation appearing in the 5 96* database view (there may be less than the total in the database 5 97* for a submodel openings). There will also be one for each 5 98* temporary relation currently defined for that opening. 5 99* 5 100* The structure in mdbm_rm_rel_array.incl.pl1 contains pointers to 5 101* all rm_rel_info structures allocated. It is used for searching 5 102* for the appropriate structure. This array is pointed to by 5 103* rm_db_info. There are two arrays, one for perm rels, one for temp 5 104* rels. 5 105* 5 106* The rm_rel_info structure points to the 5 107* mdbm_rm_attr_info.incl.pl1 structures, one for each attribute 5 108* appearing in this view of the relation. Each of these in turn 5 109* point to a mdbm_rm_domain_info.incl.pl1 structure for the domain 5 110* info for each attr. 5 111* 5 112* Most of the other information here deals with specifics of the 5 113* relation's logical definition, such as key and secondary index 5 114* attribute inidicators, security permissions, and tuple physical 5 115* construction details. 5 116* 5 117**/ 5 118 5 119 dcl 1 rm_rel_info aligned based (rmri_ptr), /* relation information */ 5 120 2 name char (32), /* from submodel */ 5 121 2 model_name char (30), /* from model */ 5 122 2 rel_id bit (36) aligned, /* unique id. */ 5 123 2 retrieve bit (1) unal, /* operations allowed by this view */ 5 124 2 modify bit (1) unal, 5 125 2 delete bit (1) unal, 5 126 2 store bit (1) unal, 5 127 2 total_key bit (1) unal, /* on if view includes full primary key */ 5 128 2 indexed bit (1) unal, /* on if exists sec. index */ 5 129 2 mdbm_secured bit (1) unal, /* on if mdbm must check security */ 5 130 2 status_perm bit (1) unal, /* if user has status. perm. */ 5 131 2 append_tuple_perm bit (1) unal, /* if user has store perm. */ 5 132 2 delete_tuple_perm bit (1) unal, /* if user has del. perm. */ 5 133 2 unused_perm bit (1) unal, /* for future use. */ 5 134 2 last_model_attr_char_var bit (1) unal, /* on => last model varying attr is char */ 5 135 2 reserved bit (24) unal, /* for future use */ 5 136 2 num_attr fixed bin, /* total no. of attr. in rel. */ 5 137 2 model_num_attr fixed bin, /* total attrs in model relation */ 5 138 2 nkey_attr fixed bin, /* no. of key attr. */ 5 139 2 model_nkey_attr fixed bin, /* total number of keys in model */ 5 140 2 primary_key_index_id bit (36) aligned, /* Index id of relation's primary key */ 5 141 2 nsec_inds fixed bin, /* no. sec. indexes */ 5 142 2 max_key_len fixed bin (35), /* max length (chars) of primary key */ 5 143 2 current_tuple_population fixed bin (35), /* last known total tuple count for this relation */ 5 144 2 last_statistics_update_count fixed bin, /* number of operations's, since this rels stats were updated */ 5 145 2 last_statistics_update_time fixed bin (71),/* last time this rels stats were updated */ 5 146 2 last_statistics_update_s_e_ref_num fixed bin (35), /* last select expr ID that updated this rels stats */ 5 147 2 ready_mode fixed bin, /* 1 => r, 2 => mr, 3 => u, 4 => l, 5 => sr, 6 => su */ 5 148 2 file_type fixed bin, /* 1 => unblocked, 2 => blocked, 3 => temporary */ 5 149 2 tuple_id_len fixed bin, /* no. bits in local tuple id */ 5 150 2 opening_id bit (36) aligned, /* relation manager opening is */ 5 151 2 key_attr_ptrs (nkey_attr_init refer (rm_rel_info.nkey_attr)) ptr, /* ptrs to key attr. */ 5 152 2 attr_ptrs (natts_init refer (rm_rel_info.num_attr)) ptr, /* ptrs to all attr. */ 5 153 2 id_list_ptr ptr, /* Id list for retrieves from the relation */ 5 154 2 scope_flags_ptr ptr; /* pointer to the scope_flags structure for the rel */ 5 155 5 156 dcl rmri_ptr ptr; 5 157 dcl (nkey_attr_init, 5 158 natts_init, 5 159 nvar_atts_init) fixed bin; 5 160 5 161 /* END mdbm_rm_rel_info.incl.pl1 */ 5 162 5 163 301 302 6 1 /* BEGIN mdbm_rm_attr_info.incl.pl1 -- jaw, 11/16/78 */ 6 2 6 3 /* WARNING 6 4* If the rm_attr_info structure is changed then the mrds_data_ 6 5* item saved_res_version MUST be incremented to invalidate all 6 6* existing saved resultants 6 7**/ 6 8 6 9 /* 6 10* 6 11* Modified by Jim Gray - - 80-11-05, to add mdbm_secured bit, so 6 12* that rm_rel_info does not have to be checked 6 13* 6 14* 81-05-28 Jim Gray : removed structure elements referring to 6 15* foreign keys. 6 16* 6 17* 82-08-19 D. Woodka : removed rm_attr_info.bit_offset for the DMS 6 18* conversion. 6 19* 6 20* 82-09-15 Davids: added the number_of_dups field. 6 21* 6 22* 82-09-20 Mike Kubicar : changed the index_id field to be bit (36) 6 23* aligned. This is to conform with the new definition in the database 6 24* model. Also removed the now useless field varying. 6 25* 6 26* 82-11-05 Davids: added the field model_defn_order and clarified the 6 27* comment for the field defn_order. 6 28* 6 29* 83-05-23 Mike Kubicar : changed number_of_dups to fixed bin (35) since 6 30* that's what relation manager returns. 6 31* 6 32**/ 6 33 6 34 6 35 /* 6 36* this structure is allocated in the static area of 6 37* mdbm_rm_db_info.incl.pl1 once for each attribute per relation in 6 38* a readied file. it in turn points to 6 39* mdbm_rm_domain_info.incl.pl1 for the attributes domain. the 6 40* rm_attr_info is pointed to by mdbm_rm_rel_info.incl.pl1. all 6 41* structures are in the rm_db_info area. the attribute data 6 42* position within a tuple as stored in the data file are kept in 6 43* this resultant model of the attribute. 6 44* */ 6 45 6 46 dcl 1 rm_attr_info aligned based (rai_ptr), /* resultant attr. info */ 6 47 2 name char (32), /* from submodel */ 6 48 2 model_name char (32), /* from model */ 6 49 2 key_attr bit (1) unal, /* if key attribute */ 6 50 2 index_attr bit (1) unal, /* if secondary index */ 6 51 2 read_perm bit (1) unal, /* user has retr. permission */ 6 52 2 modify_perm bit (1) unal, /* user has modify permission */ 6 53 2 mdbm_secured bit (1) unal, /* on => database secured */ 6 54 2 reserved bit (30) unal, /* for future use */ 6 55 2 index_id bit (36) aligned, /* index id if index_attr */ 6 56 2 defn_order fixed bin, /* relative order in which attr is defined in the view */ 6 57 2 key_order fixed bin, /* relative order defined in prim. key */ 6 58 2 bit_length fixed bin (35), /* length if fixed, max. len. if var. */ 6 59 2 domain_ptr ptr, /* to domain info */ 6 60 2 number_of_dups fixed bin (35), /* if the attribute is indexed this will 6 61* be the number of duplicate values, exact 6 62* for a page_file database, an estimate for a vfile type */ 6 63 2 model_defn_order fixed bin; /* relative order in which attr is defined in the model */ 6 64 6 65 dcl rai_ptr ptr int automatic init (null ()); 6 66 6 67 /* END mdbm_rm_attr_info.incl.pl1 */ 6 68 6 69 303 304 7 1 /* BEGIN INCLUDE FILE mdbm_seg_area.incl.pl1 - - Jim Gray 2/19/79 */ 7 2 7 3 /* these structures provide a standard for 7 4* 1) using an entire segment as an area, managed by the area manager 7 5* 2) a constant header, that has an offset to the major common structure in the area 7 6* the pointer to that structure is obtained via pointer(model_seg_ptr, model_seg.offset) 7 7* the model_area_ptr is obtained via pointer(model_seg_ptr, size(model_seg)) */ 7 8 7 9 declare 1 model_seg aligned based (model_seg_ptr), /* segment header, not to be changed */ 7 10 2 struct_offset bit (18), /* offset to major structure allocated in area */ 7 11 2 padding (3) fixed bin ; /* to set up four word boundary */ 7 12 7 13 declare model_seg_ptr ptr int automatic init (null ()); 7 14 7 15 7 16 declare model_area area (sys_info$max_seg_size - size (model_seg)) based (model_area_ptr) ; /* segment area */ 7 17 7 18 declare model_area_ptr ptr int automatic init (null ()); 7 19 7 20 dcl size builtin; 7 21 7 22 /* END INCLUDE FILE mdbm_seg_area.incl.pl1 */ 7 23 305 306 8 1 /* BEGIN INCLUDE FILE mrds_select_area.incl.pl1 (Kepner Multics) 05/29/79 1736.1 mst Tue */ 8 2 dcl 1 select_area_struct aligned based (select_area_struct_ptr), /* major structure in segment for current selection expression allocations */ 8 3 2 version fixed bin, 8 4 2 dbcb_ptr ptr; /* ptr ptr to dbcb */ 8 5 8 6 dcl select_area_struct_ptr ptr int automatic init (null ()); 8 7 8 8 dcl select_area area (sys_info$max_seg_size - size(model_seg)) based (select_area_ptr); 8 9 8 10 dcl select_area_ptr ptr int automatic init (null ()); 8 11 /* END INCLUDE FILE mrds_select_area.incl.pl1 */ 8 12 307 308 9 1 /* BEGIN INCLUDE FILE mrds_debug_names.incl.pl1 Jim Gray 8/7/79 */ 9 2 9 3 /* this include file associates module names with debug switches 9 4* that are stored in the data segment mrds_debug_ 9 5* each module has it's own bit(9) debug switch, to define for various 9 6* debug actions, with new module names to be added to the end 9 7* of this list using the next in order array index in mrds_debug_ 9 8* the convention for naming is db_{module's full name} 9 9* for the defined declaration over mrds_debug_$switch. 9 10* module.name array is then changed to reflect the new 9 11* number of modules, with the full module name added to the bottom 9 12* of the initialize list for the name array. 9 13* the module name array is used by the command level interface that sets/resets 9 14* the current status of the debug switches for each module. 9 15* the modules themselves use the db_{module name} declared variable for 9 16* that module to interagate the bits for proper debug action to take. 9 17* the definition of the meaning of the 9-bits is up to each individual module's 9 18* designer. */ 9 19 9 20 9 21 /* 9 22* HISTORY 9 23* 9 24* 80-11-12 Davids: added db_mus_mod_ubtup 9 25* 9 26* 80-11-13 Davids: added db_mu_sec_get_tuple and db_mu_sec_get_tid 9 27* 9 28* 80-12-15 Jim Gray : added mrds_dsl_set_fscope to display non 9 29* error info about being queued, and request being granted after 9 30* being queued. 9 31* 9 32* 81-01-15 Jim Gray : added mu_concurrency_control bit to allow 9 33* running MR8 and MR9 mrds against the same database at the same 9 34* time. 9 35* 9 36* 81-02-02 Jim Gray : added bit for mrds_rst_dmdm to allow 9 37* displaying internal tuple format bit offset, rather than the user 9 38* view. 9 39* 9 40* 81-02-06 Jim Gray : added bit for new mu_open_name_manager, to 9 41* dump an element from the list, when display_open_names entry 9 42* called with switch set. 9 43* 9 44* 81-05-20 Jim Gray : added bit for mrds_dsl_where_clause display 9 45* of sub_err_ messages, when cross domain compare occurs. 9 46* 9 47* 81-06-17 Jim Gray : added bit for mu_open_iocb_manager to display 9 48* iocb slot and rel name. 9 49* 9 50* 81-07-08 Jim Gray : added comment for bit 4 in mrds_dsl_permute 9 51* 9 52* 81-07-17 Jim Gray : added comment for bit 5 in mrds_dsl_permute 9 53* 9 54* 81-07-18 Jim Gray : added bit 1 for mrds_dsl_gen_srch_prog that 9 55* allows key searches, other than than specified by permute to be 9 56* done as comparisons instead. 9 57* 9 58* 81-07-22 Jim Gray : added comment about bit 2 in 9 59* mrds_dsl_gen_srch_prog 9 60**/ 9 61 9 62 declare ( 9 63 db_mrds_dsl_eval_expr bit (9) unal defined (mrds_debug_$switch (1)), 9 64 db_mrds_dsl_get_token bit (9) unal defined (mrds_debug_$switch (2)), 9 65 db_mrds_dsl_permute bit (9) unal defined (mrds_debug_$switch (3)), 9 66 db_mrds_dsl_optimize bit (9) unal defined (mrds_debug_$switch (4)), 9 67 db_mrds_dsl_search bit (9) unal defined (mrds_debug_$switch (5)), 9 68 db_mrds_dsl_translate bit (9) unal defined (mrds_debug_$switch (6)), 9 69 db_mu_retrieve bit (9) unal defined (mrds_debug_$switch (7)), 9 70 db_mrds_dsl_open bit (9) unal defined (mrds_debug_$switch (8)), 9 71 db_mrds_dsl_close bit (9) unal defined (mrds_debug_$switch (9)), 9 72 db_mrds_dsl_init_res bit (9) unal defined (mrds_debug_$switch (10)), 9 73 db_mu_sec_init_res bit (9) unal defined (mrds_debug_$switch (11)), 9 74 db_mus_mod_ubtup bit (9) unal defined (mrds_debug_$switch (12)), 9 75 db_mu_sec_get_tuple bit (9) unal defined (mrds_debug_$switch (13)), 9 76 db_mu_sec_get_tid bit (9) unal defined (mrds_debug_$switch (14)), 9 77 db_mrds_dsl_set_fscope bit (9) unal defined (mrds_debug_$switch (15)), 9 78 db_mu_concurrency_control bit (9) unal defined (mrds_debug_$switch (16)), 9 79 db_mrds_rst_dmdm bit (9) unal defined (mrds_debug_$switch (17)), 9 80 db_mu_open_name_manager bit (9) unal defined (mrds_debug_$switch (18)), 9 81 db_mrds_dsl_where_clause bit (9) unal defined (mrds_debug_$switch (19)), 9 82 db_mu_open_iocb_manager bit (9) unal defined (mrds_debug_$switch (20)), 9 83 db_mrds_dsl_gen_srch_prog bit (9) unal defined (mrds_debug_$switch (21)) 9 84 ) ; 9 85 9 86 /* list of known module names, with index into name array 9 87* the same as that into mrds_debug_$switch, 9 88* number is the current count of defined module names, 9 89* name is the modules full name. */ 9 90 9 91 declare 1 module options (constant) internal static, 9 92 2 number fixed bin init (21), 9 93 2 name char (32) dimension (21) init ( 9 94 "mrds_dsl_eval_expr", /* 1 => display value of each expression */ 9 95 "mrds_dsl_get_token", /* 1 => display the current token */ 9 96 "mrds_dsl_permute", /* each 1 => lost cost path found, 9 97* 2 => reverse partial path 9 98* 3 => use range order for path 9 99* 4 => display access method costs 9 100* 5 => display details of final low cost path */ 9 101 "mrds_dsl_optimize", /* 1 => pred tree, 9 102* 2 => paths to consider, 3 => calc_cost on */ 9 103 "mrds_dsl_search", /* 1 => display each tuple located */ 9 104 "mrds_dsl_translate", /* 1 => display the search program */ 9 105 "mu_retrieve", /* 1 => display values compared, 2 => display tuple data */ 9 106 "mrds_dsl_open", /* 1 => allow cleanup sub_error_ */ 9 107 "mrds_dsl_close", /* 1 => allow cleanup sub_error_ */ 9 108 "mrds_dsl_init_res", /* 1 => allow cleanup sub_error_ */ 9 109 "mu_sec_init_res", /* 1 => allow cleanup sub_error_ */ 9 110 "mus_mod_ubtup", /* 1 => consistency checking between the old 9 111* and new tuple during modifies will be done */ 9 112 "mu_sec_get_tuple", /* 1 => attribute values 9 113* will be zeroed in the tuple structure 9 114* is don't have read permission. */ 9 115 "mu_sec_get_tid", /* 1 => read permission to the key 9 116* is checked (if db is secured) */ 9 117 "mrds_dsl_set_fscope", /* 1 => display being queued, 9 118* and request granted from queue messages */ 9 119 "mu_concurrency_control", /* 1 => allow both dbc and db.control segs under db 9 120* so can test both MR8 and MR9 mrds 9 121* against the same database at the same time */ 9 122 "mrds_rst_dmdm", /* 1 => allow internal form of bit offset value 9 123* for attributes to be displayed, rather than user view */ 9 124 "mu_open_name_manager", /* 1 => dump mrds_open_name tree node structure, 9 125* when display_open_names entry called */ 9 126 "mrds_dsl_where_clause", /* 1 => display details of cross domain compares */ 9 127 "mu_open_iocb_manager", /* 1 => display relation and slot getting iocb for */ 9 128 "mrds_dsl_gen_srch_prog" /* 1 => do additional conditions as sequential, not key searches 9 129* when the original access was a key, 9 130* and the additional conditions can be done as key also 9 131* 2 => force key searches, regardless of strategy 9 132* used to decide between compare or key search */ 9 133 ) ; 9 134 9 135 declare mrds_debug_$switch (1:400) bit (9) unal ext ; /* data segment debug array */ 9 136 9 137 /* END INCLUDE FILE mrds_debug_names.incl.pl1 */ 9 138 309 310 311 dcl (m_d_p_i, level, number_of_variables) fixed bin; 312 313 dcl (cost, current_path_cost) float bin (63); 314 315 dcl (display_low_cost_paths, display_path_permutations, 316 display_access_method_costs, use_range_order) bit (1) unal; 317 318 dcl ( 319 attr_list_free_ptr init (null), 320 cond_free_ptr init (null), 321 current_path_ptr init (null), 322 expr_list_free_ptr init (null), 323 last_condp init (null), 324 low_cost_path_ptr init (null), 325 path_ptr init (null), 326 path_var_free_ptr init (null), 327 range_order_path_ptr init (null), 328 work_path_ptr init (null), 329 work_ptr init (null) 330 ) ptr; 331 332 dcl ( 333 mrds_data_$max_attributes, 334 mrds_data_$max_id_len, 335 mrds_data_$max_tup_var, 336 sys_info$max_seg_size 337 ) fixed bin (35) ext; 338 339 dcl code fixed bin (35); 340 341 dcl variable_array (mrds_data_$max_tup_var) fixed bin; 342 343 dcl (addr, ceil, fixed, max, null, rel, substr, unspec) builtin; 344 345 dcl ioa_ entry options (variable); 346 dcl mdb_display_path_$path entry (ptr, ptr); 347 348 dcl (temp_current_path_multiplier, current_path_multiplier) float bin (63); 349 /* number ot times access cost will be incurred */ 350 dcl finished bit (1); /* on => end of generating all permutations */ 351 dcl CONDITION_COST_FACTOR (1:6) float bin (27) init (1.5, 0.2, (4) (0.5)); 352 /* weighting for "=", "^=", and other comparisons */ 353 dcl condition_array (1:6) char (2) init ("=", "^=", "<", "<=", ">", ">=") 354 int static options (constant); /* char values for displaying condition operators */ 355 dcl access_method_name (1:6) char (20) int static options (constant) 356 init ("Total primary key", "Long key head", "Short key head", 357 "Indexed attribute", "Sequential", "Sequential"); 358 dcl first_pass bit (1); /* on => still building a path to compare against */ 359 dcl no_tuple_effect_number fixed bin; /* number of tuple variable with no select set effect */ 360 dcl no_tuple_effect_ptr ptr; /* to list of no tuple effect T.V.'s */ 361 dcl last_no_tuple_effect_ptr ptr; /* to last no tuple effect T.V. on list */ 362 dcl dummy_good_enough bit (1); 363 364 code = 0; 365 366 /* set mrds_debug_tool switches */ 367 368 display_low_cost_paths = substr (db_mrds_dsl_permute, 1, 1); 369 display_path_permutations = substr (db_mrds_dsl_permute, 2, 1); 370 display_access_method_costs = substr (db_mrds_dsl_permute, 4, 1); 371 372 if substr (db_mrds_dsl_permute, 3, 1) | dbcb.no_optimize then 373 use_range_order = "1"b; 374 else use_range_order = "0"b; 375 select_area_ptr = dbcb.select_area_ptr; 376 range_ptr = dbcb.range_ptr; 377 number_of_variables = range.num_vars; 378 no_tuple_effect_number = 0; 379 no_tuple_effect_ptr, low_cost_path_ptr, current_path_ptr = null; 380 cost = 0.; 381 variable_array (1) = 1; 382 allocate path_var in (select_area); /* set up minimum cost path */ 383 path_var.alp, path_var.elp = null; 384 low_cost_path_ptr = pvp; 385 do m_d_p_i = 2 to number_of_variables; 386 variable_array (m_d_p_i) = m_d_p_i; 387 work_ptr = pvp; 388 allocate path_var in (select_area); 389 path_var.alp, path_var.elp = null (); 390 work_ptr -> path_var.fwd_thd = pvp; 391 end; 392 path_var.fwd_thd = null (); 393 m_d_p_i = 1; 394 finished = "0"b; 395 first_pass = "1"b; 396 do while (^finished); /* generate all permutations of the path */ 397 current_path_ptr = null; 398 current_path_cost = 0.; 399 400 401 /* NOTE: in all comments, T.V. is short hand for tuple variable */ 402 403 current_path_multiplier = 1; /* previously selected tuples don't exists for first T.V. */ 404 call 405 find_attributes (variable_array (m_d_p_i), current_path_multiplier, 406 current_path_cost, code); 407 if code ^= 0 then 408 return; 409 current_path_ptr = pvp; 410 level = 1; 411 if number_of_variables > 1 then do; 412 if path_var.in_and_group | path_var.in_select_clause then 413 temp_current_path_multiplier = 414 current_path_multiplier * path_var.number_tuples_selected; 415 else temp_current_path_multiplier = current_path_multiplier; 416 417 call 418 permutations (temp_current_path_multiplier, current_path_cost, 419 level + 1, dummy_good_enough, code); 420 end; 421 else do; 422 low_cost_path_ptr = current_path_ptr; 423 current_path_ptr = null; 424 cost = current_path_cost; 425 end; 426 if code ^= 0 then 427 return; 428 code = 0; 429 if use_range_order then 430 finished = "1"b; 431 else m_d_p_i = m_d_p_i + 1; 432 433 if m_d_p_i > number_of_variables then 434 finished = "1"b; 435 436 if current_path_ptr ^= null then do; 437 work_ptr = current_path_ptr -> path_var.fwd_thd; 438 do while (current_path_ptr ^= null); 439 call free_structures (current_path_ptr); 440 current_path_ptr = work_ptr; 441 if current_path_ptr ^= null then 442 work_ptr = current_path_ptr -> path_var.fwd_thd; 443 end; 444 end; 445 end; 446 447 /* add the no tuple effect variables to the end of the low cost path, 448* they are needed for no_tuple_effect checks in optimize, 449* and will be skipped by gen_srch_prog */ 450 451 do pvp = low_cost_path_ptr repeat path_var.fwd_thd 452 while (path_var.fwd_thd ^= null ()); 453 454 end; 455 456 path_var.fwd_thd = no_tuple_effect_ptr; 457 458 /* display the final low cost path found, if the debug switch is set */ 459 460 if substr (db_mrds_dsl_permute, 5, 1) then 461 call display_final_path_details (); 462 463 /* perpare final search path by putting it in reverse order expected by mrds_dsl_optimize */ 464 465 do pvp = low_cost_path_ptr repeat path_var.fwd_thd 466 while (path_var.fwd_thd ^= null); 467 end; 468 path_ptr = pvp; /* reverse list for mrds_dsl_optimize */ 469 do m_d_p_i = 1 to number_of_variables - 1 + no_tuple_effect_number; 470 do current_path_ptr = low_cost_path_ptr 471 repeat current_path_ptr -> path_var.fwd_thd 472 while (current_path_ptr -> path_var.fwd_thd ^= path_ptr); 473 end; 474 path_ptr -> path_var.fwd_thd = current_path_ptr; 475 path_ptr = current_path_ptr; 476 end; 477 path_ptr -> path_var.fwd_thd = null; 478 return; 479 480 find_attributes: 481 proc (var_index, multiplier, cost, code); 482 483 484 /* DESCRIPTION: 485* 486* this routine gets a path_var structure for this tuple variable filled in. 487* This includes adding the list of conditions for this tuple variable 488* that can be satisfied at this point, depending on what tuple variables 489* preceed it in the search path generated so far */ 490 491 dcl multiplier float bin (63); /* times the current access cost will be incurred */ 492 493 dcl ( 494 base_variable_index, /* index of base var. */ 495 current_term, /* index to current term in and group */ 496 f_a_i, /* internal index */ 497 left_sub_tree_variable_index, /* left leaf var index */ 498 op_code, /* working op code */ 499 other_variable_index, /* index of other var. */ 500 right_sub_tree_variable_index, /* right leaf var index */ 501 var_index 502 ) fixed bin; /* Input: index of variable we are working with */ 503 504 dcl code fixed bin (35); /* internal status code */ 505 506 dcl cost float bin (63); /* internal cost */ 507 508 dcl ( 509 done, /* internal flag */ 510 found, /* internal flag */ 511 variable_index_in_and_group 512 ) bit (1); /* internal flag */ 513 514 dcl ( 515 base_variable_leaf_ptr init (null), /* to leaf of base var */ 516 other_variable_leaf_ptr init (null) 517 ) ptr; /* to leaf of other var */ 518 519 dcl sub_path_cost float bin (63); /* cost of the current path */ 520 521 dcl ops_array (5:10) fixed bin int static options (constant) 522 init (1, 2, 3, 5, 4, 6); 523 dcl rev_ops_array (6) fixed bin int static options (constant) 524 init (1, 2, 5, 6, 3, 4); 525 526 527 528 529 variable_index_in_and_group = "0"b; 530 531 if path_var_free_ptr = null then 532 allocate path_var in (select_area); /* Allocations in select_area are never freed. This area 533* is reinitd at the beginning of each new S. E.. */ 534 else do; 535 pvp = path_var_free_ptr; 536 path_var_free_ptr = path_var_free_ptr -> path_var.fwd_thd; 537 end; 538 539 path_var.alp, path_var.elp, path_var.fwd_thd = null; 540 path_var.var_index = var_index; 541 rmri_ptr = range.tup_var.ri_ptr (var_index); 542 543 call get_attr_list (rm_rel_info.num_attr, alp); 544 545 path_var.alp = alp; 546 do f_a_i = 1 to attr_list.nattr; 547 attr_list.info (f_a_i).cond_ptr = null; 548 attr_list.info.index = 0; 549 end; 550 551 current_term = 1; 552 done = "0"b; 553 do while (^done); /* look for all terms in var index */ 554 555 found = "0"b; 556 do f_a_i = current_term to and_group.num_terms while (^found); 557 pn_ptr = and_group.term_ptr (f_a_i); 558 left_sub_tree_variable_index = fixed (pred_node.id.lleaf_id.var_id); 559 right_sub_tree_variable_index = 560 fixed (pred_node.id.rleaf_id.var_id); 561 if left_sub_tree_variable_index = var_index then do; 562 /* if left leaf is in var index */ 563 base_variable_leaf_ptr = pred_node.lbr; 564 base_variable_index = left_sub_tree_variable_index; 565 op_code = ops_array (fixed (pred_node.id.op_code)); 566 other_variable_leaf_ptr = pred_node.rbr; 567 other_variable_index = right_sub_tree_variable_index; 568 found = "1"b; 569 end; 570 else if right_sub_tree_variable_index = var_index then do; 571 /* if right leaf in var. */ 572 base_variable_leaf_ptr = pred_node.rbr; 573 base_variable_index = right_sub_tree_variable_index; 574 op_code = 575 rev_ops_array (ops_array (fixed (pred_node.id.op_code))); 576 other_variable_leaf_ptr = pred_node.lbr; 577 other_variable_index = left_sub_tree_variable_index; 578 found = "1"b; 579 end; 580 end; 581 current_term = f_a_i; /* remember where to start again */ 582 if ^found then 583 done = "1"b; 584 585 else do; /* have term with leaf in var. */ 586 variable_index_in_and_group = "1"b; 587 if other_variable_index = base_variable_index then do; 588 /* ignore terms where both leaves insame var */ 589 if base_variable_leaf_ptr -> pred_leaf.expr_ptr ^= null then 590 /* if is expr in this var */ 591 call 592 add_to_expr_list (base_variable_leaf_ptr, 593 other_variable_leaf_ptr, op_code); 594 else if other_variable_leaf_ptr -> pred_leaf.expr_ptr ^= null 595 then do; 596 op_code = 597 rev_ops_array (ops_array (fixed (pred_node.id.op_code))); 598 /* changes < to >, */ 599 /* <= to =>, */ 600 /* => to =<, */ 601 /* > to < */ 602 call 603 add_to_expr_list (other_variable_leaf_ptr, 604 base_variable_leaf_ptr, op_code); 605 end; /* expr in right leaf */ 606 else call 607 add_to_attr_list (base_variable_leaf_ptr, 608 other_variable_leaf_ptr, op_code); /* if no expr leaves */ 609 end; 610 else if base_variable_leaf_ptr -> pred_leaf.expr_ptr ^= null then 611 /* if expr */ 612 call 613 add_to_expr_list (base_variable_leaf_ptr, 614 other_variable_leaf_ptr, op_code); 615 else call 616 add_to_attr_list (base_variable_leaf_ptr, 617 other_variable_leaf_ptr, op_code); 618 end; /* if have leaf in prime variable */ 619 end; /* looking for all terms in var index */ 620 621 622 /* for tuple variables not participating in this and_group 623* we use a path_var bit as an indicator. This will force calc_sub_path_cost 624* to use sequential access method for cost calcualtion, 625* as this is the method needed for the implied cross product */ 626 627 sub_path_cost = 0.0; 628 code = 0; 629 630 if ^variable_index_in_and_group then 631 path_var.in_and_group = "0"b; 632 else path_var.in_and_group = "1"b; 633 634 path_var.in_select_clause = range.tup_var.used (path_var.var_index); 635 636 call calc_sub_path_cost (multiplier, sub_path_cost, code); 637 cost = sub_path_cost; 638 639 return; 640 641 add_to_attr_list: 642 proc (bp, op, opc); 643 644 /* procedure to add term to attr. list */ 645 646 dcl ( 647 bp, /* base_variable_leaf_ptr */ 648 op, /* other_variable_leaf_ptr */ 649 savep init (null), 650 work_ptr init (null) 651 ) ptr; 652 653 dcl ptr_templ ptr based; 654 655 dcl (attr_ind, opc) fixed bin; /* op_code */ 656 657 dcl end_of_list bit (1); 658 659 work_ptr = current_path_ptr; 660 end_of_list = "0"b; 661 do while (^end_of_list); 662 if work_ptr = null then 663 end_of_list = "1"b; 664 else if work_ptr -> path_var.var_index = fixed (op -> pred_leaf.var_id) 665 then end_of_list = "1"b; 666 else work_ptr = work_ptr -> path_var.fwd_thd; 667 end; 668 669 if work_ptr ^= null | op -> pred_leaf.data_type = CONST 670 | bp -> pred_leaf.id.var_id = op -> pred_leaf.id.var_id then do; 671 attr_ind = fixed (bp -> pred_leaf.id.attr_id); 672 673 if attr_list.info.cond_ptr (attr_ind) = null then do; 674 /* if first cond. */ 675 savep = addr (attr_list.info.cond_ptr (attr_ind)); 676 attr_list.info.index (attr_ind) = attr_ind; 677 end; 678 else do; /* else find end of linked list */ 679 do condp = attr_list.info.cond_ptr (attr_ind) 680 repeat cond.fwd_thd while (cond.fwd_thd ^= null); 681 end; 682 savep = addr (cond.fwd_thd); 683 end; 684 685 if cond_free_ptr = null then /* get a condition structure */ 686 allocate cond in (select_area); /* Allocations in select_area are never freed. This area 687* is reinit at the beginning of each new S. E.. */ 688 else do; 689 condp = cond_free_ptr; 690 cond_free_ptr = cond_free_ptr -> cond.fwd_thd; 691 end; 692 693 savep -> ptr_templ = condp; /* set the values of the condition structure */ 694 cond.op_code = opc; 695 cond.pl_ptr = op; 696 cond.fwd_thd = null; 697 end; 698 699 end add_to_attr_list; 700 701 add_to_expr_list: 702 proc (bp, op, opc); 703 704 /* Procedure to add expr to expr list */ 705 706 dcl end_of_list bit (1); 707 dcl opc fixed bin; 708 dcl ( 709 bp, 710 op, 711 work_ptr init (null) 712 ) ptr; 713 714 end_of_list = "0"b; 715 work_ptr = current_path_ptr; 716 do while (^end_of_list); 717 if work_ptr = null then 718 end_of_list = "1"b; 719 else if work_ptr -> path_var.var_index 720 = fixed (op -> pred_leaf.id.var_id) then 721 end_of_list = "1"b; 722 else work_ptr = work_ptr -> path_var.fwd_thd; 723 end; 724 725 if work_ptr ^= null | op -> pred_leaf.data_type = CONST 726 | bp -> pred_leaf.id.var_id = op -> pred_leaf.id.var_id then do; 727 728 if path_var.elp = null then do; /* if first */ 729 el_nexprs_init = and_group.num_terms; 730 731 if expr_list_free_ptr = null then 732 allocate expr_list in (select_area); /* Allocations in select_area are never freed. It 733* is reinit at the beginning of each new S. E.. */ 734 else do; 735 elp = expr_list_free_ptr; 736 expr_list_free_ptr = 737 expr_list_free_ptr -> expr_list.info (1).epl_ptr; 738 end; 739 740 expr_list.nexprs = 0; 741 path_var.elp = elp; 742 end; 743 expr_list.nexprs = expr_list.nexprs + 1; 744 expr_list.info.epl_ptr (expr_list.nexprs) = bp; 745 expr_list.info.pl_ptr (expr_list.nexprs) = op; 746 expr_list.info.op_code (expr_list.nexprs) = opc; 747 end; 748 749 end add_to_expr_list; 750 751 end find_attributes; 752 753 calc_sub_path_cost: 754 proc (multiplier, cost, code); 755 756 /* DESCRIPTION: 757* 758* this routine computes the cost of accessing the current tuple variable, 759* in it's current position in the search path, thus taking into 760* account how the previous tuple variables will affect the useable access methods, 761* and the number of occurences of the access of this tuple variable 762* See the comments on the Cost Calculation Constants */ 763 764 765 var_index = path_var.var_index; 766 path_var.lk_key_ind = 0; /* unused */ 767 relation_size = rm_rel_info.current_tuple_population; 768 769 /* FORMULAS FOR NUMBER OF TUPLES SELECTED: 770* 771* L = T / (T - D) gives the number of tuples selected by a single index value. 772* where T = number of tuples in rel, D = is the number (or an estimate) of the 773* duplicate values of that index. 774* 775* Of course if L is the number selected by "=", 776* then (T - L) is the number selected by "^=". 777* 778* The number of tuples to bump that selected by an "=" condition 779* for the case of "<", ">=", etc conditions uses the formula 780* 781* L + (L / T) * (T - L) where L is the result of the above formula. 782* (T - L) is the number of values 783* not selected by an "=" condition, and (L/T) is the percentage 784* of the tuple selected by the "=" condition, so taking that percent 785* of the remaining tuples suffices to insure about twice as many selected for 786* a ">" condition etc. 787* Note that for L = T, ot L = 0, the result is 0 added tuples. 788* If T is 0, we don't have to worry about this formula. 789* 790* 791* For key head accesses, rather than indexed attributes, 792* we use the formula L = T ** (1 - (number_used_key_attrs / total_key_attrs)) 793* to approximate the selectivity of a key head search for the "=" condition. 794* 795* The other formulas remain the same. 796* 797* After computing selected tuples, we have to worry about how 798* additional conditions (comparisons) will reduce the tuples select. 799* This is done with the formula T / (C + 1), 800* where C is the cost of conditions remaining. 801**/ 802 803 /* go through all access methods useable on this tuple variable, 804* and compute the expected number of tuples selected and 805* the cost of each access method. then choose the access 806* method having the lowest cost for this tuple variable */ 807 808 if relation_size = 0 809 | (^path_var.in_select_clause & ^path_var.in_and_group) then do; 810 811 /* for empty relations avoid un-needed work, since 812* they always get a cost of 0. 813* 814* For T.V.'s not in the select clause 815* and not in this and group, 816* that will be dropped from consideration by permutations, 817* just fill in the bare essentials. */ 818 819 if rm_rel_info.ready_mode = RETRIEVE_ONLY then 820 path_var.access_method = UNORDERED_SEQUENTIAL; 821 else path_var.access_method = ORDERED_SEQUENTIAL; 822 path_var.second_cond_ptr, path_var.cond_ptr = null (); 823 path_var.attr_index = 0; 824 path_var.number_tuples_selected = relation_size; 825 cost, path_var.cost, access_method_cost = 0.0; 826 end; 827 else do; 828 do i = 1 to 6; /* init the costs */ 829 access_method (i).cost = INFINITY; 830 end; 831 832 /* get the number of conditions used against this tuple variable */ 833 834 call 835 count_conditions (tv_condition_count, tv_condition_cost, 836 tv_equal_condition, tv_not_equal_condition); 837 838 if path_var.in_and_group then do; /* force sequential for not in and group T.V. cost */ 839 840 /* CHECK ON TOTAL PRIMARY KEY OR LONG KEY HEAD POSSIBILITIES */ 841 842 call equal_key (total, equal_head, equal_fraction, equal_key_count); 843 844 if total then do; /* entire primary key useable */ 845 846 /* this access method needs the entire primary key attrs 847* to have at least one = condition specified against each. 848* It will uniquely select one tuple using a seek_key */ 849 850 access_method (1).code = TOTAL_PRIMARY_KEY; 851 access_method (1).condition_count = 852 tv_condition_count - equal_key_count; 853 access_method (1).conditions_cost = 854 tv_condition_cost 855 - (equal_key_count * CONDITION_COST_FACTOR (OTT_EQ)); 856 access_method (1).tuples_selected = 1; /* unique primary key => 1 tuple */ 857 access_method (1).cost = dbcb.access_costs.total_primary_key_cost; 858 end; 859 860 if equal_head then do; /* 1 or more key head attr useable */ 861 862 /* this case considers where a vfile select can be used 863* to do a seek_head on the primary key. It only works where 864* it needs at least one equal condition 865* on each key head attribute in order to work */ 866 867 /* we can make a bad estimate of the tuples selected 868* by a key head, using the linear relatioship: 869* rel_size * (1 - (key_head_attr_count / total_key_attr_count)) 870* An alternative formula that that works better for the fraction close to 1 is 871* rel_size ** (1 - key_head_attr_count / total_key_attr_count), 872* but both apply only to the case with the condition "=", 873* in general more tuples are selected by ">", etc. 874* and the tuples selected must be increased for that case. */ 875 876 access_method (2).code = LONG_KEY_HEAD; 877 access_method (2).condition_count = 878 tv_condition_count - equal_key_count; 879 access_method (2).conditions_cost = 880 tv_condition_cost 881 - (equal_key_count * CONDITION_COST_FACTOR (OTT_EQ)); 882 access_method (2).tuples_selected = 883 relation_size ** (1 - equal_fraction); 884 tuples_selected_temp = 885 access_method (2).tuples_selected 886 / (access_method (2).conditions_cost + 1); 887 access_method (2).tuples_selected = ceil (tuples_selected_temp); 888 access_method (2).cost = 889 (dbcb.access_costs.access_cost * access_method (2).tuples_selected) 890 + dbcb.access_costs.access_overhead; 891 end; 892 893 /* CHECK ON SHORT KEY HEAD AND INDEXED ATTR POSSIBILITIES */ 894 895 call 896 short_key (short_head, short_fraction, indexed_attr, 897 key_head_condition_cost, key_head_not_equal_condition, 898 key_head_range, key_head_attr_id, key_head_cond_ptr, 899 key_head_2nd_cond_ptr, indexed_attr_condition_cost, 900 index_attr_equal_condition, index_attr_not_equal_condition, 901 index_attr_range, index_attr_id, index_attr_cond_ptr, 902 index_attr_2nd_cond_ptr, index_attr_number_of_dups); 903 904 if short_head then do; /* the 1st key attr useable as head with other than "=" */ 905 906 /* for the first attribute of a primary key, we can use 907* vfile select, looking for a key head value. 908* The previous method already handled "=" conditions, 909* so now we look at all the other conditions, >, <, ^=, etc. */ 910 911 access_method (3).code = SHORT_KEY_HEAD; 912 access_method (3).condition_count = 913 tv_condition_count - 1 - fixed (key_head_range); 914 /* only one condition used for access unless range */ 915 access_method (3).conditions_cost = 916 tv_condition_cost - key_head_condition_cost; 917 if key_head_not_equal_condition then do; 918 if short_fraction = 1.0 then 919 access_method (3).tuples_selected = relation_size - 1; 920 else access_method (3).tuples_selected = 921 relation_size 922 - (relation_size ** (1 - short_fraction)); 923 /* "^=" => T - L */ 924 end; 925 else do; /* other than "=" or "^=" condition */ 926 if short_fraction = 1.0 then 927 access_method (3).tuples_selected = 1; 928 else access_method (3).tuples_selected = 929 relation_size ** (1 - short_fraction); 930 access_method (3).tuples_selected = 931 access_method (3).tuples_selected 932 + (access_method (3).tuples_selected / relation_size) 933 * (relation_size - access_method (3).tuples_selected); 934 /* ">", etc. 935* => L + ((L/T) * (T - L)) */ 936 end; 937 tuples_selected_temp = 938 access_method (3).tuples_selected 939 / (access_method (3).conditions_cost + 1); 940 access_method (3).tuples_selected = ceil (tuples_selected_temp); 941 access_method (3).cost = 942 (dbcb.access_costs.access_cost * access_method (3).tuples_selected) 943 + dbcb.access_costs.access_overhead; 944 end; 945 946 if indexed_attr then do; 947 948 /* 949* A secondary index is available for access. We can estimate the 950* tuples selected as rel_size / unique_index_values. for the case 951* where the condition is "=". The "=" if present is forced as the 952* access indexed attr if more than one index or condition is 953* present. For other than "=", the index selectivity must be 954* changed, to show more tuples selected than for an = condition. 955**/ 956 957 relation_index_selectivity = 958 relation_size / (relation_size - index_attr_number_of_dups); 959 GT_LT_SELECTED_TUPLES = 960 relation_index_selectivity 961 + ((relation_index_selectivity / relation_size) 962 * (relation_size - relation_index_selectivity)); 963 964 NE_SELECTED_TUPLES = relation_size - relation_index_selectivity; 965 966 access_method (4).code = INDEXED_ATTR; 967 access_method (4).condition_count = 968 tv_condition_count - 1 - fixed (index_attr_range); 969 /* only one condition being used for access unless range */ 970 access_method (4).conditions_cost = 971 tv_condition_cost - indexed_attr_condition_cost; 972 if index_attr_not_equal_condition then 973 access_method (4).tuples_selected = NE_SELECTED_TUPLES; 974 /* ^= => T - L */ 975 else do; 976 access_method (4).tuples_selected = 977 relation_index_selectivity; /* "=" => L */ 978 if ^index_attr_equal_condition then 979 access_method (4).tuples_selected = 980 GT_LT_SELECTED_TUPLES; /* ">", etc. => L + (L/T)*(T-L) */ 981 end; 982 tuples_selected_temp = 983 access_method (4).tuples_selected 984 / (access_method (4).conditions_cost + 1); 985 access_method (4).tuples_selected = ceil (tuples_selected_temp); 986 access_method (4).cost = 987 (dbcb.access_costs.access_cost * access_method (4).tuples_selected) 988 + dbcb.access_costs.access_overhead; 989 end; 990 end; 991 992 993 /* for sequential retrievals, the number of tuples that actually 994* statisfy the query will depend on the number of conditions specified, 995* the greater number of conditions usually meaning fewer tuples retrieved. 996* The number of conditions is factored in using the formula: 997* relation_size / (condition_count + 1) 998* an alternative formula considered was: 999* (0.9 ** condition_count) * relation_size */ 1000 1001 access_method (5).code = UNORDERED_SEQUENTIAL; 1002 access_method (5).condition_count = tv_condition_count; 1003 access_method (5).conditions_cost = tv_condition_cost; 1004 tuples_selected_temp = relation_size / (tv_condition_cost + 1); 1005 access_method (5).tuples_selected = ceil (tuples_selected_temp); 1006 access_method (5).cost = 1007 dbcb.access_costs.us_access_cost * relation_size; 1008 1009 /* now that all access methods have had their relative costs evaluated, 1010* chose the lowest cost access method for this tuple variable */ 1011 1012 lowest_cost = INFINITY; 1013 lowest_cost_index = 0; 1014 do i = 1 to 6; 1015 if lowest_cost > access_method (i).cost then do; /* found a lower cost */ 1016 lowest_cost = access_method (i).cost; 1017 lowest_cost_index = i; 1018 end; 1019 end; 1020 1021 if lowest_cost_index = 0 then do; /* we screwed up */ 1022 code = mrds_error_$rst_logic_error; 1023 access_method_cost = 1; /* dummy values for error */ 1024 path_var.access_method = UNORDERED_SEQUENTIAL; 1025 path_var.number_tuples_selected = 0; 1026 end; 1027 else do; 1028 code = 0; 1029 path_var.access_method = access_method (lowest_cost_index).code; 1030 path_var.number_tuples_selected = 1031 access_method (lowest_cost_index).tuples_selected; 1032 access_method_cost = access_method (lowest_cost_index).cost; 1033 end; 1034 1035 1036 /* point to condition and attribute to be used for access method */ 1037 1038 if path_var.access_method ^= TOTAL_PRIMARY_KEY 1039 & path_var.access_method ^= LONG_KEY_HEAD then do; 1040 1041 /* reset attrs/conditions selected by equal key */ 1042 1043 do i = 1 to rm_rel_info.nkey_attr; 1044 1045 j = rm_rel_info.key_attr_ptrs (i) -> rm_attr_info.defn_order; 1046 1047 attr_list.info.attr_selected (j) = "0"b; 1048 1049 do condp = attr_list.info.cond_ptr (j) repeat cond.fwd_thd 1050 while (condp ^= null ()); 1051 cond.condition_selected = "0"b; 1052 end; 1053 1054 end; 1055 1056 end; 1057 1058 /* for a long = key head, remember the number of key head attrs used. 1059* for indexed attr or short key head, remember the condition used 1060* and the attribute on which that condition appeared. 1061* Set the appriopriate bits in the condition and attr_list strucutres 1062* so that gen_srch_prog will know what to do. */ 1063 1064 if path_var.access_method = LONG_KEY_HEAD 1065 | path_var.access_method = TOTAL_PRIMARY_KEY then do; 1066 path_var.second_cond_ptr, path_var.cond_ptr = null (); 1067 path_var.attr_index = equal_key_count; /* use to save length of key head */ 1068 end; 1069 else if path_var.access_method = INDEXED_ATTR then do; 1070 path_var.cond_ptr = index_attr_cond_ptr; 1071 path_var.second_cond_ptr = index_attr_2nd_cond_ptr; 1072 path_var.attr_index = index_attr_id; 1073 1074 path_var.cond_ptr -> cond.condition_selected = "1"b; 1075 if path_var.second_cond_ptr ^= null () then 1076 path_var.second_cond_ptr -> cond.condition_selected = "1"b; 1077 path_var.alp -> attr_list.info.attr_selected (path_var.attr_index) = 1078 "1"b; 1079 end; 1080 else if path_var.access_method = SHORT_KEY_HEAD then do; 1081 path_var.cond_ptr = key_head_cond_ptr; 1082 path_var.second_cond_ptr = key_head_2nd_cond_ptr; 1083 path_var.attr_index = key_head_attr_id; 1084 1085 path_var.cond_ptr -> cond.condition_selected = "1"b; 1086 if path_var.second_cond_ptr ^= null () then 1087 path_var.second_cond_ptr -> cond.condition_selected = "1"b; 1088 path_var.alp -> attr_list.info.attr_selected (path_var.attr_index) = 1089 "1"b; 1090 end; 1091 else do; 1092 path_var.second_cond_ptr, path_var.cond_ptr = null (); 1093 path_var.attr_index = 0; 1094 end; 1095 1096 1097 1098 /* the new cost will be the old cost, plus 1099* the times this current access method cost will be incurred 1100* The addition to the cost so far, is done outside this routine 1101* as is the multiplication of the new number of tuples selected. 1102* The overall formula is cost = cost + (previously_selected * access_cost) */ 1103 1104 path_var.cost, cost = (multiplier * access_method_cost); 1105 1106 end; 1107 1108 /* optional debug display */ 1109 1110 if display_access_method_costs then do; 1111 1112 call ioa_ ("^3/RELATION STATISTICS"); 1113 call 1114 ioa_ ("^-Tuple variable: ^a^/^-In and group: ^[yes^;no^]", 1115 range.tup_var (path_var.var_index).name, path_var.in_and_group); 1116 call 1117 ioa_ ("^-In select clause: ^[yes^;no^]", path_var.in_select_clause) 1118 ; 1119 call 1120 ioa_ ("^-Relation size: ^d^/", relation_size); 1121 1122 if relation_size ^= 0 1123 & (path_var.in_select_clause | path_var.in_and_group) then do; 1124 1125 call ioa_ ("^/ACCESS METHOD COST ARRAY"); 1126 1127 do i = 1 to 6; 1128 1129 call ioa_ ("^/^a", access_method_name (i)); 1130 if access_method (i).cost = INFINITY then 1131 call ioa_ ("^-This method not useable."); 1132 else do; 1133 call 1134 ioa_ ( 1135 "^-Access method cost: ^f^/^-Tuples selected: ^d^/^-Conditions: ^d" 1136 , access_method (i).cost, 1137 access_method (i).tuples_selected, 1138 access_method (i).condition_count); 1139 call 1140 ioa_ ("^-Conditions cost: ^f", 1141 access_method (i).conditions_cost); 1142 end; 1143 1144 end; 1145 end; 1146 1147 call ioa_ ("^/ACCESS METHOD CHOSEN^/"); 1148 1149 call ioa_ ("^a", access_method_name (path_var.access_method)); 1150 call 1151 ioa_ ("^-Computed cost: ^f^/^-Multiplier: ^f", path_var.cost, 1152 multiplier); 1153 if path_var.access_method = TOTAL_PRIMARY_KEY 1154 | path_var.access_method = LONG_KEY_HEAD then 1155 call ioa_ ("^-Equal key attrs used: ^d", path_var.attr_index); 1156 else if path_var.access_method = SHORT_KEY_HEAD 1157 | path_var.access_method = INDEXED_ATTR then do; 1158 if path_var.second_cond_ptr = null () then 1159 call 1160 ioa_ ("^-Condition used: ^a", 1161 condition_array (path_var.cond_ptr -> cond.op_code)); 1162 else call 1163 ioa_ ("^-Conditions used: ^a & ^a", 1164 condition_array (path_var.cond_ptr -> cond.op_code), 1165 condition_array (path_var.second_cond_ptr -> cond.op_code)); 1166 call 1167 ioa_ ("^-Attribute used: ^a", 1168 rm_rel_info.attr_ptrs (path_var.attr_index) -> rm_attr_info.name) 1169 ; 1170 end; 1171 1172 call ioa_ ("^/SEARCH PATH SO FAR USING THIS TUPLE VARIABLE"); 1173 call 1174 ioa_ ("^-Cost of path at this point: ^f", 1175 current_path_cost + path_var.cost); 1176 1177 do temp_path_ptr = current_path_ptr 1178 repeat temp_path_ptr -> path_var.fwd_thd 1179 while (temp_path_ptr ^= null ()); 1180 1181 call 1182 ioa_ ("^-Tuple variable: ^a", 1183 range.tup_var.name (temp_path_ptr -> path_var.var_index)); 1184 1185 end; 1186 1187 call 1188 ioa_ ("^-Tuple variable: ^a^/", 1189 range.tup_var.name (path_var.var_index)); 1190 1191 end; 1192 1193 return; 1194 1195 1196 1197 dcl var_index fixed bin; 1198 1199 dcl tuples_selected_temp float bin (63); /* temp to allow ceil operation */ 1200 dcl index_attr_range bit (1); /* on => range of values available for key access */ 1201 dcl key_head_range bit (1); /* on => range of values available for key access */ 1202 dcl key_head_2nd_cond_ptr ptr; /* to second condition in range */ 1203 dcl index_attr_2nd_cond_ptr ptr; /* to second condition in range */ 1204 dcl GT_LT_SELECTED_TUPLES float bin (27); /* number of tuples to bump select$ed for other than "=" */ 1205 dcl NE_SELECTED_TUPLES float bin (27); /* number of tuples to bump selected for "^=" */ 1206 dcl key_head_condition_cost float bin (27); /* cost of condition against short key head */ 1207 dcl key_head_not_equal_condition bit (1); /* on => "^=" against short key head used */ 1208 dcl key_head_cond_ptr ptr; /* pointer to condition used for short key head */ 1209 dcl key_head_attr_id fixed bin; /* index of attr for short key head usage */ 1210 dcl indexed_attr_condition_cost float bin (27); /* cost of condition against indexed attr used */ 1211 dcl index_attr_equal_condition bit (1); /* on => "=" condition agsint indexed attr */ 1212 dcl index_attr_not_equal_condition bit (1); /* on => "^=" condition used against indexed attr */ 1213 dcl index_attr_number_of_dups fixed bin (35); /* number of duplicates in the selected index */ 1214 dcl index_attr_id fixed bin; /* index of attribute used by secondary index method */ 1215 dcl index_attr_cond_ptr ptr; /* to condtion for used index attr */ 1216 dcl relation_index_selectivity float bin (27);/* number of tuples selected by an "=" 1217* on an index value, for 1 index attr */ 1218 dcl temp_path_ptr ptr; /* used for displaying current search path */ 1219 dcl equal_key_count fixed bin; /* number of key attributes involved */ 1220 dcl tv_condition_count fixed bin; /* number of conditions/expressions against this T.V. */ 1221 dcl tv_condition_cost float bin (27); /* const of conditions against this T.V. */ 1222 dcl tv_equal_condition bit (1); /* on => = condition appears against T.V. */ 1223 dcl tv_not_equal_condition bit (1); /* on => "^=" condition appears agsinst this T.V. */ 1224 dcl (i, j) fixed bin; /* loop index */ 1225 dcl lowest_cost float bin (63); /* temp for saving lowest cost seen so far */ 1226 dcl lowest_cost_index fixed bin; /* access method array index for lowest cost */ 1227 dcl mrds_error_$rst_logic_error fixed bin (35) ext; /* program in error */ 1228 dcl total bit (1); /* on => entire primary key useable */ 1229 dcl equal_head bit (1); /* on => key equal_head useable */ 1230 dcl short_head bit (1); /* on => key short_head useable */ 1231 dcl indexed_attr bit (1); /* on => a indexed attribute can be used for access */ 1232 dcl (equal_fraction, short_fraction) float bin (27); /* percentage of total key useable in hey head */ 1233 dcl multiplier float bin (63); /* number of times this access cost will be incurred */ 1234 dcl access_method_cost float bin (27); /* cost of using this access method */ 1235 dcl cost float bin (63); /* cost of path so far */ 1236 1237 /* the array slots are used as follows: 1238* 1 => total primary key 1239* 2 => long key head 1240* 3 => short key head 1241* 4 => secondary index 1242* 5 => unordered sequential 1243* 6 => ordered sequential */ 1244 1245 dcl 1 access_method dimension (1:6), /* array for saving costs, tuples selected */ 1246 2 code fixed bin, /* encoding for the access method */ 1247 2 tuples_selected fixed bin (35), /* expected number of tuples that this method will return */ 1248 2 cost float bin (63), /* cost of this access method */ 1249 2 condition_count fixed bin, /* number of conditions involved */ 1250 2 conditions_cost float bin (27); /* cost of conditions against this T.V. */ 1251 1252 dcl RETRIEVE_ONLY fixed bin init (5) int static options (constant); 1253 /* scope retrieve ready mode */ 1254 1255 dcl INFINITY init (10e37) float bin (63) int static options (constant); 1256 1257 dcl (code, relation_size) fixed bin (35); 1258 1259 equal_key: 1260 proc (total_primary_key, equal_key_head, useable_key_fraction, 1261 useable_key_attrs); 1262 1263 1264 /* Procedure to determine if a unique index is useable */ 1265 1266 /* DESCRIPTION: 1267* 1268* the total_primary_key and useable_key_fraction will be set 1269* if the tuple variable can be accessed by unique primary key value 1270* 1271* the equal_key_head and useable_key_fraction will be set if 1272* the tuple variable can be accessed by a key head 1273* using 1 or more key head attributes using = conditions 1274* 1275* To qualify for total key or long key head, 1276* there must be the total key or long key head in the users view 1277* of this tuple variables relation. 1278* 1279* The conditions must involved only constants, or references to other 1280* tuples variables that have already appeared in the search path, 1281* and thus have thier values available. 1282* 1283* The longest possible key head for an N attr key is N-1. */ 1284 1285 1286 u_i_i = 0; 1287 total_primary_key, equal_key_head, useable = "0"b; 1288 useable_key_fraction = 0.0; 1289 if rm_rel_info.nkey_attr = rm_rel_info.model_nkey_attr then do; 1290 /* if not a partial key sub_model */ 1291 useable = "1"b; 1292 u_i_i = 1; 1293 done = "0"b; 1294 do while (^done); 1295 rai_ptr = rm_rel_info.key_attr_ptrs (u_i_i); 1296 if attr_list.info.cond_ptr (rm_attr_info.defn_order) = null then 1297 useable = "0"b; /* attr not referenced by a condition */ 1298 else do; /* attr referenced */ 1299 1300 1301 /* look for a useable "=" condition on this attribute in the primary key */ 1302 1303 equal_found = "0"b; 1304 do condp = attr_list.info.cond_ptr (rm_attr_info.defn_order) 1305 repeat cond.fwd_thd while (condp ^= null () & ^equal_found); 1306 /* look for an "=" condpition */ 1307 if cond.op_code = OTT_EQ then do; /* only if equality */ 1308 pl_ptr = cond.pl_ptr; 1309 if fixed (pred_leaf.id.var_id) = var_index then 1310 useable = "0"b; 1311 if useable then do; /* if good so far, check for problems */ 1312 if pred_leaf.data_type ^= CONST then do; 1313 end_of_list = "0"b; 1314 work_ptr = current_path_ptr; 1315 do while (^end_of_list); 1316 if work_ptr = null then 1317 end_of_list = "1"b; 1318 else if work_ptr -> path_var.var_index 1319 = fixed (pred_leaf.id.var_id) then 1320 end_of_list = "1"b; 1321 else work_ptr = work_ptr -> path_var.fwd_thd; 1322 end; 1323 if work_ptr = null then 1324 useable = "0"b; 1325 end; 1326 if useable then do; 1327 equal_found = "1"b; /* still useable => good "=" condition */ 1328 cond.condition_selected = "1"b; /* remember which condition used */ 1329 attr_list.info 1330 .attr_selected (rm_attr_info.defn_order) = "1"b; 1331 /* remember attr used */ 1332 end; 1333 end; 1334 end; 1335 end; 1336 if ^equal_found then 1337 useable = "0"b; /* can only use it if had an "=" condition */ 1338 end; /* if refer. */ 1339 if useable then do; 1340 if u_i_i < rm_rel_info.nkey_attr then 1341 u_i_i = u_i_i + 1; 1342 else done = "1"b; 1343 end; 1344 else do; 1345 done = "1"b; 1346 u_i_i = u_i_i - 1; /* back up to last useable key attr */ 1347 end; 1348 end; /* loop thru key attr */ 1349 1350 end; /* not partial key sub_model */ 1351 1352 useable_key_attrs = u_i_i; 1353 1354 if useable then do; 1355 total_primary_key = "1"b; 1356 useable_key_fraction = 1.0; 1357 end; 1358 1359 if ^useable & /* not total key available */ 1360 u_i_i >= 1 & u_i_i < rm_rel_info.nkey_attr then do; /* >= 1 key head attrs useable */ 1361 equal_key_head = "1"b; 1362 useable_key_fraction = u_i_i / rm_rel_info.nkey_attr; 1363 /* ranges from 1/N to N-1/N */ 1364 end; 1365 1366 1367 dcl u_i_i fixed bin; 1368 1369 dcl (end_of_list, useable) bit (1); 1370 1371 dcl work_ptr ptr init (null); 1372 1373 dcl equal_found bit (1); /* on => a good "=" condition found against this key attr */ 1374 dcl total_primary_key bit (1); /* on => can use entire primary key as unique index */ 1375 dcl equal_key_head bit (1); /* on => can use 1 or more attrs of key head with "=" */ 1376 dcl useable_key_fraction float bin (27); /* percent of key attrs useable as key head */ 1377 dcl done bit (1); /* on => exit key attr loop */ 1378 dcl useable_key_attrs fixed bin; /* number of key attributes involved */ 1379 1380 end equal_key; 1381 1382 short_key: 1383 proc (key_head, useable_key_fraction, secondary_index, 1384 key_head_condition_cost, key_head_not_equal_condition, key_head_range, 1385 key_head_attr_id, key_head_cond_ptr, key_head_2nd_cond_ptr, 1386 index_attr_condition_cost, index_equal_condition, 1387 index_not_equal_condition, index_attr_range, index_attr_id, 1388 index_attr_cond_ptr, index_attr_2nd_cond_ptr, index_attr_number_of_dups); 1389 1390 1391 /* Procedure to check to see if secondary indexed or key heads are referenced */ 1392 1393 /* DESCRIPTION: 1394* 1395* if the tuple variable can be access by key head, using other than an = condition 1396* then the key_head bit is set, as well as the useable_key_fraction 1397* 1398* if the tuple variable can be accessed by secondary index, 1399* then the secondary_index bit is set 1400* 1401* if neither is possible, then neither bit is set */ 1402 1403 1404 key_head_attr_id, index_attr_id = 0; 1405 key_head_2nd_cond_ptr, key_head_cond_ptr, index_attr_2nd_cond_ptr, 1406 index_attr_cond_ptr = null (); 1407 key_head_not_equal_condition, index_equal_condition, 1408 index_not_equal_condition, key_head_range, key_head, index_attr_range, 1409 useable = "0"b; /* init */ 1410 /* Determine if there is a condition 1411* on the first attribute of the primary key. This will make 1412* a key head. */ 1413 1414 /* a key head on the first key attribute is useable as an access 1415* method for this tuple variable under the following circumstances: 1416* 1) the first key order attribute has at least one condition on it 1417* 2) the condition involves constants, or a value from a tuple 1418* variable that has appeared previously in the search path */ 1419 1420 key_head_condition_cost = 0.0; 1421 i_r_i = 0; 1422 do i_r_j = 1 to rm_rel_info.nkey_attr; 1423 rai_ptr = rm_rel_info.key_attr_ptrs (i_r_j); /* find the key head */ 1424 if rm_attr_info.key_order = 1 then do; 1425 i_r_i = i_r_j; 1426 i_r_j = rm_rel_info.nkey_attr + 1; 1427 end; 1428 end; 1429 if i_r_i ^= 0 then do; /* if key head found */ 1430 rai_ptr = rm_rel_info.key_attr_ptrs (i_r_i); 1431 if attr_list.info.cond_ptr (rm_attr_info.defn_order) ^= null () 1432 then do; 1433 1434 1435 /* look through all conditions on the single key head attr 1436* until a usable one is found, and remember it. 1437* Continue looking for usable conditions until the lowest cost one is found */ 1438 1439 do condp = attr_list.info.cond_ptr (rm_attr_info.defn_order) 1440 repeat cond.fwd_thd while (condp ^= null); 1441 pl_ptr = cond.pl_ptr; 1442 condition_used = "0"b; 1443 if cond.op_code ^= OTT_EQ then do; /* "=" handled by equal_key */ 1444 1445 if pred_leaf.data_type = CONST then 1446 condition_used, useable = "1"b; 1447 else do; 1448 end_of_list = "0"b; 1449 work_ptr = current_path_ptr; 1450 do while (^end_of_list); 1451 if work_ptr = null then 1452 end_of_list = "1"b; 1453 else if work_ptr -> path_var.var_index 1454 = fixed (pred_leaf.id.var_id) then 1455 end_of_list = "1"b; 1456 else work_ptr = work_ptr -> path_var.fwd_thd; 1457 end; 1458 if work_ptr ^= null then 1459 condition_used, useable = "1"b; 1460 end; 1461 end; 1462 if condition_used then do; 1463 key_head_condition_cost = 1464 max (key_head_condition_cost, 1465 CONDITION_COST_FACTOR (cond.op_code)); 1466 if key_head_cond_ptr = null () then do; 1467 key_head_attr_id = rm_attr_info.defn_order; 1468 /* save first condition found */ 1469 key_head_cond_ptr = condp; 1470 end; 1471 else if key_head_cond_ptr -> cond.op_code ^= OTT_EQ then do; 1472 if cond.op_code ^= OTT_NE & ^key_head_range then do; 1473 1474 1475 /* favor a range condition over just a >, >=, etc */ 1476 1477 if key_head_cond_ptr ^= null () then do; 1478 if ((key_head_cond_ptr -> cond.op_code = OTT_LT 1479 | key_head_cond_ptr -> cond.op_code = OTT_LE) 1480 & (cond.op_code = OTT_GT | cond.op_code = OTT_GE)) 1481 | 1482 ((key_head_cond_ptr -> cond.op_code = OTT_GT 1483 | key_head_cond_ptr -> cond.op_code = OTT_GE) 1484 & (cond.op_code = OTT_LT | cond.op_code = OTT_LE)) 1485 then do; 1486 key_head_range = "1"b; 1487 key_head_2nd_cond_ptr = condp; 1488 end; 1489 end; 1490 if ^key_head_range 1491 & key_head_cond_ptr -> cond.op_code = OTT_NE then do; 1492 key_head_attr_id = rm_attr_info.defn_order; 1493 /* favor <, >, <=, >= 1494* over ^= condition, as = will not occur */ 1495 key_head_cond_ptr = condp; 1496 end; 1497 end; 1498 end; 1499 end; 1500 end; 1501 end; 1502 end; 1503 if useable then do; 1504 key_head = "1"b; 1505 if key_head_cond_ptr -> cond.op_code = OTT_NE then 1506 key_head_not_equal_condition = "1"b; 1507 useable_key_fraction = 1 / rm_rel_info.nkey_attr; /* ranges from 1.0 to 1/N */ 1508 end; 1509 1510 /* a secondary index access method can be used under the following circumstances: 1511* 1) for this tuple variable, we have a secondary indexed attr with at least 1512* one condition specified against it 1513* 2) that condition references either a constant, or a tuple variable 1514* that precedes this one in the current path */ 1515 1516 1517 secondary_index, useable = "0"b; /* init */ 1518 index_attr_condition_cost = 0.0; 1519 if rm_rel_info.indexed then do; /* if exists sec. ind. */ 1520 do i_r_i = 1 to rm_rel_info.num_attr; 1521 rai_ptr = rm_rel_info.attr_ptrs (i_r_i); 1522 if rm_attr_info.index_attr then do;/* if indexed */ 1523 1524 1525 /* 1526* look through all conditions on this attribute, find the one which 1527* will select the fewest number of tuples. Relational operator 1528* precedence is equal, range, in-equality, not-equal. Within each 1529* class the index with the fewest duplicate values will be chosen. 1530**/ 1531 1532 do condp = attr_list.cond_ptr (rm_attr_info.defn_order) 1533 repeat cond.fwd_thd while (condp ^= null); 1534 pl_ptr = cond.pl_ptr; 1535 condition_used = "0"b; 1536 if pred_leaf.data_type = CONST then 1537 condition_used, useable = "1"b; 1538 else do; 1539 end_of_list = "0"b; 1540 work_ptr = current_path_ptr; 1541 do while (^end_of_list); 1542 if work_ptr = null then 1543 end_of_list = "1"b; 1544 else if work_ptr -> path_var.var_index 1545 = fixed (pred_leaf.id.var_id) then 1546 end_of_list = "1"b; 1547 else work_ptr = work_ptr -> path_var.fwd_thd; 1548 end; 1549 if work_ptr ^= null then 1550 condition_used, useable = "1"b; 1551 end; 1552 if condition_used then do; 1553 index_attr_condition_cost = 1554 max (index_attr_condition_cost, 1555 CONDITION_COST_FACTOR (cond.op_code)); 1556 if index_attr_cond_ptr = null () then do; 1557 /* save 1st condition seen */ 1558 index_attr_id = rm_attr_info.defn_order; 1559 index_attr_cond_ptr = condp; 1560 index_attr_number_of_dups = rm_attr_info.number_of_dups; 1561 index_attr_range = "0"b; 1562 index_attr_2nd_cond_ptr = null (); 1563 end; 1564 else do; 1565 condition_completes_range = "0"b; 1566 if index_attr_cond_ptr ^= null () & 1567 index_attr_id = rm_attr_info.defn_order 1568 then do; 1569 if ((index_attr_cond_ptr -> cond.op_code = OTT_LT 1570 | index_attr_cond_ptr -> cond.op_code = OTT_LE) 1571 & (cond.op_code = OTT_GT | 1572 cond.op_code = OTT_GE)) 1573 | 1574 ((index_attr_cond_ptr -> cond.op_code = OTT_GT 1575 | index_attr_cond_ptr -> cond.op_code = OTT_GE) 1576 & (cond.op_code = OTT_LT | 1577 cond.op_code = OTT_LE)) 1578 then condition_completes_range = "1"b; 1579 end; 1580 call find_index_attr; 1581 1582 end; 1583 end; 1584 end; 1585 end; 1586 end; /* loop thru attr */ 1587 end; /* if sec. ind. exist */ 1588 if useable then do; 1589 secondary_index = "1"b; 1590 if index_attr_cond_ptr -> cond.op_code = OTT_EQ then 1591 index_equal_condition = "1"b; 1592 else if index_attr_cond_ptr -> cond.op_code = OTT_NE then 1593 index_not_equal_condition = "1"b; 1594 end; 1595 1596 1597 dcl (end_of_list, useable) bit (1); 1598 1599 dcl (i_r_i, i_r_j) fixed bin; 1600 1601 dcl work_ptr ptr init (null); 1602 dcl key_head_range bit (1); /* on => exists range of values on the key head attr */ 1603 dcl key_head_2nd_cond_ptr ptr; /* to second in range of values for key head range */ 1604 dcl index_attr_range bit (1); /* on => attr chosen for selection has a range */ 1605 dcl index_attr_2nd_cond_ptr ptr; /* to second value in a range condition */ 1606 dcl condition_used bit (1); /* on => this key_head/index_attr 1607* useable for this attr/condtions */ 1608 dcl condition_completes_range bit (1); /* on => exists a range of values on an indexed attr */ 1609 dcl index_attr_id fixed bin; /* index into attr_ptr array for chosen condition */ 1610 dcl index_attr_cond_ptr ptr; /* pointer to chosen condition for index */ 1611 dcl index_attr_number_of_dups fixed bin (35); /* number of dups on index chosen for selection */ 1612 dcl key_head_attr_id fixed bin; /* index into attr_ptr array |for key head attr */ 1613 dcl key_head_cond_ptr ptr; /* pointer to chosen condition for key head */ 1614 dcl key_head_not_equal_condition bit (1); /* on => "^=" appeared as condition on key head */ 1615 dcl index_equal_condition bit (1); /* on => "=" condition on indexed attr */ 1616 dcl index_not_equal_condition bit (1); /* on => "^=" on indexed attr */ 1617 dcl key_head bit (1); /* on => first key attr useable as head */ 1618 dcl secondary_index bit (1); /* on => some secondarily indexed attr useable */ 1619 dcl useable_key_fraction float bin (27); /* percentage of key attrs useable as key head */ 1620 dcl key_head_condition_cost float bin (27); /* cost of conditions on key head attr */ 1621 dcl index_attr_condition_cost float bin (27); /* cost of conditions on indexed attribute */ 1622 1623 find_index_attr: proc; /* all parameters are global, local vars start with fia_ */ 1624 1625 dcl fia_current_cond fixed bin; /* code for current condition on attribute */ 1626 dcl fia_select_cond fixed bin; /* code for condition that will be used to select 1627* a tuple unless a better condition is found */ 1628 dcl fia_COMPARE_SELECTION_TO_CURRENT (4, 4) fixed bin internal static init 1629 (1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15, 4, 8, 12, 16); 1630 /* values of array are used to decide which 1631* condition should be used to select the relation */ 1632 1633 if condition_completes_range 1634 then fia_current_cond = 4; 1635 else do; 1636 if condp -> cond.op_code > 3 1637 then fia_current_cond = 3; 1638 else fia_current_cond = condp -> cond.op_code; 1639 end; 1640 1641 if index_attr_range 1642 then fia_select_cond = 4; 1643 else do; 1644 if index_attr_cond_ptr -> cond.op_code > 3 1645 then fia_select_cond = 3; 1646 else fia_select_cond = index_attr_cond_ptr -> cond.op_code; 1647 end; 1648 1649 goto fia_do_something (fia_COMPARE_SELECTION_TO_CURRENT (fia_select_cond, fia_current_cond)); 1650 1651 1652 fia_do_something (1): /* both conditions are = */ 1653 fia_do_something (6): /* both conditions are ^= */ 1654 fia_do_something (11): /* both conditions are an inequality */ 1655 if index_attr_number_of_dups > rm_attr_info.number_of_dups 1656 then do; 1657 index_attr_cond_ptr = condp; 1658 index_attr_number_of_dups = rm_attr_info.number_of_dups; 1659 index_attr_id = rm_attr_info.defn_order; 1660 index_attr_range = "0"b; 1661 index_attr_2nd_cond_ptr = null (); 1662 end; 1663 goto exit_find_index_attr; 1664 1665 fia_do_something (2): /* select cond ^=, current cond = */ 1666 fia_do_something (3): /* select cond is an inequality, current cond is = */ 1667 fia_do_something (4): /* select cond is a range, current cond is = */ 1668 fia_do_something (10): /* select cond is ^=, current cond is an inequality */ 1669 index_attr_cond_ptr = condp; 1670 index_attr_number_of_dups = rm_attr_info.number_of_dups; 1671 index_attr_id = rm_attr_info.defn_order; 1672 index_attr_range = "0"b; 1673 index_attr_2nd_cond_ptr = null (); 1674 goto exit_find_index_attr; 1675 1676 fia_do_something (5): /* select cond =, current cond ^= */ 1677 fia_do_something (7): /* select cond is an inequality, current cond is a ^= */ 1678 fia_do_something (8): /* select cond is a range, current cond is a ^= */ 1679 fia_do_something (9): /* select cond is =, current cond is an inequality */ 1680 fia_do_something (12): /* select cond is a range, current cond is an inequality */ 1681 /* the following choices are not possible 1682* because of the way a range is completed */ 1683 fia_do_something (13): /* select cond is =, current cond completes a range */ 1684 fia_do_something (14): /* select cond is ^=, current cond completes a range */ 1685 fia_do_something (16): /* select cond is a range, current cond completes a range */ 1686 goto exit_find_index_attr; 1687 1688 fia_do_something (15): /* select cond is an inequality, 1689* current cond completes a range */ 1690 index_attr_2nd_cond_ptr = condp; 1691 index_attr_range = "1"b; 1692 goto exit_find_index_attr; 1693 1694 exit_find_index_attr: 1695 return; 1696 1697 end find_index_attr; 1698 1699 end short_key; 1700 1701 end calc_sub_path_cost; 1702 1703 count_conditions: 1704 procedure (condition_count, condition_cost, equal_seen, not_equal_seen); 1705 1706 /* DESCRIPTION: 1707* 1708* If a tuple variable is to be accessed sequentially, 1709* the number of tuples selected during the search will depend on 1710* the number of conditions specified against the tuple variable attriubtes. 1711* This routine determines the count of those conditions. 1712* This includes the count of expressions. 1713* 1714* The different operators normally will select different numbers of tuples, 1715* the number increasing from lowest to highest when the operators are 1716* "=", a range using "<" and ">", a range using only a ">", ">=, "<", or "<=", 1717* and finally "^=" for the 4 major cases. 1718* Thus The following weightings for adding 1719* conditions have been used: 1720* 1721* ">", "<", ">=", or "<=" - - - add 0.5 for each condition 1722* 1723* "=" - - - add 1.5 for each condition 1724* 1725* "^=" - - - add 0.2 for each condition 1726* 1727* These costs for conditions are then factored into the tuples selected count 1728* as follows: 1729* 1730* For an access of all tuples in the relation = T tuples, 1731* the final count used is = T / (condition_cost + 1) 1732* 1733* For a case where the tuples are accessed via some key, 1734* this is modified to only consider the conditions remaining after 1735* the conditions used by the key search are subtracted 1736* thus the final count is = T / (TC - KC + 1) 1737* where TC = total condition cost and KC = key conditions cost 1738* 1739**/ 1740 1741 condition_count = 0; /* init */ 1742 condition_cost = 0.0; 1743 equal_seen = "0"b; 1744 not_equal_seen = "0"b; 1745 1746 do i = 1 to rm_rel_info.num_attr; /* look at all attrs in view of rel */ 1747 1748 path_var.alp -> attr_list.info.attr_selected (i) = "0"b; 1749 /* reset for this T.V. */ 1750 1751 do condp = path_var.alp -> attr_list.info.cond_ptr (i) 1752 repeat condp -> cond.fwd_thd while (condp ^= null ()); 1753 1754 condp -> cond.condition_selected = "0"b;/* reset for this T.V. */ 1755 1756 condition_cost = 1757 condition_cost + CONDITION_COST_FACTOR (condp -> cond.op_code); 1758 condition_count = condition_count + 1; 1759 1760 if condp -> cond.op_code = OTT_EQ then 1761 equal_seen = "1"b; 1762 else if condp -> cond.op_code = OTT_NE then 1763 not_equal_seen = "1"b; 1764 1765 end; 1766 1767 end; 1768 1769 if path_var.elp ^= null () then do; 1770 1771 do i = 1 to path_var.elp -> expr_list.nexprs; 1772 condition_cost = 1773 condition_cost 1774 + 1775 CONDITION_COST_FACTOR (path_var.elp 1776 -> expr_list.info (i).op_code); 1777 condition_count = condition_count + 1; 1778 1779 if path_var.elp -> expr_list.info (i).op_code = 1 then 1780 equal_seen = "1"b; 1781 else if path_var.elp -> expr_list.info (i).op_code = 2 then 1782 not_equal_seen = "1"b; 1783 end; 1784 1785 end; 1786 1787 1788 1789 dcl equal_seen bit (1); /* on => an "=" condition exists against this relation */ 1790 dcl not_equal_seen bit (1); /* on => a "^=" condition exists against this relation */ 1791 dcl condition_count fixed bin; /* count of conditions against this relation */ 1792 dcl i fixed bin; /* loop index */ 1793 dcl condp ptr; /* local cond structure pointer */ 1794 dcl condition_cost float bin (27); /* cost of conditions + expressions on this T.V. */ 1795 1796 end; 1797 1798 permutations: 1799 proc (multiplier_param, cost_param, level, good_enough_rtn, code); 1800 1801 1802 /* DESCRIPTION: 1803* 1804* this routine will try all ordering of the tuple variables in this and_group, 1805* in an attempt to see how this ordering will affect possible access methoods, 1806* and the cost of using those methods, so that an overall lowest cost 1807* path through the tuple variables may be found 1808* tuple variables that are not in the and_group are treated equally with 1809* those in the and_group. the costing algorithm will put them 1810* in proper order in the final search path of tuple variables. 1811* 1812* Due to the changes on 10/01/83, this routine will no longer always try 1813* all possible orderings. If the number of tuple variables is very large 1814* and the current path looks very good, the search will skip some of the 1815* permutations. Currently, this is done by the simple method of checking 1816* if the sub-path will select only one tuple. This should be done by looking 1817* at which tuple variable provide information to determine other tuple 1818* variable and only trying the permutations that have some chance of having 1819* different costs. Unfortunally, this is much harder to do, so for now we 1820* will settle for the simple approach. 1821* 1822* This routine now returns the bit good_enough, to indict the all lower levels 1823* in the sub-path examined meet the conditions required to skip doing all 1824* permutations. 1825* */ 1826 1827 dcl (ENOUGH_TUPLE_VARIABLES_TO_NOT_TRY_ALL_POSSIBLE_PERMUTATIONS init (5), 1828 PATH_DOES_NOT_EXPAND init (1), 1829 NUMBER_OF_LEVELS_THAT_MUST_BE_PERMUTED init (2)) 1830 internal static options (constant); 1831 1832 dcl (current_variable_index, level, p_i, p_k, p_j) fixed bin; 1833 1834 dcl code fixed bin (35); 1835 1836 dcl (cost_param, current_path_cost, multiplier, multiplier_param, 1837 temp_multiplier, sub_path_cost) float bin (63); 1838 1839 dcl (done, good_enough_rtn, good_enough, in_current_path, current_good_enough) bit (1); 1840 1841 dcl ( 1842 path_ptr init (null), 1843 temp_fwd_thd init (null), 1844 work_ptr init (null) 1845 ) ptr; 1846 1847 good_enough_rtn = "0"b; 1848 multiplier = multiplier_param; 1849 current_path_cost = cost_param; 1850 current_variable_index = 1; 1851 do while (current_variable_index <= number_of_variables); 1852 done = "0"b; 1853 p_i = current_variable_index; 1854 do while (^done & p_i ^> number_of_variables); 1855 sub_path_cost = 0.; /* find this variable in the path. */ 1856 do path_ptr = current_path_ptr 1857 repeat path_ptr -> path_var.fwd_thd 1858 while (path_ptr -> path_var.fwd_thd ^= null 1859 & path_ptr -> path_var.var_index ^= variable_array (p_i)); 1860 end; 1861 if path_ptr -> path_var.var_index ^= variable_array (p_i) then do; 1862 /* Does this variable already exist in the path? */ 1863 pvp = null (); 1864 do while (pvp = null () & p_i ^> number_of_variables); 1865 /* Assume that this path is not good enough to cause skipping permutations */ 1866 current_good_enough = "0"b; 1867 call 1868 find_attributes (variable_array (p_i), multiplier, 1869 sub_path_cost, code); /* No. Create a path_var for it. */ 1870 if code ^= 0 then 1871 return; 1872 if ^path_var.in_and_group & ^path_var.in_select_clause 1873 then do; 1874 1875 /* a tuple variable with no effect on the select set was found, 1876* remove it from further considerations in the low cost path */ 1877 1878 if no_tuple_effect_ptr = null () then do; 1879 no_tuple_effect_ptr = pvp; 1880 last_no_tuple_effect_ptr = pvp; 1881 end; 1882 else do; 1883 last_no_tuple_effect_ptr -> path_var.fwd_thd = pvp; 1884 last_no_tuple_effect_ptr = pvp; 1885 end; 1886 1887 do p_j = p_i + 1 to number_of_variables; 1888 p_k = p_j - 1; 1889 variable_array (p_k) = variable_array (p_j); 1890 end; 1891 1892 number_of_variables = number_of_variables - 1; 1893 pvp = null (); 1894 sub_path_cost = 0.0; 1895 no_tuple_effect_number = no_tuple_effect_number + 1; 1896 1897 in_current_path = "1"b; 1898 do while (p_i ^> number_of_variables & in_current_path); 1899 do path_ptr = current_path_ptr 1900 repeat path_ptr -> path_var.fwd_thd 1901 while (path_ptr -> path_var.fwd_thd ^= null () 1902 & path_ptr -> path_var.var_index 1903 ^= variable_array (p_i)); 1904 1905 end; 1906 1907 if path_ptr -> path_var.var_index = variable_array (p_i) 1908 then p_i = p_i + 1; 1909 else in_current_path = "0"b; 1910 1911 end; 1912 1913 end; 1914 1915 end; 1916 if pvp ^= null () then do; 1917 /* Check to see if the current path meets the "good enough" rule */ 1918 if level > NUMBER_OF_LEVELS_THAT_MUST_BE_PERMUTED & 1919 number_of_variables > ENOUGH_TUPLE_VARIABLES_TO_NOT_TRY_ALL_POSSIBLE_PERMUTATIONS 1920 & path_var.number_tuples_selected <= PATH_DOES_NOT_EXPAND 1921 then current_good_enough = "1"b; 1922 if display_path_permutations then do; 1923 call 1924 ioa_ ( 1925 "^/Current level: ^i Current path cost: ^f Sub path cost: ^f Total: ^f" 1926 , level, current_path_cost, sub_path_cost, 1927 (current_path_cost + sub_path_cost)); 1928 call 1929 ioa_ ("^/Current variable: ^i Current cost: ^f", p_i, 1930 current_path_cost); 1931 call mdb_display_path_$path (current_path_ptr, dbcb_ptr); 1932 call mdb_display_path_$path (pvp, dbcb_ptr); 1933 end; 1934 1935 /* check for the current path exceeding the cost of the lowest cost path 1936* found so far. If it is exceeded 1937* then we can discard further consideration of the current path 1938* We must not stop however, if the first reference low cost path 1939* has not been completely built yet (first_pass true) */ 1940 1941 if current_path_cost + sub_path_cost >= cost & ^first_pass 1942 then call free_structures (pvp); /* Yes. */ 1943 else do; 1944 path_ptr -> path_var.fwd_thd = pvp; /* No. */ 1945 current_variable_index = p_i; 1946 done = "1"b; 1947 end; 1948 end; 1949 end; 1950 p_i = p_i + 1; 1951 end; 1952 1953 1954 /* check to see if this was the last variable that would make a complete 1955* path, and if so, was the current path a lower cost one than 1956* the lowest cost one seen so far. (done => lower cost) 1957* If this is the first path being built as a reference, 1958* then we must save it for comparison (first_pass true) */ 1959 1960 if level >= number_of_variables & (done | first_pass) then do; 1961 first_pass = "0"b; 1962 if pvp ^= null then do; /* a no_tuple_effect T.V. could have been last */ 1963 if path_var.in_select_clause | path_var.in_and_group then 1964 /* don't consider useless T.V.'s */ 1965 multiplier = multiplier * path_var.number_tuples_selected; 1966 end; 1967 cost = current_path_cost + sub_path_cost; 1968 path_ptr = low_cost_path_ptr; 1969 do work_ptr = current_path_ptr 1970 repeat work_ptr -> path_var.fwd_thd while (work_ptr ^= null); 1971 /* Copy the new, lower cost, path so that 1972* modifications maybe made to the current path. */ 1973 if path_ptr -> path_var.alp ^= null then 1974 call free_attr_list (path_ptr); 1975 if path_ptr -> path_var.elp ^= null then 1976 call free_expr_list (path_ptr); 1977 temp_fwd_thd = path_ptr -> path_var.fwd_thd; 1978 path_ptr -> path_var = work_ptr -> path_var; 1979 path_ptr -> path_var.fwd_thd = temp_fwd_thd; 1980 if work_ptr -> path_var.alp ^= null then 1981 call copy_attr_list (path_ptr, work_ptr); 1982 if work_ptr -> path_var.elp ^= null then 1983 call copy_expr_list (path_ptr, work_ptr); 1984 if work_ptr -> path_var.fwd_thd ^= null then 1985 path_ptr = path_ptr -> path_var.fwd_thd; 1986 else path_ptr -> path_var.fwd_thd = null; 1987 end; 1988 1989 if display_low_cost_paths then do; /* patch to display path */ 1990 do pvp = low_cost_path_ptr repeat path_var.fwd_thd 1991 while (path_var.fwd_thd ^= null); 1992 end; 1993 path_ptr = pvp; 1994 do p_i = 1 to number_of_variables - 1; 1995 do work_ptr = low_cost_path_ptr 1996 repeat work_ptr -> path_var.fwd_thd 1997 while (work_ptr -> path_var.fwd_thd ^= path_ptr); 1998 end; 1999 path_ptr -> path_var.fwd_thd = work_ptr; 2000 path_ptr = work_ptr; 2001 end; 2002 path_ptr -> path_var.fwd_thd = null; 2003 call ioa_ ("^/Cost: ^f", cost); 2004 call mdb_display_path_$path (pvp, dbcb_ptr); 2005 path_ptr = low_cost_path_ptr; 2006 do p_i = 1 to number_of_variables - 1; 2007 do work_ptr = pvp repeat work_ptr -> path_var.fwd_thd 2008 while (work_ptr -> path_var.fwd_thd ^= path_ptr); 2009 end; 2010 path_ptr -> path_var.fwd_thd = work_ptr; 2011 path_ptr = work_ptr; 2012 end; 2013 path_ptr -> path_var.fwd_thd = null; 2014 end; /* end display path patch */ 2015 2016 if level > 2 then do; /* delete the last variable index generated so 2017* we may look at the next variable index. */ 2018 do work_ptr = current_path_ptr 2019 repeat work_ptr -> path_var.fwd_thd 2020 while (work_ptr -> path_var.fwd_thd -> path_var.fwd_thd 2021 ^= null); 2022 end; 2023 call free_structures (work_ptr -> path_var.fwd_thd); 2024 good_enough_rtn = current_good_enough; 2025 return; 2026 end; 2027 else do; 2028 call free_structures (current_path_ptr -> path_var.fwd_thd); 2029 good_enough_rtn = current_good_enough; 2030 return; 2031 end; 2032 end; 2033 else if done then do; /* It was not the last variable to look at. 2034* Will this variable keep the path cost, so far, 2035* beneath that of the existing path? */ 2036 2037 if pvp = null () then 2038 temp_multiplier = multiplier; 2039 else if ^path_var.in_and_group & ^path_var.in_select_clause then 2040 temp_multiplier = multiplier; 2041 else temp_multiplier = multiplier * path_var.number_tuples_selected; 2042 2043 call permutations (temp_multiplier, current_path_cost + sub_path_cost, 2044 level + 1, good_enough, code); 2045 2046 if code ^= 0 then 2047 return; 2048 good_enough_rtn = current_good_enough & good_enough; 2049 call free_structures (path_ptr -> path_var.fwd_thd); 2050 end; 2051 else if level >= number_of_variables /* A variable to keep the cost below that of the 2052* existing path was not found. Back up a level. */ 2053 then do; 2054 good_enough_rtn = current_good_enough; 2055 return; 2056 end; 2057 2058 current_variable_index = current_variable_index + 1; 2059 /* Look for another path. */ 2060 if use_range_order then /* only one iteration t = 0.0 then */ 2061 return; 2062 2063 if good_enough_rtn then /* Do not search more if this path is good enough */ 2064 return; 2065 end; 2066 code = 0; 2067 end permutations; 2068 2069 free_structures: 2070 proc (path_var_ptr); 2071 2072 dcl work_ptr ptr init (null); 2073 2074 dcl path_var_ptr ptr; /* Input: ptr to the path_var structure to be freed */ 2075 2076 if path_var_ptr ^= null () then do; 2077 2078 path_var_ptr -> path_var.fwd_thd = path_var_free_ptr; 2079 /* Thread path_var structure onto its free list */ 2080 path_var_free_ptr = path_var_ptr; 2081 path_var_ptr = null; 2082 2083 if path_var_free_ptr -> path_var.alp ^= null then 2084 call free_attr_list (path_var_free_ptr); /* if an attribute list structure exists put it and its 2085* condition structures on their respective list */ 2086 2087 if path_var_free_ptr -> path_var.elp ^= null then 2088 call free_expr_list (path_var_free_ptr); /* if an expression list structure exists put it on 2089* its list */ 2090 2091 end; 2092 2093 end free_structures; 2094 2095 copy_attr_list: 2096 proc (copy_to_ptr, copy_from_ptr); 2097 2098 dcl ( 2099 copy_from_ptr, 2100 copy_to_ptr, 2101 from_work_ptr_1 init (null), 2102 from_work_ptr_2 init (null), 2103 to_work_ptr_1 init (null), 2104 to_work_ptr_2 init (null) 2105 ) ptr; 2106 2107 dcl (c_a_l_i, c_a_l_j) fixed bin; 2108 2109 call 2110 get_attr_list (copy_from_ptr -> path_var.alp -> attr_list.nattr, 2111 copy_to_ptr -> path_var.alp); 2112 2113 2114 2115 2116 2117 2118 from_work_ptr_1 = copy_from_ptr -> path_var.alp; 2119 to_work_ptr_1 = copy_to_ptr -> path_var.alp; 2120 2121 2122 to_work_ptr_1 -> attr_list = from_work_ptr_1 -> attr_list; 2123 2124 c_a_l_j = from_work_ptr_1 -> attr_list.nattr; 2125 2126 do c_a_l_i = 1 to c_a_l_j; 2127 if from_work_ptr_1 -> attr_list.info (c_a_l_i).cond_ptr ^= null 2128 then do; 2129 from_work_ptr_2 = 2130 from_work_ptr_1 -> attr_list.info (c_a_l_i).cond_ptr; 2131 if cond_free_ptr = null then 2132 allocate cond in (select_area) 2133 set (to_work_ptr_1 -> attr_list.info (c_a_l_i).cond_ptr); 2134 else do; 2135 to_work_ptr_1 -> attr_list.info (c_a_l_i).cond_ptr = 2136 cond_free_ptr; 2137 cond_free_ptr = cond_free_ptr -> cond.fwd_thd; 2138 end; 2139 to_work_ptr_2 = to_work_ptr_1 -> attr_list.info (c_a_l_i).cond_ptr; 2140 to_work_ptr_2 -> cond = from_work_ptr_2 -> cond; 2141 if copy_from_ptr -> path_var.cond_ptr = from_work_ptr_2 then 2142 copy_to_ptr -> path_var.cond_ptr = to_work_ptr_2; 2143 2144 if copy_from_ptr -> path_var.second_cond_ptr = from_work_ptr_2 then 2145 copy_to_ptr -> path_var.second_cond_ptr = to_work_ptr_2; 2146 from_work_ptr_2 = from_work_ptr_2 -> cond.fwd_thd; 2147 do while (from_work_ptr_2 ^= null); 2148 if cond_free_ptr = null then 2149 allocate cond in (select_area) 2150 set (to_work_ptr_2 -> cond.fwd_thd); 2151 else do; 2152 to_work_ptr_2 -> cond.fwd_thd = cond_free_ptr; 2153 cond_free_ptr = cond_free_ptr -> cond.fwd_thd; 2154 end; 2155 to_work_ptr_2 = to_work_ptr_2 -> cond.fwd_thd; 2156 to_work_ptr_2 -> cond = from_work_ptr_2 -> cond; 2157 if copy_from_ptr -> path_var.cond_ptr = from_work_ptr_2 then 2158 copy_to_ptr -> path_var.cond_ptr = to_work_ptr_2; 2159 2160 if copy_from_ptr -> path_var.second_cond_ptr = from_work_ptr_2 2161 then copy_to_ptr -> path_var.second_cond_ptr = to_work_ptr_2; 2162 from_work_ptr_2 = from_work_ptr_2 -> cond.fwd_thd; 2163 end; 2164 end; 2165 end; 2166 end copy_attr_list; 2167 2168 free_attr_list: 2169 proc (path_var_ptr); 2170 2171 dcl f_a_l_i fixed bin; 2172 2173 dcl ( 2174 path_var_ptr, 2175 work_ptr init (null) 2176 ) ptr; 2177 2178 condp = path_var_ptr -> path_var.alp -> attr_list.info (1).cond_ptr; 2179 path_var_ptr -> path_var.alp -> attr_list.info (1).cond_ptr = 2180 attr_list_free_ptr; 2181 attr_list_free_ptr = path_var_ptr -> path_var.alp; 2182 path_var_ptr -> path_var.alp = null; 2183 2184 do f_a_l_i = 1 to attr_list_free_ptr -> attr_list.nattr; 2185 /* put the condition structures on their free lists */ 2186 if condp ^= null then do; 2187 work_ptr = cond.fwd_thd; 2188 do while (condp ^= null); 2189 cond.fwd_thd = cond_free_ptr; 2190 cond_free_ptr = condp; 2191 condp = work_ptr; 2192 if condp ^= null then 2193 work_ptr = cond.fwd_thd; 2194 end; 2195 end; 2196 if f_a_l_i ^= 1 then 2197 attr_list_free_ptr -> attr_list.info (f_a_l_i).cond_ptr = null; 2198 if f_a_l_i < attr_list_free_ptr -> attr_list.nattr then 2199 condp = 2200 attr_list_free_ptr -> attr_list.info (f_a_l_i + 1).cond_ptr; 2201 end; 2202 2203 end free_attr_list; 2204 2205 get_attr_list: 2206 proc (num_of_attrs, alp_param); 2207 2208 dcl ( 2209 alp_param, /* output parameter: ptr to attr_list structure */ 2210 work_ptr_1 init (null), 2211 work_ptr_2 init (null) 2212 ) ptr; 2213 2214 dcl ptr_skel ptr based; 2215 2216 dcl num_of_attrs fixed bin; /* input parameter: size of the attr_list.info array */ 2217 2218 dcl in_attr_list_free_list bit (1) init ("0"b); 2219 2220 work_ptr_2 = addr (attr_list_free_ptr); 2221 work_ptr_1 = attr_list_free_ptr; 2222 do while (^in_attr_list_free_list & work_ptr_1 ^= null); 2223 if work_ptr_1 -> attr_list.nattr = num_of_attrs then do; 2224 work_ptr_2 -> ptr_skel = work_ptr_1 -> attr_list.info (1).cond_ptr; 2225 in_attr_list_free_list = "1"b; 2226 end; 2227 else do; 2228 work_ptr_2 = addr (work_ptr_1 -> attr_list.info (1).cond_ptr); 2229 work_ptr_1 = work_ptr_1 -> attr_list.info (1).cond_ptr; 2230 end; 2231 end; 2232 2233 if in_attr_list_free_list then 2234 alp_param = work_ptr_1; 2235 else do; 2236 al_nattr_init = num_of_attrs; 2237 allocate attr_list in (select_area) set (alp_param); 2238 end; 2239 end get_attr_list; 2240 2241 copy_expr_list: 2242 proc (copy_to_ptr, copy_from_ptr); 2243 2244 dcl (copy_from_ptr, copy_to_ptr) ptr; 2245 2246 if expr_list_free_ptr = null then 2247 allocate expr_list in (select_area) 2248 set (copy_to_ptr -> path_var.elp); 2249 else do; 2250 copy_to_ptr -> path_var.elp = expr_list_free_ptr; 2251 expr_list_free_ptr = expr_list_free_ptr -> expr_list.info (1).epl_ptr; 2252 end; 2253 copy_to_ptr -> path_var.elp -> expr_list.nexprs = el_nexprs_init; 2254 unspec (copy_to_ptr -> path_var.elp -> expr_list) = 2255 unspec (copy_from_ptr -> path_var.elp -> expr_list); 2256 end copy_expr_list; 2257 2258 free_expr_list: 2259 proc (path_var_ptr); 2260 2261 dcl path_var_ptr ptr; 2262 2263 path_var_ptr -> path_var.elp -> expr_list.info (1).epl_ptr = 2264 expr_list_free_ptr; 2265 expr_list_free_ptr = path_var_ptr -> path_var.elp; 2266 path_var_ptr -> path_var.elp = null; 2267 2268 end free_expr_list; 2269 2270 display_final_path_details: 2271 procedure (); 2272 2273 /* this routine outputs optional debug information. 2274* That info includes the final lowest cost path found, 2275* and all the conditions against that path, the access methods 2276* used for each tuple variable and so on. */ 2277 2278 call ioa_ ("^/FINAL PATH, COST = ^f^/", cost); 2279 2280 /* go through the path in the order it will be used for the search */ 2281 2282 order = 0; 2283 call ioa_ ("No tuple effect count: ^d", no_tuple_effect_number); 2284 2285 do pvp = low_cost_path_ptr repeat path_var.fwd_thd while (pvp ^= null ()); 2286 2287 order = order + 1; 2288 if ^path_var.in_select_clause & ^path_var.in_and_group then 2289 call ioa_ ("^/No tuple effect variables follow."); 2290 2291 /* output details on this tuple variable */ 2292 2293 rmri_ptr = range.tup_var.ri_ptr (path_var.var_index); 2294 call 2295 ioa_ ("^/Order: ^d Tuple variable: ^a", order, 2296 range.tup_var.name (path_var.var_index)); 2297 2298 call ioa_ ("^14xIn and group: ^[yes^;no^]", path_var.in_and_group); 2299 call 2300 ioa_ ("^14xIn select clause: ^[yes^;no^]", 2301 path_var.in_select_clause); 2302 call 2303 ioa_ ("^14xAccess method: ^a", 2304 access_method_name (path_var.access_method)); 2305 call 2306 ioa_ ("^14xTuples selected: ^d", path_var.number_tuples_selected); 2307 2308 if path_var.access_method = TOTAL_PRIMARY_KEY 2309 | path_var.access_method = LONG_KEY_HEAD then 2310 call ioa_ ("^14xEqual key attrs used: ^d", path_var.attr_index); 2311 else if path_var.access_method = SHORT_KEY_HEAD 2312 | path_var.access_method = INDEXED_ATTR then do; 2313 if path_var.second_cond_ptr = null () then 2314 call 2315 ioa_ ("^14xCondition used: ^a", 2316 condition_array (path_var.cond_ptr -> cond.op_code)); 2317 else call 2318 ioa_ ("^14xConditions used: ^a & ^a", 2319 condition_array (path_var.cond_ptr -> cond.op_code), 2320 condition_array (path_var.second_cond_ptr -> cond.op_code)); 2321 call 2322 ioa_ ("^14xAttribute used: ^a", 2323 rm_rel_info.attr_ptrs (path_var.attr_index) -> rm_attr_info.name) 2324 ; 2325 end; 2326 2327 if path_var.in_and_group then do; 2328 2329 /* output all conditions against this tuple variable, 2330* not in and group tuple variables have no conditions */ 2331 2332 conditions = 0; 2333 alp = path_var.alp; 2334 if alp ^= null () then do; 2335 2336 do i = 1 to rm_rel_info.num_attr; 2337 2338 rai_ptr = rm_rel_info.attr_ptrs (i); 2339 j = rm_attr_info.defn_order; 2340 if attr_list.info (j).cond_ptr ^= null () then do; 2341 2342 /* this attribute referenced by a condition */ 2343 2344 if conditions = 0 then /* first condition seen */ 2345 call ioa_ ("^/^14xCONDITION LIST"); 2346 call 2347 ioa_ ("^14xAttribute: ^a^/^14xSelected: ^[yes^;no^]", 2348 rm_attr_info.name, attr_list.info (j).attr_selected); 2349 2350 2351 /* output each condition on this attribute */ 2352 2353 do condp = attr_list.info (j).cond_ptr 2354 repeat cond.fwd_thd while (condp ^= null ()); 2355 2356 conditions = conditions + 1; 2357 if cond.pl_ptr -> pred_leaf.data_type = CONST then 2358 call 2359 ioa_ ( 2360 "^18xCompared(^d): ""^a"" to: CONSTANT", 2361 conditions, condition_array (cond.op_code)); 2362 else do; /* compared to attribute */ 2363 2364 call 2365 ioa_ ("^18xCompared(^d): ""^a"" to: ^a.^a", 2366 conditions, condition_array (cond.op_code), 2367 range.tup_var 2368 . 2369 name (fixed (cond.pl_ptr -> pred_leaf.id.var_id)), 2370 range.tup_var 2371 . 2372 ri_ptr ( 2373 fixed (cond.pl_ptr -> pred_leaf.id.var_id)) 2374 -> rm_rel_info 2375 . 2376 attr_ptrs ( 2377 fixed (cond.pl_ptr -> pred_leaf.id.attr_id)) 2378 -> rm_attr_info.name); 2379 end; 2380 call 2381 ioa_ ("^18xSelected: ^[yes^;no^]", 2382 cond.condition_selected); 2383 end; 2384 end; 2385 end; 2386 end; 2387 2388 /* were there any conditions seen */ 2389 2390 call ioa_ ("^14xConditions: ^d", conditions); 2391 2392 expressions = 0; 2393 elp = path_var.elp; 2394 if elp ^= null () then do; 2395 2396 /* output comparison operators involving expressions */ 2397 2398 call ioa_ ("^/^14xEXPRESSIONS"); 2399 do i = 1 to expr_list.nexprs; 2400 2401 expressions = expressions + 1; 2402 call 2403 ioa_ ("^18xCompared(^d): ""^a""", expressions, 2404 condition_array (expr_list.info.op_code (i))); 2405 end; 2406 2407 end; 2408 2409 call ioa_ ("^14xExpressions: ^d", expressions); 2410 end; 2411 end; 2412 2413 2414 dcl (i, j) fixed bin; /* loop/array indexes */ 2415 dcl expressions fixed bin; /* number of expressions seen */ 2416 dcl (order, conditions) fixed bin; /* count of path order and conditions per T.V. */ 2417 2418 end; 2419 2420 end mrds_dsl_permute; SOURCE FILES USED IN THIS COMPILATION. LINE NUMBER DATE MODIFIED NAME PATHNAME 0 04/18/00 1115.4 mrds_dsl_permute.pl1 >udd>sm>ds>w>ml>mrds_dsl_permute.pl1 293 1 08/04/88 2143.3 mrds_dbcb.incl.pl1 >ldd>incl>mrds_dbcb.incl.pl1 295 2 10/14/83 1709.1 mrds_range.incl.pl1 >ldd>incl>mrds_range.incl.pl1 297 3 10/14/83 1708.9 mrds_predicate_tree.incl.pl1 >ldd>incl>mrds_predicate_tree.incl.pl1 299 4 10/14/83 1709.1 mrds_optimize_tables.incl.pl1 >ldd>incl>mrds_optimize_tables.incl.pl1 301 5 10/14/83 1709.1 mdbm_rm_rel_info.incl.pl1 >ldd>incl>mdbm_rm_rel_info.incl.pl1 303 6 10/14/83 1709.1 mdbm_rm_attr_info.incl.pl1 >ldd>incl>mdbm_rm_attr_info.incl.pl1 305 7 10/14/83 1708.6 mdbm_seg_area.incl.pl1 >ldd>incl>mdbm_seg_area.incl.pl1 307 8 10/14/83 1708.6 mrds_select_area.incl.pl1 >ldd>incl>mrds_select_area.incl.pl1 309 9 10/14/83 1709.0 mrds_debug_names.incl.pl1 >ldd>incl>mrds_debug_names.incl.pl1 NAMES DECLARED IN THIS COMPILATION. IDENTIFIER OFFSET LOC STORAGE CLASS DATA TYPE ATTRIBUTES AND REFERENCES (* indicates a set context) NAMES DECLARED BY DECLARE STATEMENT. CONDITION_COST_FACTOR 000201 automatic float bin(27) initial array dcl 351 set ref 351* 351* 351* 853 879 1463 1553 1756 1772 CONST constant fixed bin(17,0) initial dcl 3-56 ref 669 725 1312 1445 1536 2357 ENOUGH_TUPLE_VARIABLES_TO_NOT_TRY_ALL_POSSIBLE_PERMUTATIONS constant fixed bin(17,0) initial dcl 1827 ref 1918 GT_LT_SELECTED_TUPLES 000172 automatic float bin(27) dcl 1204 set ref 959* 978 INDEXED_ATTR constant fixed bin(17,0) initial dcl 4-128 ref 966 1069 1156 2311 INFINITY 000040 constant float bin(63) initial dcl 1255 ref 829 1012 1130 LONG_KEY_HEAD constant fixed bin(17,0) initial dcl 4-128 ref 876 1038 1064 1153 2308 NE_SELECTED_TUPLES 000173 automatic float bin(27) dcl 1205 set ref 964* 972 NUMBER_OF_LEVELS_THAT_MUST_BE_PERMUTED constant fixed bin(17,0) initial dcl 1827 ref 1918 ORDERED_SEQUENTIAL constant fixed bin(17,0) initial dcl 4-128 ref 821 OTT_EQ constant fixed bin(17,0) initial dcl 4-174 ref 853 879 1307 1443 1471 1590 1760 OTT_GE constant fixed bin(17,0) initial dcl 4-174 ref 1478 1478 1569 1569 OTT_GT constant fixed bin(17,0) initial dcl 4-174 ref 1478 1478 1569 1569 OTT_LE constant fixed bin(17,0) initial dcl 4-174 ref 1478 1478 1569 1569 OTT_LT constant fixed bin(17,0) initial dcl 4-174 ref 1478 1478 1569 1569 OTT_NE constant fixed bin(17,0) initial dcl 4-174 ref 1472 1490 1505 1592 1762 PATH_DOES_NOT_EXPAND constant fixed bin(17,0) initial dcl 1827 ref 1918 RETRIEVE_ONLY constant fixed bin(17,0) initial dcl 1252 ref 819 SHORT_KEY_HEAD constant fixed bin(17,0) initial dcl 4-128 ref 911 1080 1156 2311 TOTAL_PRIMARY_KEY constant fixed bin(17,0) initial dcl 4-128 ref 850 1038 1064 1153 2308 UNORDERED_SEQUENTIAL constant fixed bin(17,0) initial dcl 4-128 ref 819 1001 1024 access_cost 277 based float bin(27) level 4 dcl 1-142 ref 888 941 986 access_costs 276 based structure level 3 dcl 1-142 access_method 000236 automatic structure array level 1 unaligned dcl 1245 in procedure "calc_sub_path_cost" access_method 7 based fixed bin(17,0) level 2 in structure "path_var" dcl 4-73 in procedure "mrds_dsl_permute" set ref 819* 821* 1024* 1029* 1038 1038 1064 1064 1069 1080 1149 1153 1153 1156 1156 2302 2308 2308 2311 2311 access_method_cost 000235 automatic float bin(27) dcl 1234 set ref 825* 1023* 1032* 1104 access_method_name 000056 constant char(20) initial array packed unaligned dcl 355 set ref 1129* 1149* 2302* access_overhead 300 based float bin(27) level 4 dcl 1-142 ref 888 941 986 addr builtin function dcl 343 ref 675 682 2220 2228 ag_ptr parameter pointer dcl 3-40 ref 24 556 557 729 al_nattr_init 000110 automatic fixed bin(17,0) dcl 4-144 set ref 2236* 2237 2237 alp 000106 automatic pointer dcl 4-143 in procedure "mrds_dsl_permute" set ref 543* 545 546 547 548 673 675 676 679 1047 1049 1296 1304 1329 1431 1439 1532 2333* 2334 2340 2346 2353 alp 16 based pointer level 2 in structure "path_var" dcl 4-73 in procedure "mrds_dsl_permute" set ref 383* 389* 539* 545* 1077 1088 1748 1751 1973 1980 2083 2109 2109* 2118 2119 2178 2179 2181 2182* 2333 alp_param parameter pointer dcl 2208 set ref 2205 2233* 2237* and_group based structure level 1 unaligned dcl 3-36 attr_id 1(18) based bit(18) level 3 packed packed unaligned dcl 3-67 ref 671 2364 attr_ind 000136 automatic fixed bin(17,0) dcl 655 set ref 671* 673 675 676 676 679 attr_index 14 based fixed bin(17,0) level 2 dcl 4-73 set ref 823* 1067* 1072* 1077 1083* 1088 1093* 1153* 1166 2308* 2321 attr_list based structure level 1 dcl 4-135 set ref 2122* 2122 2237 attr_list_free_ptr 000146 automatic pointer initial dcl 318 set ref 318* 2179 2181* 2184 2196 2198 2198 2220 2221 attr_ptrs based pointer array level 2 dcl 5-119 ref 1166 1521 2321 2338 2364 attr_selected 2 based bit(1) array level 3 packed packed unaligned dcl 4-135 set ref 1047* 1077* 1088* 1329* 1748* 2346* base_variable_index 000100 automatic fixed bin(17,0) dcl 493 set ref 564* 573* 587 base_variable_leaf_ptr 000112 automatic pointer initial dcl 514 set ref 514* 563* 572* 589 589* 602* 606* 610 610* 615* bp parameter pointer dcl 708 in procedure "add_to_expr_list" ref 701 725 744 bp parameter pointer dcl 646 in procedure "add_to_attr_list" ref 641 669 671 c_a_l_i 000150 automatic fixed bin(17,0) dcl 2107 set ref 2126* 2127 2129 2131 2135 2139* c_a_l_j 000151 automatic fixed bin(17,0) dcl 2107 set ref 2124* 2126 ceil builtin function dcl 343 ref 887 940 985 1005 code parameter fixed bin(35,0) dcl 504 in procedure "find_attributes" set ref 480 628* 636* code parameter fixed bin(35,0) dcl 1257 in procedure "calc_sub_path_cost" set ref 753 1022* 1028* code 000236 automatic fixed bin(17,0) array level 2 in structure "access_method" dcl 1245 in procedure "calc_sub_path_cost" set ref 850* 876* 911* 966* 1001* 1029 code parameter fixed bin(35,0) dcl 1834 in procedure "permutations" set ref 1798 1867* 1870 2043* 2046 2066* code parameter fixed bin(35,0) dcl 339 in procedure "mrds_dsl_permute" set ref 24 364* 404* 407 417* 426 428* cond based structure level 1 dcl 4-146 set ref 685 2131 2140* 2140 2148 2156* 2156 cond_free_ptr 000150 automatic pointer initial dcl 318 set ref 318* 685 689 690* 690 2131 2135 2137* 2137 2148 2152 2153* 2153 2189 2190* cond_ptr 4 based pointer array level 3 in structure "attr_list" dcl 4-135 in procedure "mrds_dsl_permute" set ref 547* 673 675 679 1049 1296 1304 1431 1439 1532 1751 2127 2129 2131* 2135* 2139 2178 2179* 2196* 2198 2224 2228 2229 2340 2353 cond_ptr 10 based pointer level 2 in structure "path_var" dcl 4-73 in procedure "mrds_dsl_permute" set ref 822* 1066* 1070* 1074 1081* 1085 1092* 1158 1162 2141 2141* 2157 2157* 2313 2317 condition_array 000114 constant char(2) initial array packed unaligned dcl 353 set ref 1158* 1162* 1162* 2313* 2317* 2317* 2357* 2364* 2402* condition_completes_range 000337 automatic bit(1) packed unaligned dcl 1608 set ref 1565* 1569* 1633 condition_cost parameter float bin(27) dcl 1794 set ref 1703 1742* 1756* 1756 1772* 1772 condition_count parameter fixed bin(17,0) dcl 1791 in procedure "count_conditions" set ref 1703 1741* 1758* 1758 1777* 1777 condition_count 4 000236 automatic fixed bin(17,0) array level 2 in structure "access_method" dcl 1245 in procedure "calc_sub_path_cost" set ref 851* 877* 912* 967* 1002* 1133* condition_selected 1 based bit(1) level 2 packed packed unaligned dcl 4-146 set ref 1051* 1074* 1075* 1085* 1086* 1328* 1754* 2380* condition_used 000336 automatic bit(1) packed unaligned dcl 1606 set ref 1442* 1445* 1458* 1462 1535* 1536* 1549* 1552 conditions 000240 automatic fixed bin(17,0) dcl 2416 set ref 2332* 2344 2356* 2356 2357* 2364* 2390* conditions_cost 5 000236 automatic float bin(27) array level 2 dcl 1245 set ref 853* 879* 884 915* 937 970* 982 1003* 1139* condp 000362 automatic pointer dcl 1793 in procedure "count_conditions" set ref 1751* 1751* 1754 1756 1760 1762* 1765 condp 000112 automatic pointer dcl 4-153 in procedure "mrds_dsl_permute" set ref 679* 679* 681 682 685* 689* 693 694 695 696 1049* 1049* 1051* 1052 1304* 1304* 1307 1308 1328* 1335 1439* 1439* 1441 1443 1463 1469 1472 1478 1478 1478 1478 1487 1495* 1500 1532* 1532* 1534 1553 1559 1569 1569 1569 1569* 1584 1636 1638 1657 1665 1688 2178* 2186 2187 2188 2189 2190 2191* 2192 2192 2198* 2353* 2353* 2357 2357 2364 2364 2364 2364 2380* 2383 copy_from_ptr parameter pointer dcl 2098 in procedure "copy_attr_list" ref 2095 2109 2118 2141 2144 2157 2160 copy_from_ptr parameter pointer dcl 2244 in procedure "copy_expr_list" ref 2241 2254 copy_to_ptr parameter pointer dcl 2098 in procedure "copy_attr_list" ref 2095 2109 2119 2141 2144 2157 2160 copy_to_ptr parameter pointer dcl 2244 in procedure "copy_expr_list" ref 2241 2246 2250 2253 2254 cost parameter float bin(63) dcl 313 in procedure "mrds_dsl_permute" set ref 24 380* 424* 1941 1967* 2003* 2278* cost parameter float bin(63) dcl 1235 in procedure "calc_sub_path_cost" set ref 753 825* 1104* cost 4 based float bin(63) level 2 in structure "path_var" dcl 4-73 in procedure "mrds_dsl_permute" set ref 825* 1104* 1150* 1173 cost parameter float bin(63) dcl 506 in procedure "find_attributes" set ref 480 637* cost 2 000236 automatic float bin(63) array level 2 in structure "access_method" dcl 1245 in procedure "calc_sub_path_cost" set ref 829* 857* 888* 941* 986* 1006* 1015 1016 1032 1130 1133* cost_param parameter float bin(63) dcl 1836 ref 1798 1849 current_good_enough 000117 automatic bit(1) packed unaligned dcl 1839 set ref 1866* 1918* 2024 2029 2048 2054 current_path_cost 000104 automatic float bin(63) dcl 1836 in procedure "permutations" set ref 1849* 1923* 1923 1928* 1941 1967 2043 current_path_cost 000140 automatic float bin(63) dcl 313 in procedure "mrds_dsl_permute" set ref 398* 404* 417* 424 1173 current_path_multiplier 000176 automatic float bin(63) dcl 348 set ref 403* 404* 412 415 current_path_ptr 000152 automatic pointer initial dcl 318 set ref 318* 379* 397* 409* 422 423* 436 437 438 439* 440* 441 441 470* 470* 473 474 475 659 715 1177 1314 1449 1540 1856 1899 1931* 1969 2018 2028 current_term 000101 automatic fixed bin(17,0) dcl 493 set ref 551* 556 581* current_tuple_population 31 based fixed bin(35,0) level 2 dcl 5-119 ref 767 current_variable_index 000100 automatic fixed bin(17,0) dcl 1832 set ref 1850* 1851 1853 1945* 2058* 2058 data based structure level 2 dcl 1-142 data_type 3 based fixed bin(17,0) level 2 dcl 3-67 ref 669 725 1312 1445 1536 2357 db_mrds_dsl_permute defined bit(9) packed unaligned dcl 9-62 ref 368 369 370 372 460 dbcb based structure level 1 dcl 1-142 dbcb_data based structure level 1 unaligned dcl 1-148 dbcb_ptr parameter pointer dcl 1-146 set ref 24 372 375 376 857 888 888 941 941 986 986 1006 1931* 1932* 2004* defn_order 22 based fixed bin(17,0) level 2 dcl 6-46 ref 1045 1296 1304 1329 1431 1439 1467 1492 1532 1558 1566 1659 1671 2339 display_access_method_costs 000144 automatic bit(1) packed unaligned dcl 315 set ref 370* 1110 display_low_cost_paths 000142 automatic bit(1) packed unaligned dcl 315 set ref 368* 1989 display_path_permutations 000143 automatic bit(1) packed unaligned dcl 315 set ref 369* 1922 done 000107 automatic bit(1) packed unaligned dcl 508 in procedure "find_attributes" set ref 552* 553 582* done 000321 automatic bit(1) packed unaligned dcl 1377 in procedure "equal_key" set ref 1293* 1294 1342* 1345* done 000114 automatic bit(1) packed unaligned dcl 1839 in procedure "permutations" set ref 1852* 1854 1946* 1960 2033 dummy_good_enough 000216 automatic bit(1) packed unaligned dcl 362 set ref 417* el_nexprs_init 000116 automatic fixed bin(17,0) dcl 4-164 set ref 729* 731 731 2246 2246 2253 elp 000114 automatic pointer dcl 4-163 in procedure "mrds_dsl_permute" set ref 731* 735* 740 741 743 743 744 744 745 745 746 746 2393* 2394 2399 2402 elp 20 based pointer level 2 in structure "path_var" dcl 4-73 in procedure "mrds_dsl_permute" set ref 383* 389* 539* 728 741* 1769 1771 1772 1779 1781 1975 1982 2087 2246* 2250* 2253 2254 2254 2263 2265 2266* 2393 end_of_list 000330 automatic bit(1) packed unaligned dcl 1597 in procedure "short_key" set ref 1448* 1450 1451* 1453* 1539* 1541 1542* 1544* end_of_list 000313 automatic bit(1) packed unaligned dcl 1369 in procedure "equal_key" set ref 1313* 1315 1316* 1318* end_of_list 000146 automatic bit(1) packed unaligned dcl 706 in procedure "add_to_expr_list" set ref 714* 716 717* 719* end_of_list 000137 automatic bit(1) packed unaligned dcl 657 in procedure "add_to_attr_list" set ref 660* 661 662* 664* epl_ptr 2 based pointer array level 3 dcl 4-155 set ref 736 744* 2251 2263* equal_found 000320 automatic bit(1) packed unaligned dcl 1373 set ref 1303* 1304 1327* 1336 equal_fraction 000233 automatic float bin(27) dcl 1232 set ref 842* 882 equal_head 000230 automatic bit(1) packed unaligned dcl 1229 set ref 842* 860 equal_key_count 000214 automatic fixed bin(17,0) dcl 1219 set ref 842* 851 853 877 879 1067 equal_key_head parameter bit(1) packed unaligned dcl 1375 set ref 1259 1287* 1361* equal_seen parameter bit(1) packed unaligned dcl 1789 set ref 1703 1743* 1760* 1779* expr_list based structure level 1 dcl 4-155 set ref 731 2246 2254* 2254 expr_list_free_ptr 000154 automatic pointer initial dcl 318 set ref 318* 731 735 736* 736 2246 2250 2251* 2251 2263 2265* expr_ptr 16 based pointer level 2 dcl 3-67 ref 589 594 610 expressions 000236 automatic fixed bin(17,0) dcl 2415 set ref 2392* 2401* 2401 2402* 2409* f_a_i 000102 automatic fixed bin(17,0) dcl 493 set ref 546* 547* 556* 557* 581 f_a_l_i 000100 automatic fixed bin(17,0) dcl 2171 set ref 2184* 2196 2196 2198 2198* fia_COMPARE_SELECTION_TO_CURRENT 000020 constant fixed bin(17,0) initial array dcl 1628 ref 1649 fia_current_cond 000350 automatic fixed bin(17,0) dcl 1625 set ref 1633* 1636* 1638* 1649 fia_select_cond 000351 automatic fixed bin(17,0) dcl 1626 set ref 1641* 1644* 1646* 1649 finished 000200 automatic bit(1) packed unaligned dcl 350 set ref 394* 396 429* 433* first_pass 000207 automatic bit(1) packed unaligned dcl 358 set ref 395* 1941 1960 1961* fixed builtin function dcl 343 ref 558 559 565 574 596 664 671 719 912 967 1309 1318 1453 1544 2364 2364 2364 found 000110 automatic bit(1) packed unaligned dcl 508 set ref 555* 556 568* 578* 582 from_work_ptr_1 000140 automatic pointer initial dcl 2098 set ref 2098* 2118* 2122 2124 2127 2129 from_work_ptr_2 000142 automatic pointer initial dcl 2098 set ref 2098* 2129* 2140 2141 2144 2146* 2146 2147 2156 2157 2160 2162* 2162 fwd_thd 22 based pointer level 2 in structure "path_var" dcl 4-73 in procedure "mrds_dsl_permute" set ref 390* 392* 437 441 451 454 456* 465 467 470 473 474* 477* 536 539* 666 722 1185 1321 1456 1547 1856 1860 1883* 1899 1905 1944* 1977 1979* 1984 1984 1986* 1987 1990 1992 1995 1998 1999* 2002* 2007 2009 2010* 2013* 2018 2018 2022 2023* 2028* 2049* 2078* 2411 fwd_thd 4 based pointer level 2 in structure "cond" dcl 4-146 in procedure "mrds_dsl_permute" set ref 679 681 682 690 696* 1052 1335 1500 1584 1765 2137 2146 2148* 2152* 2153 2155 2162 2187 2189* 2192 2383 good_enough 000115 automatic bit(1) packed unaligned dcl 1839 set ref 2043* 2048 good_enough_rtn parameter bit(1) packed unaligned dcl 1839 set ref 1798 1847* 2024* 2029* 2048* 2054* 2063 i 000360 automatic fixed bin(17,0) dcl 1792 in procedure "count_conditions" set ref 1746* 1748 1751* 1771* 1772 1779 1781* i 000221 automatic fixed bin(17,0) dcl 1224 in procedure "calc_sub_path_cost" set ref 828* 829* 1014* 1015 1016 1017* 1043* 1045* 1127* 1129 1130 1133 1133 1133 1139* i 000234 automatic fixed bin(17,0) dcl 2414 in procedure "display_final_path_details" set ref 2336* 2338* 2399* 2402* i_r_i 000332 automatic fixed bin(17,0) dcl 1599 set ref 1421* 1425* 1429 1430 1520* 1521* i_r_j 000333 automatic fixed bin(17,0) dcl 1599 set ref 1422* 1423 1425 1426* id 1 based structure level 2 in structure "pred_node" packed packed unaligned dcl 3-12 in procedure "mrds_dsl_permute" id 1 based structure level 2 in structure "pred_leaf" packed packed unaligned dcl 3-67 in procedure "mrds_dsl_permute" in_and_group 1 based bit(1) level 2 packed packed unaligned dcl 4-73 set ref 412 630* 632* 808 838 1113* 1122 1872 1963 2039 2288 2298* 2327 in_attr_list_free_list 000104 automatic bit(1) initial packed unaligned dcl 2218 set ref 2218* 2222 2225* 2233 in_current_path 000116 automatic bit(1) packed unaligned dcl 1839 set ref 1897* 1898 1909* in_select_clause 2 based bit(1) level 2 dcl 4-73 set ref 412 634* 808 1116* 1122 1872 1963 2039 2288 2299* index 3 based fixed bin(17,0) array level 3 dcl 4-135 set ref 548* 676* index_attr 20(01) based bit(1) level 2 packed packed unaligned dcl 6-46 ref 1522 index_attr_2nd_cond_ptr 000170 automatic pointer dcl 1203 in procedure "calc_sub_path_cost" set ref 895* 1071 index_attr_2nd_cond_ptr parameter pointer dcl 1605 in procedure "short_key" set ref 1382 1405* 1562* 1661* 1673* 1688* index_attr_cond_ptr parameter pointer dcl 1610 in procedure "short_key" set ref 1382 1405* 1556 1559* 1566 1569 1569 1569 1569 1590 1592 1644 1646 1657* 1665* index_attr_cond_ptr 000206 automatic pointer dcl 1215 in procedure "calc_sub_path_cost" set ref 895* 1070 index_attr_condition_cost parameter float bin(27) dcl 1621 set ref 1382 1518* 1553* 1553 index_attr_equal_condition 000202 automatic bit(1) packed unaligned dcl 1211 set ref 895* 978 index_attr_id 000205 automatic fixed bin(17,0) dcl 1214 in procedure "calc_sub_path_cost" set ref 895* 1072 index_attr_id parameter fixed bin(17,0) dcl 1609 in procedure "short_key" set ref 1382 1404* 1558* 1566 1659* 1671* index_attr_not_equal_condition 000203 automatic bit(1) packed unaligned dcl 1212 set ref 895* 972 index_attr_number_of_dups 000204 automatic fixed bin(35,0) dcl 1213 in procedure "calc_sub_path_cost" set ref 895* 957 index_attr_number_of_dups parameter fixed bin(35,0) dcl 1611 in procedure "short_key" set ref 1382 1560* 1652 1658* 1670* index_attr_range 000164 automatic bit(1) packed unaligned dcl 1200 in procedure "calc_sub_path_cost" set ref 895* 967 index_attr_range parameter bit(1) packed unaligned dcl 1604 in procedure "short_key" set ref 1382 1407* 1561* 1641 1660* 1672* 1691* index_equal_condition parameter bit(1) packed unaligned dcl 1615 set ref 1382 1407* 1590* index_not_equal_condition parameter bit(1) packed unaligned dcl 1616 set ref 1382 1407* 1592* indexed 21(05) based bit(1) level 2 packed packed unaligned dcl 5-119 ref 1519 indexed_attr 000232 automatic bit(1) packed unaligned dcl 1231 set ref 895* 946 indexed_attr_condition_cost 000201 automatic float bin(27) dcl 1210 set ref 895* 970 info 2 based structure array level 2 in structure "expr_list" dcl 4-155 in procedure "mrds_dsl_permute" info 2 based structure array level 2 in structure "attr_list" dcl 4-135 in procedure "mrds_dsl_permute" ioa_ 000020 constant entry external dcl 345 ref 1112 1113 1116 1119 1125 1129 1130 1133 1139 1147 1149 1150 1153 1158 1162 1166 1172 1173 1181 1187 1923 1928 2003 2278 2283 2288 2294 2298 2299 2302 2305 2308 2313 2317 2321 2344 2346 2357 2364 2380 2390 2398 2402 2409 j 000222 automatic fixed bin(17,0) dcl 1224 in procedure "calc_sub_path_cost" set ref 1045* 1047 1049 j 000235 automatic fixed bin(17,0) dcl 2414 in procedure "display_final_path_details" set ref 2339* 2340 2346 2353 key_attr_ptrs 44 based pointer array level 2 dcl 5-119 ref 1045 1295 1423 1430 key_head parameter bit(1) packed unaligned dcl 1617 set ref 1382 1407* 1504* key_head_2nd_cond_ptr parameter pointer dcl 1603 in procedure "short_key" set ref 1382 1405* 1487* key_head_2nd_cond_ptr 000166 automatic pointer dcl 1202 in procedure "calc_sub_path_cost" set ref 895* 1082 key_head_attr_id parameter fixed bin(17,0) dcl 1612 in procedure "short_key" set ref 1382 1404* 1467* 1492* key_head_attr_id 000200 automatic fixed bin(17,0) dcl 1209 in procedure "calc_sub_path_cost" set ref 895* 1083 key_head_cond_ptr parameter pointer dcl 1613 in procedure "short_key" set ref 1382 1405* 1466 1469* 1471 1477 1478 1478 1478 1478 1490 1495* 1505 key_head_cond_ptr 000176 automatic pointer dcl 1208 in procedure "calc_sub_path_cost" set ref 895* 1081 key_head_condition_cost 000174 automatic float bin(27) dcl 1206 in procedure "calc_sub_path_cost" set ref 895* 915 key_head_condition_cost parameter float bin(27) dcl 1620 in procedure "short_key" set ref 1382 1420* 1463* 1463 key_head_not_equal_condition 000175 automatic bit(1) packed unaligned dcl 1207 in procedure "calc_sub_path_cost" set ref 895* 917 key_head_not_equal_condition parameter bit(1) packed unaligned dcl 1614 in procedure "short_key" set ref 1382 1407* 1505* key_head_range 000165 automatic bit(1) packed unaligned dcl 1201 in procedure "calc_sub_path_cost" set ref 895* 912 key_head_range parameter bit(1) packed unaligned dcl 1602 in procedure "short_key" set ref 1382 1407* 1472 1486* 1490 key_order 23 based fixed bin(17,0) level 2 dcl 6-46 ref 1424 last_condp 000156 automatic pointer initial dcl 318 set ref 318* last_no_tuple_effect_ptr 000214 automatic pointer dcl 361 set ref 1880* 1883 1884* lbr 6 based pointer level 2 dcl 3-12 ref 563 576 left_sub_tree_variable_index 000103 automatic fixed bin(17,0) dcl 493 set ref 558* 561 564 577 level 000135 automatic fixed bin(17,0) dcl 311 in procedure "mrds_dsl_permute" set ref 410* 417 level parameter fixed bin(17,0) dcl 1832 in procedure "permutations" set ref 1798 1918 1923* 1960 2016 2043 2051 lk_key_ind 15 based fixed bin(17,0) level 2 dcl 4-73 set ref 766* lleaf_id 1 based structure level 3 packed packed unaligned dcl 3-12 low_cost_path_ptr 000160 automatic pointer initial dcl 318 set ref 318* 379* 384* 422* 451 465 470 1968 1990 1995 2005 2285 lowest_cost 000224 automatic float bin(63) dcl 1225 set ref 1012* 1015 1016* lowest_cost_index 000226 automatic fixed bin(17,0) dcl 1226 set ref 1013* 1017* 1021 1029 1030 1032 m_d_p_i 000134 automatic fixed bin(17,0) dcl 311 set ref 385* 386 386* 393* 404 431* 431 433 469* max builtin function dcl 343 ref 1463 1553 mdb_display_path_$path 000022 constant entry external dcl 346 ref 1931 1932 2004 model_area_ptr 000126 automatic pointer initial dcl 7-18 set ref 7-18* model_nkey_attr 25 based fixed bin(17,0) level 2 dcl 5-119 ref 1289 model_seg_ptr 000124 automatic pointer initial dcl 7-13 set ref 7-13* mrds_data_$max_attributes 000012 external static fixed bin(35,0) dcl 332 ref 541 541 541 634 634 1113 1113 1181 1181 1187 1187 2293 2293 2293 2294 2294 2364 2364 2364 2364 2364 mrds_data_$max_id_len 000014 external static fixed bin(35,0) dcl 332 ref 541 541 541 634 634 634 1113 1113 1113 1113 1181 1181 1181 1181 1187 1187 1187 1187 2293 2293 2293 2294 2294 2294 2294 2364 2364 2364 2364 2364 2364 2364 mrds_data_$max_tup_var 000016 external static fixed bin(35,0) dcl 332 ref 341 mrds_debug_$switch 000010 external static bit(9) array packed unaligned dcl 9-135 ref 368 368 369 369 370 370 372 372 460 460 mrds_error_$rst_logic_error 000024 external static fixed bin(35,0) dcl 1227 ref 1022 multiplier parameter float bin(63) dcl 491 in procedure "find_attributes" set ref 480 636* multiplier parameter float bin(63) dcl 1233 in procedure "calc_sub_path_cost" set ref 753 1104 1150* multiplier 000106 automatic float bin(63) dcl 1836 in procedure "permutations" set ref 1848* 1867* 1963* 1963 2037 2039 2041 multiplier_param parameter float bin(63) dcl 1836 ref 1798 1848 name 2 based char array level 3 in structure "range" dcl 2-5 in procedure "mrds_dsl_permute" set ref 1113* 1181* 1187* 2294* 2364* name based char(32) level 2 in structure "rm_attr_info" dcl 6-46 in procedure "mrds_dsl_permute" set ref 1166* 2321* 2346* 2364* nattr based fixed bin(17,0) level 2 dcl 4-135 set ref 546 548 2109* 2122 2124 2184 2198 2223 2237* nexprs based fixed bin(17,0) level 2 dcl 4-155 set ref 731* 740* 743* 743 744 745 746 1771 2246* 2253* 2254 2254 2399 nkey_attr 24 based fixed bin(17,0) level 2 dcl 5-119 ref 1043 1166 1289 1340 1359 1362 1422 1426 1507 1521 2321 2338 2364 no_optimize 106(18) based bit(1) level 3 packed packed unaligned dcl 1-142 ref 372 no_tuple_effect_number 000210 automatic fixed bin(17,0) dcl 359 set ref 378* 469 1895* 1895 2283* no_tuple_effect_ptr 000212 automatic pointer dcl 360 set ref 379* 456 1878 1879* not_equal_seen parameter bit(1) packed unaligned dcl 1790 set ref 1703 1744* 1762* 1781* null builtin function dcl 343 ref 379 383 389 392 397 423 436 438 441 451 465 477 6-65 7-13 7-18 8-6 8-10 318 318 318 318 318 318 318 318 318 318 318 514 514 531 539 547 589 594 610 646 646 662 669 673 679 685 696 708 717 725 728 731 822 1049 1066 1075 1086 1092 1158 1177 1296 1304 1316 1323 1371 1405 1431 1439 1451 1458 1466 1477 1532 1542 1549 1556 1562 1566 1601 1661 1673 1751 1769 1841 1841 1841 1856 1863 1864 1878 1893 1899 1916 1962 1969 1973 1975 1980 1982 1984 1986 1990 2002 2013 2018 2037 2072 2076 2081 2083 2087 2098 2098 2098 2098 2127 2131 2147 2148 2173 2182 2186 2188 2192 2196 2208 2208 2222 2246 2266 2285 2313 2334 2340 2353 2394 num_attr 22 based fixed bin(17,0) level 2 dcl 5-119 set ref 543* 1520 1746 2336 num_of_attrs parameter fixed bin(17,0) dcl 2216 ref 2205 2223 2236 num_terms based fixed bin(17,0) level 2 dcl 3-36 ref 556 729 num_vars based fixed bin(17,0) level 2 dcl 2-5 ref 377 number_of_dups 30 based fixed bin(35,0) level 2 dcl 6-46 ref 1560 1652 1658 1670 number_of_variables 000136 automatic fixed bin(17,0) dcl 311 set ref 377* 385 411 433 469 1851 1854 1864 1887 1892* 1892 1898 1918 1960 1994 2006 2051 number_tuples_selected 6 based fixed bin(35,0) level 2 dcl 4-73 set ref 412 824* 1025* 1030* 1918 1963 2041 2305* op parameter pointer dcl 708 in procedure "add_to_expr_list" ref 701 719 725 725 745 op parameter pointer dcl 646 in procedure "add_to_attr_list" ref 641 664 669 669 695 op_code based fixed bin(17,0) level 2 in structure "cond" dcl 4-146 in procedure "mrds_dsl_permute" set ref 694* 1158 1162 1162 1307 1443 1463 1471 1472 1478 1478 1478 1478 1478 1478 1478 1478 1490 1505 1553 1569 1569 1569 1569 1569 1569 1569 1569 1590 1592 1636 1638 1644 1646 1756 1760 1762 2313 2317 2317 2357 2364 op_code 4 based fixed bin(17,0) array level 3 in structure "expr_list" dcl 4-155 in procedure "mrds_dsl_permute" set ref 746* 1772 1779 1781 2402 op_code 2 based bit(6) level 3 in structure "pred_node" packed packed unaligned dcl 3-12 in procedure "mrds_dsl_permute" ref 565 574 596 op_code 000104 automatic fixed bin(17,0) dcl 493 in procedure "find_attributes" set ref 565* 574* 589* 596* 602* 606* 610* 615* opc parameter fixed bin(17,0) dcl 707 in procedure "add_to_expr_list" ref 701 746 opc parameter fixed bin(17,0) dcl 655 in procedure "add_to_attr_list" ref 641 694 ops_array 000050 constant fixed bin(17,0) initial array dcl 521 ref 565 574 596 order 000237 automatic fixed bin(17,0) dcl 2416 set ref 2282* 2287* 2287 2294* other_variable_index 000105 automatic fixed bin(17,0) dcl 493 set ref 567* 577* 587 other_variable_leaf_ptr 000114 automatic pointer initial dcl 514 set ref 514* 566* 576* 589* 594 602* 606* 610* 615* p_i 000101 automatic fixed bin(17,0) dcl 1832 set ref 1853* 1854 1856 1861 1864 1867 1887 1898 1899 1907 1907* 1907 1928* 1945 1950* 1950 1994* 2006* p_j 000103 automatic fixed bin(17,0) dcl 1832 set ref 1887* 1888 1889* p_k 000102 automatic fixed bin(17,0) dcl 1832 set ref 1888* 1889 path_ptr 000162 automatic pointer initial dcl 318 in procedure "mrds_dsl_permute" set ref 318* 468* 470 474 475* 477 path_ptr 000120 automatic pointer initial dcl 1841 in procedure "permutations" set ref 1841* 1856* 1856 1856* 1860 1861 1899* 1899 1899* 1905 1907 1944 1968* 1973 1973* 1975 1975* 1977 1978 1979 1980* 1982* 1984* 1984 1986 1993* 1995 1999 2000* 2002 2005* 2007 2010 2011* 2013 2049 path_var based structure level 1 dcl 4-73 set ref 382 388 531 1978* 1978 path_var_free_ptr 000164 automatic pointer initial dcl 318 set ref 318* 531 535 536* 536 2078 2080* 2083 2083* 2087 2087* path_var_ptr parameter pointer dcl 2261 in procedure "free_expr_list" ref 2258 2263 2265 2266 path_var_ptr parameter pointer dcl 2074 in procedure "free_structures" set ref 2069 2076 2078 2080 2081* path_var_ptr parameter pointer dcl 2173 in procedure "free_attr_list" ref 2168 2178 2179 2181 2182 pl_ptr 2 based pointer level 2 in structure "cond" dcl 4-146 in procedure "mrds_dsl_permute" set ref 695* 1308 1441 1534 2357 2364 2364 2364 pl_ptr 000104 automatic pointer dcl 3-84 in procedure "mrds_dsl_permute" set ref 1308* 1309 1312 1318 1441* 1445 1453 1534* 1536 1544 pl_ptr 6 based pointer array level 3 in structure "expr_list" dcl 4-155 in procedure "mrds_dsl_permute" set ref 745* pn_ptr 000102 automatic pointer dcl 3-27 set ref 557* 558 559 563 565 566 572 574 576 596 pred_leaf based structure level 1 unaligned dcl 3-67 pred_node based structure level 1 unaligned dcl 3-12 ptr_skel based pointer dcl 2214 set ref 2224* ptr_templ based pointer dcl 653 set ref 693* pvp parameter pointer dcl 4-96 set ref 24 382* 383 383 384 387 388* 389 389 390 392 409 412 412 412 451* 451* 454 456 465* 465* 467 468 531* 535* 539 539 539 540 545 630 632 634 634 728 741 765 766 808 808 819 821 822 822 823 824 825 838 1024 1025 1029 1030 1038 1038 1064 1064 1066 1066 1067 1069 1070 1071 1072 1074 1075 1075 1077 1077 1080 1081 1082 1083 1085 1086 1086 1088 1088 1092 1092 1093 1104 1113 1113 1116 1122 1122 1149 1150 1153 1153 1153 1156 1156 1158 1158 1162 1162 1166 1173 1187 1748 1751 1769 1771 1772 1779 1781 1863* 1864 1872 1872 1879 1880 1883 1884 1893* 1916 1918 1932* 1941* 1944 1962 1963 1963 1963 1990* 1990* 1992 1993 2004* 2007 2037 2039 2039 2041 2285* 2285* 2288 2288 2293 2294 2298 2299 2302 2305 2308 2308 2308 2311 2311 2313 2313 2317 2317 2321 2327 2333 2393* 2411 rai_ptr 000122 automatic pointer initial dcl 6-65 set ref 6-65* 1295* 1296 1304 1329 1423* 1424 1430* 1431 1439 1467 1492 1521* 1522 1532 1558 1560 1566 1652 1658 1659 1670 1671 2338* 2339 2346 range based structure level 1 dcl 2-5 range_order_path_ptr 000166 automatic pointer initial dcl 318 set ref 318* range_ptr 000100 automatic pointer dcl 2-23 in procedure "mrds_dsl_permute" set ref 376* 377 541 634 1113 1181 1187 2293 2294 2364 2364 range_ptr 2 based pointer level 3 in structure "dbcb" dcl 1-142 in procedure "mrds_dsl_permute" ref 376 rbr 10 based pointer level 2 dcl 3-12 ref 566 572 ready_mode 37 based fixed bin(17,0) level 2 dcl 5-119 ref 819 relation_index_selectivity 000210 automatic float bin(27) dcl 1216 set ref 957* 959 959 959 964 976 relation_size 000302 automatic fixed bin(35,0) dcl 1257 set ref 767* 808 824 882 918 920 920 928 930 930 957 957 959 959 964 1004 1006 1119* 1122 rev_ops_array 000042 constant fixed bin(17,0) initial array dcl 523 ref 574 596 ri_ptr based pointer array level 3 dcl 2-5 ref 541 2293 2364 right_sub_tree_variable_index 000106 automatic fixed bin(17,0) dcl 493 set ref 559* 567 570 573 rleaf_id 2(06) based structure level 3 packed packed unaligned dcl 3-12 rm_attr_info based structure level 1 dcl 6-46 rm_rel_info based structure level 1 dcl 5-119 rmri_ptr 000120 automatic pointer dcl 5-156 set ref 541* 543 767 819 1043 1045 1166 1289 1289 1295 1340 1359 1362 1422 1423 1426 1430 1507 1519 1520 1521 1746 2293* 2321 2336 2338 savep 000132 automatic pointer initial dcl 646 set ref 646* 675* 682* 693 second_cond_ptr 12 based pointer level 2 dcl 4-73 set ref 822* 1066* 1071* 1075 1075 1082* 1086 1086 1092* 1158 1162 2144 2144* 2160 2160* 2313 2317 secondary_index parameter bit(1) packed unaligned dcl 1618 set ref 1382 1517* 1589* select_area based area dcl 8-8 ref 382 388 531 685 731 2131 2148 2237 2246 select_area_ptr 000132 automatic pointer initial dcl 8-10 in procedure "mrds_dsl_permute" set ref 375* 382 388 8-10* 531 685 731 2131 2148 2237 2246 select_area_ptr 36 based pointer level 3 in structure "dbcb" dcl 1-142 in procedure "mrds_dsl_permute" ref 375 select_area_struct_ptr 000130 automatic pointer initial dcl 8-6 set ref 8-6* short_fraction 000234 automatic float bin(27) dcl 1232 set ref 895* 918 920 926 928 short_head 000231 automatic bit(1) packed unaligned dcl 1230 set ref 895* 904 sub_path_cost 000116 automatic float bin(63) dcl 519 in procedure "find_attributes" set ref 627* 636* 637 sub_path_cost 000112 automatic float bin(63) dcl 1836 in procedure "permutations" set ref 1855* 1867* 1894* 1923* 1923 1941 1967 2043 substr builtin function dcl 343 ref 368 369 370 372 460 temp_current_path_multiplier 000174 automatic float bin(63) dcl 348 set ref 412* 415* 417* temp_fwd_thd 000122 automatic pointer initial dcl 1841 set ref 1841* 1977* 1979 temp_multiplier 000110 automatic float bin(63) dcl 1836 set ref 2037* 2039* 2041* 2043* temp_path_ptr 000212 automatic pointer dcl 1218 set ref 1177* 1177* 1181* 1185 term_ptr 2 based pointer array level 2 dcl 3-36 ref 557 to_work_ptr_1 000144 automatic pointer initial dcl 2098 set ref 2098* 2119* 2122 2131 2135 2139 to_work_ptr_2 000146 automatic pointer initial dcl 2098 set ref 2098* 2139* 2140 2141 2144 2148 2152 2155* 2155 2156 2157 2160 total 000227 automatic bit(1) packed unaligned dcl 1228 set ref 842* 844 total_primary_key parameter bit(1) packed unaligned dcl 1374 set ref 1259 1287* 1355* total_primary_key_cost 276 based float bin(27) level 4 dcl 1-142 ref 857 tup_var 2 based structure array level 2 dcl 2-5 tuples_selected 1 000236 automatic fixed bin(35,0) array level 2 dcl 1245 set ref 856* 882* 884 887* 888 918* 920* 926* 928* 930* 930 930 930 937 940* 941 972* 976* 978* 982 985* 986 1005* 1030 1133* tuples_selected_temp 000162 automatic float bin(63) dcl 1199 set ref 884* 887 937* 940 982* 985 1004* 1005 tv_condition_cost 000216 automatic float bin(27) dcl 1221 set ref 834* 853 879 915 970 1003 1004 tv_condition_count 000215 automatic fixed bin(17,0) dcl 1220 set ref 834* 851 877 912 967 1002 tv_equal_condition 000217 automatic bit(1) packed unaligned dcl 1222 set ref 834* tv_not_equal_condition 000220 automatic bit(1) packed unaligned dcl 1223 set ref 834* u_i_i 000312 automatic fixed bin(17,0) dcl 1367 set ref 1286* 1292* 1295 1340 1340* 1340 1346* 1346 1352 1359 1359 1362 unspec builtin function dcl 343 set ref 2254* 2254 us_access_cost 301 based float bin(27) level 4 dcl 1-142 ref 1006 use_range_order 000145 automatic bit(1) packed unaligned dcl 315 set ref 372* 374* 429 2060 useable 000314 automatic bit(1) packed unaligned dcl 1369 in procedure "equal_key" set ref 1287* 1291* 1296* 1309* 1311 1323* 1326 1336* 1339 1354 1359 useable 000331 automatic bit(1) packed unaligned dcl 1597 in procedure "short_key" set ref 1407* 1445* 1458* 1503 1517* 1536* 1549* 1588 useable_key_attrs parameter fixed bin(17,0) dcl 1378 set ref 1259 1352* useable_key_fraction parameter float bin(27) dcl 1619 in procedure "short_key" set ref 1382 1507* useable_key_fraction parameter float bin(27) dcl 1376 in procedure "equal_key" set ref 1259 1288* 1356* 1362* used based bit(1) array level 3 packed packed unaligned dcl 2-5 ref 634 var_id 1 based bit(18) level 3 in structure "pred_leaf" packed packed unaligned dcl 3-67 in procedure "mrds_dsl_permute" ref 664 669 669 719 725 725 1309 1318 1453 1544 2364 2364 var_id 1 based bit(18) level 4 in structure "pred_node" packed packed unaligned dcl 3-12 in procedure "mrds_dsl_permute" ref 558 var_id 2(06) based bit(18) level 4 in structure "pred_node" packed packed unaligned dcl 3-12 in procedure "mrds_dsl_permute" ref 559 var_index parameter fixed bin(17,0) dcl 493 in procedure "find_attributes" ref 480 540 541 561 570 var_index based fixed bin(17,0) level 2 in structure "path_var" dcl 4-73 in procedure "mrds_dsl_permute" set ref 540* 634 664 719 765 1113 1181 1187 1318 1453 1544 1856 1861 1899 1907 2293 2294 var_index 000160 automatic fixed bin(17,0) dcl 1197 in procedure "calc_sub_path_cost" set ref 765* 1309 variable_array 000174 automatic fixed bin(17,0) array dcl 341 set ref 381* 386* 404* 1856 1861 1867* 1889* 1889 1899 1907 variable_index_in_and_group 000111 automatic bit(1) packed unaligned dcl 508 set ref 529* 586* 630 work_path_ptr 000170 automatic pointer initial dcl 318 set ref 318* work_ptr 000334 automatic pointer initial dcl 1601 in procedure "short_key" set ref 1449* 1451 1453 1456* 1456 1458 1540* 1542 1544 1547* 1547 1549 1601* work_ptr 000316 automatic pointer initial dcl 1371 in procedure "equal_key" set ref 1314* 1316 1318 1321* 1321 1323 1371* work_ptr 000172 automatic pointer initial dcl 318 in procedure "mrds_dsl_permute" set ref 318* 387* 390 437* 440 441* work_ptr 000124 automatic pointer initial dcl 1841 in procedure "permutations" set ref 1841* 1969* 1969* 1978 1980 1980* 1982 1982* 1984* 1987 1995* 1995* 1998 1999 2000 2007* 2007* 2009 2010 2011 2018* 2018* 2022 2023 work_ptr 000100 automatic pointer initial dcl 2072 in procedure "free_structures" set ref 2072* work_ptr 000150 automatic pointer initial dcl 708 in procedure "add_to_expr_list" set ref 708* 715* 717 719 722* 722 725 work_ptr 000102 automatic pointer initial dcl 2173 in procedure "free_attr_list" set ref 2173* 2187* 2191 2192* work_ptr 000134 automatic pointer initial dcl 646 in procedure "add_to_attr_list" set ref 646* 659* 662 664 666* 666 669 work_ptr_1 000100 automatic pointer initial dcl 2208 set ref 2208* 2221* 2222 2223 2224 2228 2229* 2229 2233 work_ptr_2 000102 automatic pointer initial dcl 2208 set ref 2208* 2220* 2224 2228* NAMES DECLARED BY DECLARE STATEMENT AND NEVER REFERENCED. ALL_OP internal static bit(6) initial packed unaligned dcl 3-44 AND_OP internal static bit(6) initial packed unaligned dcl 3-44 ARRAY internal static fixed bin(17,0) initial dcl 3-60 ATTR internal static fixed bin(17,0) initial dcl 3-56 CURRENT_OP internal static bit(6) initial packed unaligned dcl 3-44 EQ_OP internal static bit(6) initial packed unaligned dcl 3-44 EXPRES internal static fixed bin(17,0) initial dcl 3-56 GE_OP internal static bit(6) initial packed unaligned dcl 3-44 GT_OP internal static bit(6) initial packed unaligned dcl 3-44 LEAF internal static fixed bin(17,0) initial dcl 3-60 LE_OP internal static bit(6) initial packed unaligned dcl 3-44 LT_OP internal static bit(6) initial packed unaligned dcl 3-44 NE_OP internal static bit(6) initial packed unaligned dcl 3-44 NODE internal static fixed bin(17,0) initial dcl 3-60 NOT_OP internal static bit(6) initial packed unaligned dcl 3-44 OR_OP internal static bit(6) initial packed unaligned dcl 3-44 V_C internal static fixed bin(5,0) initial dcl 3-64 V_V internal static fixed bin(5,0) initial dcl 3-64 db_mrds_dsl_close defined bit(9) packed unaligned dcl 9-62 db_mrds_dsl_eval_expr defined bit(9) packed unaligned dcl 9-62 db_mrds_dsl_gen_srch_prog defined bit(9) packed unaligned dcl 9-62 db_mrds_dsl_get_token defined bit(9) packed unaligned dcl 9-62 db_mrds_dsl_init_res defined bit(9) packed unaligned dcl 9-62 db_mrds_dsl_open defined bit(9) packed unaligned dcl 9-62 db_mrds_dsl_optimize defined bit(9) packed unaligned dcl 9-62 db_mrds_dsl_search defined bit(9) packed unaligned dcl 9-62 db_mrds_dsl_set_fscope defined bit(9) packed unaligned dcl 9-62 db_mrds_dsl_translate defined bit(9) packed unaligned dcl 9-62 db_mrds_dsl_where_clause defined bit(9) packed unaligned dcl 9-62 db_mrds_rst_dmdm defined bit(9) packed unaligned dcl 9-62 db_mu_concurrency_control defined bit(9) packed unaligned dcl 9-62 db_mu_open_iocb_manager defined bit(9) packed unaligned dcl 9-62 db_mu_open_name_manager defined bit(9) packed unaligned dcl 9-62 db_mu_retrieve defined bit(9) packed unaligned dcl 9-62 db_mu_sec_get_tid defined bit(9) packed unaligned dcl 9-62 db_mu_sec_get_tuple defined bit(9) packed unaligned dcl 9-62 db_mu_sec_init_res defined bit(9) packed unaligned dcl 9-62 db_mus_mod_ubtup defined bit(9) packed unaligned dcl 9-62 model_area based area dcl 7-16 model_seg based structure level 1 dcl 7-9 module internal static structure level 1 unaligned dcl 9-91 natts_init automatic fixed bin(17,0) dcl 5-157 nkey_attr_init automatic fixed bin(17,0) dcl 5-157 num_ands_init automatic fixed bin(17,0) dcl 3-41 num_terms_init automatic fixed bin(17,0) dcl 3-41 nvar_atts_init automatic fixed bin(17,0) dcl 5-157 pred_array based structure level 1 unaligned dcl 3-29 pred_ptr automatic pointer dcl 3-34 rel builtin function dcl 343 select_area_struct based structure level 1 dcl 8-2 size builtin function dcl 7-20 sys_info$max_seg_size external static fixed bin(35,0) dcl 332 NAMES DECLARED BY EXPLICIT CONTEXT. add_to_attr_list 002104 constant entry internal dcl 641 ref 606 615 add_to_expr_list 002273 constant entry internal dcl 701 ref 589 602 610 calc_sub_path_cost 002445 constant entry internal dcl 753 ref 636 copy_attr_list 007375 constant entry internal dcl 2095 ref 1980 copy_expr_list 010052 constant entry internal dcl 2241 ref 1982 count_conditions 005742 constant entry internal dcl 1703 ref 834 display_final_path_details 010162 constant entry internal dcl 2270 ref 460 equal_key 004463 constant entry internal dcl 1259 ref 842 exit_find_index_attr 005741 constant label dcl 1694 ref 1663 1674 1676 1692 fia_do_something 000000 constant label array(16) dcl 1652 ref 1649 find_attributes 001420 constant entry internal dcl 480 ref 404 1867 find_index_attr 005624 constant entry internal dcl 1623 ref 1580 free_attr_list 007640 constant entry internal dcl 2168 ref 1973 2083 free_expr_list 010136 constant entry internal dcl 2258 ref 1975 2087 free_structures 007316 constant entry internal dcl 2069 ref 439 1941 2023 2028 2049 get_attr_list 007755 constant entry internal dcl 2205 ref 543 2109 mrds_dsl_permute 000714 constant entry external dcl 24 permutations 006126 constant entry internal dcl 1798 ref 417 2043 short_key 004753 constant entry internal dcl 1382 ref 895 THERE WERE NO NAMES DECLARED BY CONTEXT OR IMPLICATION. STORAGE REQUIREMENTS FOR THIS PROGRAM. Object Text Link Symbol Defs Static Start 0 0 11704 11732 11514 11714 Length 12356 11514 26 407 167 0 BLOCK NAME STACK SIZE TYPE WHY NONQUICK/WHO SHARES STACK FRAME mrds_dsl_permute 270 external procedure is an external procedure. find_attributes 358 internal procedure is called by several nonquick procedures. add_to_attr_list internal procedure shares stack frame of internal procedure find_attributes. add_to_expr_list internal procedure shares stack frame of internal procedure find_attributes. calc_sub_path_cost internal procedure shares stack frame of internal procedure find_attributes. equal_key internal procedure shares stack frame of internal procedure find_attributes. short_key internal procedure shares stack frame of internal procedure find_attributes. find_index_attr internal procedure shares stack frame of internal procedure find_attributes. count_conditions internal procedure shares stack frame of internal procedure find_attributes. permutations 179 internal procedure calls itself recursively. free_structures 72 internal procedure is called by several nonquick procedures. copy_attr_list internal procedure shares stack frame of internal procedure permutations. free_attr_list 70 internal procedure is called by several nonquick procedures. get_attr_list 69 internal procedure is called by several nonquick procedures. copy_expr_list internal procedure shares stack frame of internal procedure permutations. free_expr_list 64 internal procedure is called by several nonquick procedures. display_final_path_details internal procedure shares stack frame of external procedure mrds_dsl_permute. STORAGE FOR AUTOMATIC VARIABLES. STACK FRAME LOC IDENTIFIER BLOCK NAME find_attributes 000100 base_variable_index find_attributes 000101 current_term find_attributes 000102 f_a_i find_attributes 000103 left_sub_tree_variable_index find_attributes 000104 op_code find_attributes 000105 other_variable_index find_attributes 000106 right_sub_tree_variable_index find_attributes 000107 done find_attributes 000110 found find_attributes 000111 variable_index_in_and_group find_attributes 000112 base_variable_leaf_ptr find_attributes 000114 other_variable_leaf_ptr find_attributes 000116 sub_path_cost find_attributes 000132 savep add_to_attr_list 000134 work_ptr add_to_attr_list 000136 attr_ind add_to_attr_list 000137 end_of_list add_to_attr_list 000146 end_of_list add_to_expr_list 000150 work_ptr add_to_expr_list 000160 var_index calc_sub_path_cost 000162 tuples_selected_temp calc_sub_path_cost 000164 index_attr_range calc_sub_path_cost 000165 key_head_range calc_sub_path_cost 000166 key_head_2nd_cond_ptr calc_sub_path_cost 000170 index_attr_2nd_cond_ptr calc_sub_path_cost 000172 GT_LT_SELECTED_TUPLES calc_sub_path_cost 000173 NE_SELECTED_TUPLES calc_sub_path_cost 000174 key_head_condition_cost calc_sub_path_cost 000175 key_head_not_equal_condition calc_sub_path_cost 000176 key_head_cond_ptr calc_sub_path_cost 000200 key_head_attr_id calc_sub_path_cost 000201 indexed_attr_condition_cost calc_sub_path_cost 000202 index_attr_equal_condition calc_sub_path_cost 000203 index_attr_not_equal_condition calc_sub_path_cost 000204 index_attr_number_of_dups calc_sub_path_cost 000205 index_attr_id calc_sub_path_cost 000206 index_attr_cond_ptr calc_sub_path_cost 000210 relation_index_selectivity calc_sub_path_cost 000212 temp_path_ptr calc_sub_path_cost 000214 equal_key_count calc_sub_path_cost 000215 tv_condition_count calc_sub_path_cost 000216 tv_condition_cost calc_sub_path_cost 000217 tv_equal_condition calc_sub_path_cost 000220 tv_not_equal_condition calc_sub_path_cost 000221 i calc_sub_path_cost 000222 j calc_sub_path_cost 000224 lowest_cost calc_sub_path_cost 000226 lowest_cost_index calc_sub_path_cost 000227 total calc_sub_path_cost 000230 equal_head calc_sub_path_cost 000231 short_head calc_sub_path_cost 000232 indexed_attr calc_sub_path_cost 000233 equal_fraction calc_sub_path_cost 000234 short_fraction calc_sub_path_cost 000235 access_method_cost calc_sub_path_cost 000236 access_method calc_sub_path_cost 000302 relation_size calc_sub_path_cost 000312 u_i_i equal_key 000313 end_of_list equal_key 000314 useable equal_key 000316 work_ptr equal_key 000320 equal_found equal_key 000321 done equal_key 000330 end_of_list short_key 000331 useable short_key 000332 i_r_i short_key 000333 i_r_j short_key 000334 work_ptr short_key 000336 condition_used short_key 000337 condition_completes_range short_key 000350 fia_current_cond find_index_attr 000351 fia_select_cond find_index_attr 000360 i count_conditions 000362 condp count_conditions free_attr_list 000100 f_a_l_i free_attr_list 000102 work_ptr free_attr_list free_structures 000100 work_ptr free_structures get_attr_list 000100 work_ptr_1 get_attr_list 000102 work_ptr_2 get_attr_list 000104 in_attr_list_free_list get_attr_list mrds_dsl_permute 000100 range_ptr mrds_dsl_permute 000102 pn_ptr mrds_dsl_permute 000104 pl_ptr mrds_dsl_permute 000106 alp mrds_dsl_permute 000110 al_nattr_init mrds_dsl_permute 000112 condp mrds_dsl_permute 000114 elp mrds_dsl_permute 000116 el_nexprs_init mrds_dsl_permute 000120 rmri_ptr mrds_dsl_permute 000122 rai_ptr mrds_dsl_permute 000124 model_seg_ptr mrds_dsl_permute 000126 model_area_ptr mrds_dsl_permute 000130 select_area_struct_ptr mrds_dsl_permute 000132 select_area_ptr mrds_dsl_permute 000134 m_d_p_i mrds_dsl_permute 000135 level mrds_dsl_permute 000136 number_of_variables mrds_dsl_permute 000140 current_path_cost mrds_dsl_permute 000142 display_low_cost_paths mrds_dsl_permute 000143 display_path_permutations mrds_dsl_permute 000144 display_access_method_costs mrds_dsl_permute 000145 use_range_order mrds_dsl_permute 000146 attr_list_free_ptr mrds_dsl_permute 000150 cond_free_ptr mrds_dsl_permute 000152 current_path_ptr mrds_dsl_permute 000154 expr_list_free_ptr mrds_dsl_permute 000156 last_condp mrds_dsl_permute 000160 low_cost_path_ptr mrds_dsl_permute 000162 path_ptr mrds_dsl_permute 000164 path_var_free_ptr mrds_dsl_permute 000166 range_order_path_ptr mrds_dsl_permute 000170 work_path_ptr mrds_dsl_permute 000172 work_ptr mrds_dsl_permute 000174 temp_current_path_multiplier mrds_dsl_permute 000174 variable_array mrds_dsl_permute 000176 current_path_multiplier mrds_dsl_permute 000200 finished mrds_dsl_permute 000201 CONDITION_COST_FACTOR mrds_dsl_permute 000207 first_pass mrds_dsl_permute 000210 no_tuple_effect_number mrds_dsl_permute 000212 no_tuple_effect_ptr mrds_dsl_permute 000214 last_no_tuple_effect_ptr mrds_dsl_permute 000216 dummy_good_enough mrds_dsl_permute 000234 i display_final_path_details 000235 j display_final_path_details 000236 expressions display_final_path_details 000237 order display_final_path_details 000240 conditions display_final_path_details permutations 000100 current_variable_index permutations 000101 p_i permutations 000102 p_k permutations 000103 p_j permutations 000104 current_path_cost permutations 000106 multiplier permutations 000110 temp_multiplier permutations 000112 sub_path_cost permutations 000114 done permutations 000115 good_enough permutations 000116 in_current_path permutations 000117 current_good_enough permutations 000120 path_ptr permutations 000122 temp_fwd_thd permutations 000124 work_ptr permutations 000140 from_work_ptr_1 copy_attr_list 000142 from_work_ptr_2 copy_attr_list 000144 to_work_ptr_1 copy_attr_list 000146 to_work_ptr_2 copy_attr_list 000150 c_a_l_i copy_attr_list 000151 c_a_l_j copy_attr_list THE FOLLOWING EXTERNAL OPERATORS ARE USED BY THIS PROGRAM. fx1_to_fl2 call_ext_out_desc call_ext_out call_int_this call_int_other return_mac fl2_to_fx1 alloc_auto_adj mpfx2 mpfx3 ext_entry int_entry trunc_fx2 ceil_fl divide_fx1 divide_fx2 double_power_double_op_alloc_ THE FOLLOWING EXTERNAL ENTRIES ARE CALLED BY THIS PROGRAM. ioa_ mdb_display_path_$path THE FOLLOWING EXTERNAL VARIABLES ARE USED BY THIS PROGRAM. mrds_data_$max_attributes mrds_data_$max_id_len mrds_data_$max_tup_var mrds_debug_$switch mrds_error_$rst_logic_error LINE LOC LINE LOC LINE LOC LINE LOC LINE LOC LINE LOC LINE LOC 24 000707 6 65 000721 7 13 000723 7 18 000724 8 6 000725 8 10 000726 318 000727 341 000742 351 000746 364 000772 368 000774 369 001001 370 001005 372 001011 374 001024 375 001025 376 001031 377 001033 378 001035 379 001036 380 001042 381 001044 382 001046 383 001054 384 001061 385 001064 386 001073 387 001075 388 001101 389 001107 390 001114 391 001120 392 001122 393 001127 394 001131 395 001132 396 001134 397 001136 398 001140 403 001142 404 001144 407 001163 409 001166 410 001171 411 001173 412 001176 415 001211 417 001213 420 001234 422 001235 423 001237 424 001241 426 001243 428 001246 429 001247 431 001254 433 001255 436 001262 437 001266 438 001271 439 001276 440 001304 441 001306 443 001315 445 001316 451 001317 454 001331 456 001334 460 001336 465 001343 467 001355 468 001360 469 001361 470 001373 473 001403 474 001406 475 001410 476 001411 477 001413 478 001416 480 001417 514 001425 529 001430 531 001431 535 001446 536 001451 539 001454 540 001467 541 001473 543 001534 545 001545 546 001554 547 001563 548 001570 549 001603 551 001605 552 001607 553 001610 555 001612 556 001613 557 001627 558 001636 559 001641 561 001645 563 001651 564 001653 565 001654 566 001661 567 001663 568 001665 569 001667 570 001670 572 001673 573 001675 574 001676 576 001704 577 001706 578 001710 580 001712 581 001714 582 001715 586 001722 587 001724 589 001727 594 001737 596 001744 602 001753 605 001755 606 001756 609 001760 610 001761 615 001771 619 001773 627 001774 628 001776 630 002000 632 002010 634 002016 636 002065 637 002100 639 002103 641 002104 646 002106 659 002111 660 002114 661 002115 662 002120 664 002127 666 002144 667 002147 669 002150 671 002173 673 002201 675 002210 676 002213 677 002216 679 002217 681 002232 682 002235 685 002237 689 002254 690 002256 693 002260 694 002262 695 002265 696 002270 699 002272 701 002273 708 002275 714 002277 715 002300 716 002303 717 002306 719 002315 722 002332 723 002335 725 002336 728 002361 729 002371 731 002374 735 002414 736 002416 740 002420 741 002421 743 002426 744 002427 745 002436 746 002441 749 002444 753 002445 765 002447 766 002454 767 002456 808 002461 819 002470 821 002476 822 002500 823 002506 824 002511 825 002513 826 002520 828 002521 829 002527 830 002533 834 002535 838 002537 842 002546 844 002550 850 002553 851 002555 853 002560 856 002570 857 002572 860 002577 876 002602 877 002604 879 002607 882 002617 884 002631 887 002640 888 002643 895 002653 904 002655 911 002660 912 002662 915 002672 917 002675 918 002700 920 002712 924 002730 926 002731 928 002737 930 002751 937 002774 940 003003 941 003006 946 003016 957 003021 959 003036 964 003050 966 003052 967 003054 970 003064 972 003067 976 003076 978 003101 982 003107 985 003116 986 003121 1001 003131 1002 003133 1003 003135 1004 003137 1005 003146 1006 003151 1012 003160 1013 003162 1014 003163 1015 003171 1016 003177 1017 003201 1019 003203 1021 003205 1022 003207 1023 003213 1024 003215 1025 003223 1026 003224 1028 003225 1029 003227 1030 003237 1032 003241 1038 003243 1043 003252 1045 003263 1047 003271 1049 003275 1051 003305 1052 003310 1054 003313 1064 003315 1066 003326 1067 003333 1068 003337 1069 003340 1070 003342 1071 003344 1072 003350 1074 003354 1075 003357 1077 003366 1079 003373 1080 003374 1081 003376 1082 003400 1083 003404 1085 003410 1086 003413 1088 003422 1090 003427 1092 003430 1093 003435 1104 003440 1110 003447 1112 003452 1113 003466 1116 003553 1119 003577 1122 003617 1125 003633 1127 003647 1129 003655 1130 003675 1133 003720 1139 003751 1144 003772 1147 003774 1149 004010 1150 004035 1153 004065 1156 004117 1158 004123 1162 004154 1166 004211 1172 004245 1173 004261 1177 004310 1181 004320 1185 004376 1187 004402 1193 004462 1259 004463 1371 004465 1286 004467 1287 004470 1288 004501 1289 004503 1291 004510 1292 004512 1293 004514 1294 004515 1295 004520 1296 004527 1303 004540 1304 004541 1307 004557 1308 004562 1309 004565 1311 004575 1312 004577 1313 004602 1314 004603 1315 004605 1316 004610 1318 004617 1321 004633 1322 004636 1323 004637 1326 004644 1327 004646 1328 004650 1329 004654 1335 004662 1336 004670 1339 004673 1340 004675 1342 004704 1343 004706 1345 004707 1346 004711 1348 004713 1352 004714 1354 004717 1355 004721 1356 004725 1359 004727 1361 004740 1362 004744 1380 004752 1382 004753 1601 004755 1404 004757 1405 004761 1407 004766 1420 005017 1421 005021 1422 005022 1423 005033 1424 005041 1425 005044 1426 005046 1428 005051 1429 005053 1430 005055 1431 005063 1439 005072 1441 005103 1442 005106 1443 005107 1445 005112 1448 005121 1449 005122 1450 005124 1451 005126 1453 005135 1456 005151 1457 005154 1458 005155 1462 005164 1463 005166 1466 005176 1467 005202 1469 005205 1470 005207 1471 005210 1472 005214 1477 005224 1478 005230 1486 005254 1487 005257 1490 005261 1492 005271 1495 005274 1500 005276 1503 005304 1504 005306 1505 005313 1507 005323 1517 005334 1518 005342 1519 005344 1520 005351 1521 005361 1522 005373 1532 005376 1534 005411 1535 005414 1536 005415 1539 005424 1540 005425 1541 005427 1542 005432 1544 005441 1547 005455 1548 005460 1549 005461 1552 005470 1553 005472 1556 005502 1558 005506 1559 005511 1560 005513 1561 005515 1562 005521 1563 005523 1565 005524 1566 005525 1569 005535 1580 005564 1584 005565 1586 005573 1588 005575 1589 005577 1590 005604 1592 005615 1699 005623 1623 005624 1633 005625 1636 005632 1638 005641 1641 005642 1644 005653 1646 005662 1649 005663 1652 005667 1657 005674 1658 005676 1659 005700 1660 005702 1661 005706 1663 005710 1665 005711 1670 005714 1671 005720 1672 005722 1673 005726 1674 005730 1676 005731 1688 005732 1691 005735 1692 005740 1694 005741 1703 005742 1741 005744 1742 005745 1743 005747 1744 005753 1746 005757 1748 005771 1751 006001 1754 006010 1756 006013 1758 006021 1760 006022 1762 006032 1765 006040 1767 006043 1769 006045 1771 006055 1772 006065 1777 006102 1779 006103 1781 006114 1783 006122 1796 006124 1798 006125 1841 006133 1847 006137 1848 006144 1849 006146 1850 006150 1851 006152 1852 006156 1853 006157 1854 006160 1855 006166 1856 006170 1860 006205 1861 006210 1863 006216 1864 006221 1866 006233 1867 006234 1870 006253 1872 006256 1878 006270 1879 006274 1880 006275 1881 006276 1883 006277 1884 006301 1887 006304 1888 006315 1889 006317 1890 006325 1892 006327 1893 006332 1894 006335 1895 006337 1897 006340 1898 006342 1899 006350 1905 006365 1907 006370 1909 006400 1911 006401 1915 006402 1916 006403 1918 006407 1922 006425 1923 006427 1928 006464 1931 006510 1932 006523 1941 006536 1944 006556 1945 006562 1946 006564 1950 006566 1951 006567 1960 006570 1961 006601 1962 006602 1963 006607 1967 006623 1968 006626 1969 006630 1973 006636 1975 006652 1977 006666 1978 006671 1979 006676 1980 006677 1982 006705 1984 006714 1986 006725 1987 006730 1989 006733 1990 006736 1992 006752 1993 006755 1994 006756 1995 006767 1998 006777 1999 007002 2000 007004 2001 007005 2002 007007 2003 007012 2004 007035 2005 007050 2006 007053 2007 007065 2009 007077 2010 007102 2011 007104 2012 007105 2013 007107 2016 007112 2018 007116 2022 007130 2023 007132 2024 007141 2025 007146 2028 007147 2029 007160 2030 007165 2033 007166 2037 007170 2039 007200 2041 007213 2043 007217 2046 007244 2048 007247 2049 007257 2050 007267 2051 007270 2054 007272 2055 007276 2058 007277 2060 007300 2063 007303 2065 007311 2066 007312 2067 007314 2069 007315 2072 007323 2076 007325 2078 007331 2080 007336 2081 007342 2083 007344 2087 007357 2093 007374 2095 007375 2098 007377 2109 007404 2118 007422 2119 007427 2122 007433 2124 007442 2126 007444 2127 007453 2129 007461 2131 007465 2135 007502 2137 007504 2139 007506 2140 007511 2141 007520 2144 007532 2146 007543 2147 007545 2148 007552 2152 007567 2153 007572 2155 007574 2156 007577 2157 007606 2160 007620 2162 007631 2163 007633 2165 007634 2166 007636 2168 007637 2173 007645 2178 007647 2179 007656 2181 007660 2182 007665 2184 007670 2186 007677 2187 007704 2188 007707 2189 007715 2190 007720 2191 007721 2192 007723 2194 007732 2196 007733 2198 007742 2201 007751 2203 007753 2205 007754 2208 007762 2218 007765 2220 007766 2221 007771 2222 007774 2223 010002 2224 010006 2225 010011 2226 010013 2228 010014 2229 010017 2231 010022 2233 010023 2236 010031 2237 010035 2239 010051 2241 010052 2246 010054 2250 010100 2251 010104 2253 010106 2254 010114 2256 010134 2258 010135 2263 010143 2265 010152 2266 010157 2268 010161 2270 010162 2278 010163 2282 010204 2283 010205 2285 010225 2287 010235 2288 010236 2293 010262 2294 010325 2298 010357 2299 010402 2302 010425 2305 010452 2308 010475 2311 010526 2313 010532 2317 010563 2321 010620 2327 010653 2332 010661 2333 010662 2334 010664 2336 010670 2338 010701 2339 010712 2340 010714 2344 010722 2346 010743 2353 010773 2356 011004 2357 011005 2364 011043 2380 011200 2383 011221 2385 011225 2390 011227 2392 011247 2393 011250 2394 011255 2398 011261 2399 011300 2401 011307 2402 011310 2405 011343 2409 011345 2411 011365 2418 011373 ----------------------------------------------------------- Historical Background This edition of the Multics software materials and documentation is provided and donated to Massachusetts Institute of Technology by Group BULL including BULL HN Information Systems Inc. as a contribution to computer science knowledge. This donation is made also to give evidence of the common contributions of Massachusetts Institute of Technology, Bell Laboratories, General Electric, Honeywell Information Systems Inc., Honeywell BULL Inc., Groupe BULL and BULL HN Information Systems Inc. to the development of this operating system. Multics development was initiated by Massachusetts Institute of Technology Project MAC (1963-1970), renamed the MIT Laboratory for Computer Science and Artificial Intelligence in the mid 1970s, under the leadership of Professor Fernando Jose Corbato. Users consider that Multics provided the best software architecture for managing computer hardware properly and for executing programs. Many subsequent operating systems incorporated Multics principles. Multics was distributed in 1975 to 2000 by Group Bull in Europe , and in the U.S. by Bull HN Information Systems Inc., as successor in interest by change in name only to Honeywell Bull Inc. and Honeywell Information Systems Inc. . ----------------------------------------------------------- Permission to use, copy, modify, and distribute these programs and their documentation for any purpose and without fee is hereby granted,provided that the below copyright notice and historical background appear in all copies and that both the copyright notice and historical background and this permission notice appear in supporting documentation, and that the names of MIT, HIS, BULL or BULL HN not be used in advertising or publicity pertaining to distribution of the programs without specific prior written permission. Copyright 1972 by Massachusetts Institute of Technology and Honeywell Information Systems Inc. Copyright 2006 by BULL HN Information Systems Inc. Copyright 2006 by Bull SAS All Rights Reserved