Hi Sebastian,
You can achieve better performance by constructing the path as you
walk the tree.
e.g.
WITH
tree(
id,
depth,
path
) AS (
SELECT id,
1,
id
FROM languoid
WHERE parent_id IS NULL
UNION ALL
SELECT l.id,
t.depth+1,
t.path || '/' || l.id
FROM tree t
JOIN languoid l ON t.id = l.parent_id
)
SELECT id,
depth,
path
FROM tree
ORDER BY 1;
-Jake
On Sat, Dec 22, 2018 at 11:53 PM Sebastian Bank
<sebastian.b...@uni-leipzig.de> wrote:
>
> Hi,
>
> given a table that represents an adjacency tree, I use a recursive CTE
> together with group_concat() to generate the path for each tree item.
>
> With SQLite up to version 3.25.3 the query below (with the 500 example
> items inserted below) takes about 0.2 seconds on my system. With version
> 3.26.0 it takes over 6 seconds (with the full data set of around 24000
> items, it seems to become infeasible).
>
> Thanks and best,
>
> Sebastian Bank
>
>
> CREATE TABLE languoid (
> id VARCHAR(8) NOT NULL,
> parent_id VARCHAR(8),
> PRIMARY KEY (id),
> FOREIGN KEY(parent_id) REFERENCES languoid (id)
> );
>
> INSERT INTO languoid (id, parent_id) VALUES
> ("abin1243", NULL), ("abis1238", NULL), ("abkh1242", NULL), ("abkh1243",
> "abkh1242"),
> ("abaz1241", "abkh1243"), ("ashk1247", "abaz1241"), ("bezs1238",
> "abaz1241"), ("tapa1256", "abaz1241"),
> ("abkh1244", "abkh1243"), ("abzh1238", "abkh1244"), ("bzyb1238",
> "abkh1244"), ("samu1242", "abkh1244"),
> ("circ1239", "abkh1242"), ("adyg1241", "circ1239"), ("abad1240",
> "adyg1241"), ("bezh1247", "adyg1241"),
> ("natu1243", "adyg1241"), ("shap1240", "adyg1241"), ("xaku1238",
> "adyg1241"), ("kaba1278", "circ1239"),
> ("grea1271", "kaba1278"), ("ubyk1235", "abkh1242"), ("abun1252", NULL),
> ("abun1253", "abun1252"),
> ("abun1254", "abun1252"), ("abun1255", "abun1252"), ("adai1235", NULL),
> ("afro1255", NULL),
> ("berb1260", "afro1255"), ("awji1241", "berb1260"), ("ghad1239",
> "berb1260"), ("aytw1238", "ghad1239"),
> ("eltu1238", "ghad1239"), ("kaby1244", "berb1260"), ("atla1275",
> "kaby1244"), ("cent2194", "atla1275"),
> ("cent2195", "cent2194"), ("stan1324", "cent2194"), ("nort3248",
> "atla1275"), ("ghom1257", "nort3248"),
> ("senh1238", "nort3248"), ("tach1250", "atla1275"), ("susi1238",
> "tach1250"), ("kaby1243", "kaby1244"),
> ("grea1281", "kaby1243"), ("less1241", "kaby1243"), ("nafu1238",
> "berb1260"), ("jbal1238", "nafu1238"),
> ("jerb1241", "nafu1238"), ("jerb1242", "nafu1238"), ("tame1243",
> "nafu1238"), ("zuar1238", "nafu1238"),
> ("siwi1238", "berb1260"), ("sawk1238", "siwi1238"), ("siwi1239",
> "siwi1238"), ("tuar1240", "berb1260"),
> ("sout3263", "tuar1240"), ("tama1365", "sout3263"), ("tadg1238",
> "tama1365"), ("tadh1242", "tama1365"),
> ("timb1263", "tama1365"), ("tawa1286", "sout3263"), ("ioul1238",
> "tawa1286"), ("tawa1287", "tawa1286"),
> ("tawa1288", "tawa1286"), ("taya1257", "sout3263"), ("airr1242",
> "taya1257"), ("tana1297", "taya1257"),
> ("taha1241", "tuar1240"), ("ghat1242", "taha1241"), ("hogg1238",
> "taha1241"), ("unun9880", "berb1260"),
> ("guan1277", "unun9880"), ("west2724", "berb1260"), ("tets1235",
> "west2724"), ("zena1248", "west2724"),
> ("zena1250", "berb1260"), ("chen1266", "zena1250"), ("moza1250",
> "zena1250"), ("ouar1239", "moza1250"),
> ("taga1278", "ouar1239"), ("oued1238", "taga1278"), ("tari1264",
> "taga1278"), ("tema1244", "taga1278"),
> ("tema1243", "ouar1239"), ("tazn1238", "moza1250"), ("gour1247",
> "tazn1238"), ("sout3056", "tazn1238"),
> ("toua1238", "tazn1238"), ("tidi1241", "moza1250"), ("tidi1242",
> "tidi1241"), ("titt1238", "tidi1241"),
> ("tumz1238", "moza1250"), ("sene1271", "zena1250"), ("nucl1705",
> "sene1271"), ("tmag1238", "sene1271"),
> ("tach1249", "zena1250"), ("tari1263", "zena1250"), ("east2803",
> "tari1263"), ("riff1234", "tari1263"),
> ("east2804", "riff1234"), ("beni1249", "east2804"), ("cent2333",
> "east2804"), ("arze1238", "cent2333"),
> ("beni1250", "cent2333"), ("beni1251", "cent2333"), ("guel1234",
> "cent2333"), ("tems1234", "cent2333"),
> ("kebd1234", "east2804"), ("sout3264", "east2804"), ("beni1252",
> "sout3264"), ("igze1238", "sout3264"),
> ("meta1239", "sout3264"), ("west2882", "riff1234"), ("boqq1234",
> "west2882"), ("urri1238", "west2882"),
> ("tuni1262", "zena1250"), ("chad1250", "afro1255"), ("bium1280",
> "chad1250"), ("hurz1242", "bium1280"),
> ("mbuk1243", "hurz1242"), ("vame1236", "hurz1242"), ("dume1239",
> "vame1236"), ("gwen1242", "vame1236"),
> ("mayo1276", "vame1236"), ("mber1261", "vame1236"), ("nort3156",
> "bium1280"), ("gida1247", "nort3156"),
> ("lamm1244", "gida1247"), ("higi1241", "nort3156"), ("hyaa1239",
> "higi1241"), ("nkaf1238", "higi1241"),
> ("bana1305", "nkaf1238"), ("gamb1258", "bana1305"), ("gili1246",
> "bana1305"), ("higi1242", "nkaf1238"),
> ("kamw1239", "higi1242"), ("kiry1234", "higi1242"), ("psik1239",
> "higi1241"), ("nucl1685", "psik1239"),
> ("wula1250", "psik1239"), ("zlen1238", "psik1239"), ("jina1243",
> "nort3156"), ("jina1244", "jina1243"),
> ("maje1243", "jina1243"), ("hwal1242", "maje1243"), ("kaji1238",
> "maje1243"), ("nucl1687", "maje1243"),
> ("koto1263", "nort3156"), ("lagw1237", "koto1263"), ("affa1240",
> "lagw1237"), ("logo1273", "lagw1237"),
> ("logo1274", "lagw1237"), ("mser1242", "koto1263"), ("gawi1244",
> "mser1242"), ("houl1238", "mser1242"),
> ("kabe1249", "mser1242"), ("kalo1266", "mser1242"), ("nucl1691",
> "mser1242"), ("lama1287", "nort3156"),
> ("hdii1240", "lama1287"), ("turr1244", "hdii1240"), ("lama1288",
> "lama1287"), ("cent2190", "lama1288"),
> ("dlig1238", "cent2190"), ("hedk1239", "cent2190"), ("waga1267",
> "cent2190"), ("ghud1238", "lama1288"),
> ("nort3048", "lama1288"), ("dzub1245", "nort3048"), ("gwoz1239",
> "nort3048"), ("legh1238", "nort3048"),
> ("zala1252", "nort3048"), ("zala1251", "lama1288"), ("vemg1240",
> "lama1287"), ("vemg1241", "vemg1240"),
> ("visi1243", "vemg1240"), ("marg1267", "nort3156"), ("bura1296",
> "marg1267"), ("bium1270", "bura1296"),
> ("kilb1234", "bium1270"), ("huba1236", "kilb1234"), ("luwa1242",
> "huba1236"), ("marg1266", "kilb1234"),
> ("marg1265", "bium1270"), ("gula1275", "marg1265"), ("gwar1244",
> "marg1265"), ("lass1239", "marg1265"),
> ("wurg1238", "marg1265"), ("bura1297", "bura1296"), ("bura1292",
> "bura1297"), ("hyil1238", "bura1292"),
> ("pabi1240", "bura1292"), ("pela1248", "bura1292"), ("ciba1236",
> "bura1297"), ("nggw1242", "bura1297"),
> ("puta1243", "bura1297"), ("mand1472", "marg1267"), ("dghw1240",
> "mand1472"), ("cine1238", "dghw1240"),
> ("dghw1239", "dghw1240"), ("gudu1252", "dghw1240"), ("chen1265",
> "gudu1252"), ("chik1255", "gudu1252"),
> ("gava1240", "gudu1252"), ("gvok1239", "dghw1240"), ("podo1243",
> "mand1472"), ("mata1306", "podo1243"),
> ("park1239", "podo1243"), ("wand1280", "mand1472"), ("glav1244",
> "wand1280"), ("bokw1242", "glav1244"),
> ("ngos1242", "glav1244"), ("nucl1680", "glav1244"), ("wand1281",
> "wand1280"), ("malg1251", "wand1281"),
> ("wand1278", "wand1281"), ("gama1258", "wand1278"), ("gwan1267",
> "wand1278"), ("jamp1241", "wand1278"),
> ("kamb1315", "wand1278"), ("kira1252", "wand1278"), ("masf1235",
> "wand1278"), ("maza1303", "wand1278"),
> ("mura1277", "wand1278"), ("nucl1682", "wand1278"), ("ziog1238",
> "wand1278"), ("mofu1249", "marg1267"),
> ("meri1245", "mofu1249"), ("dugw1239", "meri1245"), ("mike1242",
> "dugw1239"), ("mere1246", "meri1245"),
> ("dugu1258", "mere1246"), ("zulg1242", "meri1245"), ("gemz1238",
> "zulg1242"), ("mine1239", "zulg1242"),
> ("zulg1243", "zulg1242"), ("mofu1250", "mofu1249"), ("mofu1248",
> "mofu1250"), ("dime1245", "mofu1248"),
> ("gudu1251", "mofu1248"), ("mass1267", "mofu1248"), ("moko1254",
> "mofu1248"), ("njel1238", "mofu1248"),
> ("zidi1238", "mofu1248"), ("nort3046", "mofu1250"), ("dour1242",
> "nort3046"), ("waza1238", "nort3046"),
> ("toko1243", "mofu1249"), ("mada1293", "toko1243"), ("molo1266",
> "toko1243"), ("muya1243", "toko1243"),
> ("wuzl1236", "toko1243"), ("maro1246", "nort3156"), ("bald1241",
> "maro1246"), ("nort3047", "maro1246"),
> ("mutu1250", "nort3047"), ("sout3051", "maro1246"), ("mimi1245",
> "sout3051"), ("mutu1251", "sout3051"),
> ("rumm1238", "sout3051"), ("musg1255", "nort3156"), ("bium1279",
> "musg1255"), ("musg1256", "bium1279"),
> ("mbar1260", "musg1256"), ("musg1254", "musg1256"), ("beeg1236",
> "musg1254"), ("lugg1238", "musg1254"),
> ("mani1302", "musg1254"), ("mpus1238", "musg1254"), ("muzu1238",
> "musg1254"), ("ngil1246", "musg1254"),
> ("vulu1239", "musg1254"), ("musk1256", "bium1279"), ("koto1264",
> "musg1255"), ("budu1265", "koto1264"),
> ("kuri1265", "budu1265"), ("nort3049", "budu1265"), ("nucl1686",
> "budu1265"), ("sout3052", "budu1265"),
> ("koto1265", "koto1264"), ("afad1236", "koto1265"), ("malg1250",
> "koto1265"), ("doug1242", "malg1250"),
> ("droo1238", "malg1250"), ("goul1242", "malg1250"), ("mara1413",
> "malg1250"), ("nucl1688", "malg1250"),
> ("wali1273", "malg1250"), ("masl1241", "koto1265"), ("nucl1689",
> "masl1241"), ("saoo1238", "masl1241"),
> ("mpad1242", "koto1265"), ("bodo1278", "mpad1242"), ("diga1245",
> "mpad1242"), ("maka1322", "mpad1242"),
> ("nucl1690", "mpad1242"), ("shoe1243", "mpad1242"), ("woul1238",
> "mpad1242"), ("ngal1301", "koto1265"),
> ("sout3145", "bium1280"), ("bium1271", "sout3145"), ("bata1316",
> "bium1271"), ("baca1245", "bata1316"),
> ("baca1246", "bata1316"), ("muly1238", "baca1246"), ("opal1238",
> "baca1246"), ("wadu1238", "baca1246"),
> ("bata1314", "bata1316"), ("dems1242", "bata1314"), ("garo1255",
> "bata1314"), ("jira1247", "bata1314"),
> ("kobo1254", "bata1314"), ("mala1531", "bata1314"), ("ndee1246",
> "bata1314"), ("riba1250", "bata1314"),
> ("wadi1258", "bata1314"), ("zumu1241", "bata1314"), ("fali1290",
> "bata1316"), ("fali1285", "fali1290"),
> ("gude1246", "fali1290"), ("fali1286", "gude1246"), ("fali1287",
> "gude1246"), ("fali1288", "gude1246"),
> ("fali1289", "gude1246"), ("gudu1250", "bata1316"), ("kumb1278",
> "gudu1250"), ("holm1250", "bata1316"),
> ("jimi1254", "bata1316"), ("djim1239", "jimi1254"), ("jimo1235",
> "jimi1254"), ("mala1532", "jimi1254"),
> ("wadi1259", "jimi1254"), ("zumo1247", "jimi1254"), ("ngwa1251",
> "bata1316"), ("nzan1240", "bata1316"),
> ("dede1238", "nzan1240"), ("hood1240", "nzan1240"), ("lovi1238",
> "nzan1240"), ("maga1269", "nzan1240"),
> ("maih1239", "nzan1240"), ("muti1238", "nzan1240"), ("nggw1243",
> "nzan1240"), ("paka1255", "nzan1240"),
> ("roge1238", "nzan1240"), ("shar1250", "bium1271"), ("shar1249",
> "shar1250"), ("tsuv1243", "shar1250"),
> ("zizi1238", "shar1250"), ("bium1274", "sout3145"), ("buwa1244",
> "bium1274"), ("buwa1243", "buwa1244"),
> ("gava1241", "buwa1244"), ("daba1262", "bium1274"), ("maza1304",
> "daba1262"), ("kola1291", "maza1304"),
> ("musg1253", "maza1304"), ("nucl1683", "daba1262"), ("nive1238",
> "nucl1683"), ("polo1246", "nucl1683"),
> ("mbed1242", "bium1274"), ("mina1276", "bium1274"), ("besl1239",
> "mina1276"), ("gamd1238", "mina1276"),
> ("jing1267", "mina1276"), ("bium1275", "sout3145"), ("east2649",
> "bium1275"), ("boga1251", "east2649"),
> ("gaan1243", "east2649"), ("gabi1247", "gaan1243"), ("nucl1684",
> "gaan1243"), ("hwan1240", "east2649"),
> ("west2707", "bium1275"), ("jara1274", "west2707"), ("tera1251",
> "west2707"), ("bura1293", "tera1251"),
> ("nyim1251", "tera1251"), ("pidl1239", "tera1251"), ("mata1311",
> "sout3145"), ("cuvo1236", "mata1311"),
> ("mafa1239", "mata1311"), ("cent2189", "mafa1239"), ("koza1239",
> "cent2189"), ("ldam1238", "cent2189"),
> ("moko1255", "cent2189"), ("moko1256", "cent2189"), ("ouza1238",
> "cent2189"), ("east2648", "mafa1239"),
> ("roua1238", "east2648"), ("soul1242", "east2648"), ("nucl1678",
> "mafa1239"), ("west2706", "mafa1239"),
> ("mago1253", "west2706"), ("mavo1238", "west2706"), ("mefe1242",
> "mata1311"), ("muhu1241", "mefe1242"),
> ("nucl1679", "mefe1242"), ("sera1269", "mefe1242"), ("shug1252",
> "mefe1242"), ("suku1272", "sout3145"),
> ("unun9878", "bium1280"), ("jilb1238", "unun9878"), ("east2632",
> "chad1250"), ("east2633", "east2632"),
> ("bare1279", "east2633"), ("guil1240", "bare1279"), ("jalk1246",
> "bare1279"), ("komi1275", "bare1279"),
> ("saka1296", "bare1279"), ("east2709", "east2633"), ("dang1275",
> "east2709"), ("birg1240", "dang1275"),
> ("birg1239", "birg1240"), ("abgu1238", "birg1239"), ("agra1238",
> "birg1239"), ("dugu1257", "birg1239"),
> ("east2639", "birg1239"), ("mogu1251", "birg1240"), ("koff1242",
> "mogu1251"), ("mogu1252", "mogu1251"),
> ("mogu1253", "mogu1251"), ("mogu1254", "mogu1251"), ("tora1267",
> "birg1240"), ("dang1276", "dang1275"),
> ("bidi1241", "dang1276"), ("biga1242", "bidi1241"), ("gara1267",
> "bidi1241"), ("jekk1238", "bidi1241"),
> ("nalg1238", "bidi1241"), ("oboy1238", "bidi1241"), ("dang1274",
> "dang1276"), ("cent2187", "dang1274"),
> ("east2637", "dang1274"), ("west2704", "dang1274"), ("miga1249",
> "dang1276"), ("damb1250", "miga1249"),
> ("doga1242", "miga1249"), ("gami1251", "miga1249"), ("nucl1674",
> "miga1249"), ("unun9877", "dang1276"),
> ("jonk1238", "unun9877"), ("doug1241", "jonk1238"), ("musu1240",
> "jonk1238"), ("mabi1242", "dang1275"),
> ("mubi1247", "east2709"), ("kaja1254", "mubi1247"), ("masm1239",
> "mubi1247"), ("mubi1246", "mubi1247"),
> ("zire1244", "mubi1247"), ("east2710", "east2633"), ("mawa1270",
> "east2710"), ("saba1281", "east2710"),
> ("saba1276", "saba1281"), ("soko1263", "saba1281"), ("beda1245",
> "soko1263"), ("nucl1673", "soko1263"),
> ("tamk1242", "saba1281"), ("ubii1238", "east2710"), ("muku1242",
> "east2633"), ("doli1242", "muku1242"),
> ("gugi1238", "muku1242"), ("mezi1238", "muku1242"), ("moki1243",
> "muku1242"), ("mori1277", "muku1242"),
> ("segi1242", "muku1242"), ("east2640", "east2632"), ("east2641",
> "east2640"), ("kera1255", "east2641"),
> ("nyim1250", "kera1255"), ("kwan1285", "east2641"), ("aloa1239",
> "kwan1285"), ("gaya1250", "kwan1285"),
> ("kawa1287", "kwan1285"), ("mind1262", "kwan1285"), ("mobo1238",
> "kwan1285"), ("ngam1281", "kwan1285"),
> ("nucl1675", "kwan1285"), ("tcha1244", "kwan1285"), ("east2645",
> "east2640"), ("east2721", "east2645"),
> ("lele1276", "east2721"), ("nanc1253", "east2721"), ("east2722",
> "east2645"), ("gabr1256", "east2722"),
> ("gabr1253", "gabr1256"), ("kimr1241", "gabr1256"), ("buru1318",
> "kimr1241"), ("kimr1242", "kimr1241"),
> ("tchi1253", "kimr1241"), ("kaba1292", "east2722"), ("gabl1238",
> "kaba1292"), ("toba1280", "east2722"),
> ("gabr1254", "toba1280"), ("moon1238", "toba1280"), ("nucl1677",
> "toba1280"), ("east2775", "east2640"),
> ("east2643", "east2775"), ("mire1238", "east2643"), ("ndam1251",
> "east2643"), ("ndam1252", "ndam1251");
>
> WITH RECURSIVE tree(child_id, parent_id, steps) AS (
> SELECT child.id AS child_id, child.id AS parent_id, 0 AS steps
> FROM languoid AS child
> UNION ALL
> SELECT tree.child_id AS child_id, parent.parent_id AS parent_id,
> tree.steps + 1 AS steps
> FROM tree JOIN languoid AS parent ON parent.id = tree.parent_id
> WHERE parent.parent_id IS NOT NULL
> )
> SELECT languoid.id, (SELECT group_concat(path_part, "/") AS group_concat_1
> FROM (
> SELECT tree.parent_id AS path_part
> FROM tree
> WHERE tree.child_id = languoid.id ORDER BY tree.steps DESC)
> ) AS path
> FROM languoid
> ORDER BY languoid.id;
> _______________________________________________
> sqlite-users mailing list
> sqlite-users@mailinglists.sqlite.org
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
