# Log 2022-07-13
- [Fast Pagination in PostgreSQL](https://chrisdone.com/posts/postgresql-pagination/)
- [HaskellDB: A long tutorial](https://chrisdone.com/posts/haskelldb-tutorial/#fn3) - HaskellDB has a Query monad that does [[Relational Algebra]] and query planning
- [Functional Relational Algebra](https://docs.racket-lang.org/fra/index.html) in [[Racket]]
A series of books about relational algebra and something called [[Tutorial D]]. I'm unclear if these are good ideas, or something I should skip. I'll work my way through the intro.
- [The Third Manifesto - Documents and Books](https://www.dcs.warwick.ac.uk/~hugh/TTM/documents_and_books.html)
- [https://www.dcs.warwick.ac.uk/~hugh/TTM/DTATRM.pdf](https://www.dcs.warwick.ac.uk/~hugh/TTM/DTATRM.pdf) with Tutorial D
A data-parallel programming framework designed to efficiently process large volumes of data to quickly respond to arbitrary changes in input collections, [[Differential Dataflow]]:
- [Differential Dataflow (paper)](https://github.com/TimelyDataflow/differential-dataflow/raw/master/differentialdataflow.pdf)
- [GitHub - TimelyDataflow/differential-dataflow: An implementation of differential dataflow using timely dataflow on Rust.](https://github.com/TimelyDataflow/differential-dataflow)
How to build a tiny [[SQL]] [[Relational Databases]] in [[C]], with a lot of [[B-Tree]] work:
- [How Does a Database Work? | Let’s Build a Simple Database](https://cstack.github.io/db_tutorial/)
A long post by [[Jamie Brandon]] listing all the things that are quirky and annoying and bad about [[SQL]], putting things into perspective, especially as [[SQL]] is the only widespread implementation of [[Relational Algebra]] that we have in the industry:
- [Against SQL](https://www.scattered-thoughts.net/writing/against-sql/)
- [Some Were Meant for C](https://www.humprog.org/~stephen//research/papers/kell17some-preprint.pdf) on the endurance of the C programming language because it is "porous".
A page about the [[N+1 Problem]]:
- [◉ Performance: N+1 Query Problem](https://secure.phabricator.com/book/phabcontrib/article/n_plus_one/)
## Query Planning from Zulip
Here's a sketch of a Query planner by [[Jamie Brandon]] on a thread by [[Brian Hicks]]:
```elm
import Set
import Dict
import Array
type Constant
= String String
| Int Int
type Plan
= ReadTable { name: String }
| FilterConstant { input: Plan, column: Int, constant: Constant }
| Project { input: Plan, columns: Array.Array Int }
| Join { left: Plan, right: Plan, left_key_columns: Array.Array Int, right_key_columns: Array.Array Int }
| Difference { left: Plan, right: Plan }
type alias Relation = Set.Set (Array.Array Constant)
type alias Database = Dict.Dict String Relation
run_plan : Plan -> Database -> Relation
run_plan plan database =
case plan of
ReadTable { name } ->
case Dict.get database name of
Just relation -> relation
Nothing -> Set.empty -- TODO insert error handling here
FilterConstant { input, column, constant } ->
let
input_relation = run_plan input database
in
Set.filter (\ row -> (Array.get column row == constant)) input_relation
Project { input, columns } ->
let
input_relation = run_plan input database
in
Set.map (\ row -> Array.map (\ i -> Array.get i row) columns) input_relation
Join { left, right, left_key_columns, right_key_columns } ->
let
left_relation = run_plan left database
right_relation = run_plan right database
left_index =
Set.foldl
(\ left_row index ->
let
key = Array.map (\ i -> Array.get i left_row) left_key_columns
in
Dict.insert key left_row index)
Dict.empty
left_relation
in
right_relation.foldl
(\ right_row result ->
let
key = Array.map (\ i -> Array.get i right_row) right_key_columns
in
case Dict.get key left_index of
Just left_row -> Set.insert (Array.append left_row right_row) result
Nothing -> result)
Set.empty
Difference { left, right } ->
let
left_relation = run_plan left database
right_relation = run_plan right database
in
Set.diff left_relation right_relation
```
And two more links from [[Jamie Brandon]]:
- [materialize/mod.rs at main · MaterializeInc/materialize · GitHub](https://github.com/MaterializeInc/materialize/blob/main/src/expr/src/relation/mod.rs#L34-L224)
- [cockroach/plan.go at master · cockroachdb/cockroach · GitHub](https://github.com/cockroachdb/cockroach/blob/master/pkg/sql/plan.go#L139-L215)
Here is the Query planner that [[Brian Hicks]] ultimately wrote in his "bad-datalog":
- [brian/bad-datalog: A bad datalog, which hopefully will become better over time. Maybe someday it'll even be released as a package! - src/Datalog/Database.elm at main - bad-datalog - Git in the Bytes Zone](https://git.bytes.zone/brian/bad-datalog/src/branch/main/src/Datalog/Database.elm#L230)
- [Ryo Nakao](https://nakabonne.dev/posts/write-tsdb-from-scratch/)
## Kindle hacking
A page about hacking an old kindle, not exactly what I want as this just roots the kindle itself. Probably cool to keep the Kindle intact instead of taking it apart, and buying a proper E-Ink kit:
- [Turning an old Amazon Kindle into a eink development platform – adq](https://blog.lidskialf.net/2021/02/08/turning-an-old-kindle-into-a-eink-development-platform/)
A set of links about driving actual [[E-Ink]] displays:
- [Driving E-ink display – Essential scrap](http://essentialscrap.com/eink/)
This uses a $20 Waveshare 2.7 inch e-paper HAT:
- [Hacking Together an E-ink Dashboard — Andrew Healey](https://healeycodes.com/hacking-together-an-e-ink-dashboard)
- [Microsoft MakeCode for micro:bit](https://makecode.microbit.org/#editor)
## Links from coffee shop
- [https://www.lix.polytechnique.fr/Labo/Samuel.Mimram/teaching/INF551/course.pdf](https://www.lix.polytechnique.fr/Labo/Samuel.Mimram/teaching/INF551/course.pdf)
- [Distributed Tracing in Practice [Book]](https://www.oreilly.com/library/view/distributed-tracing-in/9781492056621/)
- [LMS: Program Generation and Embedded Compilers in Scala](https://scala-lms.github.io/)
- [https://www.cs.purdue.edu/homes/rompf/papers/rompf-icfp15.pdf](https://www.cs.purdue.edu/homes/rompf/papers/rompf-icfp15.pdf)
- [Building Efficient Query Engines in a High-Level Language](http://www.vldb.org/pvldb/vol7/p853-klonatos.pdf)
## Dev Log
![[Dev Log 2022-07-13]]
Some links about [[Structural Editing]]:
- [Structural Editing, a Guide for the Perplexed - Paulus Esterhazy - YouTube](https://www.youtube.com/watch?v=ubcERtDyLDw)
## More links about relational algebra
Links from criticism of [[Tutorial D]]:
- [set-bag-irrelevance](http://h2.jaguarpaw.co.uk/posts/set-bag-irrelevance/)
- [https://wiki.c2.com/?NewQueryLanguagesOnExistingEngines](https://wiki.c2.com/?NewQueryLanguagesOnExistingEngines)
- [https://wiki.c2.com/?BagAtational](https://wiki.c2.com/?BagAtational)
- [https://wiki.c2.com/?BagAtationalDiscussion](https://wiki.c2.com/?BagAtationalDiscussion)
- [https://wiki.c2.com/?DatabaseIsRepresenterOfFacts](https://wiki.c2.com/?DatabaseIsRepresenterOfFacts)
- [https://wiki.c2.com/?RelationalAlgebra](https://wiki.c2.com/?RelationalAlgebra)
- [https://wiki.c2.com/?BagSetImpedanceMismatch](https://wiki.c2.com/?BagSetImpedanceMismatch)
- [https://wiki.c2.com/?BagNeedScenarios](https://wiki.c2.com/?BagNeedScenarios)
- [https://wiki.c2.com/?BagVersusSetControversyRoadmap](https://wiki.c2.com/?BagVersusSetControversyRoadmap)
## Pairing with Mukarram and Maxwell
[[Markdown]] has been standardized.
## Evening links
About [[PostgreSQL]] internals:
- [The Internals of PostgreSQL : Chapter 3 Query Processing](http://www.interdb.jp/pg/pgsql03.html)
- [PostgreSQL 14 Internals : Postgres Professional](https://postgrespro.com/community/books/internals)
Things that can go wrong with [[RabbitMQ]]:
- [What I Wish Someone Would Have Told Me About Using Rabbitmq Before It Was Too Late – Ryan Rodemoyer – Growth-minded software developer trying to change the world.](https://ryanrodemoyer.github.io/what-i-wish-someone-would-have-told-me-about-using-rabbitmq-before-it-was-too-late/)