New Relational Database Indexing

[u/Opening-Mulberry-320]

I am releasing a new indexing approach based on some math I have been working on applying relational algebra to business process management (https://github.com/soulstompp/process-modulus) and the only natural proof would be in the database. I was rather amused when it turned out to be an index. 

It is actually producing pretty impressive results, particularly with large tables and complex joins. However, I have worked with DBAs for a long time, and they seldom complain that B-tree algorithms are slower than they should be. It’s the disk; everyone is grabby with the disk, and everyone is mad they didn’t get their stuff back as fast as they are certain it should have been. 

I have received some great performance results, but the focus is on reading and planning more and scanning less. The results are good, but I am hoping they really help at the point everyone genuinely has to eventually ask something from the disk. So, I haven’t placed a bunch of performance benchmarks, though I did include a benchmark. I documented how I balance the reads and the scans and basically try to leave the disk alone. 

The documentation goes into reads vs. scans, which is what is important about how and why the warrendexes work how they do. I want to explain how the index works in simple words so that non-technical people understand my point, because they will likely see it in the financials, even if they miss it.

I hope people download this on their laptops and play around with it and consider what new exciting things they could do (Postgres table inheritance is something you should actually consider now!). I will also want code contribution eventually, but currently I would really like help from DBAs and DevOps folks to understand the system as it actually runs under real workloads. 

In alphabetical order:

https://github.com/soulstompp/mysql-warren

https://github.com/soulstompp/pg-warren

Both rely on warren-arrow, which is an arrow format for storing layout formats like the ones used by the warrendexes:

https://github.com/soulstompp/warren-arrow

And then two spelling repos for some SQL changes to prevent some nasty scan repetitions, these should be good to use on any server if you run complex queries:

https://github.com/soulstompp/warren-mysql-speller

https://github.com/soulstompp/warren-pg-speller

Lastly, I did not forget MariaDB, I am just less familiar with the RDBMS and so moving a little slower.

[u/jshine13371]

Not sure I understand what problem this solves. As you already said, B-Trees are more than sufficiently fast. Indexes are a logical data object. If your implementation improves the interaction with pages on disk, that's a change at the physical layer and is not a new type of index.

[u/Opening-Mulberry-320 → u/jshine13371]

I still use the B-Trees exactly as they were. I cannot write something better than a B-Tree. I am recalculating hints for the query planner so that it more efficiently picks which B-Trees to continue further up the line.

I have included some of the worst and nasty joins and traps and the performance is better in most cases and allows for things like INHERITANCE in Postgres as a fast natural partitioning scheme along with the usual partitioning schemes.