Wednesday, October 18, 2006

Refactoring: Derived table, UNION...WTF?

I greatly admire the works of the Dutch literary author Gerard Reve (1923 - 2006). On many occasions, he was asked whether his stories were real-life stories, and he always answered like this:

If you mean "did this sequence of events factually take place?" then I can be brief: No. And that's a good thing too, because if a writer would describe reality, the result would be very hard to believe, if not completely inconceivable. The course taken by real life is just too crazy. A true description is bound to be seem like a constructed mannerism and no reader can be expected to believe even one word of it.
However, as far as the single events are concerned, I exclusively use only those things bourne from reality.

If you ever read The Daily WTF you will probably agree that this point of view makes a lot of sense. Each time a really crazy or insensible piece of code pops up on the Daily's there are always people commenting, saying something like:

No...this just cannot be true. I refuse to believe that software developers from large professional organisations can deliver this kind of crap..and get away with it.

Well, the odds are that indeed the pieces of code that appear there should not be taken too literally. I mean, for one thing, the code appears with indentation, and sometimes even with comments: no way this is real code. Real Code is Worse than what you'll ever find on The Daily WTF.

My take on WTF


The reason I'm choosing this topic because I was recently asked to take a look at a database query which was giving "...trouble...". Usually this means: "...not performing as fast as we'd like...".

