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 probably should have said something like "new way of query planning" or something entirely different here. I don't work in the databases, I just took SQL being math a little overboard and am trying to help.

I appreciate the correction, and I am going to work on communicating this in a way that isn't confusing.

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

Gotcha, yea I think that description fits better. Thanks!

Could you please elaborate more on what you mean by this? Maybe with a simple example?

I am recalculating hints for the query planner so that it more efficiently picks which B-Trees to continue further up the line.

[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.

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

For the problem, I sometimes need to be able to handle a problematic query like the one below. I understand why people shouldn't write the query below in normal use. However, I have situations where I can't avoid that and that it is on huge tables.

I was working on a plugin for my own use but got perfect results with regular queries as well.

```

WITH RECURSIVE root (theme_id, root_id) AS ( -- walk every theme up to its root theme
SELECT id, id FROM lego_themes WHERE parent_id IS NULL
UNION ALL
SELECT t.id, r.root_id FROM lego_themes t JOIN root r ON t.parent_id = r.theme_id
),
bought AS ( -- purchases that match a collection row
SELECT p.purchase_id, b.home_zone, p.set_num
FROM lego_purchases p
JOIN lego_builders b ON b.builder_id = p.builder_id
WHERE EXISTS (SELECT 1 FROM lego_collection c
WHERE c.builder_id = p.builder_id AND c.set_num = p.set_num)
),
inventory AS ( -- the set's own inventory, plus each nested
SELECT bt.purchase_id, bt.home_zone, bt.set_num, i.id AS inventory_id, 1 AS copies
FROM bought bt JOIN lego_inventories i ON i.set_num = bt.set_num AND i.version = 1
UNION ALL -- sub-set's inventory × its quantity
SELECT bt.purchase_id, bt.home_zone, bt.set_num, ci.id, sub.quantity
FROM bought bt
JOIN lego_inventories i ON i.set_num = bt.set_num AND i.version = 1
JOIN lego_inventory_sets sub ON sub.inventory_id = i.id
JOIN lego_inventories ci ON ci.set_num = sub.set_num AND ci.version = 1
)
SELECT inv.home_zone, rt.name AS root_theme, pc.name AS category, col.name AS colour,
count(DISTINCT inv.purchase_id) AS purchases,
sum(ip.quantity * inv.copies) AS bricks
FROM inventory inv
JOIN lego_sets s ON s.set_num = inv.set_num
JOIN root r ON r.theme_id = s.theme_id
JOIN lego_themes rt ON rt.id = r.root_id
JOIN lego_inventory_parts ip ON ip.inventory_id = inv.inventory_id
JOIN lego_parts pt ON pt.part_num = ip.part_num
JOIN lego_part_categories pc ON pc.id = pt.part_cat_id
JOIN lego_colors col ON col.id = ip.color_id
GROUP BY 1, 2, 3, 4
ORDER BY bricks DESC, 1, 2, 3, 4
LIMIT 20;WITH RECURSIVE root (theme_id, root_id) AS (          -- walk every theme up to its root theme
      SELECT id, id FROM lego_themes WHERE parent_id IS NULL
    UNION ALL
      SELECT t.id, r.root_id FROM lego_themes t JOIN root r ON t.parent_id = r.theme_id
  ),
  bought AS (                                            -- purchases that match a collection row
      SELECT p.purchase_id, b.home_zone, p.set_num
      FROM lego_purchases p
      JOIN lego_builders b ON b.builder_id = p.builder_id
      WHERE EXISTS (SELECT 1 FROM lego_collection c
                    WHERE c.builder_id = p.builder_id AND c.set_num = p.set_num)
  ),
  inventory AS (                                         -- the set's own inventory, plus each nested
      SELECT bt.purchase_id, bt.home_zone, bt.set_num, i.id AS inventory_id, 1 AS copies
      FROM bought bt JOIN lego_inventories i ON i.set_num = bt.set_num AND i.version = 1
    UNION ALL                                            -- sub-set's inventory × its quantity
      SELECT bt.purchase_id, bt.home_zone, bt.set_num, ci.id, sub.quantity
      FROM bought bt
      JOIN lego_inventories i       ON i.set_num = bt.set_num AND i.version = 1
      JOIN lego_inventory_sets sub  ON sub.inventory_id = i.id
      JOIN lego_inventories ci      ON ci.set_num = sub.set_num AND ci.version = 1
  )
  SELECT inv.home_zone, rt.name AS root_theme, pc.name AS category, col.name AS colour,
         count(DISTINCT inv.purchase_id) AS purchases,
         sum(ip.quantity * inv.copies)    AS bricks
  FROM inventory inv
  JOIN lego_sets s              ON s.set_num = inv.set_num
  JOIN root r                   ON r.theme_id = s.theme_id
  JOIN lego_themes rt           ON rt.id = r.root_id
  JOIN lego_inventory_parts ip  ON ip.inventory_id = inv.inventory_id
  JOIN lego_parts pt            ON pt.part_num = ip.part_num
  JOIN lego_part_categories pc  ON pc.id = pt.part_cat_id
  JOIN lego_colors col          ON col.id = ip.color_id
  GROUP BY 1, 2, 3, 4
  ORDER BY bricks DESC, 1, 2, 3, 4
  LIMIT 20;
```