SQLite 3.26.0 recursive CTE performance regression

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

SQLite 3.26.0 recursive CTE performance regression

Sebastian Bank
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
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: SQLite 3.26.0 recursive CTE performance regression

Richard Hipp-3
On 12/22/18, Sebastian Bank <[hidden email]> wrote:
>
> 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).

Thank you for the report.  Bisecting shows that the slowdown is a
result of the fix for ticket
https://sqlite.org/src/info/787fa716be3a7f650cac in check-in
https://sqlite.org/src/info/531eca6104e41e43

I'll see if we can find a way to get your query to run fast again
without breaking the fix.

--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: SQLite 3.26.0 recursive CTE performance regression

Jake
In reply to this post by Sebastian Bank
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
<[hidden email]> 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
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: SQLite 3.26.0 recursive CTE performance regression

Keith Medcalf

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-
>[hidden email]] 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
><[hidden email]> 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
>> [hidden email]
>> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-
>users
>_______________________________________________
>sqlite-users mailing list
>[hidden email]
>http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users



_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: SQLite 3.26.0 recursive CTE performance regression

Richard Hipp-3
In reply to this post by Sebastian Bank
On 12/22/18, Sebastian Bank <[hidden email]> wrote:
>
> 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).

There are now enhancements on a branch
(https://www.sqlite.org/src/timeline?r=reuse-subqueries) that should
fix your performance problem.

Since you seem to be someone who writes intense SQL, it would be
really cool if you could try out that branch and see if it solves or
causes any other problems.

--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: SQLite 3.26.0 recursive CTE performance regression

Sebastian Bank
Am 24.12.2018 um 13:12 schrieb Richard Hipp:

> There are now enhancements on a branch
> (https://www.sqlite.org/src/timeline?r=reuse-subqueries) that should
> fix your performance problem.
>
> Since you seem to be someone who writes intense SQL, it would be
> really cool if you could try out that branch and see if it solves or
> causes any other problems.

Thank a lot. After compiling at check-in 06de44ec, the example query as
well as my full query are back to the execution time from 3.25.3 again.

While the variant proposed by Jake is faster and simpler for getting
just the paths (thanks for that), the full query includes additional
things like selecting properties of certain ancestors along the path.

Best,
Sebastian
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users