Optimization: find paths in SQL with recursive common table expressions

[goodmami]

The SQLite backend is quick to start up and to perform several queries, but it gets slower on operations that require many separate SQL queries, such as paths. One potential solution is a recursive common table expression.

[fcbond]

Or you can trade space for time and use an ancestor table: https://evolt.org/working_with_hierarchical_data_in_sql_using_ancestor_tables We did this in OMW 1.0.

…

On Mon, Nov 2, 2020 at 10:23 AM Michael Wayne Goodman < ***@***.***> wrote: The SQLite backend is quick to start up and to perform several queries, but it gets slower on operations that require many separate SQL queries, such as paths. One potential solution is a recursive common table expression <https://www.sqlite.org/lang_with.html#recursive_common_table_expressions> . — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#38>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAIPZRSXMO26V6DMLGFZFITSNYJHXANCNFSM4TG5ESSQ> .

-- Francis Bond <http://www3.ntu.edu.sg/home/fcbond/> Division of Linguistics and Multilingual Studies Nanyang Technological University

[goodmami]

Thanks! I'm concerned how it would scale when we consider more than just hypernym relations, but it's worth considering.

[fcbond]

I defined this only for hypernym (and instance) relations, as they are the main transitive relations where you want to check inclusion. So I agree it is not a full solution for all possible queries, but I think may be a good one for a very common set.

…

On Mon, Nov 2, 2020 at 10:39 AM Michael Wayne Goodman < ***@***.***> wrote: Thanks! I'm concerned how it would scale when we consider more than just hypernym relations, but it's worth considering. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#38 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAIPZRR63VBMA7WC5BDY7X3SNYLDPANCNFSM4TG5ESSQ> .

-- Francis Bond <http://www3.ntu.edu.sg/home/fcbond/> Division of Linguistics and Multilingual Studies Nanyang Technological University

[goodmami]

Some updates to this:

Here is a query that recursively finds relations within the same lexicon:

WITH RECURSIVE
  rt(rowid) AS
    (SELECT rowid FROM relation_types WHERE type IN (?,...)), -- hypernym, instance_hypernym, etc.
  tgt(rowid, path, depth) AS
    (SELECT ?, ">"||?||",", 0 -- synset rowid, twice
     UNION ALL
       SELECT rels.target_rowid,
              tgt.path||rels.rowid||">"||rels.target_rowid||",",
              tgt.depth+1
         FROM synset_relations AS rels
         JOIN tgt ON rels.source_rowid = tgt.rowid
        WHERE rels.lexicon_rowid IN (?,...) -- target lexicons
          AND rels.type_rowid IN rt
          AND tgt.depth < ? -- depth limit
          AND NOT instr(tgt.path, ">"||rels.target_rowid||",")
        ORDER BY 3 DESC
        LIMIT 1000000
    )
SELECT rowid, path, depth FROM tgt;

Despite the string operations for avoiding cycles (see https://stackoverflow.com/q/66866542/1441112), it is fairly fast. And not only does it return all transitive relations, but also the path to get there and the depth, and the search can be limited by depth. However, it can easily become slow by broadening the query to, e.g., all relations, or even just hypernym and hyponym. For this reason, the (row) LIMIT is important and also an appropriate depth limit.

More importantly, it does not do expanded (inter-lexicon) search. I tried to replicate the two-step process currently used (first intra-lexicon relations, then expanded ones) by adding this second recursive part:

     UNION ALL
       SELECT ss.rowid, tgt2.path||exp.rowid||">"||ss.rowid||",", tgt2.depth+1
         FROM tgt AS tgt2
         JOIN synsets AS ss1 ON tgt2.rowid = ss1.rowid
         JOIN synsets AS ss2 ON ss2.ili_rowid = ss1.ili_rowid
         JOIN synset_relations AS exp ON exp.source_rowid = ss2.rowid
         JOIN synsets AS ss3 ON ss3.rowid = exp.target_rowid
         JOIN synsets AS ss ON ss.ili_rowid = ss3.ili_rowid
        WHERE exp.lexicon_rowid IN (?,...)  -- expand lexicons
          AND exp.type_rowid IN rt
          AND tgt2.depth < ? -- depth limit, again
          AND NOT instr(tgt2.path, ">"||ss.rowid||",")
          AND ss.lexicon_rowid IN (?,...)  -- target lexicons, again
        ORDER BY 3 DESC
        LIMIT 1000000

But recursive queries with more than one recursive part were not added to SQLite until version 3.34, and Python's version is at 3.31, so I'm not sure if the above even works. When I try something like the above as the only recursive query, it works but is very slow. I suspect that joining synsets 4 times at every recursive step is slowing things down. These 4 are necessary because we start with a synset rowid and relations are between synset rowids, but the expansion happens in ILI, so:

1. Join to get ILI of source synset
2. Join to get other synsets with that ILI
3. Join to get ILIs of matching relations' target synsets
4. Join to get synsets in target lexicon with those ILIs

This could perhaps be simpler if ILIs were required by all synsets. As it is, imagine if the PWN did not have ILIs: the relations still work between its synsets. Since they are optional we have to check, at every relation traversal, if there are relations within the current lexicon as well as the expanded ones available via ILI traversals.

[goodmami]

Changing the label to "maintenance" as this doesn't change functionality, only (potentially) performance.