# TableStatistics

## Farrago Table Statistics

A table's statistics are a compact summary of the table's contents. They allow the optimizer to estimate the cost of reading the table when applying a filter. For example, it is possible to directly estimate the cost for the following query.

```select * from sales where sales.region in ('WEST', 'NORTH');
```

Table statistics are collected upon the execution of DDL statements. To keep the implementation clean, statistics are not updated by DML statements.

```ANALYZE TABLE FRED
COMPUTE STATISTICS
[ FOR ALL COLUMNS | FOR COLUMNS (a,b,c) ]
ANALYZE TABLE FRED
ESTIMATE STATISTICS
[ FOR ALL COLUMNS | FOR COLUMNS (a,b,c) ]
[ SAMPLE n PERCENT ]
```

It is possible to COMPUTE STATISTICS based on all data or to ESTIMATE STATISTICS based upon a sample of the data. One may collect statistics for selected columns or for all columns.

The syntax (and internal model) support statistics collection on remote tables. However, this feature is initially deferred.

### Statistics collected

The following data are collected.

1. Number of rows in table, unless estimating and the current session personality maintains an up-to-date row count in FemAbstractColumnSet
2. For each index of a table, the number of pages used by the index, possibly via estimation
3. For each column, a histogram of values
4. The cardinality (number of distinct values) in each column

Cardinality is computed exactly when

1. Computing statistics. The cardinality falls trivially out of building a histogram of the complete column.
2. The column is a single-column primary key. The cardinality equals the row count.
3. The column has a single-column unique constraint and does not allow null values. The cardinality equals the row count.

Otherwise, cardinality is estimated. If a column has a single-column unique constraint, but allows null values, the number of nulls in the column is estimated and all other rows are assumed to contain distinct values. If a column is the first column specified in an index, the number of distinct values is computed from the index. If none of the previous cases is true, cardinality is estimated via the algorithms described in [1].

### Statistics interface

The interface for statistics is built into eigenbase. Any RelNode relation may be queried for it's statistics:

```public interface RelNode
{
...
/**
* Returns statistics for the RelNode or null if none exist
*/
public RelStatSource getStatistics();
...
}
```

Statistics are then accessed on a per column basis.

```public interface RelStatSource
{
/**
* Returns statistics for a projected column or null if
* no statistics exist for the column
*
* @param ordinal zero based column ordinal
*/
RelStatColumnStatistics getColumnStatistics(int ordinal);
}
```

Column statistics may be queried for selectivity, etc:

```public RelStatColumnStatistics
{
// returns the number of distinct values stored in the column
public Double getDistinctRowCount();
// returns the selectivity of a search parameter
public Double getSelectivity(
List<SargIntervalSequence> sargSeqList);
// returns the cardinality of a search parameter
public Double getCardinality(
List<SargIntervalSequence> sargSeqList);
}
```

Null is returned in cases of complete uncertainty. Otherwise, the best guess is returned. It may be helpful to report a "confidence level," though this is not supported yet. It may also be possible to estimate additional features such as min()/max(), though such features would be implementation specific.

Initially, it was thought the optimizer could access statistics through extended utility methods such as:

```// returns selectivity of
Double RexUtil.getSelectivity(RexNode, RelStatSource stats)
```

The upper levels of the optimizer interface are being redesigned to better work with multiple systems. RelationalExpressionMetadata describes the redesign.

(Farrago interface)

For Farrago, statistics are collected into the catalog model, as described below. RelStatSource is implemented by net.sf.farrago.catalog.FarragoTableStatistics. A Farrago RelNode, such as LcsRowScanRel, could return one of these corresponding to its catalog table.

```...
// constructor
public FarragoTableStatistics(FarragoRepos repos, FemAbstractTable table);
...
```

### Statistics model

Statistics are modeled directly as catalog fields. This allows for easy access to the data. Views may be built on top of the basic data. The data can be exported and loaded as catalog objects via stored procedure utilities which call MDR.

AbstractColumnSet:

1. rowCount - Long
2. analyzeTime - String

LocalIndex:

1. pageCount - Long
2. analyzeTime - String

ColumnHistogram

1. percentageSampled - Float
2. sampleSize - Long
3. distinctValueCount - Long
4. distinctValueCountEstimated - Boolean
5. barCount – Integer
6. rowsPerBar – Long
7. rowsLastBar – Long
8. analyzeTime - String
9. ColumnHasHistogram, a 1-to-0..1 composite relation from AbstractColumn

ColumnHistogramBar

1. startingValue – String
2. valueCount – Long
3. ordinal – Integer (0 based)
4. ColumnHistogramHasBar, a 1-to-many composite ordered relation

### Histograms encoding

The histogram is a strictly "equal depth" histogram, in which each bar of the histogram represents a fixed number of rows. Values can span bars. For example:

One could estimate the number of rows for a value by finding the upper and lower bound for the value, and finding the number of bars spanned. Values entirely contained within one bar would be given a portion of that bar:

Alabama: (2-1) = 1 bar (1.5 actual) Alaska: 1/2 = 0.5 bars (0.2 actual) Arizona: (4-2) = 2 bars (1.7 actual) Arkansas: (5-4) = 1 bar (0.9 actual) California: (16-5) = 11 bars (11 actual)

In effect, the result is accurate +/- one bar. Given 100 bars, this would be +/- 1% of the table. Smaller values would be less accurate, but larger values (more importantly) would be more accurate.

### Implementation

Histogram. A histogram helps to estimate the number of rows for each value. To generate a histogram, the following SQL is issued. Sampling is implemented via a sampling clause (see below). Cardinality is derived from the histogram.

```SELECT COLX, COUNT(*) FROM T GROUP BY COLX ORDER BY COLX
```

Row count.

```SELECT COUNT(*) FROM T
```

Page count. Analyze updates this for both clustered and unclustered indexes. The actual mechanism for computing the counts will be pluggable via a new method, computeIndexStats, on the interface FarragoMedLocalDataServer. If a distinct value count is required from the index, it is obtained via the same interface.

### Sampling

As part of this task, table sampling has been implemented as per the SQL2003 specification.

The histogram query becomes

```SELECT COLX, COUNT(*) FROM T TABLESAMPLE SYSTEM(P) GROUP BY COLX ORDER BY COLX
```

where P is the percentage given in the ANALYZE TABLE DDL. If left unspecified, the row count is used to select a percentage that will produce a sample large enough to be statistically valid.