SQL statements do not require the user to specify anything about the access path to be used for tuple retrieval. Nor does a user specify in what order joins are to be performed. The System R optimizer chooses both join order and an access path for each table in the SQL statement. Of the many possible choices, the optimizer chooses the one which minimizes “total access cost” for performing the entire statement.

The first type is a segment scan to find all the tuples of a given relation. A series of NEXTs on a segment scan simply examines all pages of the segment which contain tuples, from any relation, and returns those tuples belonging to the given relation.

These indexes are stored on separate pages from those containing the relation tuples. Indexes are implemented as B-trees, whose leaves are pages containing sets of (key, identifiers of tuples which contain that key). Therefore a series of NEXTs on an index scan does a sequential read along the leaf pages of the index, obtaining the tuple identifi- ers matching a key, and using them to find and return the data tuples to the user in key value order.

COST = PAGE FETCHES + W * (RSI CALLS)

For each relation T,
- NCARD(T), the cardinality of relation T. T中元组的基数。

- TCARD(T), the number of pages in the segment that hold tuples of relation T. segment中的page的数量。

- P(T), the fraction of data pages in the segment that hold tuples of relation T. 
  P(T) = TCARD(T) / (no. of non-empty pages in the segment). 

For each index I on relation T,
- ICARD(I), number of distinct keys in index I. 不同key的数量。
- NINDX(I), the number of pages in index I. 这个索引使用的pages的数量。

column = value
  F = 1 / ICARD(column index) if there is an index on column. 
  This assumes an even distribution of tuples among the index key values. F = 1/10 otherwise

column1 = column2
  F = 1/MAX(ICARD(column1 index), ICARD(column2 index)) if there are indexes on both column1 and column2. 
  This assumes that each key value in the index with the smaller cardinality has a matching value in the other index.
  F = 1/ICARD(column-i index) if there is only an index on column-i 
  F = 1/10 otherwise
  
column > value (or any other open-ended comparison)
  F = (high key value - value) / (high key value - low key value)
  Linear interpolation of the value within the range of key values yields F if the column is an arithmetic type and value is known at access path selection time.
  F = 1/3 otherwise (i.e. column not arithmetic)
  There is no significance to this number, other than the fact that it is less selec- tive than the guesses for equal predicates for which there are no indexes, and that it is less than 1/2. We hypothesize that few queries use predicates that are satis- fied by more than half the tuples.
  
column BETWEEN value1 AND value2
  F = (value2 - value1) / (high key value - low key value)
  A ratio of the BETWEEN value range to the entire key value range is used as the selectivity factor if column is arithmetic and both value1 and value2 are known at access path selection.
  F = 1/4 otherwise
  Again there is no significance to this choice except that it is between the default selectivity factors for an equal predicate and a range predicate.
  
column IN (list of values)
   F = (number of items in list) * (selectivity factor for column = value) This is allowed to be no more than 1/2.
   
columnA IN subquery
  F = (expected cardinality of the subquery result) / (product of the cardinalities of all the relations in the subquery’s FROM-list).
  The computation of query cardinality will be discussed below. This formula is derived by the following argument: Consider the simplest case, where subquery is of the form “SELECT columnB FROM relationC ...”. Assume that the set of all columnB values in relationC contains the set of all columnA values. If all the tuples of relationC are selected by the subquery, then the predicate is always TRUE and F = 1. If the tuples of the subquery are restricted by a selectivity factor F’, then assume that the set of unique values in the subquery result that match columnA values is proportionately restricted, i.e. the selectivity factor for the predicate should be F’. F’ is the product of all the sub- query’s selectivity factors, namely (subquery cardinality) / (cardinality of all pos- sible subquery answers). With a little optimism, we can extend this reasoning to include subqueries which are joins and subqueries in which columnB is replaced by an arithmetic expression involving column names. This leads to the formula given above.
  
(pred expression1) OR (pred expression2)
  F = F(pred1) + F(pred2) - F(pred1) * F(pred2)
  
(pred1) AND (pred2)
   F = F(pred1) * F(pred2)
  Note that this assumes that column values are independent.
  
NOT pred
F = 1 - F(pred)

Unique index matching an equal predicate -> 1+1+W

Clustered index I matching one or more boolean factors -> F(preds) * (NINDX(I) + TCARD) + W * RSICARD

Non-clustered index I matching one or more boolean factors -> F(preds) * (NINDX(I) + NCARD) + W * RSICARD or F(preds) * (NINDX(I) + TCARD) + W * RSICARD if this number fits in the System R buffer

Clustered index I not matching any boolean factors -> (NINDX(I) + TCARD) + W * RSICARD

Non-clustered index I not matching any boolean factors -> (NINDX(I) + NCARD) + W * RSICARD
or (NINDX(I) + TCARD) + W * RSICARD if this number fits in the System R buffer

Segment scan -> TCARD/P + W * RSICARD

Using an index access path or sorting tuples produces tuples in the index value or sort key order. We say that a tuple order is an interesting order if that order is one specified by the query block’s GROUP BY or ORDER BY clauses.

A heuristic is used to reduce the join order permutations which are considered. When possible, the search is reduced by consideration only of join orders which have join predicates relating the inner relation to the other relations already participating in the join. This means that in joining relations t1,t2,...,tn only those orderings til,ti2,...,tin are examined in which for all j (j=2,...,n) either

(1) tij has at least one join predicate with some relation tik, where k < j, or

(2) for all k > j, tik has no join predicate with til,tit,...,or ti(j-1).

 For each plan to join a set of relations, the order of the composite result is kept in the tree. This allows consideration of a marge scan join which would not require sorting the composite. After the complete solutions (all of the relations joined together) have been found, the optimizer chooses the cheapest solution which gives the required order, if any was specified.

N = (product of the cardinalities of all relations T of the join so far) * (product of the selectivity factors of all applicable predicates).

C-nested-loop-join(pathl,path2)= C-outer(path1) + N * C-inner(path2)

C-merge(pathl,path2)= C-outer(path1) + N * C-inner(path2)

C-inner(sorted list) = TEMPPAGES/N + W*RSICARD

where TEMPPAGES is the number of pages required to hold the inner relation. This formula assumes that during the merge each page of the inner relation is fetched once.

A correlation subquery must in principle be re-evaluated for each candidate tuple from the referenced query block. This re-evaluation must be done before the correlation subquery’s parent predicate in the higher level block can be tested for acceptance or rejection of the candidate tuple.