michelpp

The performance while querying sqlite objects with sqlite_query() is identical to that of using an in-memory sqlite database. once Postgres 18 is released which contains some specific optimizations around expanded datum lifecycles there will be further improvements to sqlite_exec's behavior.

For Postgres < 18 sqlite_exec() will incur a flatten/expand cycle, but this can be worked around in most cases by bundling SQL into a single sqlite_exec call instead of multiple ones. Once Postgres 18 is released this will no longer be an issue.

This work is the result of a fairly long running discussion thread [1] on the pgsql-hackers mailing list around improving expanded datum handling for non-array types in general so that one of my other extensions, OneSparse, can take advantage of them.

We discussed adding a "skeleton" expanded example into the Postgres test modules, but it wouldn't be useful. As I generally prefer to make useful things, I took a page from the ideas in pglite-fusion [2] and made it a true first class expanded datum which requires no server filesystem access.

[1] https://www.postgresql.org/message-id/flat/CACxu%3DvKMWjj%2B...

[2] https://github.com/frectonz/pglite-fusion

A cool project with this would be 3D print a mini Connection Machine 5 (CM-5) model made out of Raspi CM5 modules. Some tiny led panels would be killer.

https://en.wikipedia.org/wiki/Connection_Machine#/media/File...

RLS is very useful and can solve multi tenancy and other problems, but it is complicated and can add a significant per row cost to queries if your policies get complicated.

The common path of comparing some constant like the role name to some column in the table is fine, and it's fast enough as the policy checker already has the row in hand when it does the check, but the natural tendency for people to want to abstract their policies into a function like has_permission() will blow up fast.

The best approach I've seen from pyramation's launchql [1] which precomputes policies into a bitstring and then masks that against a query constant bitstring of required permissions. Flexible policy definitions compiled into the row as bits so the check is as fast as possible.

[1] https://github.com/launchql/launchql

With the expanded datum api you can also work with subscriptable array types to only expand elements lazily as needed. It might already works if you try it, but support for it might be hardwired only to nested stock arrays, something to look into.

Here's an example of a simple expanded object to start from:

https://github.com/michelp/pgexpanded

"War is diplomacy by other means" - Clausewitz

Then you need one wrapper per database, with this approach you can have one database per row.

I think the right approach would be to store the sqlite database as a varlena type that can be TOASTed and then "expanded" using the Expanded Datum API so that it's a live open database connection for the life of the transaction:

https://www.postgresql.org/docs/17/xtypes.html#XTYPES-TOAST

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

> Here we are talking of graphs in the milions nodes/edges,

That ought to be enough for anybody.

> would TC support that

TC is a purely structural algorithm, it counts triangles so it doesn't take any weights into consideration, but it does return a vector of normalized ranking from 0.0 to 1.0, which you could combine with an existing biasing strategy to boost results that have strong centrality.

PageRank is one of several interesting centrality metrics that could be applied to a graph to influence RAG on structural data, another one is Triangle Centrality which counts triangles around nodes to figure out their centrality based on the concept that triangles close relationships into a strong bond, where open bonds dilute centrality by drawing weight away from the center:

https://arxiv.org/abs/2105.00110

The paper shows high efficiency compared to other centralities like PageRank, however in some research using the GraphBLAS I and my coauthors found that TC was slower on a variety of sparse graphs than our sparse formulation of PR for graphs up to 1.8 billion edges, but that TC appears to scale better as graphs get larger and is likely more efficient in the trillion edge realm.

https://fossies.org/linux/SuiteSparse/GraphBLAS/Doc/The_Grap...

My twice reading list:

  - Godel, Escher, Bach - Hoffstadter
  - The Soul of a New Machine - Kidder
  - The Emperor's New Mind - Penrose
  - The Connection Machine - Hillis
  - Algorithmics - Harel

I got this out a bit early to get some eyeballs on it and open it up to community contribution. I have a branch in progress converting the various Python examples and notebooks we have over to SQL. So stay tuned.

For docs the best reference to the algebra is the SuiteSparse User Guide, but that doesn't cover the SQL side of things. I'm working on an idea where I put markdown comments in the sql test files and simulate the Python doctest tool so I can render markdown documentation from the test files. If that works out they'll end up on github pages as the official SQL docs with links out to the SuiteSparse User Guide for the low level details.

