Optimizing regex based query in sqlite
I noticed that my assumption that multiple inner joins should just take the sum in time of the individual joins is apparently not true.
I got the query up to a decent speed by preprocessing the parts to be joined, so a more efficient join strategy can be used:
SELECT Websites.*,
       L1.label1,
       L2.label2
  FROM Websites
       JOIN
       (
           SELECT Websites.*,
                  Label1.label1
             FROM Websites
                  JOIN
                  Label1 ON (Websites.protocol REGEXP '^' || Label1.protocol_re || '$' AND 
                             Websites.domain REGEXP '^' || Label1.domain_re || '$' AND 
                             Websites.path REGEXP '^' || Label1.path_re || '$') 
       )
       AS L1 USING (
           protocol,
           domain,
           path
       )
       JOIN
       (
           SELECT Websites.*,
                  Label2.label2
             FROM Websites
                  JOIN
                  Label1 ON (Websites.protocol REGEXP '^' || Label2.protocol_re || '$' AND 
                             Websites.domain REGEXP '^' || Label2.domain_re || '$' AND 
                             Websites.path REGEXP '^' || Label2.path_re || '$') 
       )
       AS L2 USING (
           protocol,
           domain,
           path
       );

It may not look like much, but it works very well.