News for hackers. Stuff that matters.
Re:Why do database columns have a character length of 191? by shadowgovt on Monday May 17, 2021 @03:27PM (#27187306)
Newbie database question:

I'm surprised the database cares at all about field length for indexing purposes, because I'd assume for indexing purposes it would hash the field and be done with it; a hash is a great tool for doing quick equality-comparisons.

Is this not sufficient because the index also needs to support sorting, so the original values matter to high resolution?

Re:Why do database columns have a character length of 191? by masklinn on Monday May 17, 2021 @04:14PM (#27187900)
Databases use btree indices for two reasons:

1. They provide much better locality and updatability, because databases would historically get the data from extremely slow IO (spinning rust) btrees are a great fit, they're also extremely predictable (search, insert, and delete work in O(log n)).

2. hash indices only support exact matches, btrees support prefix and range matching, and they are ordered, so when all the stars align you don't even need to touch the data pages, you can serve an entire query by just reading the index.

Most databases allow opt-in hash indexes (and even other more complicated forms of indexes), but these are either much less flexible (hash) or much more expensive (gist/gin). The btree remains an excellent default.

Re:Why do database columns have a character length of 191? by TazeTSchnitzel on Monday May 17, 2021 @06:31PM (#27189215)
Prefixes are a neat trick. One nice consequence is that an index for the column pair (a, b) is also an index for (a).
Re:Why do database columns have a character length of 191? by branko_d on Tuesday May 18, 2021 @02:11PM (#27198726)
And if the cardinality of a is low, it can even be an index for b! This is called “skip scan”.

Oracle has supported this for a long time, and apparently newer versions of MySQL as well.

Re:Why do database columns have a character length of 191? by masklinn on Tuesday May 18, 2021 @07:49AM (#27193466)
Yup, also that `like ‘foo%’` can use the index.
Re:Why do database columns have a character length of 191? by throwaway81523 on Monday May 17, 2021 @03:33PM (#27187385)
Hash indexing is sometimes used, but B-trees are more common so you can select with ORDER BY and also because you can insert additional records as many times as you want, by splitting nodes now and then, but never having to rehash the whole index.
Re:Why do database columns have a character length of 191? by ericyan on Monday May 17, 2021 @04:08PM (#27187818)
Hash index is only useful for exact matches, a full table scan would be required for any other kinds of queries. That is why most database engines have settled with B+ tree.

Regardless the type of index, field length still matters if you care about performance. Smaller fields and smaller indices means you can fits more things (the working set) in RAM and less I/O when you have to hit disks.

Re:Why do database columns have a character length of 191? by zeroimpl on Monday May 17, 2021 @07:32PM (#27189639)
Hash tables perform poorly when they need to be resized periodically as the table grows (as everything needs to get rehashed). Using a tree structure instead ensures consistent performance.