Are there canonical-forms for database queries?

Question

Say I want to make an "Optimized query generator". Basically a SQL query optimizer that is a lot better than what can be put in an SQL server based on time/space limitations. It would take a query and DB stats as input and generate an SQL query tailored for the target system that will quickly optimize to a nearly ideal plan.

How much of SQL would need to be supported? Is there a subset of SQL that is flexible enough to easily describe most useful queries but enough smaller than full SQL to make it worth trimming it down to? Also is there a better way to describe queries if you don't need to stick "close to the machine"?

I'm not thinking of a program that you would process existing SQL through but rather a tool for creating new SQL from. It wouldn't actual need to take SQL as input as long as the input language is able to describe the requirements of the query.

I guess another form of the question would be: are their any parts of SQL that are only there for performance and never improve readability/understandability?

---

As pointed out by someone doing this would require "tons of product-specific knowledge" and that (e.g. nested sub queries vs whatever, what kind of indexes should be used, that sort of thing) is exactly what the tool would be intended to encapsulate so that the user doesn't need to learn that knowledge.

---

note: I am not interested in generating actual query plans as that is the DBMS's job and can't be done from SQL anyway. I'm interested in a system that can automate the job of making good SQL for a given DBMS from an input that doesn't need to be tuned for that DBMS.

Answer 1

You might find the patterns in "SQL Queries for Mere Mortals" useful as they work through a structured canonical format starting with English descriptions.

Online at Safari, if you want to take a quick peek.

Answer 2

Bramha, I'm not sure if you know what you are asking. SQL Optimization isn't simply a matter of making sure that query components are in the right order. You seem to recognize that you'll need to have intimate knowledge of the indices, data page layouts, etc. etc. but you'd still be left with just reording query clauses unless you gain the appropriate "hooks" into the SQL Server query processor. Because that is what MS does - it essentially "compiles" queries down into a deeper, more fundamental level to optimize the data access.

Answer 3

I'm surprised to hear you describe SQL as "close to the machine". SQL itself is declarative rather than procedural, and one of the interesting aspects of relational databases is the freedom implementers have to innovate, since SQL itself dictates very little about how the queries should be executed.

I think for sheer utility, it would be very difficult to improve on SQL. I'm not saying it's the perfect language, but it is the lingua franca of relational (and even some non-relational) databases.

Answer 4

umm...there are (I think, too lazy to google it) nine relational operators (scan, jump, hash-merge, etc.) that are used to construct the execution plan of a SQL query. The choice of operators is based on the usage statistics of the target database tables, available indices, et al.

It sounds like you're trying to recreate what the query planner already does...?

EDIT:

1. I don't think that most queries have that many options in how they can be executed, and
2. I don't think there is anything you could do to the SQL to force the DB engine to create an execution plan "your way" even if you did fine a more optimal solution.
3. unless you are planning on creating your own database engine!

I am very confused by this question; it looks like reinventing the wheel but with no wagon to mount it on!?

Answer 5

Is your intent to write this for a single specific database engine? If not, I suspect that you'll have a rather difficult time of this. Optimization of database queries relies heavily on the exact specifics of the engine's implementation and internals, as well as the tables, indexes, primary/foreign key relations, type and distribution of data, etc, etc. The actual logic of creating an optimized query would likely have very little overlap between different database engines. (For that matter, at least for MySQL the table type would make a huge difference on optimizations.) Each release of each supported DB engine may have significantly different characteristics, as well -- keep in mind that if you're generating SQL, then you need to be able to predict how the engine's own optimizer/query planner will handle the SQL you've generated.

The thing is, query optimization relies only weakly on relational theory, and very heavily on detailed knowledge of the DB's guts and the data being held. Even if you're able to extract the DB's metadata, I suspect that you'll have a difficult time producing a better query plan than the DB itself would -- and if you're not getting the DB's metadata, then your cause is hopeless.

Answer 6

Good luck - you've chosen to compete with such companies as Microsoft and Oracle, who live or die by how well their query optimizers do exactly what you propose. The first and primary way to compare one database product with another is with benchmark testing, where the same query workload is applied to each of them, timing measurements are taken, and the winner in most cases is determined by speed of execution.

The world will be impressed if you can do significantly better than the publisher on any of these benchmarks, using their products. At least you'll have a solid career opportunity with whichever one(s) you use.