On Tue, 19 May 2015 20:44:17 +0000 Eric Hill <Eric.Hill at jmp.com> wrote:
> But then what about a query like this: > > SELECT * FROM T1 > LEFT OUTER JOIN T2 ON ( T2.a = T1.a ) AND ( T2.b = > T1.b ) AND ( T2.c = T1.c ); > > xBestIndex will get called here for T1 with 3 constraints, c, b, and > a, in that order. In this case, though, it seems (to the > uninitiated, at least ;-) that the "best index" would be: > > CREATE INDEX T1_all ON T1 (c, b, a); Given that query, any index that includes a, b, and c would serve equally well. The order of the criteria in the ON clause is immaterial. > I guess xBestIndex is saying "Tell me about indexes that you already > have available so I can take advantage of them", Right. > I have *no* indexes, but I am willing to make whatever indexes would > be most helpful, if I could just figure that out. Depending on the physical characteristics of thing you're representing as a virtual table, you might not want any indexes. If every access requires either a sequential scan or a random access to computed location, all search criteria are either perfect or inconsequential. If that's fast enough, it's fast enough. If you want to make it faster, indexes are certainly an option. Don't start by guessing, though. Rather than beginning by trying to anticipate what the query-generation tool will produce (and thus what xBestIndex combinations will be interrogated), it's better to put the horse before the cart and consider the data. Once you've characterized your data, you apply that information to that supplied by xBestIndex. If you have a table in 1NF, you have a key. What are the columns that identify a row? That's your primary key, and your first index. There may be other sets of columns that uniquely identify a row; these also could use an index to enforce/verify uniqueness. Suppose your primary key is {a,b,c} and you want to construct an index for it. At this point I start will talking out of school, because I don't know anything about the SQLite query planner. But if I go astray I'm sure others will correct me. The choice of the first column in the index is the main concern, and it is influenced by the dominant search criteria i.e., the kinds of queries that will be submitted. Queries in general are of two kinds: point queries, returning one row (specifying values for every column in the index), and range queries (specifying an incomplete set of values for the index). Point queries are indifferent to column order: find row in index and return. Range queries are the interesting ones. In a B+ tree such as SQLite uses for its indexes, rows will be sorted in column order. If your index is {a,b,c}, all the "a" rows will be together and all the "b" columns within those "a"'s, and so on. When the query says, where a between x and y the I/O engine can scoop all the row references out of contiguous pages in the index. Whereas if the query says, where b between x and y the index is all but useless. Because it's sorted by "a", it would have to be scanned from beginning to end to find all the "b"'s that meet the criteria. The other important criterion to answering xBestIndex, as Hick mentioned, is cardinality. You can create for each column a histogram of the frequency distribution for the values in that column. If the column domain is two values (e.g., 'male' and 'female'), for example, the probability of it matching a queried value X might be 50%. (I think I read that at Google 4 employees in 5 are men, in which case there a value of 'female' would be a much more useful 20%.) You can use the combination of selective cardinality and your intuition (or experience) for probable search criteria to create other indexes. Your answer to xBestIndex will be based on the product of the selectivity of the contiguous columns (starting from the first) in the applicable index. Cardinality is only one part of the equation, however; the other is the operator. Equality is at least an opportunity for a point query, but inequality implies a range. How big a range? If we're talking about ages, for example, where age > x If X is 0, that's not very useful, whereas if X is 100, it's very selective of human beings (assuming age is in years). Problem is, X isn't supplied (for good reason) to xBestIndex. How to answer? You can only work with what you know: the cardinality of the column, the operator, and the rowcount. Rows and cardinality you know, and they apply directly to equality comparisons. For inequality, you need a heuristic. A quarter of a century ago, during the Late Bronz Age, Sybase used a simple heuristic: every inequality selected 25% of the table. That meant a BETWEEN query (two inequalities) was 6.25% = 0.25 * 0.25. I doubt they pulled that number out of a hat. Absent better information, that might be your best option. I hope that's of some use. Complicated, for sure, and no small amount of work. Welcome to the woolly world of query optimization. --jkl