In this case, the people having trouble were actually consultants from a professional IT service provider. They were trying to migrate some enterprise application from a big, operational Oracle database to MySQL 5.0 Server. Their efforts were all experimental, and so ar, they were quite enthusiastic about MySQL. However, there were two troublesome queries performancewise. (I will discuss only one - the other one is also a story on it's own.)

They found that in this particular case, Oracle took 30ms whereas MySQL took a little over one minute. Of course this is a huge difference, and I was immediately challenged.

The query I got was somewhat like this:

select *
from (
select film_id
, title
, release_year
, 'PG'
from film
where rating in ('PG','PG-13')
union
select film_id
, title
, release_year
, 'R'
from film
where rating in ('R','NC-17')
union
select film_id
, title
, release_year
, rating
from film
where rating not in ('PG','PG-13','R','NC-17')
) film
where release_year > 2005
and release_year <= 2006

Well, of course, their enterprise application was not built on the sakila sample database: I stylized the original query to make it tangible. But don't let that distract you - just look.

Now I'm not saying that I'm not guilty of writing bad code. I mean, we all started somewhere, that is: from nothing. We all had to learn, and alas, in a lot of cases, you can only learn by making mistakes. However, things like the Daily WTF should be valuable eye-openers for developers and software engineers to always remain focussed on monitoring the quality of code. Even, or especially if it's their own.

So, instead of taking the chuckly attitude of laughing at someone else's apparent WTF, I'll try and do a step by step refactoring of this query. This will probably not be interesting for advanced users, and they can still have their laugh. If you can't appreciate the WTF-edness, keep reading: this article is for you.

A Simple Query


What we see here is essentially a simple query. A subselect appears in the FROM-clause: this is sometimes referred to as a derived table or an inline-view. If we forget the complexity of the subquery for a while and pretend that it actually is a real view, we can see easily that it really is simple:

select ...
from (/*complexity goes here*/) film
where ...

So, no JOIN, no GROUP BY, and not correlelated subselects. Normally, this query should be quite fast, right? So why is it so slow now?

Well, we could use the basic performance and tuning instincts, and start asking questions like:

  • What engine is used for the film table?

  • Is there an index on release_year?

  • What is the size of the supa_dupa_xyz buffer?


However, I don't think that's really necessary at this point. Right now, we need to know but one thing, and that is that the resultset of an inline view is computed before as a separate step.

Using EXPLAIN


We sure can witness this using EXPLAIN:

explain
select *
from ( -- 1
... -- 2
UNION
... -- 3
UNION
... -- 4
) film -- union result
where ...
;
+----+--------------+--------------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+--------------+--------------+------+---------------+------+---------+------+------+-------------+
| 1 | PRIMARY | <derived2> | ALL | NULL | NULL | NULL | NULL | 1000 | Using where |
| 2 | DERIVED | film | ALL | NULL | NULL | NULL | NULL | 952 | Using where |
| 3 | UNION | film | ALL | NULL | NULL | NULL | NULL | 952 | Using where |
| 4 | UNION | film | ALL | NULL | NULL | NULL | NULL | 952 | Using where |
| | UNION RESULT | <union2,3,4> | ALL | NULL | NULL | NULL | NULL | NULL | |
+----+--------------+--------------+------+---------------+------+---------+------+------+-------------+

The explain result is not too hard to interpret: The first row has the select_type equal to PRIMARY and this corresponds to the outer query. The table mentions that it queries <derived2>, which means it queries on the subquery (I don't know why it does not use the subquery alias - it just doesn't).

The second, third and fourth row in the explain result refer to the queries that are UNION-ed together inside the subselect. It's a bit puzzling that the select_type for the second row is marked DERIVED, but it just means it's the first thing that is evaluated as part of the subquery.

The third and fourth row correspond to the sets that are to be UNION-ed to the total result of the subquery, and that's why you see UNION there in the select_type column.

For those that do not know: UNION is a so-called set operator, it takes the resultsets produced by the queries on the left and right hand side, and constructs a new resultset out of it that contains the rows from the resultset operands. So, UNION 'adds up' rows in a vertical manner. (The much used and well known JOIN operator 'adds up' resultsets in the horizontal direction)

The final row represents the actual 'adding up' of the all the rows from the three queries inside the subselect, and that's why it has UNION RESULT in the select_type column. This step is not trivial, because UNION is required to filter out any duplicate rows in the final result after applying the UNION. More about that later.

Do we really need a derived table?


Now, we were about to think whether we really need the derived table. What would happen if we'd simply expand the contents of the subquery? It will require some work, because we would have to duplicate the WHERE clause of the outer query into the individual UNION-ed queries:

select film_id
, title
, release_year
, 'PG'
from film
where rating in ('PG','PG-13')
and release_year > 2005
and release_year <= 2006
union
select film_id
, title
, release_year
, 'R'
from film
where rating in ('R','NC-17')
and release_year > 2005
and release_year <= 2006
union
select film_id
, title
, release_year
, rating
from film
where rating not in ('PG','PG-13','R','NC-17')
and release_year > 2005
and release_year <= 2006

So, what would this do to the result from EXPLAIN? Well, we don't expect the subquery step again in oour result:

+----+--------------+--------------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+--------------+--------------+------+---------------+------+---------+------+------+-------------+
| 1 | PRIMARY | film | ALL | NULL | NULL | NULL | NULL | 952 | Using where |
| 2 | UNION | film | ALL | NULL | NULL | NULL | NULL | 952 | Using where |
| 3 | UNION | film | ALL | NULL | NULL | NULL | NULL | 952 | Using where |
| | UNION RESULT | <union1,2,3> | ALL | NULL | NULL | NULL | NULL | NULL | |
+----+--------------+--------------+------+---------------+------+---------+------+------+-------------+

The result does not show a huge difference from what we had: first our PRIMARY step selected from the derived table - now it does so directly from the union result. However, in reality, it can make all the difference.

In our original query, the whole union result was first built, and after that, the WHERE-clause on release_year was applied. This means that the whole of the union result must be scanned row by row to filter for the right release_year.

The modification 'pushed down' the WHERE-clause and applied it directly on the individual sets. Apart from enabling us to cut out the subselect (and thus, the extra scan), a nice side effect is that this could potentially make the UNION result faster too, because each WHERE-clause could filter out rows, leaving less total rows to 'sum up' by the UNION operation.

So, when do I use a derived table?


Why would anybody ever use a inline view like this? What's the point, can't we always expand it into the outer query? Well, No. There is one case where it is literally impossible to expand it. That's when you're aggregating aggregates.

An example: suppose you have a soccer team database, and you want to take the average of the maximum number of goals per season per player. That's two levels of aggregation, first max(no_of_goals) per player per season, and then, the average of that (also per player per season).

You can find another example here on nesting repeated groups.

Why a UNION? Can't we use UNION ALL?


I just mentioned that the UNION operator discards duplicate rows from the final resultset. Although that can be a nice functionality now and then it really is rarely needed.

In most cases, the sets in the union don't have any overlap. Can we say something about this particular query? Well, first of all, the three queries all select the same columns from the film table, so potentially there could be overlap between he resultsets. However, the first two queries each select a different constant in the SELECT-list:

select ..
, 'PG'
from ..
where ..
union
select ..
, 'R'
from ..
where ..

So, by definition, these two queries can never yield duplicates, meaning that we don't need the UNION to discard any duplicate rows: on the contrary, we'd rather have it skip that step because that is most likely faster. We can do that using UNION ALL:

select ..
, 'PG'
from ..
where ..
union all
select ..
, 'R'
from ..
where ..

It's actually a good idea to always write UNION ALL in case you know for sure that there is no everlap. Even if performance is not an issue, it makes the code more explicit. This makes it easier for the database to devise a query plan, and it will also be easier to fellow developers to see the exact intention.

Concerning the third query in the UNION, what is happening with that one? Well, it also selects from the code>filmtable, and again, it uses the same columns. However this one does not select a constant, but the rating column.

Now if we only could somehow prove that the values in the rating column here will never contain either of the values 'PG' or 'R' (the constants selected by the previous two queries) we must conclude that this resultset can never overlap with the resultset from either of the other queries. In other words, we would be able to safely use the UNION ALL trick here too.

The WTF-edness


We can find out if the third query will ever select a 'PG' or 'R' in the rating column by loooking at the WHERE-clause:

where rating not in ('PG','PG-13','R','NC-17')

Mmm, the WHERE-clause explicitly excludes the 'PG' and 'R' values. At least, that means that we can use the UNION ALL trick here too.

But wait a minute...let's look at the other WHERE-s too, ok?

select ..
from ..
where rating in ('PG','PG-13')
and ..
union all
select ..
from ..
where rating in ('R','NC-17')
and ..
union all
select ..
from ..
where rating not in ('PG','PG-13','R','NC-17')
and ..

Now that's beatiful: the third set selects exactly all the data not selected by the first and second. This means we can skip all the mumbo-jumbo and just write:

select film_id
, title
, release_year
, case rating
when 'PG-13' then 'PG'
when 'NC-17' then 'R'
else rating
end
from film
where release_year > 2005
and release_year <= 2006

So the CASE expression now makes up for the rating column.

Needless to say that the explain output has shrunk quite a lot:

+----+-------------+-------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+------+---------------+------+---------+------+------+-------------+
| 1 | SIMPLE | film | ALL | NULL | NULL | NULL | NULL | 952 | Using where |
+----+-------------+-------+------+---------------+------+---------+------+------+-------------+

Finally...


Just a short summary:

  • Real-life code can be very bad

  • Avoid derived tables

  • Use UNION ALL instead of UNION


Sadly I have not been able to test it myself. I'm quite confident that the reasoning behind this refactoring is sound, but you never know...

If you have any questions or suggestions, post a comment to the article.

Friday, October 06, 2006

Nedap/Groenendaal ES3B Voting Machines: Why Manufacturing Processes Should not be Closed

Here's a quick summary of the security analysis (8M pdf, in English) of the ES3B voting computer, manufactured by Nedap/Groendendaal. This type of apparatus is used to collect about 90% of all the votes for local and federal elections held in the Netherlands. (A slightly modified version of this type of voting computer is also used in Germany and France.)

The analysis is performed by a Dutch Citizens' Movement, whose name can be roughly translated into the We Don't Trust Voting Computers Foundation. Despite the arguably provocative name, their research project (various materials, in english) and the culminating report concerning the Nedap/Groenendaal voting computer seem fairly sound and objective.

To put it mildy, the report does not shine a favourable light on the quality of the voting machine for its intended purpose. The findings in the report appeared on Dutch national television on 5 october 2006. The publication of the report was slashdotted.

The whole affair would be quite entertaining (the report learns you how to turn the voting computer into a fairly lousy but fully functional chess-player) if not for the disturbing denial by both the Dutch authorities and the manufacturer concerning the obvious risks of fraudulent abuse of these voting machines if used in democratic elections. The total lack of convincing procedures to test the correct functioning of the machines are equally uncanny. The report describes fairly simple fixes for all of the flaws found during a months time research of only a few of these voting machines.

The final conclusion is that although the design of the machines includes data redundancy and independence of remote resources to remedy technical failures, no efforts seem to have been made at all to build safety measures against malignant use for fraudulent purposes. Instead, the manufacter openly advocates reliance on obscuring details about both the hardware and the sofware, claiming that openness would only benefit a small elite, which probably consists mainly of characters that seek to abuse that knowledge for malignent purposes.

Some quotes from the report:
Dutch election law requires physical keys to be used as part of an electronic voting system.
...
The key system chosen [...] for [the] locks [...] always comes with the same key [...] the same key is used [...] throughout The Netherlands. Spare keys can be ordered [...] for roughly a Euro [....]. We ordered [...] 100 of these keys without any problem. [...] typical applications for this lock include “copy machines and office furniture” [...] this [...] type of lock [can be opened] with a bent paperclip.
...
The Nedap ES3B system as it is in use by a typical Dutch municipality consists of multiple S3B voting computers, at least as many ballot memory modules, a reader unit to be attached to a PC via the serial port and an installed copy of the ISS (Integraal Stem Systeem) software running on a PC under Microsoft Windows.
(ISS or Integraal Stem Systeem translates to Integral Voting System)
For those that are more visually orientated, a slide of a typical setup is available from the manufacturers' site:


More quotes from the report:

The ISS software has a ‘maintenance mode’ that is supposed to be only accessible to members of the “verkiezingswacht”, the Nedap election-day helpdesk. You need a password to get the software in this mode. A quick look in the binary revealed this password to be “GEHEIM”, the Dutch word for “SECRET”. The maintenance mode, among other things, allows the helpdesk to read the binary contents of a ballot module plugged into the programming slot of a reader unit. By sniffing the serial commands between the ISS software and the reader unit, we figured out how to issue these commands ourselves and subsequently wrote a program in Tcl that we could use to read the entire contents of a ballot memory module.
...
We claimed [that] the Nedap was just another computer, and [that it could be programmed] to play chess or to lie about the election results. ...[the manufacturer spokesperson said that] "[with] regard to the claim that our machine can play chess: I’d like to see that demonstrated”. [...] our first goals now [...] was to make [the voting machine] play chess.


For the benefit of the non-Dutch readers, here are a few relevant paraphrases translated from the manufacturer's spokesperson (which appears to be the owner of the business himself, Jan Groenendaal):
It may be true that the technical knowledge concerning the operation of the system is known to only a limited group, but that does not have to be a problem.
...
I would very much like to see a demonstration of the statement that it is also possible to play a game of chess with our voting machines.
...
We understand the concern raised against personal computer based voting machines...However, our voting machine is a Dedicated Special Purpose Machine, meant for counting votes and nothing else. It merely records the pressing of buttons on a keyboard, but in very, very secure manner. [...] In addition, we have always taken care for the voting machines to work "stand alone", that is: without any network connections to exclude any external influences. Therefore, Hackers absolutely don't stand a chance.
...
One of the objections we repeatedly face is that the source code of the embedded software is not publicly available. There is some merit in that argument. However this is caused by the government policy which is directed at providing municipalities with voting machines from commercial vendors that operate in a free market. Because of competition, vendors shield their intellectual properties. [...] This should not be blown out of proportion.
...
Opening the sourcecode would allow only a small circle of people to judge it, which when then form just a very small new elite. For sure, this is no guarantee that individuals can understand the machine's operation. [...] "Open Source Software" advocates claim an increase in software quality when there is freedom to propose or contribute enhancements. This may be true for certain wide-spread applications. Elections are however not such an application. Opening up the source increases the possibilities for an attack by malignant forces. The fact that only a small group of people have inside knowledge might also be regarded as a positive thing.

Well, after reading this I think most people can probe the satisfaction the hackers must've felt after all the efforts they must've endured before they could finally write this:
After having learned roughly how the hardware worked we used a gcc 68000 crosscompiler to create a Nedap IO-library containing functions to initialize the system, write data to the display, read the keyboard, and write debug messages to the UART. [...] we then managed to compile and run Tom Kerrigan's Simple Chess Program (TSCP). This was non-trivial only because we had to squeeze out quite a few tables to make it run using only the available 16 kBytes of RAM.
...
It knows all the rules and every now and then it can be surprisingly clever for what it is. But in all honesty we have to admit that it does not play chess all that well.

Then, playtime is definitevely over:
When we started to think about demonstration software that would lie about election results (called “Nedap PowerFraud”), we kept in mind that the system should not lie after an election that was obviously a test of the system. We decided we needed to store the votes and only decide whether or not to perform the fraud at the moment the election was closed, so our program would have as much information as possible to make that decision.
...
The ES3B’s EEPROM [...stores...] a few system configuration parameters [...] and some settings [...] most of the space is used for two circular buffers holding [logs]. In these logs, the device keeps the system time [...] these times are not as helpful as one might think [...] We updated the circular buffer routines that deal with the error log [...] making space for our stolen votes [...] we steal votes only from the number one on each list. Since the majority of voters pick the first candidate on a given party’s list, this is quite acceptable.
...
We then built “hooks” into the regular ES3B code. Every time a voter casts a ballot, our code generates a random number [...] If the number is below the programmed percentage of votes we want to steal, that vote is not written to the ballot module [but to the corrupted log]. At the end of the election, our software determines whether this was a real election or not. It then [writes] these votes into [...] the ballot module, just like the real software does.

Now it might seem far fetched to reprogam the EEPROM's. However:
To determine the recipient of the stolen votes, PowerFraud does a case-insensitive match of all party names with a programmed string. If it finds a match, that party becomes the recipient of he stolen votes. This allows for the fraudulent EPROMs to be inserted long before the candidate lists are known, and it allows a fraudulent ROM to perform the same fraud year after year, even though the relative position of the party on the keyboard changes. It is significant to note that the Dutch interior ministry assumes this to be impossible. A recent statement 13 says: “Fraud during the production of voting machines does not make sense because the lists of candidates are not known then.

The authors then show that in the present implementation, there is not much chance of detecting the fraudulent behaviour of the voting machine. Also, there are no physical means that allow anybody to check whether or not the machine has been tampered with. So basically, all it takes once you have the reporgrammed EEPROM, is fairly short amount of time to replace it. It can then sit there for years and years in the machine to steal votes.

Apart from this, to me, quite intimidating attack a number of other, simple hacks are mentioned:
It would appear that if a special character is displayed, the controller has to do extra work every time the display is updated. This causes the display refresh frequency to drop from 72Hz to 58 Hz. The difference between these two frequencies can be determined by ear. In The Netherlands, the name of the major political party CDA is written in full on the display when the voter chooses any CDA candidate: “Christen Democratisch Appèl”. So using only a simple scanner or short-wave receiver, we can tell whether or not a voter is currently voting for a party or candidate with an accent in the name.
...
In all cases we could receive the signal at a few meters. In one case we could receive the signal up to 25 meters away. [...] We also noticed energy present at 3845 Hz when the vote-button is pressed.


Shortly after the television broadcast, a little reponse appeared on the manufacturer's website:
It occurred to us that our machine works remarkably well. The voting machine does exactly what it is told to do. This was completely expected behaviour, as was confirmed by all involved. We can only conclude that the name of the citizens' movement that calls itself the "We Don't Trust Voting Computers Foundation" depicts our machine in an unjust manner. We feel that the "We Don't Trust People Foundation" would have been a more suitable name.


Personally, I would not vouch that opening up the manufacturing process of these voting machines are a guarantee to twart these kinds of attacks. However, what frightens me is the trust placed by the manufacturer by the 'security' gained from obscurity. Clearly, their statement that the voting machine does exaclty what people tell it to do is not true. Nobody intended the machine to emit the radiation that allows one to see when the "vote" button is pushed.

Also, given that fact that these undoubtedly devoted hackers still took only a month to know probably more about this machine than most of the employees of the manufacturer, does not really convince when the manufacturer claims that it needs to keep everything closed in order to guard their intellectual property.

Frankly, it seems that striving towards a free market for voting machines (which, according to the Nedap spokesman, is a policy of the Dutch government) is probably better served when the manufacturers would be obliged to open up every single bit of the manufacturing process. This kind of "quality through openness" sure is one of the main reasons why I joined MySQL. I strongly and firmly believe in openness as a drive that is especially suitable to drive commercial product development.

Anyway - would my vote count? Next month's elections could be particularly interesting.

Wednesday, October 04, 2006

Did you know that....: Custom Graphs in MySQL Administrator

Here's a quick tip to make a custom Graph in MySQL Administrator.



MySQL Administrator can be separately installed from the MySQL GUI Tool Bundle. Oh yeah, did you know that finding and reporting bugs in the GUI tools might win you an iPOD?

Now, about that tip: it's a documented feature, but not well known nonetheless.

Click the "Health" item in the left sidebar, and choose one of the tab pages:



Once you've opened the page, the right-click is your friend in many ways. Just right-click inside the frame enclosing the graphs to add a new graph. A right-click directly above the horizontal line to add an entire new tab page.

Simply right-click inside a graph to invoke a little menu. From there, you can edit the existing graph:




Enjoy!

DuckDB bag of tricks: Processing PGN chess games with DuckDB - Rolling up each game's lines into a single game row (6/6)

DuckDB bag of tricks is the banner I use on this blog to post my tips and tricks about DuckDB . This post is the sixth installment of a s...