Is this SQL databases or No-SQL? [LWN.net]

Is this SQL databases or No-SQL?

Posted Mar 28, 2014 1:03 UTC (Fri) by Wol (subscriber, #4433)
In reply to: Is this SQL databases or No-SQL? by intgr
Parent article: A discussion between database and kernel developers

> If I understand correctly, it seems that these delimiters are exposed to the coder, which invites misuse: are you sanitizing these values correctly in the input data?

Bang on - there are various safeguards in place that help prevent misuse, but at the end of the day it's down to the programmer to get it right.

> I haven't used Oracle much in particular, but I think query optimizers are a godsend based on my experience with PostgreSQL.

Let's look at what a relational optimiser has to do. Assuming crude unoptimised data access, EVERY row you look for has to search half the table!

Okay, if I'm only searching for a single row in Pick, it's quite likely I'll have to do the same. BUT!!!

Let's take the example of an invoice. Have you keyed it on the invoice number? I quite likely have. If I have, my mvDBMS can tell the OS where on the disk the data I am looking for is, with a 97% chance of being right. "Open file X, seek to position Y, read that block". If your invoice table is big (let's say 1Mb) you've got to read 1/2Mb to find it!

I've now got ALL the invoice data. Chances are (in fact it's pretty certain) your invoice data is plastered over several tables, so you are going to get further clobbered. Then what happens if you want to access the related customer details? Yet again, you probably have the data plastered over several tables and have to read half of each table to retrieve the data. My invoice record will contain the company key, and once again, I will be able to tell the OS exactly where to find it with a 97% chance of being right.

In other words, a raw unoptimised RDBMS data access is incredibly inefficient, and it gets worse as the database gets bigger. An efficiency of 1% is probably very good! So an optimiser doesn't have to be very good in order to earn its keep.

