We do not use foreign keys (2016)

Granted, I have never worked with a database the size of Github, so I've never had to deal with sharding issues. But, even though foreign keys can be a PITA in some situations, I prefer the DBMS to do it for me than rely on the application. Foreign keys have always kept my back. I've been burned a few times when they weren't used.

That's exactly my experience and viewpoint.

> It all came to a head when I naively asked an experienced SQL developer how to represent a tree in SQL and learned one way to do it was to have CHILD nodes with FK references to PARENT nodes. So any time you want to get all the CHILDREN of a PARENT you have to query all children to see if they have a FK to the appropriate PARENT.

One far-less-painful solution: use what's called a "closure table" to track the ancestor-descendant relationships not just at the parent-child level, but also grandparent-grandchild, greatgrandparent-greatgrandchild, etc.

For example (assuming Postgres, and eliding some NOT NULL constraints for readability):

    CREATE TABLE node (
        id INTEGER PRIMARY KEY,
        parent_id INTEGER REFERENCES node
        name TEXT
    );
    
    CREATE TABLE node_closure (
        ancestor_id INTEGER REFERENCES node,
        descendant_id INTEGER REFERENCES node,
        depth INTEGER,
        PRIMARY KEY (ancestor_id, descendant_id)
    );
    

Then, whenever inserting a new node (assuming that Postgres allows specifying integer primary key values on insert, which I don't recall if it restricts by default):

    -- First node
    INSERT INTO node VALUES (0, NULL, "foo");
    INSERT INTO node_closure VALUES
        (0, 0, 0); -- self
    
    -- Second node (child of first node)
    INSERT INTO node VALUES (1, 0, "foobar");
    INSERT INTO node_closure VALUES
        (1, 1, 0), -- self
        (1, 0, 1); -- parent
    
    -- Third node (child of first node; sibling of second node)
    INSERT INTO node VALUES (2, 0, "foobaz");
    INSERT INTO node_closure VALUES
        (2, 2, 0), -- self
        (2, 0, 1); -- parent
    
    -- Fourth node (child of second node, grandchild of first node)
    INSERT INTO node VALUES (3, 1, "foobarbaz");
    INSERT INTO node_closure VALUES
        (3, 3, 0), -- self
        (3, 1, 1), -- parent
        (3, 0, 2); -- grandparent

The upside is that it's now trivial to query for a node and all its descendants:

    SELECT descendant.name
    FROM node AS descendant
    JOIN node_closure ON descendant.id = node_closure.descendant_id
    JOIN node AS ancestor ON ancestor.id = node_closure.ancestor_id
    WHERE ancestor.name = 'foo';

Or more succinctly (if you already know the ID):

    SELECT name FROM node JOIN node_closure ON node.id = node_closure.descendant_id
    WHERE node_closure.ancestor_id = 0;

Either of which gives you:

    ----
    name
    ----
    foo
    foobar
    foobaz
    foobarbaz

As part of this upside, since you're not having to loop through every level of ancestry, reads for deeply-nested descendants are much faster.

The downside is that you have to do extra inserts to an extra table. The inserts themselves can be automated by adding a trigger on node which automatically creates/updates/deletes node_closure rows as necessary (which is why you'd still want the parent_id in the main table: so that the trigger can grab that and build the closure rows, and so that if the closure table gets out-of-sync you can fall back on that and rebuild it), but that still leaves a performance impact on writes (pretty negligible for shallow descendants, but it gets worse for deeper ones).

Personally, I'd opt for a closure table if I know that reads are going to be more common than writes. If writes are more common than reads, then sure, some sort of crazy recursive query might be preferable.

I will add to the pile of agreements on this.

Also, if you do end up sharding a relational database, it is often by identifying subgraphs of document-like structures that you can shard on. Need to ensure these subgraphs do not have foreign key relations with one another, but you can maintain the valuable foreign key relations WITHIN the subgraphs.

Practical example: database of user profiles where suddenly you have billions? You can skill keep foreign keys on user to email-addresses or user-to-comments while eliminating cross-user foreign keys.

I would also add a good rule of thumb: when you make the design decision to remove a database feature, you need to assume that you now need to handle that feature yourself, or your data will get corrupted. For example, when removing FK constraints, or transactional boundaries, or introduce irregular checkpointing, you now need to implement a data repair system, because your data will get broken. At which point you are probably going to end up using a change event log (your own transaction log) and a system that replays the logs in order to repair and rebuild the database.

Transactions are a pretty widely used RDBMS feature AFAIK.