User's Guide
PART 4. Database Administration and Advanced Use
CHAPTER 25. Query Optimization
Join enumeration, the process of costing each possible join strategy and making a selection, is the heart of any optimizer. Adaptive Server Anywhere uses a proprietary join enumeration algorithm to search for an optimal access plan. This algorithm considers the cost of various strategies and works to find an inexpensive strategy.
When processing any query, Anywhere always accesses any one table by one method. It either scans the table sequentially, or selects one—and only one—index and accesses the rows through it.
Join enumerationIn selecting a join strategy, Anywhere considers the following pieces of information.
selectivity estimates of the number of rows in each intermediate result
estimates of scan factor for each indexed retrieval
the size of the cache—different cache sizes can lead to different join strategies.
Anywhere begins by using selectivity information, as determined in the previous step, to select an access order.
Anywhere derives the estimates of scan factors from estimates of index fan-out. The fan-out of an index can vary greatly depending on the type of index and the page size that you selected when you launched the engine or created the database. Larger fan-out is better, because it allows Anywhere access to locate specific rows using fewer pages and hence fewer resources.
The amount of cache space available to Anywhere can affect the outcome of the optimizer's choice of join strategy. The larger the fraction of space consumed by any one query, the more likely that pages will need to be swapped for those on disk. If Anywhere decides that a particular strategy will result in using excessive cache space, it assigns that strategy a higher cost.
The number of possible join strategies can be huge. A join of n tables allows n! possible join orders. For example, a join of 10 tables may have 10! = 3,628,800 possible orders.
When faced with joins that involve a large number of tables, Anywhere attempts to prune the set of possible strategies. It eliminates those that fall into certain categories, so as to focus effort on investigating possibilities which are more likely to be efficient.
Anywhere always selects plans that minimize the number of Cartesian products required to compute the result. Instead, it favors indexed access.
Index selectionIn addition to selecting an order, the optimizer must choose a method of accessing each of these tables. It can choose to either scan a table sequentially, or to access it by through an index. Some tables may have a few indexes, further increasing the number of possible strategies.
The optimizer analyzes each join strategy to determine which type of access—indexed or sequential scan—would best suit each table in that strategy. Although one index may be well suited to one join strategy, it can be a poor choice for another strategy that joins the tables in a different order. By making a custom index selection for each join order, the optimizer gains the opportunity to choose a better access plan.
Anywhere decides to use an index instead of embarking on a sequential scan whenever an index is available and the selectivity is less than 20%.