Showing posts with label hack. Show all posts
Showing posts with label hack. Show all posts

Friday, October 21, 2011

MySQL Hacks: Preventing deletion of specific rows

Recently, someone emailed me:
I have a requirement in MYSQL as follows:
we have a table EMP and we have to restrict the users not delete employees with DEPT_ID = 10. If user executes a DELETE statement without giving any WHERE condition all the rows should be deleted except those with DEPT_ID = 10.

We are trying to write a BEFORE DELETE trigger but we are not able to get this functionality.

I have seen your blog where you explained about Using an UDF to Raise Errors from inside MySQL Procedures and/or Triggers. Will it helps me to get this functionality? Could you suggest if we have any other alternatives to do this as well?
Frankly, I usually refer people that write me these things to a public forum, but this time I felt like giving it a go. I figured it would be nice to share my solution and I'm also curious if others found other solutions still.

(Oh, I should point out that I haven't asked what the underlying reasons are for this somewhat extraordinary requirement. I normally would do that if I would be confronted with sucha a requirement in a professional setting. In this case I'm only interested in finding a crazy hack)

Attempt 1: Re-insert deleted rows with a trigger

My first suggestion was:
Raising the error won't help you achieve your goal: as soon as you raise the error, the statement will either abort (in case of a non-transactional table) or rollback all row changes made up to raising the error (in case of a transactional table)

Although I find the requirement strange, here's a trick you could try:

write a AFTER DELETE FOR EACH ROW trigger that re-inserts the rows back into the table in case the condition DEPT_ID = 10 is met.

Hope this helps...

Alas, I should've actually tried it myself before replying, because it doesn't work. If you do try it, a DELETEresults in this runtime error:
Can't update table 'emp' in stored function/trigger because it is already used by statement which invoked this stored function/trigger.
This is also known as "the mutating table problem".

Attempt 2: Re-insert deleted rows into a FEDERATED table

As it turns out, there is a workaround that meets all of the original demands. The workaround relies on the FEDERATED storage engine, which we can use to trick MySQL into thinking we're manipulating a different table than the one that fires the trigger. My first attempt went something like this:

CREATE TABLE t (
id INT AUTO_INCREMENT PRIMARY KEY,
dept_id INT,
INDEX(dept_id)
);

CREATE TABLE federated_t (
id INT AUTO_INCREMENT PRIMARY KEY,
dept_id INT,
INDEX(dept_id)
)
ENGINE FEDERATED
CONNECTION = 'mysql://root@localhost:3306/test/t';

DELIMITER //

CREATE TRIGGER adr_t
AFTER DELETE ON t
FOR EACH ROW
IF old.dept_id = 10 THEN
INSERT INTO t_federated
VALUES (old.id, old.dept_id);
END IF;
//

DELIMITER ;
So the idea is to let the trigger re-insert the deleted rows back into the federated table, which in turn points to the original table that fired the trigger to fool MySQL into thinking it isn't touching the mutating table. Although this does prevent one from deleting any rows that satisfy the DEPT_ID = 10 condition, it does not work as intended:

mysql> INSERT INTO t VALUES (1,10), (2,20), (3,30);
Query OK, 3 rows affected (0.11 sec)

mysql> DELETE FROM t;
ERROR 1159 (08S01): Got timeout reading communication packets

mysql> SELECT * FROM t;
+----+---------+
| id | dept_id |
+----+---------+
| 1 | 10 |
| 2 | 20 |
| 3 | 30 |
+----+---------+
3 rows in set (0.00 sec)
At this point I can only make an educated guess about the actual underlying reason for this failure. It could be that the deletion is locking the rows or even the table, thereby blocking the insert into the federated table until we get a timeout. Or maybe MySQL enters into an infinite loop of deletions and insertions until we hit a timeout. I didn't investigate, so I don't know, but it seems clear this naive solution doesn't solve he problem.

Attempt 3: Deleting from the FEDERATED table and re-inserting into the underlying table

It turns out that we can solve it with a FEDERATED table by turning the problem around: Instead of manipulating the original table, we can INSERT and DELETE from the FEDERATED table, and have an AFTER DELETE trigger on the FEDERATED table re-insert the deleted rows back into the original table:

DROP TRIGGER adr_t;

DELIMITER //

CREATE TRIGGER adr_federated_t
AFTER DELETE ON federated_t
FOR EACH ROW
IF old.dept_id = 10 THEN
INSERT INTO t
VALUES (old.id, old.dept_id);
END IF;
//

