sql: analyze where conditions to avoid full table scans in SELECT

[petermattis]

Processing of SELECT statements currently always performs a full table scan. We need to analyze the where condition to determine restrictions that allow for partial scans or individual row lookups. The analysis would look for restrictions on a prefix of the primary key (the only supported index at the moment). Retrieval of individual rows will also have to take into account the columns needed by the select expression.

[veteranlu]

Mysql has condition pushdown and index condition pushdown optimization, these avoid reading full rows corresponding to all tuples that do not match the condition.

[veteranlu]

Mysql condition pushdown:
http://dev.mysql.com/doc/refman/5.6/en/index-condition-pushdown-optimization.html
http://dev.mysql.com/doc/refman/5.6/en/condition-pushdown-optimization.html

[petermattis]

@veteranlu The condition pushdown optimization is a bit different from what this issue is in reference to which is basic support for using indexes to avoid full table scans. I'll have to read those docs further, but it sounds similar to filtering functionality I'd like to add the basic KV ScanRequest. Essentially, I want to add an optional `filter' expression that can restrict what key/value pairs are returned from a scan.

[petermattis]

The SQLite documentation on their query planner gives a decent overview of when indexes can be used: https://www.sqlite.org/queryplanner.html