Quite the difference indeed ... sqlite> .once q2 sqlite> 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; Run Time: real 1.968 user 1.968750 sys 0.000000
sqlite> .once q1 sqlite> 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; Run Time: real 0.007 user 0.000000 sys 0.000000 --- The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume. >-----Original Message----- >From: sqlite-users [mailto:sqlite-users- >[email protected]] On Behalf Of Jake Thaw >Sent: Saturday, 22 December, 2018 17:14 >To: SQLite mailing list >Subject: Re: [sqlite] SQLite 3.26.0 recursive CTE performance >regression > >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 ><[email protected]> 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 >> [email protected] >> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite- >users >_______________________________________________ >sqlite-users mailing list >[email protected] >http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users _______________________________________________ sqlite-users mailing list [email protected] http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