I'm extending Postgres with the GraphBLAS/SparseBLAS APIs for sparse and dense linear algebra operations directly in SQL with OneSparse. Like JSON/JSONB did for unstructured data, OneSparse does for matrices, vectors and linear algebra optimized with the SuiteSparse JIT compiler to target dense and sparse kernels for CPUs and GPUs.

https://github.com/OneSparse/OneSparse

Hello HN!

Six years ago I release a prototype integration of SuiteSparse as a Postgres extension, and it received quite a bit of attention here on HN. Since then I have gotten deeply involved in the GraphBLAS community, sitting on the C API Committee and working with many different implementors and language binding authors, and that experience has changed both the API and my depth of understanding. I picked pggraphblas back up again and have done a complete rewrite applying the lessons learned and most modern techniques to the code and to support the most up to date features of SuiteSparse like JIT compilation, automatic parallelization and GPU support.

Like the JSON/JSONB types did for unstructured data, OneSparse makes dense and sparse matrices and vectors fully native Postgres types. OneSparse supports optimized, parallel matrix multiplication and other operations like reduction, selection, assignment, extraction, elementwise union, and intersection. These methods can be used for both traditional numeric algebraic computing, or sparse graph analytics over adjacency and incidence matrices.

I often tell people that GraphBLAS is "Technology from the Future" as as the future of computing becomes more computation dense but information sparse, powerful language abstractions like Linear Algebra become even more useful in the hands of scientists, researchers, and programmers who want to express their ideas in high level ways but still be able to target many different architectures like CPUs and GPUs with little or no code changes.

We're an open source company and OneSparse is truely open source Postgres extension. We have a fun and exciting list of TODO features at the bottom of our README, so please reach out to us if you feel like contributing to this completely new paradigm for understanding your data and utilizing Linear Algebra!

I found my pic, they spelled my trail name a bit differently: https://athikerpictures.org/hikers/2329

I thruhiked in 1995, and while I did go to the ATC headquarters to sign in, I don't recall having my photo taken, but it may have been. I do however vividly recall the photo archive at Rusty's Hardtime Hollow just off the Blue Ridge Parkway section of the AT a few miles but was well worth the trip.

Rusty had polaroids of hikers going way back, they lined the walls of every building, when he built new bunkhouses, he started new annual collections. There were thousands of them. Every night he would roll his truck down into the parking are blast James Brown and feed what he could to whatever he had or whatever hikers could bring. Wood fired hot tub, sauna, huge garden, it was a paradise after almost a 1000 miles on foot.

I hope the ATC was also able to recover Rusty's photos, because he had a real gold mine. The few years after hiking when I lived in the area I would bring beverages and hot dogs for the hikers. I lost touch with Rusty after I went west. I was hiking recently in Maine and talking to another thruhiker who went through in the 2000 and she said the Hollow is gone now which would be a shame of his archive could not be recovered.

An inexpensive 10 hole Hohner harmonica is a fun and easy way to learn a bit about music and self expression. when I was 10 my parents got me a book by Klutz Press, "Country and Blues Harmonica for the Musically Hopeless" that came with a cheap plastic Hohner harp and a cassette tape where the author Jon Gindick walks you through everything you need to know to get started on straight and cross harp. The whole tape is now on YouTube!

https://www.youtube.com/watch?v=2fayFSiceZA

The hardest skill to master on a harmonica is playing one note at a time without bleeding into the holes on either side. Once you master single hole pucker, introducing the side holes adds more texture and harmony at your discretion. The second hardest skill is "bending" by changing your embouchure and air stream flow to bend the pitch of the reed. You can't really effectively bend until you single note pucker since the reeds bend at different rates which only sounds good when you've mastered both skills which are key to a good cross harp player.

If you decide to get a harp for starters the plastic Hohner Marine Band harp is super tough and forgiving. The more expensive wooden comb blues harps sound amazing but they take some skill to master.

Diatonic harmonicas are keyed, where the "C" note (4th hole blow) can be in any whole tone, so some transpositional thinking is required once you get good. If you want to play cross harp (aka "blues") with a guitar player typically playing in the key of E, then get a harp keyed in A.

