PSquare: practical quantiles

0. Motivation

Recently I’ve started to notice an interesting pattern. When you take something you thought was simple and look deep inside with a magnifying glass, it usually opens the whole new world of fascinating discoveries. It could be one of the principles of the universe, or just me overreacting on simple things. In any case one of such examples I wanted to share in this blog post, I hope it will bring the same joy to the readers as it did to me. Let’s talk about quantiles!

How many engineers does it take to make subscripting work?

Are you tired of this syntax in PostgreSQL?

SELECT jsonb_column->'key' FROM table;
UPDATE table SET jsonb_column =
            jsonb_set(jsonb_column, '{"key"}', '"value"');

The select part is actually fine. But for updates, especially for complex updates, it could be pretty verbose and far from being ergonomic. What would you say to this syntax instead?

SELECT jsonb_column['key'] FROM table;
UPDATE table SET jsonb_column['key'] = '"value"';

Evolution of tree data structures for indexing: more exciting than it sounds

0. How to read me?

I have to admit, my research blog posts are getting longer and longer. From one side I find it genuinely encouraging, because if one gets so much information just by scratching the topic, imagine what’s hidden beneath the surface! One university professor once said “what could be interesting in databases?”, and it turns out freaking a lot! On the other side it certainly poses problems for potential readers. To overcome them I would suggest an interesting approach: print this blog post out, or open it on your tablet/e-reader, where you can make notes with a pencil or markers. Now while reading it try to spot ideas particularly exciting for you and mark them. Along the way there would be definitely some obscure parts or questions, write them on the sides as well. You can experiment with the diagrams, changing or extending them, or just drawing funny faces. But do not read everything at once, have no fear of putting it aside for a while, and read in chunks that are convenient for you. Some parts could be skipped as the text is build out of relatively independent topics. The table of contents can help and guide you. Having said that we’re ready to embark on the journey.

• Introduction
• RUM conjecture
• B-tree basics
• Beyond the hard leavers of basics
  • Key normalization
  • Prefix truncation
  • Dynamic prefix truncation
  • Suffix truncation
  • Indirection vector
  • SB-tree
• Why is it not enough?
  • Partitioned B-tree
  • Hybrid indexes
  • Bw-Tree
  • DPTree
• Trie
• Learned indexes
• Is that all?
• References

1. Introduction

Whenever we speak about indexes, especially in PostgreSQL context, there is a lot to talk about: B-tree, Hash, GiST, SP-GiST, GIN, BRIN, RUM. But what if I tell you that even the first item in this list alone hiding astonishing number of interesting details and years of research? In this blog post I’ll try to prove this statement, and we will be concerned mostly with B-tree as a data structure.

Query optimizer and chess?

Do not be afraid, this short blog post is about databases and does not contain any unreasonable metaphysical references. In fact, it’s a result of a journey through couple of whitepapers and books with an unexpected intersection of two rather different fields. I will try to describe everything step by step, so that we can see if chess has anything in common with database query optimizer.