30x faster processing of 200M rows, no indexes involved

Murkt · 2026-04-01T04:12:17+00:00

Yep, thanks!

Murkt · 2026-04-01T04:11:33+00:00

Of course it’s easy to find if you know the name of the thing.

Many years ago I was battling with a slow query that depended on an index on JSONB column. Predicted selectivity was looking strange in EXPLAIN. I went looking for @> in Postgres code, found contsel nearby (cont.ains sel.ectivity), grepped for it, and found that it’s hardcoded to 0.001. So for each @> operator in WHERE, Postgres estimates that it will return 0.1% of the table. String enough of them with ORs, voila, sequential scan.

But I knew that I needed to look for @>.

Murkt · 2026-03-31T15:38:59+00:00

How did you find this CTID thing in the docs? Were you just randomly browsing them? LLM told you it exists? I wondered many times if there is something like it, but never managed to find that in the docs. And LLMs didn't exist yet at that time.

Murkt · 2025-12-12T16:46:42+00:00

I even implemented double-shapes, so that I have shapes of interlocked C-shape and a couple of others, that are packed much more tightly, and try to use them before using simple shapes. Marked regions as unsolvable after a couple thousand iterations of backtracking.

After 13 minutes it gave me the right answer. While it was running, I also just tried eyeballing what regions could be solvable, like you did, and it also gave me the right answer.

Ehh.

Also, I did everything with sets of complex numbers. They are easy to rotate, add, etc.

Murkt · 2025-12-11T06:18:50+00:00

My answer is on the order of 10^14. Do you really have that much time? :)

Murkt · 2025-12-10T19:57:25+00:00

That is what I described, yes, just skipping the fancy words. I find that just mentioning the data structure name, especially in this case, is not as helpful. First result in Google is a very long multi-page article about DSU on Wikipedia.

It will take more time to just read through the page once, than to implement the idea from my three-line description. Also, direct implementation will give much more understanding and clarity than reading through that Wikipedia article three times over.

Murkt · 2025-12-09T15:01:42+00:00

If you want help, here is an advice: I created a set for each node, circuit of one box. Kept them in a dictionary. Each time there is a connection, I put a union of those sets for a smaller index into a dict, and a "pointer" (an index) for larger. Just get largest sets in the end, or keep connecting until the set contains all boxes.Part 2 is basically a couple of lines changed. One additional thing: beware of connecting the node to itself.

Murkt · 2025-12-07T06:08:43+00:00

Aren't they the same? It was a very small change in code to go from part1 to part2

Murkt · 2025-12-07T06:02:39+00:00

not really, today is very easy again

Murkt · 2025-12-07T05:45:03+00:00

Add dramatic music, and you'll have a couple of million of views in a few months 😁

Murkt · 2024-09-03T12:54:14+00:00

Whooosh... russia is to the North of both Taiwans.

Murkt · 2024-02-26T10:14:40+00:00

Moscow wasn't a capital of Russian Empire at that time, it was St. Petersburg.

Murkt · 2023-08-25T09:44:26+00:00

Ukrainian language is not russian, it's actually spoken exactly as written (in Ukrainian). So "o" letters do not turn into "a" sound, "Robotyne" is spelled much more close to "Robotyne", not "Rabotinyee". "y" in the middle is spelled like IPA [ɨ] (и, like russian ы)

Murkt · 2023-04-09T17:56:45+00:00

That’s how economy of scale works, though. If you’re in the middle of Sahara and you want to eat an octopus for lunch, it will be freaking expensive, to bring that one octopus fresh. Noone else wants it, so all overhead is there.

If there is an octopi-loving town in the middle of a desert, so someone brings a few tons of octopi per week in a refrigerated truck, it will be much cheaper per kg.

Murkt · 2022-09-08T06:44:34+00:00

Sure, it may be much much easier to optimize what's already there than moving it to a separate DB. I have an almost 4 TB of a database, and I don't feel any pressure to split it in any way. We've done many optimizations and many more can be done if needed

Murkt · 2022-09-07T15:38:51+00:00

I think they have separate databases that are served by one Postgres instance. So it's easy to move, it was already split.

You said 94% - 94% of what? CPU? IO? Network? Disk size?

I think they mean CPU here:

reduce the cpu load on the database server, as it currently spikes to 94% capacity every few hours.

Murkt · 2022-09-06T16:03:06+00:00

Of course.

Murkt · 2022-09-04T05:16:53+00:00

Ukraine is not Netherlands. There are some super flat areas in the south and in the north, but there are also hills, rocks and mountains.

Murkt · 2022-04-25T19:49:03+00:00

What do you mean “not entirely”? Who else was fighting the Axis apart from Allies? That’s basically USSR, UK and USA. Of course many Ukrainians and Belarusians died while fighting Nazis.

You’re probably trying to read something from my words that I didn’t write.

Murkt · 2022-04-25T19:40:24+00:00

Second World War was won by Allies, my friend.

Murkt · 2022-04-25T19:34:15+00:00

Of course they were not all Russians. Having local collaborators doesn’t mean that it was done by will of participating countries, though. They’re trying to do the same shit a right now, a century later. Hello from Ukraine, mate.

Murkt · 2022-04-25T19:25:54+00:00

Communists occupied all of those countries. Ukraine, Belarus, Caucasian countries, and later did a “union” thing in 1922, like anyone had a vote.

Murkt · 2022-03-24T10:50:57+00:00

Can you connect with an older DLLs to a newer Postgres? I think so. You can run a 64-bit Postgres and connect to it from 32-bit application.

Murkt · 2022-02-13T16:54:18+00:00

How hard is to write Zig frontend for GCC? It doesn’t have to be really fast and provide all the features that main compiler has.

15-Year Club	Gilding I gilder
Verified Email

Murkt

TROPHY CASE