optimizer

Documentation

Overview

Package optimizer provides query optimization for XxSql.

Package optimizer provides query optimization for XxSql.

Index

• Constants
• func CalculateSelectivityFromConditions(selectivities []float64) float64
• func IsLowSelectivity(selectivity float64) bool
• type AnalyzeTable
  • func NewAnalyzeTable() *AnalyzeTable
  • func (a *AnalyzeTable) AddRow(columns []string, values []types.Value)
  • func (a *AnalyzeTable) BuildHistogram(column string, values []types.Value, numBuckets int)
  • func (a *AnalyzeTable) Finalize() *Statistics
  • func (a *AnalyzeTable) SetIndexStatistics(name string, columns []string, distinctKeys uint64, height int, clustered bool)
• type ColumnStatistics
• type Cost
• type HistogramBucket
• type IndexStatistics
• type Optimizer
  • func NewOptimizer() *Optimizer
  • func (o *Optimizer) ChooseIndex(tableName string, where sql.Expression, ...) (string, PlanType)
  • func (o *Optimizer) EstimateCost(tableName string, rowCount uint64, indexStats *IndexStatistics, ...) Cost
  • func (o *Optimizer) EstimateRows(tableName string, rowCount uint64, selectivity float64) uint64
  • func (o *Optimizer) EstimateSelectivity(tableName string, column string, op sql.BinaryOp, value types.Value, ...) float64
  • func (o *Optimizer) GetStatistics(tableName string) *Statistics
  • func (o *Optimizer) ShouldUseIndex(tableName string, rowCount uint64, indexStats *IndexStatistics, ...) bool
  • func (o *Optimizer) UpdateStatistics(tableName string, stats *Statistics)
• type PlanType
  • func (p PlanType) String() string
• type Statistics
  • func (s *Statistics) EstimateColumnSelectivity(column string, op string, value types.Value) float64

Constants

const SelectivityThreshold = 0.3

SelectivityThreshold is the threshold for using an index.

Functions

func CalculateSelectivityFromConditions

func CalculateSelectivityFromConditions(selectivities []float64) float64

CalculateSelectivityFromConditions calculates overall selectivity from multiple conditions.

func IsLowSelectivity

func IsLowSelectivity(selectivity float64) bool

IsLowSelectivity returns true if the selectivity is below the threshold.

Types

type AnalyzeTable

type AnalyzeTable struct {
	Stats *Statistics
}

AnalyzeTable analyzes a table and collects statistics.

func NewAnalyzeTable

func NewAnalyzeTable() *AnalyzeTable

NewAnalyzeTable creates a new analyzer.

func (*AnalyzeTable) AddRow

func (a *AnalyzeTable) AddRow(columns []string, values []types.Value)

AddRow adds a row to the statistics.

func (*AnalyzeTable) BuildHistogram

func (a *AnalyzeTable) BuildHistogram(column string, values []types.Value, numBuckets int)

BuildHistogram builds a histogram for a column.

func (*AnalyzeTable) Finalize

func (a *AnalyzeTable) Finalize() *Statistics

Finalize completes the analysis and returns the statistics.

func (*AnalyzeTable) SetIndexStatistics

func (a *AnalyzeTable) SetIndexStatistics(name string, columns []string, distinctKeys uint64, height int, clustered bool)

SetIndexStatistics sets statistics for an index.

type ColumnStatistics

type ColumnStatistics struct {
	Name          string
	DistinctCount uint64
	NullCount     uint64
	MinValue      types.Value
	MaxValue      types.Value
	Histogram     []HistogramBucket
}

ColumnStatistics represents statistics for a column.

type Cost

type Cost struct {
	IOCost      float64 // Disk I/O cost
	CPUCost     float64 // CPU cost
	TotalCost   float64 // Total cost
	Cardinality uint64  // Estimated number of rows
}

Cost represents the estimated cost of a query operation.

type HistogramBucket

type HistogramBucket struct {
	LowerBound    types.Value
	UpperBound    types.Value
	DistinctCount uint64
	RowCount      uint64
}

HistogramBucket represents a bucket in an equi-height histogram.

type IndexStatistics

type IndexStatistics struct {
	Name         string
	Columns      []string
	DistinctKeys uint64
	Clustered    bool // True for primary key
	Selectivity  float64
	Height       int
	LeafPages    uint64
}

IndexStatistics represents statistics for an index.

type Optimizer

type Optimizer struct {
	// contains filtered or unexported fields
}

Optimizer provides query optimization.

func NewOptimizer

func NewOptimizer() *Optimizer

NewOptimizer creates a new optimizer.

func (*Optimizer) ChooseIndex

func (o *Optimizer) ChooseIndex(tableName string, where sql.Expression, availableIndexes map[string]*IndexStatistics) (string, PlanType)

ChooseIndex selects the best index for a query.

func (*Optimizer) EstimateCost

func (o *Optimizer) EstimateCost(tableName string, rowCount uint64, indexStats *IndexStatistics, selectivity float64) Cost

EstimateCost estimates the cost of different execution plans.

func (*Optimizer) EstimateRows

func (o *Optimizer) EstimateRows(tableName string, rowCount uint64, selectivity float64) uint64

EstimateRows estimates the number of rows returned by a predicate.

func (*Optimizer) EstimateSelectivity

func (o *Optimizer) EstimateSelectivity(tableName string, column string, op sql.BinaryOp, value types.Value, stats *Statistics) float64

EstimateSelectivity estimates the selectivity of a predicate. Returns a value between 0 and 1 representing the fraction of rows that match.

func (*Optimizer) GetStatistics

func (o *Optimizer) GetStatistics(tableName string) *Statistics

GetStatistics returns statistics for a table.

func (*Optimizer) ShouldUseIndex

func (o *Optimizer) ShouldUseIndex(tableName string, rowCount uint64, indexStats *IndexStatistics, selectivity float64) bool

ShouldUseIndex decides whether to use an index based on cost estimation.

func (*Optimizer) UpdateStatistics

func (o *Optimizer) UpdateStatistics(tableName string, stats *Statistics)

UpdateStatistics updates statistics for a table.

type PlanType

type PlanType int

PlanType represents the type of execution plan.

const (
	PlanTypeTableScan PlanType = iota
	PlanTypeIndexScan
	PlanTypeIndexRangeScan
	PlanTypeIndexPointLookup
)

func (PlanType) String

func (p PlanType) String() string

String returns the string representation of the plan type.

type Statistics

type Statistics struct {
	RowCount    uint64
	ColumnStats map[string]*ColumnStatistics
	IndexStats  map[string]*IndexStatistics
}

Statistics represents table and index statistics.

func (*Statistics) EstimateColumnSelectivity

func (s *Statistics) EstimateColumnSelectivity(column string, op string, value types.Value) float64

EstimateColumnSelectivity estimates selectivity using histogram.