This is a nice blog and I like the versioning feature, if you're looking to explore this idea more I made a very simple unversioned FSM extension for Postgres years ago for fun and no profit:

https://github.com/michelp/pgfsm

Implement the GraphBLAS API of course!

https://graphblas.org/

In Danny Hillis' lecture on the architecture of the CM-5 [1], he talks about some of the historical motivation behind the CM-2 described in his thesis paper turned into a book "The Connection Machine" [2] which goes into some detail on the alpha, beta, and dot operators and the xapping data type (the book calls it a "xector") described in detail in this paper.

Years ago I attempted to take a stab at implementing this language on CUDA I called hillisp [3] but at the time Dynamic Parallelism didn't exist yet and my available hardware was pretty weak, but it was fun to learn more about CUDA which was relatively early technology at the time.

[1] https://www.youtube.com/watch?v=Ua-swPZTeX4

[2] https://www.amazon.com/Connection-Machine-Press-Artificial-I...

[3] https://github.com/michelp/hillisp

RIP Mr. Barth. I carried a dog eared copy of Lost in the Funhouse with me through 20 years of my life, picking it up and putting it down whenever I needed something to shift my perspective or jar me out of a rut. Psychoactive writing at its best, the titular story is so transpositional that sometimes I feel like that family trip to the beach was a real memory that actually happened to me.

Tackling these boundary problems are the literal "edge cases" in geospatial indexing and they exist everywhere, so this i a good reason for using an existing library as the authors have already solved them.

Hexagons are cool, but they are not necessarily the bestagon for a spherical geometry since you cannot break a hexagon into smaller hexagons, whereas an S2 cell is a "cube" with spherical sides or HEALPix uses a rhombic dodecahedron [0] both of which can be split into smaller divisions of themselves.

Not to discourage you from your experimentation, it's all trade offs and you might find a good one. Good luck!

[0] https://en.wikipedia.org/wiki/HEALPix

I experimented with geospatial Hilbert Curves as a Postgres extension [0] for PostGIS using the S2 [1] spherical geometry library. S2 uses a scale free cell coverage pattern that is numbered using six interlocking space filling Hilbert Curves [2]. This approach is similar to what is used in this article. S2 doesn't use hexagons but a different cell structure but the idea is generally the same.

By having both high level (cell) and low level (cell id) geometries it was a very powerful library which allowed projection from the hilbert space into a Postgres spatial index (spgist) including various trees, like noted in this article. It appears to be still quite active in development.

[0] https://github.com/michelp/pgs2

[1] https://s2geometry.io/

[2] https://s2geometry.io/devguide/s2cell_hierarchy

I don't know much about it, but I think this has been tried?

https://dylibso.com/blog/pg-extism/

Looking at the repo though it looks like it hasn't been updated in a while.

This looks very cool and it's nice to see some finicky details like PG_GETARG abstracted away.

Are there any plans to make pgzx a Trusted Language so that Zig functions could be written with CREATE FUNCTION? Rust recently achieved this milestone and AWS RDS now supports PL/Rust.

Being a trusted language would mean it could be used to create Trusted Language Extensions (TLEs) and could be installed on cloud hosted databases without filesystem access.

This is very cool and a real interesting read! For those in the comments confused about how this is better, the paper is talking about synthesizing matrix multiplication pipelines in hardware, like an FPGA or ASIC. On a CPU or GPU you won't notice because adds and multiplications take the same amount of time generally, but multiplication units takes up many more transistors, so if you can reduce the circuit complexity you can increase the speed and parallel throughput and reduce power and routing complexity. This approach could be particularly useful for efficient sparse matrix multiplication accelerators.

Another cool way to eliminate multiplication in matrix multiplication is to use different semirings [1]. The Tropical Semiring [2] for example substitutes addition for multiplication and min (or max) for addition. It's still matrix multiplication but with substituted binary operations. The research in this relatively new field of Tropical Algebra [3] is quite active and rich right now, being used for all kinds of optimization problems and in research for optimizing neural networks [4] . This approach also lends itself to hardware synthesis since most FPGA configurable logical blocks can add/min/max in one clock cycle, whereas efficient multiplication requires fixed dedicated on-chip hardware multipliers.