But for Pick? Let's take my worst case - assume I haven't keyed on invoice no. If I don't have an index I'll have to scan the entire table - so my worst case is equal to yours (if I'm being stupid!) But all I've got to do is declare an index on the invoice no ... and it takes one disk read (97% probability) to convert from invoice no to invoice key, and one more to retrieve the invoice.

(Okay, you can index your primary invoice table on invoice no too, but then you have to index all your subtables too, with all the overhead that involves.)

So. Your SQL optimiser can achieve a doubling of performance by increasing efficiency by a fraction of a percent.

My Pick optimiser (if I had one) can achieve a maximum of 1/3 of one percent increase in performance before it hits the unbreachable barrier of perfect efficiency. It's just not worth spending any effort searching for those sort of gains.

Oh - and there's another thing to take home from this. When making my claims about RDBMSs, I'm mostly speculating. You see, I'm *not* *allowed* to know what's going on under the covers, so I'm forced to guess. Because I know pretty much exactly what's going on under the covers of Pick, I can use logic to reason about it, and PROVE what's going on. I've got figures to work with. (Okay, the figures I have are the inverse of 97%. In a properly balanced Pick file, it takes on average 1.05 "get this block from disk" commands to score a direct hit on the target data. Oh, and rebalancing the file after a write (if that's necessary) incurs about 3 more writes. That's not that much overhead.)

And because every Pick record MUST have a key, most of the time I'm not searching for data, but targeting known records for which I have the key. (Plus I have far fewer tables to search to retrieve the same data.)

Cheers,
Wol

to post comments

Is this SQL databases or No-SQL?

Posted Mar 28, 2014 8:31 UTC (Fri) by cladisch (✭ supporter ✭, #50193) [Link]

> If I don't have an index I'll have to scan the entire table - so my worst case is equal to yours (if I'm being stupid!) But all I've got to do is declare an index on the invoice no ... and it takes one disk read (97% probability) to convert from invoice no to invoice key, and one more to retrieve the invoice.

Most relational databases (even SQLite) can store table rows ordered by their primary key (typically called "index-organized" or "clustered" tables), so no separate index lookup would be required.

> When making my claims about RDBMSs, I'm mostly speculating. You see, I'm *not* *allowed* to know what's going on under the covers, so I'm forced to guess.

Nobody forbids you to find out what's going on under the covers. Most relational database document low-level details (or even their file format) to allow manual optimizations.

Is this SQL databases or No-SQL?

Posted Mar 28, 2014 10:28 UTC (Fri) by intgr (subscriber, #39733) [Link] (7 responses)

> Have you keyed it on the invoice number? I quite likely have. If I have, my mvDBMS can tell the OS where on the disk the data I am looking for is, with a 97% chance of being right. "Open file X, seek to position Y, read that block". If your invoice table is big (let's say 1Mb) you've got to read 1/2Mb to find it!

What the? How does Pick know the position in the file, where to look for that row? I assume that by "keying" you mean what RDBMSes call indices. Isn't it dishonest to compare indexed access in Pick against non-indexed access in an RDBMS? No reasonable person creates a table without indices when they expect row lookups to be fast.

> I've now got ALL the invoice data. Chances are (in fact it's pretty certain) your invoice data is plastered over several tables, so you are going to get further clobbered. Then what happens if you want to access the related customer details? Yet again, you probably have the data plastered over several tables and have to read half of each table to retrieve the data.

This is true, but you're only talking about OLTP performance, with the assumption that every access to an invoice needs to read all the invoice lines and vice versa. It's true that a system like Pick will be far more efficient RDBMSes in this scenario, but in the all the systems I work on, OLTP queries are not the bottleneck (unless you do crazy things like don't index your data properly). It's the more complex queries that kill you: find all customers that have item X on their invoice; give me a breakdown of the costs of all invoice lines by item type. That's where query optimizers really shine. All evidence I've seen suggests that Pick deals terribly with these.

Even in development, I frequently whip up multi-line queries to look for anomalies in the data. It often just blows me away how these queries complete in seconds, despite churning through gigabytes of data and without any advance planning to make them fast.

In other words: you're worrying about optimizing something that's already more than fast enough. I worry about optimizing the things that are hard to optimize.

----

Also, PostgreSQL has a powerful type system, including composite types, arrays, mapping types, JSON, etc. You *can* organize data like you do in Pick if you want to. But there are real advantages to normalizing (with exceptions of course).

> When making my claims about RDBMSs, I'm mostly speculating. You see, I'm *not* *allowed* to know what's going on under the covers, so I'm forced to guess

That may be true for Oracle, but the page layout of PostgreSQL is documented. http://www.postgresql.org/docs/current/static/storage-pag... The difference from Pick is that the storage layout is not part of the API, but just an implementation detail. If the developers need to change it in a future version, for performance or other reasons, they can.

Is this SQL databases or No-SQL?

Posted Mar 28, 2014 19:33 UTC (Fri) by Wol (subscriber, #4433) [Link] (6 responses)

> What the? How does Pick know the position in the file, where to look for that row? I assume that by "keying" you mean what RDBMSes call indices. Isn't it dishonest to compare indexed access in Pick against non-indexed access in an RDBMS? No reasonable person creates a table without indices when they expect row lookups to be fast.

Urmmm. No.

What I mean by "keying" is sort-of what an RDBMS would call a primary key. In Pick, a primary key is mandatory. And that key contains all the information required for Pick to go straight to the place on disk where that row is stored. Pick files use linear hashing, so basically it's a modern hashed file. And unlike in a traditional hashed file, it only requires rewriting about three disk blocks to change the modulo. So it's FAST.

(So basically, the difference between a key and an index may be minor but it's crucial. An index tells you the key, while a key directly tells you where the data is. And again, Pick gives you rope. Screw up your primary keys and you screw up the hashing, which cripples performance. But in modern implementations that is HARD.)

> This is true, but you're only talking about OLTP performance, with the assumption that every access to an invoice needs to read all the invoice lines and vice versa. It's true that a system like Pick will be far more efficient RDBMSes in this scenario, but in the all the systems I work on, OLTP queries are not the bottleneck (unless you do crazy things like don't index your data properly). It's the more complex queries that kill you: find all customers that have item X on their invoice; give me a breakdown of the costs of all invoice lines by item type. That's where query optimizers really shine. All evidence I've seen suggests that Pick deals terribly with these.

Erm - no. Assuming I've understood what you want, it's a sequence of commands in Pick (and no, a Pick SELECT and a SQL SELECT are not equivalent).

SELECT INVOICES WHERE ITEM-TYPE EQ "X". If I've got an index on X, that's a single request to disk. That gives me a list of all invoices.
SELECT INVOICES SAVING CUST-ID. Okay, I have to go down my list of invoices but, assuming they're scattered randomly on disk that's 105 disk seeks per 100 invoices.
Okay, I can't remember the syntax for the next command, but it's something like
SELECT INVOICES WITH CUST-ID IN CURRENT SELECTLIST. If we have an index on CUST-ID, once again that's 105 seeks per 100 customers.

I've now got a list of invoices to report on ...

LIST INVOICES BY.EXP ITEM-TYPE TOTAL PRICE

Note that absolutely *nowhere* have I had to search for any information whatsoever. The user provided the initial "X", and every single data access from then on has been keyed - with a near perfect disk hit rate. I've had to throw away about 5% of my disk seeks because they failed to hit their target.

There are two places you might score on me. Sorting and collating the final report is one. But if you can't fit all the invoice details in ram I think I'm going to fly past you. I don't know the internals of the sort, but I suspect the systems I'm used to scan through each invoice in turn, creating an (invoice, line, price) tuple, and then sort that. They will then scan through that sorted list building up the report as they go. So they have to read each invoice at least twice, and once more for each extra relevant line.

But if it all fits in ram, the OS disk caching will help me, just as much as being able to store the entire report in ram will help you.

The other place you will score is indices. Your optimiser will spot it needs to scan INVOICES multiple times, and it will build indices on the fly if they don't exist. Pick assumes the user knows what s/he is doing, and gives you the rope to hang yourself.

Plus, you say "that's only relevant for OLTP" - erm no there too. Okay, it's only Monte Carlo probability, but in pretty much ALL scenarios the cost of retrieving that extra data is minimal, while the chance of it being required is relatively high. So much so that it's well worth it. If the system has been designed by a "practitioner in the art" (in this case an accountant), they will have subconsciously skewed the definition of an object such that this is pretty much inevitable.

As an aside, it was mentioned way back in the thread that PostgreSQL often requires gigabytes of temporary storage. I just cannot CONCEIVE of Pick needing that much, even if handling those sort of quantities of data!

> But there are real advantages to normalizing (with exceptions of course).

I couldn't agree more !!! But not in storing the data in First Normal Form. In fact, if a Pick developer did not normalise the data ON PAPER before designing his Pick schema, I would consider him negligent!

> Even in development, I frequently whip up multi-line queries to look for anomalies in the data. It often just blows me away how these queries complete in seconds, despite churning through gigabytes of data and without any advance planning to make them fast.

> In other words: you're worrying about optimizing something that's already more than fast enough. I worry about optimizing the things that are hard to optimize.

To quote from the Pick FAQ - "SQL optimises the easy task of finding things in memory, Pick optimises the hard task of getting them from disk into memory".

And to repeat my Xeon 800 war story - this Oracle system was designed to replace the old Pick system. It took Oracle Consultants some SIX MONTHS of hard work before it could run that query faster than the Pentium 90 system it was replacing ...

> That may be true for Oracle, but the page layout of PostgreSQL is documented. http://www.postgresql.org/docs/current/static/storage-pag... The difference from Pick is that the storage layout is not part of the API, but just an implementation detail. If the developers need to change it in a future version, for performance or other reasons, they can.

My point is that you're not supposed to know that information, not that you can't have insider knowledge. And if developers do need to change it, you have no recourse when all your finely tuned racing queries suddenly become bogged down in treacle. It's not their fault if your system is suddenly unusably slow and you have six months work (or more) retuning the system to get response times back to acceptable. Okay, that's unlikely to happen, but Oracle customers complain about it often enough. It just can't happen with Pick.

Cheers,
Wol

Is this SQL databases or No-SQL?

Posted Mar 29, 2014 0:11 UTC (Sat) by Wol (subscriber, #4433) [Link]

Replying to myself, let's expand a little on the following ...

> but in pretty much ALL scenarios the cost of retrieving that extra data is minimal, while the chance of it being required is relatively high.

Let's assume we've got 1000 invoices, and we're only reporting on 100 of them - 1 in ten. Let's also assume that we've got 10 invoices per block.

Using schoolboy howler statistics, we want 1 invoice in 10, there are 10 invoices per block, so we are going to have to read every block and we will only use 1 of the invoices in it. So we will get absolutely no benefit in the form of "accidentally" reading in another invoice row. The only possible benefit we will get is if we want multiple columns in the same row. (My howler may have simplified the maths, but doesn't affect the truth of the supposition :-)

The smaller the proportion of rows you want to access becomes, relative to the table size, the starker this effect becomes. So, by storing all the invoice data in a single row, a Pick database will benefit from this effect far more than an RDBMS, and the larger the database becomes, the more significant this benefit becomes. Because in everyday use it is rare to want to scan most of the database - you will only be interested in a few rows.

Cheers,
Wol

Is this SQL databases or No-SQL?

Posted Apr 10, 2014 10:02 UTC (Thu) by nix (subscriber, #2304) [Link] (4 responses)

The other place you will score is indices. Your optimiser will spot it needs to scan INVOICES multiple times, and it will build indices on the fly if they don't exist.

You need to use some actual databases, rather than just reading Codd and assuming everyone implemented what he suggested. While doing that (incrementally, no less) would be really cool, nobody ever does that and I don't know of any database system that implements it. Indices are explicitly-constructed entities.

Yes, this does mean that in a lot of databases you end up with a rule that on particular large tables all queries must use an index, and often the database can even enforce that rule. But... you can have more than one index, allowing for more forms of lookup than just primary-keyed, and you can still have totally ad-hoc queries on smaller tables.

As far as I can see, Pick throws all that flexibility away. I can easily see myself having to rethink half an application because I want to add one query, since oops now I need to change what the primary key is! This seems very far from ideal.

(Disclaimer: I work for Oracle now, but in the period of my life when I did things with databases, I didn't.)

Is this SQL databases or No-SQL?

Posted Apr 10, 2014 20:14 UTC (Thu) by cladisch (✭ supporter ✭, #50193) [Link] (3 responses)

> > […] it will build indices on the fly if they don't exist.

> I don't know of any database system that implements it.

As shown in this example, SQLite is happy to create a temporary index if it is estimated to be faster overall.

Is this SQL databases or No-SQL?

Posted Apr 15, 2014 14:45 UTC (Tue) by nix (subscriber, #2304) [Link] (2 responses)

Neat!

I did some digging in response: other, bigger RDBMSes (including PostgreSQL) will also create temporary indexes in temporary tablespace if needed. They're not visible to the database user, though, and are thrown away after the query terminates.

Is this SQL databases or No-SQL?

Posted Apr 15, 2014 15:27 UTC (Tue) by intgr (subscriber, #39733) [Link] (1 responses)

> bigger RDBMSes (including PostgreSQL) will also create temporary indexes

I think you are misunderstanding. The "temporary indexes" you speak probably refers to explicitly created indexes CREATE TEMPORARY TABLE tables issued by the client. I guess you were reading this: http://www.postgresql.org/docs/current/static/runtime-con...

PostgreSQL can create temporary in-memory hash tables, do temporary sorts (such as for merge joins or ORDER BY) and mid-query materialization of intermediate results. Sorts and materialized results can spill out to disk when there isn't enough memory to keep them, but they aren't called "temporary indexes" since they don't resemble actual index data structures.

Is this SQL databases or No-SQL?

Posted Apr 20, 2014 18:27 UTC (Sun) by nix (subscriber, #2304) [Link]

Yes, but those appear to be what wol is referring to as 'indexes' (they index the data, after all). They're not SQL-level entities, or user-visible, of course.