2

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?

3
  • I don't understand why you are storing the descendant records, instead of just having each record store who its parent is. SQLite is so much faster than most code or algorithms.
    – HalR
    Oct 17, 2013 at 2:56
  • @HalR Well, without storing the descendant count, you'd have to compute it dynamically, which isn't easy either (because SQLite has no recursive queries).
    – CL.
    Oct 17, 2013 at 7:34
  • Recursive triggers: limited depth (10, by default). Will not work with "ON CASCADE DELETE".
    – SqliteDog
    Nov 12, 2013 at 7:58

4 Answers 4

3

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.

1
  • It's not just the speed, but also the fact that I have to keep track of the integrity of this column in my code. I was hoping there's a way to do it inside a trigger after INSERT / DELETE. This way I can add records from a different app, and not worry about that number being off. Anyway thanks for the answer:)
    – nice ass
    Oct 24, 2013 at 22:17
3

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

2
+300

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;
1

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.

2
  • Interesting, this is the first time I hear about this. But while this helps with counts, it looks like it forces me to keep the integrity of the entire set by manually deleting orphan nodes. Currently I'm relying on "DELETE CASCADE"
    – nice ass
    Nov 14, 2013 at 22:52
  • @onetrickpony DELETE CASCADE is dangerous to rely on for heirarchies, unless you know the max level of recursion. SQLite seems to have a maximum level of 10: sqlite.org/c3ref/c_limit_attached.html#sqlitelimittriggerdepth
    – DennisK
    Nov 15, 2013 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.