Discovering the Computer Science Behind Postgres Indexes

http://blog.codeship.com/discovering-computer-science-behind-postgres-indexes/

by kilimchoi • 11 years ago

105 21 11 years ago

blog.codeship.com

I'm always at a loss.

"indices is generally preferred in mathematical, financial, and technical contexts, while indexes is relatively common in general usage"

fmela• 11 years ago

I think of "indices" as the plural of index and "indexes" as a present verb meaning to index (e.g. the "the background process indexes the tables").

thaumasiotes3• 11 years ago

This isn't hard to explain -- most people producing "general usage" don't know Latin and nearly never refer to even a singular index.

duaneb2• 11 years ago

Different languages have different plurals. Both are accepted because of the history of using latin suffixes (i.e. indices) and because it is the correct way to pluralize regular noun (i.e. indexes). This is the same reason "iris" has three accepted plurals: iris (genitive, from common use and genus name), irises (english plural), and irides (latin plural).

thaumasiotes3• 11 years ago

Something's gone wrong here. If iris is the genitive, no plural form can be irides. (Also, I tend to think of iris as being from Greek, although apparently the English word does come from a Latin borrowing.)

Cieplak• 11 years ago

If this interests you, I highly recommend exploring the documentation in the postgres source:

https://github.com/postgres/postgres/tree/master/src/backend...

https://github.com/postgres/postgres/blob/master/src/backend...

nodesocket• 11 years ago

Bravo for the amazingly detailed writeup. I know how long these things can take, and give kudos to the author.

grey• 11 years ago

I've wanted something like this for years! A great real world example of a data structure that really made an impression on me during my computer science education, connecting theory to implementation

patmcguire• 11 years ago

Am I correct in thinking that if it weren't for the order-by statement in the first query, it would have stopped after the first occurrence?

vampirechicken2• 11 years ago

No. Without any indication that the value in that column is unique the query engine must read the entire table in order to insure that it has found every row that meets the search criteria.

thaumasiotes3• 11 years ago

But the original query includes "limit 1". Why is it necessary to find every row meeting the search criterion? Only one will be returned, and without an ORDER BY clause it doesn't matter which one.

StavrosK• 11 years ago

It seems that way to me, certainly.

mrinterweb2• 11 years ago

"The term B-Tree actually stands for “balanced tree.”"

B-tree means "binary tree" and are not inherently balanced. There are plenty of specific types of self balancing tree algorithms, but I believe the default implementation of b-trees by definition are not self-balanced.

Edit: this comment is incorrect. There is a difference between b-trees and binary trees.

msluyter• 11 years ago

The wikipedia article on b-trees suggests a variety of possibilities for the etymology, "binary" not really being one of them:

After a talk at CPM 2013 (24th Annual Symposium on Combinatorial Pattern Matching, Bad Herrenalb, Germany, June 17–19, 2013), Ed McCreight answered a question on B-tree's name by Martin Farach-Colton saying: "Bayer and I were in a lunch time where we get to think a name. And we were, so, B, we were thinking… B is, you know… We were working for Boeing at the time, we couldn't use the name without talking to lawyers. So, there is a B. It has to do with balance, another B. Bayer was the senior author, who did have several years older than I am and had many more publications than I did. So there is another B. And so, at the lunch table we never did resolve whether there was one of those that made more sense than the rest. What really lives to say is: the more you think about what the B in B-trees means, the better you understand B-trees."[3]

https://en.wikipedia.org/?title=B-tree#Etymology

mrinterweb2• 11 years ago

I was confused. The wiki article says at the top "Not to be confused with Binary tree." Then in the first paragraph:

"The B-tree is a generalization of a binary search tree in that a node can have more than two children (Comer 1979, p. 123). Unlike self-balancing binary search trees, the B-tree is optimized for systems that read and write large blocks of data."

Long ago in one of my CS classes, I wrote binary tree, 2-3, 2-3-4, red black, and AVL tree algorithms. So I guess I learned about binary vs self-balancing. I did not know about b-trees. I made the mistake of thinking that b-tree meant binary tree.

calinet6• 11 years ago

One of the best classes I took in college CS was the database class, where we dove into the internals of Postgres and learned how the core CS concepts we had learned the year prior applied in real life. It was a great lightbulb moment that solidified the education unexpectedly well, in hindsight. And of course, gave me great respect for the code quality and rigor of the Postgres system.

patzerhacker• 11 years ago

In my undergrad CS class we had to write a small RDBMS using the techniques learned in class and then had to dive into the internals of Postgres. It remains my favorite class taken during my undergrad, followed closely by the graduate level computer graphics course I was able to take.

petergeoghegan• 11 years ago

"""B-Link-Trees: Lehman and Yao’s paper actually discusses an innovation they researched related to concurrency and locking when multiple threads are using the same B-Tree. Remember, Postgres’s code and algorithms need to be multithreaded because many clients could be searching or modifying the same index at the same time. By adding another pointer from each B-Tree node to the next sibling node — the so-called “right arrow” — one thread can search a tree even while a second thread is splitting a node without locking the entire index"""

The big innovation of Lehman and Yao was that their right link technique obviates the need for "latch coupling", or in Postgres terms the crabbing of buffer locks. In other words, the Postgres implementation need only lock one page/buffer at a time as an index scan descends the B-Tree, rather than alternately locking a single page, then its child, then unlocking the parent, and once again locking the child (the grandchild of the original page). Certain other B-Tree implementations must do this until their descent reaches a leaf page, and locking multiple pages at once just to service index scans can hurt concurrency a lot (I think that they might need to be exclusive locks for writes, which is particularly poor).

These low-level locks are not to be confused with lock manager locks that have deadlock detection and so on. They're low-level Readers–writer locks, and are far more lightweight (hence the Postgres term "LWLock").

The basic idea of Lehman and Yao is that index scans of all types may detect and recover from a concurrent page split my following a right-link (having found that the page high key is logically less than the scankey value). It won't matter that the parent page was observed to not have the new downlink that is inserted after a page split, except that we need to look right.

Discovering the Computer Science Behind Postgres Indexes

Related Stories