4 ms·

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) basica

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.

exabrial 4y ago
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.
- simscitizen 4y ago
  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.

exabrial 4y ago

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.

simscitizen 4y ago
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.