index

Documentation

Overview

Package index implements the general index optimization algorithm.

The main idea of the algorithm is to find the best index for the query by three-star index algorithm. For more information, please refer to the Chapter 4 of the book 《Relational database index design and the optimizers》.

A single table SELECT using a three-star index normally needs only one random disk drive read and a scan of a thin slice of an index.

The three-star index algorithm described in the following steps:

1. An index deserves the first star if the index rows relevant to the SELECT are next to each other or at least as close to each other as possible. This minimizes the thickness of the index slice that must be scanned.
2. The second star is given if the index rows are in the right order for the SELECT.
3. If the index rows contain all the columns referred to by the SELECT the index is given the third star. This eliminates table access: The access path is index only.

Suppose we have a SQL:

SELECT CNO, FNAME
FROM CUST
WHERE LNAME = :LNAME AND CITY = :CITY
ORDER BY FNAME

To Qualify for the first star: Pick the columns from all equal predicates (WHERE COL = . . .). Make these the first columns of the index—in any order. For above SQL, the three-star index will begin with columns LNAME, CITY or CITY, LNAME. In both cases the index slice that must be scanned will be as thin as possible.

To Qualify for the second star: Add the ORDER BY columns. Do not change the order of these columns, but ignore columns that were already picked in step 1. For example, if above SQL had redundant columns in the ORDER BY, say ORDER BY LNAME, FNAME or ORDER BY FNAME, CITY, only FNAME would be added in this step. When FNAME is the third index column, the result table will be in the right order without sorting. The first FETCH call will return the row with the smallest FNAME value.

To Qualify for the third star: Add all the remaining columns from the SELECT statement. The order of the columns added in this step has no impact on the performance of the SELECT, but the cost of updates should be reduced by placing volatile columns at the end. Now the index contains all the columns required for an index-only access path.

Index

• type Optimizer
  • func NewOptimizer(opts ...optimizerOption) *Optimizer
  • func (o *Optimizer) Optimize(ast SelectAST) (columns []string, err error)
• type SelectAST

Types

type Optimizer

type Optimizer struct {
}

Optimizer give best index advice for the single table query.

func NewOptimizer

func NewOptimizer(opts ...optimizerOption) *Optimizer

NewOptimizer creates a new optimizer.

func (*Optimizer) Optimize

func (o *Optimizer) Optimize(ast SelectAST) (columns []string, err error)

Optimize try him best to give three-star index advice for ast.

type SelectAST

type SelectAST interface {
	// EqualPredicateColumnsInWhere find the equal predicate column in where clause.
	//
	// For example, the SQL: select * from t where a = 1 and b = 2;
	// it returns []string{"a", "b"}.
	EqualPredicateColumnsInWhere() []string

	// ColumnsInOrderBy find the columns in order by clause.
	//
	// For example, the SQL: select * from t order by a desc, b;
	// it returns []string{"a desc", "b"}.
	ColumnsInOrderBy() []string

	// ColumnsInProjection find columns in select projection.
	//
	// For example, the SQL: select a, b from t;
	// it returns []string{"a", "b"}.
	//
	// If projection returns all columns, it returns nil.
	ColumnsInProjection() []string
}

SelectAST contain an abstract syntax tree of a single table SQL. It abstracts the syntax differences between different database.