Efficient ways of counting the number of descendant records

Question

Consider this tree-like table structure:

CREATE TABLE nodes(
  id INTEGER PRIMARY KEY AUTOINCREMENT,
  name TEXT NOT NULL,
  parent INTEGER,
  descendant_count INTEGER NOT NULL DEFAULT 0,
  FOREIGN KEY(parent) REFERENCES nodes(id) ON DELETE CASCADE
);

The descendant_count column stores the number of descendant records.

Right now I'm maintaining it manually, by incrementing the value on each new insert (or decrementing it on deletions). Essentially I keep getting the parent record, then run

 UPDATE nodes SET descendant_count = (descendant_count + 1) ? WHERE...

on each parent, until I reach the root. Obviously this is quite slow on a deeply nested structure.

Is it possible to use triggers to achieve this? Or are there faster and more reliable ways of doing it?

---

update - 11.08.03

It appears that SQLite supports recursive triggers. So if I update the count for a single node only, a trigger should then be able to update counts on all parent nodes:

CREATE TRIGGER setCounts AFTER UPDATE ON nodes
WHEN (NEW.descendant_count <> OLD.descendant_count)
BEGIN

  -- subtract old counts
  UPDATE nodes
    SET descendant_count = descendant_count - OLD.descendant_count
    WHERE id = NEW.parent;

  -- add new counts
  UPDATE nodes
    SET descendant_count = descendant_count + NEW.descendant_count
    WHERE id = NEW.parent;
END;

I tested it and it seems the numbers are right, so this is possible after all?

Answer 1

you can optimize your solution as follows. since the updates cascade recursively up your tree, this is a substantial savings...

CREATE TRIGGER setCounts AFTER UPDATE ON nodes
WHEN (NEW.descendant_count <> OLD.descendant_count)
BEGIN
  IF NEW.parent_id IS NOT NULL THEN
      UPDATE nodes
      SET descendant_count = descendant_count 
          + NEW.descendant_count - OLD.descendant_count
      WHERE id = NEW.parent;
  END IF;
END;

furthermore you must be handle the case where you reassign parents. eg:

update node set parent_id = 20 WHERE parent_id = 10

for that you need another trigger

CREATE TRIGGER setCounts2 AFTER UPDATE ON nodes
WHEN (NEW.parent_id <> OLD.parent_id)
BEGIN
  IF OLD.parent_id IS NOT NULL THEN
      UPDATE nodes SET descendant_count = descendant_count - OLD.descendant_count
      WHERE id = OLD.parent;
  END IF;

  IF NEW.parent_id IS NOT NULL THEN
      UPDATE nodes SET descendant_count = descendant_count + NEW.descendant_count
      WHERE id = NEW.parent;
  END IF;
END;

Answer 2

SQLite does not have recursive queries; you have to do this loop in your code.

Please note that SQLite is an embedded database and has no client/server communication overhead, so doing this logic in your application is not any slower than it would be if it were supported in a trigger or directly in the database.

Answer 3

You can use a nested set model. It's much more cheaper to count descendants but more expensive to delete and insert nodes.

Answer 4

Under the Adjacency list model (which is what you are using) it is pretty hard to keep the integrity of the table.

Consider something like the nested set model. There are some tradeoffs in speed for certain operations, but for quite a lot of operations, there is also a big performance boost.