Abstraction boundaries are optimization boundaries
blog.snork.dev
blog.snork.dev
On the other hand the classic data abstraction story (signatures/interfaces for structures/modules) naturally allows for selecting or optimising implementations depending on uses. There was some great work done in the early 2000s on that (see [4]) and I'm sure the state-of-the-art has moved on since [5].
[1] https://dblp.org/pid/d/SKDebray.html
[2] https://en.wikipedia.org/wiki/Self_(programming_language)
[4] https://dblp.org/pid/59/4501.html
[5] https://en.wikipedia.org/wiki/Interprocedural_optimization
> This problem is usually caused by a leaky abstraction; the ORM, or whatever database abstraction you are using, can’t anticipate that it would need to send N queries, so it can’t automatically optimize this down to a single query.
If you do an if-statement with an ORM before doing an update-statement, the result of the if-statement is already stale before the update occurs. If you skipped the ORM and put your if-statement as a where-clause, it's less of a problem.
> However, this only works since Haskell is declarative / pure; the low-level operational semantics (like evaluation order) are abstracted away from the programmer, and as such are amenable to optimization.
What else is declarative / pure? SQL. Not ORMS.
Thank you. People so often forget (or don’t realize) that their RDBMS is also doing a ton of optimization on their query, and a primary reason it’s able to do so in real-time is because SQL is declarative.
With DelegateDecompiler, you can turn native lambdas into Linq Expressions. (You just need to re-wrap the decompiled method body to remove the extra "this" parameter from the lambda). With this, you can write C# code, and it will generate SQL code.
In this EF code, we're deducting an amount from some balance, not necessarily the highest balance:
// Find the highest balance
var maxAccount = await db.MyAccounts.OrderByDescending(x => x.Balance).FirstAsync();
...
// Deduct an amount
maxAccount.Balance -= amount;
To solve this, maybe instead best practice would be to ensure the database connection is not in a global variable and must be passed down. That would make it more obvious when a database is improperly used within a loop.
The same problem exists for any expensive operation within a loop (say, a database query while parsing the results of an API call, or vice versa).
The fundamental issue isn't just that your compiler doesn't understand SQL. The problem is that your compiler doesn't understand how data is or will be stored. It's blind to the current state of the dataset.
For example, maybe it's the case that the data is stored in a hashtable and it's rarely written. In that case, N+1 might actually be the right way to query the data to avoid excessive read locks across the database.
Perhaps the data has 1, 2 or several indexes created against it. Those indexes can change at anytime and have to be consciously made as building them can take a lot of resources.
RDBMS build up a huge amount of statistics for optimizations purposes. That's all information you'd have to have the compiler JIT into the application to get similar performance or to have a good feeling for how to do the optimization.
It's correct that abstraction boundaries are optimization boundaries, but I don't think you need to make queries part of the language itself to raise the boundary.
To give a concrete example, take the Django ORM in Python. If you write a function which returns a single database record, then calling that function many times in a loop is naturally going to result in an n+1 query. However, if you instead return a QuerySet, then what you're returning is a lazily-evaluated sequence of records. Then, the caller can make the choice on whether to immediately evaluate the query (when they only need one record) or collect together a bunch of QuerySets and union them into a single query.
In other words we give the caller more control and thus more opportunity to optimize for their use case.
The key is capabilities rather than implementation. If your data structure is good at iteration and bad at random access, present an abstraction that supports enumeration but not indexing. But don’t present an abstraction that hands out Nodes and lets the caller mess around with their Next pointers.
In that case you might just abandon ORM and preload the context with something more efficient.
Take a look at last decade's solution to this problem:
https://github.com/facebook/Haxl/blob/main/example/sql/readm...
SQL's declarative model has an impedance mismatch with imperative programming, ORMs attempt to deal with that mismatch.
SQL hides complexity but Codd's goals when developing the relational model was to allow non programmers to access data.
The design decisions and tradeoff analysis was massively different than just an abstraction targeting developers.
There are many different persistence models that have vastly different tradeoffs, costs and benefits.
Balancing integration and disintegration drivers are complex and can impact optimization in many ways.
Technically ORMs attempt to deal with the mismatch between relations[1] and the rich data structures (objects) general purpose programming languages normally allow expression of. Hence the literal name: Object-Relation Mapping. That SQL, the language, is declarative is immaterial.
> but Codd's goals when developing the relational model was to allow non programmers to access data.
That is unlikely. He was staunchly opposed to database vendors adding "veneer" to make use more friendly and considered SQL an abomination. Codd was dead set on mathematical purity, which is, I'd argue, also why his vision ultimately failed in practice as actual relational databases are too hard to understand for those not well versed in the math.
[1] Technically tables, since we're talking about SQL, which isn't relational. But the mapping idea is the same either way.
The relation is the table, normalization, foreign keys, candidate keys etc are all extensions to that base model for Codd.
Some of the impedance mismatch is due to that, and not just the declarative nature or extensions
Specifically I think the Alice book covers how with a candidate key + the remaining tuples in the row form the row but only the candidate key has an identity, the rest of the row is a substring.
Some quotes from the link, but searching for 'user' will hit what I think justifies my interpretation.
> Future users of large data banks must be protected from having to know how the data is organized in the machine (the internal representation).
> To sum up, it is proposed that most users should interact with a relational model of the data consisting of a collection of time-varying relationships (rather than relations). Each user need not know more about any relationship than its name together with the names of its domains (role qualified whenever necessary): Even this information might be offered in menu style by the system (subject to security and privacy constraints) upon request by the user.
No. A table is a list/multiset of tuples, while a relation is a set of tuples. If you squint hard enough they might look similar, but they are not the same. The relational model has no concept of tables.
> Some of the impedance mismatch is due to that
ORM doesn't really have an impedance mismatch in and of itself. It is just a data transformation.
The impedance mismatch that is oft spoken of in association with ORM revolves around the N+1 problem. This is where you get some bizarreness that has to lean on hacks to overcome the real-world constraints that the mathematical model doesn't account for. If you are using something like SQLite that isn't so much of a problem in practice, of course.
The typical normalization let's say in a star schema is viewable as a least fixed point. FO+LFP=P
It is similar to what Codd called adjacency lists, which luckily died in the 80s, because they conflicted with real adjacency lists. recursive CTEs add transitive closure, which when added to FO gets you to L or NL, I forget which .
Still it doesn't matter, the relational part of the relational model is attributes or column names...it is equivalent.
The relational part is defined, most importantly, by the set. That was key to Codd's model, and the source of his primary criticism of SQL.
But his ideas went out of fashion long ago. Postgres, pre-1995, was the last time we saw a relational database anyone heard of. Sure, there have been some esoteric attempts more recently to revive the concept, but they never went anywhere. For all intents and purposes the relational model is dead. We live in a tablational world now.
> it is equivalent.
It is not, though. In fact, I posit that lists/multisets are easier to reason about, at least where one doesn't have a strong mathematical understanding (i.e. the layman), and that is why SQL "won". A list, if carefully constrained, can represent a set — which is maybe what you are struggling to suggest — but that does not make it a set.
Especially if I add the constraint that rows have to be unique?
Relations=Tables Rows=Tuples Columns=Attributes
I think we may be from different schools of set theory, where I am from the more abstract direction, where set membership, inclusion and equality are separate concepts and don't need to be decided on to define a relation.
Not that my view is better just different.
I just happened to come through the {{foo},{foo}}=={{foo}} school.
This is kind of like saying that a dynamically-typed programming language is statically-typed because you can add tests to enforce the same constraints as what static typing enables.
There is a lot of truth in that statement, but you completely fail to capture the differences in calling said language statically-typed. And, sure, for a silly comment on HN, who cares, right? But on the other hand, what are you gaining by obscuring the differences? It is not like said programming language is somehow better because you call it statically-typed. It is still the same language no matter what you call it.
SQL does not follow the relational model, as it was proposed by Codd. And that's okay. Arguably it is better because of it. Why not call it what it is?
> Not that my view is better just different.
Of course you can view things however your little heart desires. You can even see what I call a chicken as being a relational database if that is what floats your boat. But we are not talking about your view, we are talking about Codd's view. Every single comment that preceded this was clearly about Codd's take, to the point that you even linked to some of his work for us to engross in his thoughts. And we know very well how Codd felt about tables. He wrote about everything he thought was wrong with SQL at length.
What is generally considered Standard set theory today is typically ZF(C), which can be viewed and was intentionally developed as what is not called a "material set theory" or sometimes a "membership based set theory"
In ZF(C), sets are characterized only by the binary “∈” operation and propositional equality of sets.
It is actually the less common schools like the Elementary Theory of the Category of Sets (ETCS), where individual elements have no identity and must be unique.
There are well documented disagreements between Zermelo and Frege vs Cantor and Lawvere, was the former was for membership and the later were against it.
With ∈ or "is a member of" both of the following hold:
Given a set A={1,2,3,4}; 3 ∈ A
Given a set A={1,1,2,2,3,3,4,4}; 3 ∈ A
In computer science and databases, this is less than just a trivial factoid depending how deep you get, it will directly relate to how you can trade space for time or reduce communication costs to save on time.
And yes even historically there were very popular network protocols where they would append the same element to a set and shift the complexity from insert time to read time.
To be clear I am not asserting any claim of better outside of local context to doing so.
You are absolutely correct that no production quality RDBMs are based on Codd's rules. That absolutely doesn't change the fact of what the term 'relational model' means, nor does it remove the reality that they follow enough of it so that where it breaks, even from a set centric perspective, is directly related to that origin. Especially in parallel, distributed systems that are the norm now.
And the fact that things moved, doesn't change the reality that the 'relation' in the 'relational model' is as described in previous posts.
However, we are specifically talking about Codd. His definition for the relational model does not match anything we use today. Tablational databases are something quite different.
So, sure, you can call what I call dynamically-typed languages statically-typed if you want. You're not wrong. Definitions cannot be wrong, fundamentally. But it is different, and since we're not talking about your definition and never were...
> The term relation is used here in its accepted mathematical sense. Given sets S_1, S_2, ..., S_n (not necessarily distinct), R is a relation on these n sets if it is a set of ntuples each of which has its first element from S_1, its second element from S_z , and so on.’ We shall refer to S_i as the jth domain of R.
Note the "(not necessarily distinct)" part and how he uses a table to describe it on the same page.
From what is called the "Alice book" Foundations of Databases - Abiteboul, Hull, Vianu[1] the seminal textbook in database theory.
> In the 1970s, Codd’s relational model revolutionized the field. In this model, humans view the data as organized in relations (tables), and more “declarative” languages are provided for data access.
Unfortunately I can't find chapter 3, where the relational model is described in detail online.
But for more concrete SQL as defined in ISO/IEC 9075-2:1999 (E)[2]....calls them "tables"
Outside of didactic simplifications or domain specific conventions I am not finding anything.
I could be convinced otherwise...but as every real world practical RDBMS has to impose order of often multple tables to scale, through logs, cache etc...and as what everyone agrees is SQL has to support various transaction isolation levels which ensures that on a concrete implementation detail, that rows aren't unique, but that the special case of a membership function, expressly being an 'element' is supported in them all. Plus you only get DISTINCT with a candidate key, and by default SQL is using bags/multisets anyway...there is just to much undefined behavior with indistinct rows and so we avoid them but they are allowed.
In fact, while useful for teaching and day to day use, you are actually violating the axiom of pairing, which is also used to construct the singleton's in modern ZFC.
In fact AC is called the well-ordering axiom by some, expressly because it allows it.
I think you are possibly confusing the absence of ordering from the users perspective?
Either way I have provided actual cites and would appreciate the same, because I would rather learn where I am wrong than prove myself right.
[0] https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf [1] http://webdam.inria.fr/Alice/pdfs/Chapter-1.pdf [2] https://web.cecs.pdx.edu/~len/sql1999.pdf
You did, but I am not sure why. Best to come to a discussion to discuss it yourself. If you have to rely on third-parties to write for you, why bother participating at all?
But, for the sake of trying to demonstrate good faith, I'll break my rule of not providing citations this once and give you this:
Codd, E.F. (1988) Fatal Flaws in SQL:
"Relations in the relational model and in mathematics do not have duplicate rows."
If you want to still call it as such, go nuts! You can call it a "flying monkey" for all anyone cares. But, if you do call SQL relational, I am interested in what you would call a database that does adhere strictly to Codd's model since also calling it relational wouldn't paint an accurate picture. There are clear differences, as you even told earlier.
It is important to realize that relations are abstract data structures that we treat like sets, not objects we constructed from sets.
If you want to do the set specific approach, reviewing any books on basic set theory and their intentional and extensional set definitions with show your argument is confusing the map for the territory.
The set operations applied to relations produce relations or relations of relations.
Same in material set theory, excluding membership, the only set operation that isn't predicated, this operating on the set, and not opening it up to act on its members.
While the platonic ideal may seem to make it seem different, urelements/atoms/individuals are not what those operations are acting on.
That is what made ZF(C) different.
Remember that Codd was targeting the hierarchical model, records etc...
While the other camp was targeting the network model, specifically using lists.
From the platonic view, uniqueness is a trivial, syntax property, you make that choice, and it has costs.
The typical example is I am a person who lives in (a member) the US, and the US is a member of the UN. Yet I am not a member of the UN.
Similar challenges are why Codd added Recursive CTEs to capture some of the expressiveness of the network model, which OOP is related to.
The problems Codd was targeting in your cite were mostly addressed post SQL99 with the addition of structural data options, specifically challenges with foreign keys.
The intersection of a column and a row being a field, which maps to cobol record concepts is why tables and relations are equal.
If you look at the 1970 paper I provided above, you can see where his concrete implementation using arrays calls out it isn't equal and requires distinct entries.
Note the link to the author's page allowing you to download the Alice book in its entirety works now.
I encourage you to get it.
The concept of a relation as a data structure is far more abstract than it seems.
Yes Codd did attempt to become more prescriptive later, but there is a reason no one exactly implemented it, just like platonic ideals it doesn't really work for real world needs, nor is it required for ACID transactions.
But the relation is still a binary operations that is equivalent to a table.
That paper is the criticism (of SQL). Is the contention here simply about not understanding that we're talking about what Codd thought, not what others thought/think? It seems abundantly clear what Codd thought. His language doesn't offer a whole lot of ambiguity as far as I am concerned.
> The concept of a relation as a data structure is far more abstract than it seems.
If you want to interpret that way, sure. You can imagine a relation any way you want. But that's not what we're talking about.
> From the platonic view, uniqueness is a trivial, syntax property, you make that choice
Absolutely. Akin to choosing to define your program constraints in tests instead of using a type system. The end result is effectively the same, but one offers certain guarantees out of the box, while the other relies on you to get things right. They, while effectively the same, are not identical. There is good reason why we have static and dynamic typed classifications, just as we have relational and tablational. There is not some kind of magic in there, it is merely a communication device so that others can figure out what you are trying to say.
> but there is a reason no one exactly implemented it
Right, because the relational model, as Codd saw it, isn't really all that good, at least not in real-world scenarios. Just as we've brought up many times before. There is good reason why SQL "won". Why embarrass SQL by calling it relational?
But, if you wish to — and fair enough if you do, I would still love to know what you would call a database that is built in the eye of Codd? It cannot also be relational if SQL is deemed as such. As you point out, there are clear differences. Calling them both relational would be confusing.
As you said, the challenge of understanding math is why the relational vision failed, but also why the industry keeps reviving the network data model.
Theoretically all. However, often ORM and query building are combined into a unified framework that links them together into a higher order abstraction. You may know this type of thing by names like the active record pattern or the data mapper pattern, with concrete implementations like ActiveRecord and Entity Framework. Such frameworks often make it difficult to use the ORM component in isolation (and even where that isn't the case, doing so largely defeats the purpose of using the framework anyway), and as such you become constrained by the limits of the query builder. I suspect that is what you are really thinking of.
But due to the constraints of its querying abilities, not the ORM aspect. ORM is only concerned with the data once it is materialized. How you materialize that data, be it the product of a network relationship, or a fact-oriented model, is immaterial. Remember, EF isn't just an ORM toolkit. It is an ORM toolkit plus a number of other features. But since we're only talking about ORM those other features don't relate to the discussion.
> while structs and pointers are naïvely easy to understand, that's why ORMs remain popular.
And, well, because it is an all-round good idea to turn externally-sourced data models into internal data models anyway. It makes life a hell a lot easier as things start to change over time. Even if you were to receive serialized data that is shaped exactly in the structure you want it at a given moment in time, you still would want to go through a mapping process to provide the clean break from someone else's data model and your own. This isn't limited to SQL database tables. You'd do the same if you received, say, JSON from a web service.
The fallacy with lazy loading ORMs is that they often give you no or very poorly suited methods for specifying what needs to be loaded or not. Even when they do, the problem is that you cannot separate the data loading aspects from the querying aspects. You end up with data repository service classes that do "findBooksByYearWithAuthorAndSequels" rather than just "findBooksByYear" and a separate way for specifying "WithAuthorAndSequels" that doesn't require you to come up with a ridiculous naming scheme.