launchbadge
Fix compile time verification performance regression for sqlite
The sqlite CTE feature (#1816) introduced severe performance degradation, and this PR attempts to fix it.
This patch drastically reduces search space by adding memorization based on register type and cursor data type. Pushing new states on to the Stack is guarded by a HashSet, where if no new information is gained about an instruction (i.e. different register/cursor data type), the instruction will not be searched again.
Now the example query in #1921 only takes 5s to verify instead of several minutes. It might be possible to further optimize this by stop tracking unnecessary information, which could save a lot of memory allocations.
@liningpan do you have time to address the CI failures I mentioned before? The logs are gone now but if you amend your commit to update the SHA and push it to re-run the workflows we'll get new logs.
I though initially CI failed at formatting, and I believe I fixed them. I was waiting for you to trigger CI.
Get Outlook for iOShttps://aka.ms/o0ukef
From: Austin Bonander @.> Sent: Friday, September 2, 2022 8:47:26 PM To: launchbadge/sqlx @.> Cc: Lining Pan @.>; Mention @.> Subject: Re: [launchbadge/sqlx] Fix compile time verification performance regression for sqlite (PR #1946)
@liningpanhttps://nam12.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fliningpan&data=05%7C01%7C%7C0437255e19414a35a8fc08da8d45dfb7%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C637977628498825884%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=%2Bxm%2FzrXbKTNRFQq%2BHgDMFdLhR48R6sLZrf7TJ0%2F657Y%3D&reserved=0 do you have time to address the CI failures I mentioned before? The logs are gone now but if you amend your commit to update the SHA and push it to re-run the workflows we'll get new logs.
— Reply to this email directly, view it on GitHubhttps://nam12.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Flaunchbadge%2Fsqlx%2Fpull%2F1946%23issuecomment-1236006508&data=05%7C01%7C%7C0437255e19414a35a8fc08da8d45dfb7%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C637977628498825884%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=y%2B65xW0EQh4GiG1xEboxT1f%2BkqmoCe9kfyXncYWFd40%3D&reserved=0, or unsubscribehttps://nam12.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fnotifications%2Funsubscribe-auth%2FAED47ZU6MNZAMJBH5FQ74ZTV4KNZ5ANCNFSM52PTDQRA&data=05%7C01%7C%7C0437255e19414a35a8fc08da8d45dfb7%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C637977628498825884%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&sdata=5S9awzkL1gzxpigJCZm58Hl1J5kNCPcw%2B3sAsNEn%2Bi8%3D&reserved=0. You are receiving this because you were mentioned.Message ID: @.***>
Yeah, sorry. It's easy to get sidetracked and forget about PRs in the queue. I don't even have the "Approve and Run" button anymore though, you'll need to update the branch for it to come back I think. A simple rebase should do it.
Although the CI pipeline appears to be passing, I'm not 100% certain about the correctness of this patch and the additional memory consumed by the branch state hash table. That being said it should still use way less memory than what's previously stored in the query history structure.
I would also like to hear the original author's (sqlite CTE #1816) opinion @tyrelr.
Overall, I think this is a good approach and it worked when I tested it. It is a bit unfortunate to need a 3rd way of storing column-states. But there is no simple way to avoid that due to HashMaps not implementing Hash (with good reason).
Based on reading the code, the only piece of information that seems to be discarded is which register is pointed at by a PseudoCursor. That should be almost impossible to cause an issue in practice. Literally everything in the state except that pseudocursor would need to be identical to cause a mistaken short-circuit. Then, for that mistaken short-circuit to matter, the two nearly identical states would need to result in significantly different output data types. Such a query plan would be valid, but would be unlike any other query plan I've seen sqlite generate.
@liningpan @tyrelr is it possible for this PR to cause type/null inference changes?
In practice, I expect that a different result would never actually happen. It requires a very atypical query plan for the issue above to occur, I expect sqlite would never generate such a plan.
But theoretically, this could change type/null inference if sqlite DID happen to generate that weird query plan.
For safety, I've earmarked this for 0.7.0, which I've started working on.