3 ms·
A hash table isn't much use for queries that return multiple rows, or use aggregate functions. (SELECT avg(price) FROM sales WHERE date_trunc('month', timestamp
by andrewf 17y ago
A hash table isn't much use for queries that return multiple rows, or use aggregate functions. (SELECT avg(price) FROM sales WHERE date_trunc('month', timestamp) = '2009-06-01').
Not only can a b-tree locate the edges of such a range, but if you're accessing k rows from an n-row table, your index access time is O(k + log(n)) with k quickly becoming the dominant factor.
Even when you're accessing one row per query, these queries will often be favouring a particular cluster of row, rather than being perfectly evenly distributed over the table. In such cases a b-tree will provide better locality of reference; you'll hit cached data in memory rather than disk far more often.
- neilc 17y agoA hash table isn't much use for queries that return multiple rows, or use aggregate functions. Neither of those claims is true. A hash index is perfectly useful for queries that return multiple rows: the index just stores all the duplicate values for the search predicate in the matching hash bucket. And hash indexes can certainly be used with aggregate functions: you first use the hash index to evaluate the query predicate (WHERE clause), and then you evaluate the aggregation or grouping clause over the results of the hash index.
- andrewf 17y agoSorry, I should have been clearer here. I was referring to queries with range predicates. Your counterexamples are true where all the returned/aggregated rows have the same indexed value; it may make sense to hash index under such circumstances, but b-trees are a more sensible default. I guess you could also have a situation where a range predicate maps nicely to a proportionate number of hash buckets. I don't know if any databases are clever enough to do this.