Another way to efficiently remove multiplications with a different but related semiring is to use a Log Semiring [5]. If you have to multiply chains of probabilities (like Markov chains) then the numbers quickly become very small and floating point loses its accuracy to represent the numbers. By scaling the numbers first by taking the log, multiplication becomes addition and addition becomes x + log1p(exp(y - x)).

[1] https://en.wikipedia.org/wiki/Semiring

[2] https://en.wikipedia.org/wiki/Tropical_semiring

[3] https://en.wikipedia.org/wiki/Tropical_geometry

[4] https://proceedings.mlr.press/v80/zhang18i/zhang18i.pdf

[5] https://en.wikipedia.org/wiki/Log_semiring

Love PMO, get there a day or two early on a moonless weekend and you can usually score one of the campsites.

>* The Christmas Valley area has a lot of interesting things like Fort Rock, Crack-in-the-Ground, Hole-in-the-Ground and the sand dunes.

Great list, I'd also add Summer Lake Hot Springs, Freemont Point Lookout, The Lost Forest, Glass Butte, the sunstone mines near Plush, pretty much all of the Malheur National Wildlife Refuge, Crane Hot Springs, might as well throw in Painted Hills, there's so much!

The midwest can definitely get dark, but the "seeing" isn't as good as the oregon outback for a few reasons, 1) elevation, most of eastern oregon is above 1200m, steens mountain is almost 3000m. 2) climate, the midwest can be very humid and hazy, whereas the high desert is very arid and clear, 3) obscuration, eastern oregon is covered in mountain ranges with dry basins in between (hence "basin and range" name), and you only have to go over one range from any kind of town to have its light totally blocked.

Was Alvord hot springs not open? I know they've been hit or miss over the years. It's pretty primitive, basically a hole dynamited into the ground but the water is amazing and it's usually never busy. They also have a great access road to the playa.

> Abstractions should be seen as models. They are always wrong, but they are sometimes useful. (And sometimes not.)

George Box was very specifically talking about statistical models when he coined that aphorism. Matrices are linear algebra and graphs are graph theory, I find it hard to think they are not correct and useful models.

> A forward traversal >v of node v enters from the left, reads the sequence stored in the node, and exits from the right. A reverse traversal <v enters from the right, reads the reverse complement of the sequence, and exits from the left.

I'm not an expert in this field but I'm guessing you're talking about De Bruijn graphs, which can be very elegantly modeled with incidence matrices, here's an example of one using the GraphBLAS that downloads data from BioPython, loads it into incidence matrices and graphs it. This is just a simple example, SuiteSparse can handle many billions of edges:

https://github.com/Graphegon/Graphony?tab=readme-ov-file#exa...

Traversing bidirectionally is quite easy, the upper triangle of a matrix are the directed outgoing edges, and the lower triangle are the incoming. This style of "push/pull" optimization is common in the GraphBLAS.

> In a good graph representation, you can do this by maintaining a small state that does not grow significantly with the length of the context or the number of underlying paths.

Again if I understand you correctly, in the GraphBLAS this is accomplished by using accumulators and masks. During traversal data can be accumulated, with a stock operator or one you define, into a vector or matrix, and that object can be used to efficiently mask subsequent computations to avoid unnecessary work or determine when you've reached a termination condition.

> Matrices don't feel like a good abstraction for graphs like this.

Mathematically, graphs and matrices are isomorphic. Regardless of algorithm or storage format like edge lists, tuples or CSR, every graph is a matrix, and vice versa. And if you have a matrix, you have linear algebra to operate on it.

Some people don't like Linear Algebra to operate on graphs, so I guess for them it is "not good", but on the other hand, it's Linear Algebra and Graph Theory, whose roots date back to the 2nd century BC, forward through great minds like Descartes and Euler, permeating every kind of math, science, physics and engineering discipline humans have ever created. That's a strong argument for its goodness.

Now it is entirely possible, likely even, that the current SuiteSparse implementation doesn't have exactly the tool needed or maybe not the precise best storage format, but these missing pieces do not invalidate the underlying mathematical foundation that it's based on.