A couple of times where I've needed to parse SQL I would typically write a module for sqlite3 and get it to do the parsing for me. But annoyingly I can't remember _why_ I did this or what I was trying to achieve.
[0] https://15799.courses.cs.cmu.edu/spring2022/project1.html
Being read-heavy the app was an ideal candidate for output caching. But - there were no hooks in the admin code to add cache invalidation. And I wasn't going to crawl through 10s of thousands of badly written lines and add cache invalidation calls manually, because I would miss some.
So I hooked into the database layer, parsed the SQL queries and extracted the table names. The read-heavy pages on the frontend were tagged in the cache with the names of the tables they read data from. In the backend, I'd collect the table names in all the write SQL queries and then clear the cache that was tagged with these table names.
Working at the table level rather than row level it cleared more data than was needed, but it was simple and effective.
It worked really well but never went into production - in the end we forced a rewrite of the app. One day I'd like to revisit the idea.
A few examples:
- Inlining scalar function calls (less impactful now with Sql Server 2019)
- Removing joins from a query when we know it won't impact the number of records
- Deepening where conditions against derived tables
- Killing "branches" of union queries when they can be determined to not matter statically
Yes, we could write the queries that way in the first place, but it would make them harder to compose, more verbose, and harder for the programmer to communicate intent. Not to mention, often the user can impact what the query will be, making it less feasible.
Could I ask what your process is for detecting whether a rewrite rule is still useful in subsequent versions of the DBMS? Do you read the release notes and test things out manually, or do you have an automated A/B test thing going on?
Additionally, have you ever had a rewrite rule change from being beneficial to being detrimental after upgrading versions? If so, how did you detect that?
Thanks!
Edit: Also, what considerations do you have for rewrite rule order? Do you find that it makes a significant difference in practice?
We've never had a rule change from being beneficial to detrimental. For most of them, I don't think that would be possible, because they just involve giving Sql less irrelevant things to chew on. For a few of them, like the manual scalar function inlining, I could see that being possible, so we will just need to keep checking.
For rewrite rule order, I guess we just do the ones that can enable other optimizations first. So far, that has been pretty simple to determine. For example, when we trim joins from inner queries, we first trim their selections (depending on what is actually used in the outer queries).
Whatever you're doing is really confusing me (see my prev post). A multi-thousand line piece of the SQL I wrote was tested on mssql 2019 and there was a blatant perf. fuckup from it's previous home on mssql 2016 (or was it 2014). Poss. down to the new cardinality estimator, I dunno.
> For example, when we trim joins from inner queries, we first trim their selections (depending on what is actually used in the outer queries).
If you looked at the query plans you will see this happens automatically. And very reliably because it is easy (indeed, quite straightforward) to do automatically.
Also... 'we just read release notes' - these optimisations are not documented (except maybe in one place which they carefully undocumented after the 1st release) because these are trade secrets. The optimiser is one of the most important and carefully guarded parts of mssql - it's not in the notes and never will be.
No offence but... seriously, wat???
.
- Inlining scalar function calls (less impactful now with Sql Server 2019)
write them as table valued funcs and it'll inline them for you (ugly but it works and is easy)
.
- Removing joins from a query when we know it won't impact the number of records
That's just tree pruning. It does that
.
- Deepening where conditions against derived tables
If I understand you that's predicate pushdown. MSSQL does it well.
.
- Killing "branches" of union queries when they can be determined to not matter statically
Not sure what you mean. Can you give an example?
We tested all of these before taking the time to do the rewriting, and no, either they don't, or they way they did it isn't good enough. You can say I'm lying if you want, I'm not going to spend time arguing about it.
^1 specifically https://github.com/DerekStride/tree-sitter-sql , but there are a few others around too
Since some of the tables are multi-petabyte with thousand of downstream consumers, the savings have been in the millions of USD, because of CPU savings mostly, but also there is the benefit of improved wall time and data arriving much earlier to dashboards and reports.
We also created some other datasets that tell you how the tables are normally joined and another team created a ML model that now we use in an internal tool that automatically recommends the best join keys when you join 2 or more tables (since we have lots of historical info on that already stored).
We also had to create a very efficient table profiler to evaluate the candidates, because in some cases there are columns that are widely used in equi-where conditions, but their cardinality is very high, making them bad partition columns.
One guy created a parser that actually gets the most common values used to filter each column, I guess we could use that in the future to materialize some views; my original vision of the project was to continue with partial aggregations for common computations. The thing is there are several pieces of code that are pretty much copy/pasted and reused in many pipelines, so why not materialize those and rewrite the SQL of the subsequent pipelines to leverage the materialized version? huge savings there.
We are planning to present it in VLDB or a similar forum, there are some aspects of it that we need to 'clean' if we want to open source it.
Other parts of the system include the candidate evaluation and the module that computes the expected savings for the best candidate selected during evaluation; this system in particular has a lot of specific Presto and Spark logic that might need to get more general if we want to open source it.
In the class project mentioned elsewhere, I found normalizing queries to be pretty slow in practice (naive standardized formatting + query templatization, tried various Python libraries, settled on pglast). I didn't think about trying "skip if fingerprint matches", which may help considerably. Fast normalization is nice! :)
yes! that's something we are trying to do, since we have a way to create signatures for SQL statements and subqueries are just SQL statements then we can get all the "signatures" a query use and compare if other queries are using the same signatures. Then just sort those queries by number of times used and put some other perf metrics like IO/CPU needed to compute it and you get a good starting point.
Microsoft did something similar with Azure, using bipartite graphs, their solution was more advanced as they also baked in constraints like "the materialized view can't be more than X GB in size" but the end result is the same. (https://www.microsoft.com/en-us/research/uploads/prod/2018/0...)
- syntax highlighting
- algebraic manipulations
- optimization analysis of queries seen
- analysis of equivalence of queries
- query rewriting (for style, performance, etc.)
- RDBMS portability layer (implement a common
subset of SQL, port queries to different
engines; see previous item)
I briefly looked into Apache Calcite and DataFusion[2], but I am unsure if I am on the right track. If someone has any ideas about where to look, please let me know.
[1] https://stripe.com/en-gb/sigma [2] https://github.com/apache/arrow-datafusion
That looks like an entire DB engine, isn't it?
> map the public schema to the private schema
sounds like view.
It seems like a pretty major project as you describe it.
If you know about TTM, you might also know about "Applied Mathematics for Database Professionals". What I'm referring to is their "execution model 6" becoming possible *WITHOUT* any [procedural form of] coding [by mere programmers].
Another way of saying this is "You can have CREATE ASSERTION if you want to".
I'd appreciate you omitting the codeshitter ad-homs, it undermines your case.
Pretty sure no declarative statement can be made efficient automatically so that remains a dream (though one I will need to look at) so it will kill performance. I too hate procedural enforcements but there seems to be no way round them. Have you got a reliable statement anywhere that says efficient 'create assertion' in sql is possible in general?
AMfDbP book - it's on my reading list already. Thanks for the pointer.
codeshitter ad-homs : yeah well I know they are. The fact of the matter is the history between SIRA_PRISE and me (and why I did it in the first place) is now almost 20 yrs old, and I know how it's been received, and that's primarily due to (a) how the codeshitters (and the way how they are subject to the Dunning-Kruger effect) have come to dominate the entire industry and (b) how that economic system I too am bound to operate/survive in prevents the managers who control the system from taking "too much" (say, > 0.01%) risks.
And about "Pretty sure no declarative statement can be made efficient automatically so that remains a dream" : there fucking sure ain't no better way to piss me off, not just to the other side of the planet, but to plain outright Mars or Jupiter. You're just too pretty damn sure of yourself. AM4DP makes +- the same statement as you although the authors there still did manage to *NOT* make the same logically flawed inference from "not anybody knowing today how it can be done" to "cannot be done". You apparently fall into the category of people who do make that inference. The article exposing the exact opposite of your convictions was published in Oracle Users Magazine somewhere around 2013, IIRC. I'd need to look up the exact details by now, but it was already an incredible surprise Oracle User Group even wanted to publish on the solution of a problem that Oracle Corporation itself wasn'y (and still isn't, probably due to the power of certain people within that company who have been labeled 'bean keepers') prepared to invest in.
In fact, the only reason I wrote that article in the first place was Toon Koppelaars using that very word 'dream' (which you also used in your reply) to associate the idea with SQL's CREATE ASSERTION, when I already knew it needn't be a 'dream' no longer ... Well, if anyone just wanted to believe, which they don't, you inluded, apparently ... To Toon's credit, although he also used the adjective 'impossible' to qualify that 'dream', he did manage to end his title phrase with a *question* mark. You ended yours with an exclamation mark.
And just for the record, this statement is *NOT* to be interpreted as "every thinkable constraint can be implemented with sub-millisecond violation detection". Sunt certi denique fines, quos ultra citraque nequit consistere rectum. The "fines" in case being the bounds of what algorithmics as it is known today, can do for us. Constraints like "all the people who obtained a degree in mathematics must be paid in the top 5% of salaries" (if anyone ever wanted to formally declare and enforce any rule like that) inevitably takes us into realms of 2nd-order logic that no known algorithm today can guarantee us execution times like the ones we have grown accustomed to from what is supported by SQL systems these days).
As for "do you have a reliable statement" ... I have two answers but neither have the quality of being dependable on the academic level of meaning you might probably want to attach to the words "reliable" and "dependable". The first answer is "No, because the only other person in the entire world that I'm aware of achieving results in the same area is professor Davide Martinenghi and his PhD thesis on the subject, of which I don't even consider myself capable enough to academically assess the equivalence between his results and mine" and the second answer is "No, because that 'reliable' statement would have to be made by me myself and I have nothing(*) but my own implementation to 'prove' it and I'm very well aware that on an academic level, a seemingly working implementation is not a proof".
(*) I did write a paper on the subject and it's been seen by Chris Date (who by proxy answered that he was 'impressed'), by Hugh Darwen, and by Adrian Hudnott. And I will rather take it to my grave with me than disclose it any further.
And about the *scrutinously detailed subject* of your question whether "efficient 'create assertion' in sql is possible in general" : I have grown convinced that *IN SQL*, it isn't. But the reasons are *ENTIRELY* related to SQL's depending on 3VL. I have grown convinced (in fact, for my own conviction, I think I have sufficiently demonstrated) that in some *other* DMl language that *embraces 2VL*, it is *perfectly feasible*. And in fact, I think SIRA_PRISE itself is its own proof, in that respect : *ALL* the rules that SIRA_PRISE imposes as business rules on its users are implemented as mere declared database constraints on the catalog, and are enforced using the *exact* same machinery that also enforces the *user* declared business rules on the *user* databases. When I showed my system to a former colleague of mine who made his entire career in data [base] administration backed by a degree in mathematics, he merely responded that there just ain't no better POC than that.
" Standard SQL is relationally complete in its support for declarative constraints by permitting the inclusion of query expressions in the CHECK clause of a constraint declaration.
We do not yet know—and it is an important and interesting research topic—how to do the kind of optimization that would be needed for the DBMS to work out efficient evaluation strategies along the lines of the authors’ custom-written solutions. "
So it can't. But then you say.
> But the reasons are ENTIRELY related to SQL's depending on 3VL.
Easy to fix. Simply require the assertion to be defined on tables (ok, ok, relvars) with 'not null' on every column, also require a PK to ensure uniqueness, and you're away. Except you aren't.
I'm not going to argue with you. Your knowledge is clearly considerable but it comes with something extra I don't need.
That other snippet "Standard SQL is relationally complete ... CHECK clause ..." is technically correct, but the standard allows subqueries referencing other tables than the one the CHECK clause is on, but as far as I'm aware no product supports that (and the ones that do leave the user exposed to risk of faulty behaviour). Sadly, such a feature is necessary if we'd want to write, say, an FK constraint in the form of CHECK clause on the referencing table : CHECK (EXISTS (SELECT 1 FROM PARENT WHERE <FK equality tests here> ) ).
Also that's bloody odd because date or darwen (or both) explicitly called out this behaviour as flawed in SQL when in fact it's obviously logically consistent, and they know logic and SQL, so... why are they critising it? How very strange.
Again, thanks for pointing this out. How did I never realise this?
Events we receive e.g. from MySQL aren't fully self-descriptive, you need to know the schema they adhere to in order to interpret them. As table schemas can change over time and as -- due to the async nature of streaming the transaction log -- we may receive change events produced from before a table's schema was changed, we cannot simply query the current table schema. Parsing incoming DDL events is the only way for keeping the connector's view on the schema in sync.
You can also reverse engineer missing foreign key relationships by parsing all of an apps' stored procedures (for relationship diagrams, etc.). Or just what external entities are referenced from "other" databases to get an idea of minimal schemas needed for automated testing.