/* BEGIN mrds_optimize_tables.incl.pl1 -- jaw, 2/23/79 */ /* HISTORY: 81-07-06 Jim Gray : added number of tuples selected, and the access methods currently available to the path_var structure, to allow the cost of a search path to be properly calculated. 81-07-07 Jim Gray : added in_and_group and cost to path_var for handling not in and_group tuple variables. 81-07-13 Jim Gray : removed calc_cost related structures that are no longer used. Also commented the access methods available. Added cond_ptr and attr_index to path_var to make gen_srch_prog use access specified by permute. 81-07-14 Jim Gray : added condition_selected and attr_selected bits to the cond and attr_list structures respectively, so that the permute logic in gen_srch_prog could be removed, and the desires of permute could be passed to gen_srch_prog. Also added description of structures in this include file. 81-07-17 Jim Gray : removed unused path_array structure once used by the discarded calc_cost routine, now replaced by permute. 81-07-19 Jim Gray : added in_select_clause bit to path_var for use by optimize, gen_srch_prog and the permute display for properly handling no_tuple_effect tuple variables, and not producing cross products not specified by the user. 81-07-21 Jim Gray : added a second condition pointer to the path var structure, so that permute could detect, make use of, and pass on the info for doing range searches on key heads and secondary indexes. 83-04-22 Mike Kubicar : removed attr_list.info.used. It is no longer needed. */ /* DESCRIPTION: The major structure of this include file is the path_var structure. It is used to hold an ordered list of tuple variables from the selection expression range clause, in the order in which they will be used for doing I/O on the database in order to retrieve the data necessary to evaluate the selection expression. The alp in this structure points to the attr_list structure which contains a list of all attributes referenced by this particular tuple variable in the selection expression. The elp in this path_var structure for this tuple variable similarly points to the expr_list structure, which contains information on all expressions in the selection expression which reference the tuple variable. The attr_list structure in turn has a list of all conditions (comparisons involving it) against that attribute in a linked list of cond structures pointed to by the cond_ptr. The op_code encoding for thecond and expr_list structures is that used in the pred_node structures of the predicate tree, and that given by the named constants starting OTT_... The path_array structure was originally intended for use by mrds_dsl_calc_cost, which is obsolete. Now only one element is used to point to the path returned by permute. */ dcl 1 path_var aligned based (pvp), /* info on one path through and group */ 2 var_index fixed bin, /* index of this var */ 2 in_and_group bit (1) unal, /* on => this tuple variable participates in the and group */ 2 in_select_clause bit (1), /* on => this tuple variable selected */ 2 pad bit (34) unal, /* for future use */ 2 cost float bin (63), /* partial sub path cost, or total for not in and_group */ 2 number_tuples_selected fixed bin (35), /* estimate of tuples selected by access method */ 2 access_method fixed bin, /* encoding for the method of access to this tuple variable: 1 => unique key search 2 => long key head search, only "=" conditions 3 => short key head, other than "=" conditions 4 => indexed attr 5 => unordered sequential search 6 => ordered sequential search */ 2 cond_ptr ptr, /* to condition on this T.V. to be used for accessing it */ 2 second_cond_ptr ptr, /* to second condition when a range is specified */ 2 attr_index fixed bin, /* attr_ptr array definition order index of attr to be used for accessing this T.V. */ 2 lk_key_ind fixed bin, /* link index or key id */ 2 alp ptr, /* to attribute list */ 2 elp ptr, /* to expr list */ 2 fwd_thd ptr; /* to next in path */ dcl pvp ptr; /* ACCESS METHODS AVAILABLE TO MRDS: 1) any number of key attributes making up a total primary key, with at least one "=" condition against each allows use of a vfile seek_key, to find the 1 unique tuple referenced 2) any number of key head attributes with at least one "=" condition against each allows use of vfile select, to find >1 tuples whose key has this prefix value 3) the first key head attribute having other than a "=" condition, or any number of conditions against it allows use of vfile select, to find >1 tuples whose key has this prefix 4) a single secondarily indexed attribute with any condition or number of conditions against it allows use of vfile select, to find the >= 1 tuples whose values match that of the value or range of values given 5) an unordered sequential search, where no updates against the database relation will be done allows use of mu_scan_records, which goes through the records without touching the vfile keys 6) an ordered sequential search, which must touch the vfile keys in order to get the tuple records, thus producing an in-order retrieval */ dcl ((TOTAL_PRIMARY_KEY init (1)), (LONG_KEY_HEAD init (2)), (SHORT_KEY_HEAD init (3)), (INDEXED_ATTR init (4)), (UNORDERED_SEQUENTIAL init (5)), (ORDERED_SEQUENTIAL init (6))) fixed bin int static options (constant); dcl 1 attr_list aligned based (alp), /* info on all ref. attr. for a t.v. */ 2 nattr fixed bin, /* number of attrs in rel */ 2 info (al_nattr_init refer (attr_list.nattr)), /* definition order array */ 3 attr_selected bit (1) unal, /* on => this attr used by access method chosed */ 3 pad bit (35) unal, 3 index fixed bin, /* definition order, same as array element number */ 3 cond_ptr ptr ; /* to list of conditions on attr. */ dcl alp ptr; dcl al_nattr_init fixed bin; dcl 1 cond aligned based (condp), /* info on attr condition */ 2 op_code fixed bin, /* op code translated from pred_node */ 2 condition_selected bit (1) unal, /* on => this condition used by access method chosen */ 2 pad bit (35) unal, 2 pl_ptr ptr, /* to pred leaf of other attr */ 2 fwd_thd ptr; /* to next condition */ dcl condp ptr; dcl 1 expr_list aligned based (elp), /* info for expr in this var */ 2 nexprs fixed bin, 2 info (el_nexprs_init refer (expr_list.nexprs)), 3 epl_ptr ptr, /* to pred leaf for this expr */ 3 op_code fixed bin, 3 reserved bit (36) unal, /* for future use */ 3 pl_ptr ptr; /* to pred leaf of other var */ dcl elp ptr; dcl el_nexprs_init fixed bin; /* COMPARISON OPERATOR NAMED CONSTANTS: The following named constants represent the comparison operators "=", "^=", "<", "<=", ">", ">=". They are used in the predicate tree nodes, the cond and expr_list structure, and in gen_srch_prog structures. */ dcl ((OTT_EQ init (1)), (OTT_NE init (2)), (OTT_LT init (3)), (OTT_LE init (4)), (OTT_GT init (5)), (OTT_GE init (6))) fixed bin int static options (constant); /* END mrds_optimize_tables.incl.pl1 */ */ ----------------------------------------------------------- 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 */