doc/indexing.md
以下优化算法基于个人当前理解，能力有限，如有偏颇还请斧正。
SELECT * FROM tbl WHERE a = 123;
SELECT * FROM tbl WHERE a = 123 AND b = 456;
SELECT * FROM tbl WHERE a IS NULL;
SELECT * FROM tbl WHERE a <=> 123;
SELECT * FROM tbl WHERE a IS TRUE;
SELECT * FROM tbl WHERE a IS FALSE;
SELECT * FROM tbl WHERE a IS NOT TRUE;
SELECT * FROM tbl WHERE a IS NOT FALSE;
SELECT * FROM tbl WHERE a IN ("xxx"); -- IN单值
思考：对于多列非等值，为filtered最小列加索引可能比较好。因为输入可变，所以现在只按散粒度排序。对于高版本MySQL如果开启了Index Merge，考虑为非等值列加单列索引可能会比较好。
SELECT * FROM tbl WHERE a >= 123 -- <, <=, >=, >, !=, <>
SELECT * FROM tbl WHERE a BETWEEN 22 AND 44; -- NOT BETWEEN
SELECT * FROM tbl WHERE a LIKE 'blah%'; -- NOT LIKE
SELECT * FROM tbl WHERE a IS NOT NULL;
SELECT * FROM tbl WHERE a IN ("xxx"); -- IN多值
等值查询优化为等值列添加索引非等值查询优化的列追加在等值列索引后SELECT * FROM tbl WHERE c = 9 AND a > 12 AND b > 345; -- INDEX(c, a)或INDEX(c, b)
如果使用了OR操作符，即使OR两边是简单的查询条件也会对优化器带来很大的困难。一般对OR的优化需要依赖UNION ALL或Index Merge等多索引访问技术来实现。SOAR目前不会对使用OR操作符连接的字段进行索引优化。
GROUP BY相关字段能否加入索引列表需要依赖WHERE子句中的条件。当查询指定了WHERE条件，在满足WHERE子句只有等值查询时，可以对GROUP BY字段添加索引。当查询未指定WHERE条件，可以直接对GROUP BY字段添加索引。
ORDER BY相关字段能否加入索引列表需要依赖WHERE子句和GROUP BY子句中的条件。当查询指定了WHERE条件，在满足WHERE子句只有等值查询且无GROUP BY子句时，可以对ORDER BY字段添加索引。当查询未指定WHERE条件，在满足无GROUP BY子句时，可以对ORDER BY字段添加索引。
对于使用了IN，EXIST等词的SUBQUERY或UNION类型的SQL，先将其拆成多条独立的SELECT语句。然后基于上面简单查询索引优化算法，对单条SELECT查询进行优化。SUBQUERY的连接列暂不考虑添加索引。
SELECT * FROM film WHERE language_id = (SELECT language_id FROM language LIMIT 1);
1. SELECT * FROM film;
2. SELECT language_id FROM language LIMIT 1;
SELECT * FROM city a LEFT JOIN country b ON a.country_id=b.country_id
UNION
SELECT * FROM city a RIGHT JOIN country b ON a.country_id=b.country_id;
1. SELECT * FROM city a LEFT JOIN country b ON a.country_id=b.country_id;
2. SELECT * FROM city a RIGHT JOIN country b ON a.country_id=b.country_id;
如下类型的查询条件无法使用索引或SOAR无法给出正确的索引建议。
-- MySQL无法使用索引
SELECT * FROM tbl WHERE a LIKE '%blah%';
SELECT * FROM tbl WHERE a IN (SELECT...)
SELECT * FROM tbl WHERE DATE(dt) = 'xxx'
SELECT * FROM tbl WHERE LOWER(s) = 'xxx'
SELECT * FROM tbl WHERE CAST(s …) = 'xxx'
SELECT * FROM tbl where a NOT IN()
-- SOAR不支持的索引建议
SELECT * FROM tbl WHERE a = 'xxx' COLLATE xxx -- vitess语法暂不支持
SELECT * FROM tbl ORDER BY a ASC, b DESC -- 8.0+支持
SELECT * FROM tbl WHERE `date` LIKE '2016-12%' -- 时间数据类型隐式类型转换
由于索引长度受数据库版本及不同配置参数影响，参考InnoDB限制。这里将索引长度限制定义为可配置值，用户可以根据实际情况进行设置。
ALTER TABLE `sakila`.`film_text` add index `idx_description` (`description`(255)) ;
SOAR支持将DELETE， UPDATE， INSERT， REPLACE四种类型语句转换为SELECT查询。对转换后的SELECT查询进行索引优化。以下为转换示例。
UPDATE film SET length = 10 WHERE language_id = 20;
SELECT * FROM film WHERE language_id = 20;
DELETE FROM film WHERE length > 100;
SELECT * FROM film WHERE length > 100;
INSERT INTO city (country_id) SELECT country_id FROM country;
SELECT country_id FROM country;
REPLACE INTO city (country_id) SELECT country_id FROM country;
SELECT country_id FROM country;
Cardinality = ColumnDistinctCount/TableTotalRows * 100%
由于直接对线上表进行COUNT(DISTINCT)操作会影响数据库请求执行效率，因此默认各列的散粒度均为1。用户可以通过指定-sampling参数开启数据采样。SOAR会将线上数据随机采样至测试环境求取散粒度。
以下说明摘抄自PostgreSQL数据直方图采样算法。默认k(-sampling-statistic-target)设置为100，即最多采样3万行记录。
The following choice of minrows is based on the paper
"Random sampling for histogram construction: how much is enough?"
by Surajit Chaudhuri, Rajeev Motwani and Vivek Narasayya, in
Proceedings of ACM SIGMOD International Conference on Management
of Data, 1998, Pages 436-447. Their Corollary 1 to Theorem 5
says that for table size n, histogram size k, maximum relative
error in bin size f, and error probability gamma, the minimum
random sample size is
r = 4 * k * ln(2*n/gamma) / f^2
Taking f = 0.5, gamma = 0.01, n = 10^6 rows, we obtain
r = 305.82 * k
Note that because of the log function, the dependence on n is
quite weak; even at n = 10^12, a 300*k sample gives <= 0.66
bin size error with probability 0.99. So there's no real need to
scale for n, which is a good thing because we don't necessarily
know it at this point.
随机采样使用的SQL如下，其中变量r, n的含义见上面的说明。
SELECT * FROM `tbl` WHERE RAND() < r LIMIT n;