DELIMITER ;
Now, the DELETE does work as intended:

mysql> DELETE FROM federated_t;
Query OK, 3 rows affected (0.14 sec)

mysql> SELECT * FROM federated_t;
+----+---------+
| id | dept_id |
+----+---------+
| 1 | 10 |
+----+---------+
1 row in set (0.00 sec)
Of course, to actually use this solution, one would grant applications access only to the federated table, and "hide" the underlying table so they can't bypass the trigger by deleting rows directly from the underlying table.

Now, even though this solution does seem to fit the original requirements, I would not recommend it for several reasons:
  • It uses the FEDERATED storage engine, which hasn't been well supported. For that reason, it isn't enabled by default, and you need access to the MySQL configuration to enable it, limiting the applicability of this solution. Also, you could run into some nasty performance problems with the FEDERATED storage engine
  • The solution relies on a trigger. In MySQL, triggers can really limit performance
  • Perhaps the most important reason is that this solution performs "magic" by altering the behaviour of SQL statements. Arguably, this is not so much the fault of the solution as it is of the original requirement.

An Alternative without relying on magic: a foreign key constraint

If I were to encounter the original requirement in a professional situation, I would argue that we should not desire to alter the semantics of SQL commands. If we tell the RDBMS to delete all rows from a table, it should either succeed and result in all rows being deleted, or it should fail and fail completely, leaving the data unchanged.

So how would we go about implementing a solution for this changed requirement?

We certainly could try the approach that was suggested in the original request: create a trigger that raises an exception whenever we find the row should not be deleted. However, this would still rely on a trigger (which is slow). And if you're not on MySQL 5.5 (or higher), you would have to use one of the ugly hacks to raise an exception.

As it turns out, there is a very simple solution that does not rely on triggers. We can create a "guard table" that references the table we want to protect using a foreign key constraint:

mysql> CREATE TABLE t_guard (
-> dept_id INT PRIMARY KEY,
-> FOREIGN KEY (dept_id)
-> REFERENCES t(dept_id)
-> );
Query OK, 0 rows affected (0.11 sec)

mysql> INSERT INTO t_guard values (10);
Query OK, 1 row affected (0.08 sec)

mysql> DELETE FROM t;
ERROR 1451 (23000): Cannot delete or update a parent row: a foreign key constraint fails (`test`.`t_guard`, CONSTRAINT `t_guard_ibfk_1` FOREIGN KEY (`dept_id`) REFERENCES `t` (`dept_id`))
mysql> DELETE FROM t WHERE dept_id != 10;
Query OK, 2 rows affected (0.05 sec)
(Like in the prior example with the federated table, the guard table would not be accessible to the application, and the "guard rows" would have to be inserted by a privileged user)

Finally: what a quirkyy foreign key constraint!

You might have noticed that there's something quite peculiar about the foreign key constraint: typically, foreign key constraints serve to relate "child" rows to their respective "parent" row. To do that, the foreign key would typically point to a column (or set of columns) that make up either the primary key or a unique constraint in the parent table. But in this case, the referenced column dept_id in the t table is contained only in an index which is not unique. Strange as it may seem, this is allowed by MySQL (or rather, InnoDB). In this particular case, this flexibility (or is it a bug?) serves us quite well, and it allows us to guard many rows in the t table with dept_id = 10 with just one single row in the guard table.

Thursday, July 24, 2008

Inspect the Query Cache using MySQL Information Schema Plug-ins

A while ago I wrote about MySQL 5.1 information schema plug-ins.

At the time, I wrote a plug-in to report the contents of the query cache, but for all kinds of reasons, I never found the time to write a decent article about it, nor to release the code.

I am not sure if I'll ever find the time to write that article, but I just tidied up the code, and installed it in a new MySQL 5.1.26-rc server. It seems to work there, so I put the code up on the web.

Inside the source file, there's instructions to build and deploy it. If all goes well, you can do things like:

mysql> select * from information_schema.mysql_cached_queries\G
*************************** 1. row ***************************
STATEMENT_ID: 1
SCHEMA_NAME: test
STATEMENT_TEXT: select count(*) from world.city
RESULT_BLOCKS_COUNT: 1
RESULT_BLOCKS_SIZE: 512
RESULT_BLOCKS_SIZE_USED: 106
1 row in set (0.00 sec)

