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
