Hacker News new | ask | show | jobs
by gz09 106 days ago
That would be surprising to me if anyone would think this is novel.

Using bitmaps to indicate whether things are in-use or not is very common in systems programming. Like you said PG does it, but most other systems do this too. It's not specific to databases: in an operating system, one of the first thing it needs is an allocator, the allocator most likely will use some bitmap trick somewhere to indicate what's free vs. what's available etc.
1 comments
SigmundA 106 days ago
Interesting so you don't find it odd that an article about the storage engine of a SQL database system explains the solution to problem without once mentioning that it is the way most other sql database engines solve it? It is mentioned several times sql table are typically sparse, but not that this is how its typically solved, only this is how you solved it...

>The fix is simple: we stop storing Option<T> and instead we store a bitmap that records which fields are None.

Right here would have been the opportunity to let those not familiar with database internals know. Something like "This technique has been widely used in many RDBMS systems over the years, you can see the PG version of this in their documentation for page layout".

Instead you go into detail on what a null bitmap is and how to implement it, calling it a "trick". Which is strange if you think your target audience is assumed to already know this common technique.

I mean not one mention of the origin of the trick or even calling it a common solution to this problem...

link
gz09 106 days ago
> not one mention of the origin of the trick

And who or what would you say is the origin? The "trick" is so old I'm afraid it is lost to time to say who invented the bitmap. It was used in MULTICS or THE long before PostgreSQL was invented.

link
SigmundA 106 days ago
There is a lot of space between no acknowledgment at all like this article and tracing down the exact origin of who and when invented to null bit map in what system.

Your version comes off as self promotion, going into detail how to implement a the technique with out once calling it a common technique or even mentioning its widely used in the industry to solve the problem you are solving.

It would be like saying finding rows in storage is slow so we implemented a b-tree in a separate structure for certain columns and go into detail how to create a b-tree, calling it a "trick" while never once acknowledging the is the most common form of indexing in RDBMS's, would you understand how this would seem strange?

link