Are you interested in this plugin-in? Do you have any suggestions? Download it, and put your comments here.

Tuesday, July 08, 2008

MySQL Percentile aftermath: Calculating all quantiles

Are you getting fed up yet with my posts on calculating percentiles? Well, I'm sorry but I'm not quite finished.

Here's a simple, fast method to calculate the specified number of quantiles:

-- set the number of quantiles, for exmple:
-- quartiles: 4
-- deciles: 10
-- percentiles: 100

SET @quantiles:=4; -- select quartiles

-- calculate all quantiles
--
--
SELECT amount AS metric
, @n DIV (@c DIV @quantiles) AS quantile
, @n AS N
FROM sakila.payment
CROSS JOIN (
SELECT @n:=0 -- rownumber
, @c:=COUNT(*) -- need this to calculate quantile partitions
FROM sakila.payment
) c
WHERE NOT ( -- modulo zero (=false), we are at the quantile
(@n:=@n+1) % (@c DIV @quantiles) -- rownumber equal to the quantile partition?
)
ORDER BY amount; -- need ordered partitions

You can find this snippet on MySQL Forge.

Monday, December 17, 2007

Calculating the Financial Median in MySQL

I believe I found a new method to calculate the median in MySQL. I would not be surprised if this method has been figured out by somebody else already. However, I can't seem to find any resources on the internet describing this method, so for now I flatter myself by assuming the method is original.

(Please do post your comments to this blog to correct me on that should I be wrong so I have a chance to rectify.)

The method I'm describing is a one-pass, pure SQL method. It does not require subqueries, cursors or user variables. However, it does rely on the MySQL specific functions GROUP_CONCAT() and SUBSTRING_INDEX()

I'll be maintaining a snippet for this method at MySQL Forge.
If you want to know what the median is, and how my snippet works, read on.

Some background


Like the mean and the mode, the median is an important metric to characterize the distribution of values in a collection. If we have a ordered collection of (numerical) values, the median is the value for which the number of entries that has a value that is higher than the median is exactly equal to the number of entries that has a value that is lower than the median. If there is an odd number of entries in the collection, the value of the median corresponds to the value of the entry that lies exactly in the middle of the list. If there is an even number of entries, the median is calculated as the mean of the two middle values.

MySQL offers a number of aggregate functions. Unfortunately, MySQL does not offer a function to calculate the median.

Even though MySQL does not support a MEDIAN() function natively, it is still possible to calculate it. You can:

The snippet

Here's a snippet that shows how to calculate the median replacement cost for a film in the sakila sample database:

select
(
substring_index( -- left median: max value in lower half:
substring_index(
group_concat( -- list all values in ascending order
f.replacement_cost
order by f.replacement_cost
)
, ','
, ceiling(count(*)/2) -- left half of the list
)
, ','
, -1 -- keep only the last value in list
)
+ substring_index( -- right median: min value in upper half:
substring_index(
group_concat( -- list all values in ascending order
f.replacement_cost
order by f.replacement_cost
)
, ','
, -ceiling(count(*)/2) -- right half of the list
)
, ','
, 1 -- keep only the first value in list
)
) / 2 -- average of left and right medians
as median
from sakila.film f;
(For the latest version, refer to MySQL Forge)

So, how does this snippet work? In the remainder of this post, I'll explain the inner workings of this method in a top-down fashion.

The mean of the left and right median

The method I'm describing always takes the mean of the 'left' and 'right' median.

select
(
left-median(f.replacement_cost)
+ right-median(f.replacement_cost)
) / 2 -- average of left and right medians
as median
from sakila.film f;
(Note that the usage of left-median() and right-median() is just an explanation of the structure - in reality there are not two distinct functions by that name)

The terms 'left median' and 'right median' are not common so they need an explanation.

Let's visualize the process to determine the median. We can do this by imagining that we have an ordered list of values and that we point our left index finger to the lowest value in the list and our right index finger to the highest value in the list.

Now, we look at our fingers. If there is more than one entry between our right and left finger, we move or left finger one entry to the right and our right finger one entry to the left, and we keep doing that until there are no more entries between our left and right finger. Once we're there, the value of the entry that is pointed to by our left finger is the 'left median' and the value of the entry pointed to by our right finger is the 'right median'.

If we had an even number of entries, then the left and right median each correspond to distinct entries - if there was an odd number of entries then the left and right median correspond to one and the same entry.

