Hacker News Reader

Comment by simscitizen | Hacker News Reader

The obvious answer is that there are certain queries that cannot be made fast with normal indices. What index would you suggest for these queries?

  SELECT * FROM Foo WHERE Bar != 42;
  SELECT * FROM Baz WHERE x > 42 ORDER BY y DESC LIMIT 10

The usual solution is to constrain the query language in some way to prevent users from issuing queries that can't be satisfied efficiently using an index. If you are disciplined enough to do that then you can probably pretty easily suggest (or even automatically generate) indices for your users based on query patterns.

View on HN

If most of the Foo table has Bar=42, an index on Bar works, or you may have to rewrite the query as (Bar < 42 or Bar > 42) on some DBs. If Bar=42 is just a few rows then yeah it's best to do a table scan.

For the second query, an index on (y, x) is very good most of the time. You would use the natural sort order of the index, and prune x <= 42 rows from the result set by only using the index. If almost all of the table is x <= 42 it's better to index on x, have it sort everything and throw away beyond the limit. Although if you are specifying a limit just for pagination, then it's decent to get e.g. the Nth element from the y sort order, and then only query where (y > ? and y <= ? and x > 42), possibly with a different limit and some other clauses if y is not unique.

I feel like these types of queries are basically non-existent in OLTP though. If you are going to block expensive queries, knowing the queries ahead of time makes it a lot easier.

> I feel like these types of queries are basically non-existent in OLTP though.

The second query feels pretty normal in any system that has filters and sorting on a collection.

SELECT * FROM Foo WHERE Bar != 42; if Bar was an INT and had a high density (1/distinct values) then a columnstore index on Bar might perform faster than a per-row index. Worth trying out as it isn't certain and would depend on row cardinality.

SELET * FROM Baz WHERE x > 42 ORDER BY y DESC LIMIT 10; a per-row index on x should in theory seek all values above 42 rather than perform an index/table scan, and the ordering and row limitation would be processed last i.e. in the SELECT. Again, not certain though.

SQL Server already has the missing_index_stats DMVs which can suggest indexes based on previous query use, and generating frequency diagrams / histograms based on previous queries run is relatively straightforward and would contribute to any index suggestion engine.

I don't think either of this would be difficult:

For the first, if the 42 value is fixed, you can actually make that query quite fast. In MySQL you could create a functional index for the boolean condition and quickly find all the rows that don't meet that criteria. Basically all the rows are sorted at insert and your query would take ms (constant time).

For the second, even if the 42 is not fixed, you could create a composite index for X, and Y DESC and get very acceptable results (log time).

The 42 was meant to be a placeholder in the examples. Imagine it is a ? and bound at runtime instead.

In the second query, a composite index over (x, y) basically does the same job as an index over just x. The general query plan is to iterate over all values > x and keep the 10 smallest values around in memory to satisfy the ORDER BY.

The point is that there are many queries that seem deceptively simple but are actually extremely hard or even impossible to automatically index. Those queries which result in table scans, large index scans, and large sorts can easily dominate all the other queries which are easily indexable in terms of resource usage.

Gotcha. Yeah, you'd definitely be constrained to log time, though with proper bucket sizing it'd be manageable if the values were more bounded. For large datasets, there's just not a real good way to make this fast if you need an _exact_ answer. If you can deal with a probabilistic answer there's faster methods.

So basically I realize there are ways to generate index suggestions (or even generate indices automatically) by observing query patterns, keeping stats on cardinality of various columns, etc. We actually did that at Parse; we would observe query patterns and generate indices (including compound indices) at runtime that seemed to benefit the application's query pattern. There wasn't an option for this, it was just enabled by default.

However we ran into the problem that users still made many queries which were essentially impossible to index. On many of the DB nodes, the resources used by these unindexable queries dominated the resources used by all of the easily indexed queries.

I left the experience thinking that there really wasn't any good solution to the problem for general users other than making the query language force users to only make queries that can be obviously satisfied by common index types.

Reply on news.ycombinator.com