At any rate, once we found the left and right median, it is clear that their mean is the true median. If we have an even number of entries, we have to calculate the mean of the two middle values anyway, and if there is an odd number of entries, taking the mean of two identical values results of course in that same value which does thus result in a correct value for the median.

GROUP_CONCAT: an ordered list of values

In the example, we use GROUP_CONCAT to generate a list of values in ascending order:

GROUP_CONCAT( -- list all values in ascending order
f.replacement_cost
ORDER BY f.replacement_cost
)

This gets us a string consisting of concatenated replacement_cost values in ascending order, separated by the default separator, which is a comma (',').

We use the same list in both the calculation of the left and the right median.

Note that the length of the concatenation result returned by GROUP_CONCAT() is limited. By default, it is as small as 1024 bytes. Personally I think this is way too small so I have it configured to be 64K by default. You can set the length at runtime too like this:

SET group_concat_max_len := 65535
You can specify larger values than 65535 too, and I suspect that the maximum packet size is the practical maximum:

SET group_concat_max_len := @@max_allowed_packet
To inspect the current value, you can do this:

SELECT @@group_concat_max_len

Getting the 'left' half of the list

Once we have the list of values, we can split it in two halves with little effort. We do this using the SUBSTRING_INDEX() function.

The SUBSTRING_INDEX() function processes a string argument and gets a substring based on the position of a particular occurrence of another substring.

In this case, the comma ',' is the substring that separates the values in our ordered list. But of all the commas in the list, which occurrence of the comma do we need to find?

Suppose our list contains 4 values. Then, these values are separated by three comma's:

values: '1,2,3,4'
commas: ^ ^ ^
1 2 3
If we want to divide this list in two equal halves, then the second comma is the divisor between the left and right halves of our list. With SUBSTRING_INDEX() this expression would get us the left half of the this list:

SUBSTRING_INDEX('1,2,3,4', ',', 2) -- the substring up to the 2nd occurrence of ','
and the result will be:

'1,2'
So now we have the first half of the list, and by definition, the last entry in that list, '2' is the left median of the original list '1,2,3,4'.

Now what if we would've had an odd number of entries in our list? Supose our list would've been like this:

values: '1,2,3'
commas: ^ ^
1 2
In this case too, we need the second comma to end up with a left substring that has the left median as last entry in the list (which also happens to be the proper median because this is a list with an odd number of entries).

As it turns out, we can conveniently generalize the SUBSTRING_INDEX expression like this:

SUBSTRING_INDEX(list, separator, CEILING(#entries/2))
In other words, if we divide the number of entries in our list by two, and then round to the nearest higher integer, this gives us the particular occurrence of the separator what we are looking for to halve our list as required. Of course, calculating the number of entries is simply a matter of using the COUNT() aggregate function.

Excising the 'left' median

To actually obtain the left median itself, we just need to excise the last value from the left half of the list of values. We do this by applying SUBSTRING_INDEX() again.

Again, we need to make a substring in terms of the occurrence of the comma that separates the values in our list. This time, we need to get the substring found directly after the last comma in the list. With SUBSTRING_INDEX() we can conveniently express this in the following manner:

SUBSTRING_INDEX(list, separator, -1)
This means: search the list from right to left and find the first occurrence of the separator. Return the substring that appears after the separator (that is, the substring appearing on the right hand of the separator).

Getting the 'right' median

The process to obtain the right median is a mirror of obtaining the left median: instead of obtaining the last value in the left half of the ordered list of values, we now need to obtain the first value of the right half of the list. This is actually as simple as reversing the sign of the occurrence argument in the SUBSTRING_INDEX() calls:

left half: SUBSTRING_INDEX(list, separator, CEILING(COUNT(*)/2))
right half: SUBSTRING_INDEX(list, separator, -CEILING(COUNT(*)/2))

last entry: SUBSTRING_INDEX(list, separator, -1)
first entry: SUBSTRING_INDEX(list, separator, 1)

A few remarks

I think that in many cases, this can be a fair method to calculate the median. The advantage of this method is that it is relatively fast because the query itself is relatively simple.

It would be interesting to see how this method behaves when handling millions of rows. Maybe I will run some benchmarks on that later on.

In the mean while, feel free to post your thoughts, suggstions or critique on this blog.

DuckDb Performance: min, max, and median vs quantile

I was playing with some classical statistics in DuckDB and I ran into something I'd like to share. It's about the measures minimum,...