Wednesday, November 22, 2006

MySQL: A Stored Procedure to Create FEDERATED Tables.

The FEDERATED storage engine is a MySQL feature that lets you access the tables (and views) on a remote MySQL server. In terms of purpose and functionality, it best compares to a "linked table" in MS Access, and to a lesser extent, to Oracle database links.

Creating a federated table is tedious, because in the local database, you need to define a table with exactly the same structure as the remote table. That includes the index definitions, because these are used by the local optimizer to create a query plan (although the statistics for the index will not be locally available)

I created a procedure to make life easier (well, at least as far as creating FEDERATED/ tables is concerned). You can grab if here:

http://forge.mysql.com/snippets/view.php?id=54 https://github.com/sordidfellow/MysqlSnippets/blob/master/p_create_federated_table.sql

Sample1:


call p_create_federated_table(
'192.168.0.100'
, 3306
, 'my_remote_username'
, 'my_remote_password'
, 'my_remote_schema'
, 'my_remote_table'
, 'my_local_schema'
, 'my_local_table'
);


This sample will create a FEDERATED table named 'my_local_table' in the schema 'my_local_schema'. The created table will point to the table 'my_remote_table' in the schema 'my_remote_schema' on the remote MySQL Server on the host 192.168.0.100 that is listening on port 3306

Sample2:


call p_create_federated_table(
'myhost.mydomain.org'
, NULL
, NULL
, NULL
, 'my_schema'
, 'my_table'
, NULL
, NULL
);


This sample will create a FEDERATED table with the same name as the specified remote table, and in the local schema with the same name as the specified remote schema. The remote mysql server is listening on the default mysql port (usually 3306) on the host myhost.mydomain.org'.

If you want to know how it works exactly: the procedure has got pretty good comments. Go get it at http://forge.mysql.com/snippets/view.php?id=54 github, and let me know what you think.

Code

Stephen kindly went into the wayback machine and retrieved the code that used to be on the now defunct MySQL Forge website. Thank you stephen! You can also view the code on github.
delimiter $$

drop  procedure if exists 
p_create_federated_table
$$
create procedure 
p_create_federated_table

(
    -- the ip address or name of the remote mysql server host (if NULL, 'localhost')
    p_remote_host     varchar(32)   
    -- the port where the remote  mysql server is listening (if NULL, 3306)
,   p_remote_port     int unsigned  
    -- the user on the remote server that accesses the table (if NULL, 'root') 
,   p_remote_user     varchar(16)   -- 
    -- the password for the remote user (if NULL, omitted)
,   p_remote_password varchar(32)
    -- the schema in which the remote table resides
,   p_remote_schema   varchar(64)
    -- the name of the remote table
,   p_remote_table    varchar(64)
    -- the local schema to create the local FEDERATED table (if NULL, p_remote_schema)
,   p_local_schema    varchar(64)
    -- the name of the local FEDERATED table (if NULL, p_remote_table)
,   p_local_table     varchar(64)
)
LANGUAGE SQL
NOT DETERMINISTIC
MODIFIES SQL DATA
SQL SECURITY INVOKER
COMMENT 'Creates a FEDERATED table.'
/*
    Changelog
    WHEN?      WHO? WHAT?
    -----------------------------------------------------------
    2007-02-20 RPB  added handler to ignore warning 1366. Not sure why this appears.
                    lowered the group_concat_max_len (bug #23856)
                    removed the ORDER BY clauses from the GROUP_CONCATs on COLUMN_TYPE (bug #23856)
                    added output so we can see what's taking so long
                    added changelog
    2006-11-20 RPB  Created Initial version  
*/ 
begin
    -- size used for the GROUP_CONCAT buffer if current is lower
    -- please see http://bugs.mysql.com/bug.php?id=23856
    declare v_group_concat_max_len smallint 
        default 16384;
    -- stores the original size of the GROUP_CONCAT buffer to restore it
    declare v_old_group_concat_max_len int unsigned
        default @@group_concat_max_len;
    -- stores the original sql_mode
    declare v_old_sql_mode varchar(255)
        default @@sql_mode;
    -- Used to drop temporary tables
    declare v_drop_table_name varchar(64);

    -- set the GROUP_CONCAT buffer sufficiently large
    set @@group_concat_max_len := greatest(
        v_group_concat_max_len
    ,   v_old_group_concat_max_len
    );
    -- set the sql_mode to default to prevent invalid column defaults
    set @@sql_mode := '';

    -- The following block contains all the meat
    -- We use a separate block to allow for proper error handling.
    -- All errors that might be expected are handled inside this block
    -- This should guarantee that the outer block is always completed.
    -- That is necessary, beause we need to do a little cleaning up 
    -- before exiting the procedure.
    begin
        -- Used for defaulting the specified host
        declare v_remote_host     varchar(32) 
            default coalesce(p_remote_host,'localhost');
        -- Used for defaulting the specified user
        declare v_remote_user     varchar(16) 
            default coalesce(p_remote_user,'root');
        -- Used for defaulting the local schema
        declare v_local_schema    varchar(64)
            default coalesce(p_local_schema,p_remote_schema);
        -- Used for defaulting the local schema
        declare v_local_table     varchar(64)
            default coalesce(p_local_table,p_remote_table);
        -- Holds the connectstring prefix for FEDERATED tables
        declare v_connectstring   varchar(255)
            default concat(
                'mysql://'
            ,   v_remote_user
            ,   if(p_remote_password is null
                ,   ''
                ,   concat(':',p_remote_password)
                )
            ,   '@'
            ,   v_remote_host
            ,   if(p_remote_port is null
                ,   ''
                ,   concat(':',p_remote_port)
                )
            ,   '/'
            );

        -- Various conditions we might encounter
        -- We rename them just for clarity
        declare TABLE_EXISTS_ERROR condition FOR 1050;
        declare UNKNOWN_COLUMN_ERROR condition FOR 1054;
        declare SYNTAX_ERROR condition FOR 1064;
        declare GROUP_CONCAT_TRUNCATION_ERROR condition FOR 1260;
        declare INCORRECT_VALUE_ERROR condition FOR 1366;
        declare TRUNCATION_ERROR condition FOR 1406;
        declare FEDERATION_ERROR condition FOR 1429;

        -- Various handlers. These will execute if one of the conditions occur.
        -- They all show a friendly error message and the exit the inner block.
        -- Execution is resumed at the clean up code, just before 
        -- the end of the proceudre
        declare exit handler for FEDERATION_ERROR 
            select  'Federation error' error_type
            ,       'Check the connectstring.' error_message
            ,       v_connectstring connectstring
            ;
        declare exit handler for GROUP_CONCAT_TRUNCATION_ERROR 
            select  'GROUP_CONCAT Truncation' error_type
            ,       'Increase GROUP_CONCAT_MAX_LEN.' error_message
            ,      @@group_concat_max_len group_concat_max_len
            ;
/*
        declare exit handler for SYNTAX_ERROR 
            select 'Syntax Error' error_type
            ,      'Check this statement.' error_message
            ,      @create_table_statment statement
            ;
*/
        declare exit handler for TABLE_EXISTS_ERROR 
            select 'Table Exists' error_type
            ,      'Drop the table first.' error_message
            ,      concat(v_local_schema,'.',v_local_table) table_identifier
            ;
        declare exit handler for UNKNOWN_COLUMN_ERROR 
            select 'Unknown Column' error_type
            ,      'Unexpected error, check the statement.' error_message
            ,      @create_table_statement table_identifier
            ;
        declare exit handler for NOT FOUND 
            select 'No such Table' error_type
            ,      'The requested table was not found on the remote host.' error_message
            ,      concat(p_remote_schema,'.',p_remote_table) table_identifier
            ;
 declare continue handler for INCORRECT_VALUE_ERROR 
            select 'We hit warning 1366. It''s probably nothing serious.'
            ;
        declare exit handler for SQLEXCEPTION
            select 'SQL Exception' error_type
            ,      'Unexpected generic error. Debug the procedure.' error_message
            ,      concat(
                           'CALL ',schema(),'.', p_create_federated_table,'(' 
                   ,       if( p_remote_host is null
                           ,   'NULL'
                           ,   concat('''',p_remote_host,'''')
                           )
                   ,',',   if( p_remote_port is null
                           ,   'NULL'
                           ,   p_remote_port
                           )
                   ,',',   if( p_remote_user is null
                           ,   'NULL'
                           ,   concat('''',p_remote_user,'''')
                           )
                   ,',',   if( p_remote_password is null
                           ,   'NULL'
                           ,   concat('''',p_remote_password,'''')
                           )
                   ,',',   if(
                               p_remote_schema is null
                           ,   'NULL'
                           ,   concat('''',p_remote_schema,'''')
                           )
                   ,',',   if( p_remote_table is null
                           ,   'NULL'
                           ,   concat('''',p_remote_table,'''')
                           )
                   ,',',   if( p_local_schema is null
                           ,   'NULL'
                           ,   concat('''',p_local_schema,'''')
                           )
                   ,',',   if( p_local_table is null
                           ,   'NULL'
                           ,   concat('''',p_local_table,'''')
                           )
                   ,   ')'
                   ) call_command
            ; 

        -- The following block creates temporary federated tables 
        -- on the remote information_schema. 
        -- These are needed to generate the structure 
        -- of the local federated table. 
 select 'Getting remote metadata...';
        begin
            -- Prefix used for the temporary tables
            declare v_temp_table_prefix char(25)
                default 'p_create_federated_table$';
            -- Used to fetch the generated DDL from the cursor
            declare v_create_table_statment text;
            -- Cursor loop control variable
            declare v_no_more_rows boolean
                default FALSE;
            -- Cursor generates DDL for createing temporary federated
            -- tables on the remote information_schema.
            -- We need this to generate the DDL to create the actual 
            -- federated table specified by the user.
            declare csr_metadata cursor for 
                select      table_name
                ,           concat(
                                'create temporary table'
                            ,'\n',schema(),'.'
                            ,v_temp_table_prefix,table_name,'('
                            ,'\n',group_concat(
                                    column_name
                                ,   ' '
                                ,   column_type
                                ,   if(
                                        character_set_name is null
                                    ,   ''
                                    ,   concat(
                                            ' character set '
                                        ,   character_set_name
                                        ,   ' collate '
                                        ,   collation_name
                                        )
                                    )
                                ,   if( is_nullable='NO'
                                    ,   ' NOT NULL'
                                    ,   ''
                                    )
                                    separator '\n,'
                                )
                            ,'\n',')'
                            ,'\n','engine = federated'
                            ,'\n','connection = '
                            ,'\n',''''
                            ,     v_connectstring
                            ,     table_schema
                            ,     '/'
                            ,     table_name
                            ,     '''' 
                            )
                from        information_schema.columns
                where       table_schema = 'information_schema'
                and         table_name IN (
                                'COLUMNS'
                            ,   'STATISTICS'
                            ,   'TABLE_CONSTRAINTS'
                            )
                group by    table_schema
                ,           table_name
                ;
            -- handler to control the cursor loop
            declare continue handler for NOT FOUND 
                set v_no_more_rows := TRUE;

            set @drop_temporary_tables_statement := null;

            -- loop through the cursor
            open csr_metadata;
            my_loop: loop
                -- get the DDL for the temporary federated 
                -- information_schema table
                fetch csr_metadata 
                into  v_drop_table_name
                ,     v_create_table_statment;
  
                -- basic cursor loop control exits if cursor is exhausted
                if v_no_more_rows then
                    close csr_metadata;
                    leave my_loop;
                end if;
                -- build a statement to drop all temporary tables
                set @drop_temporary_tables_statement := if (
                    @drop_temporary_tables_statement is null
                ,   concat(
                        'DROP TEMPORARY TABLE IF EXISTS '
                    ,   v_temp_table_prefix
                    ,   v_drop_table_name
                    )
                ,   concat(
                        @drop_temporary_tables_statement
                    ,   ','
                    ,   v_temp_table_prefix
                    ,   v_drop_table_name
                    )
                );

                -- kludge: need a user variable to execute the DDL string
                -- dynamically with the PREPARE syntax
                set @create_table_statment := v_create_table_statment;

                -- create the temporary federated information_schema table 
                prepare stmt from @create_table_statment;
                execute stmt;
                deallocate prepare stmt;

            end loop;
        end;
 -- Reset the variable. Mainly to simplify debugging
 select 'Generating CREATE TABLE statement for FEDERATED table...';
 set @create_table_statment:='...generating statement...';
        -- This creates the actual ddl for the requested local FEDERATED table.
        -- It selects the DDL directly into the user variable. 
        -- It does this by querying the remote information_schema.
        -- This DDL includes the index definitions of the remote table.
        select      concat(
                        'create table if not exists'
                    ,'\n','`',v_local_schema,'`'
                    ,'.' ,'`',v_local_table,'`'
                    ,     '('
                    ,'\n',column_definitions
                    ,     coalesce(index_definitions,'')
                    ,'\n',')'
                    ,'\n','engine = federated'
                    ,'\n','connection = '
                    ,'\n',''''
                    ,     v_connectstring
                    ,     column_definitions.table_schema
                    ,     '/'
                    ,     column_definitions.table_name
                    ,     '''' 
                    ) stmt
        into        @create_table_statement
        from        (
                    select      table_schema
                    ,           table_name 
                    ,           group_concat(
                                        '`',column_name,'` '
                                    ,   column_type
                                    ,   if(
                                            character_set_name is null
                                        ,   ''
                                        ,   concat(
                                                ' character set '
                                            ,   character_set_name
                                            ,   ' collate '
                                            ,   collation_name
                                            )
                                        )
                                    ,   if( is_nullable='NO'
                                        ,   ' not null'
                                        ,   ''
                                        )
                                    ,   if( column_default is null
                                        ,   ''
                                        ,   concat(
                                                ' default '
                                            ,   case
                                                    when data_type = 'TIMESTAMP' 
                                                    and  column_default = 'CURRENT_TIMESTAMP'
                                                        then column_default
                                                    when data_type like '%char' 
                                                    or   data_type like 'date%'
                                                    or   data_type like 'time%'
                                                    or   data_type in ('set','enum')
                                                        then concat('''',column_default,'''')
                                                    else column_default
                                                end
                                            )
                                        )
                                    ,   if(extra='','',concat(' ',extra))
                                    ,   ' comment '
                                    ,   '''',column_comment,''''                                        
                                        separator '\n,'
                                ) as column_definitions
                    from        p_create_federated_table$columns
                    where       table_schema = p_remote_schema
                    and         table_name   = p_remote_table
                    group by    table_schema
                    ,           table_name
                    ) column_definitions
        left join   (
                    select      index_definitions.table_schema
                    ,           index_definitions.table_name 
                    ,           concat(
                                    '\n,'
                                ,   group_concat(
                                        case c.constraint_type 
                                            when 'PRIMARY KEY' then 
                                                constraint_type
                                            when 'UNIQUE' then 
                                                concat(
                                                    'CONSTRAINT '
                                                ,   constraint_name
                                                ,   ' '
                                                ,   constraint_type
                                                )
                                            else
                                                concat(
                                                    if( index_type in (
                                                            'FULLTEXT'
                                                        ,   'SPATIAL'
                                                        )
                                                    ,   concat(
                                                            index_type
                                                        ,   ' '
                                                        )
                                                    ,   ''
                                                    ) 
                                                ,   if( non_unique
                                                    ,   ''
                                                    ,   'UNIQUE '
                                                    )
                                                ,   'INDEX '
                                                ,   '`',index_name,'`'
                                                )
                                        end
                                    ,   index_columns
                                    ,   if( index_type in (
                                                'BTREE'
                                            ,   'HASH'
                                            )
                                        ,   concat(
                                                ' USING '
                                            ,   index_type
                                            )
                                        ,   ''
                                        )
                                        order by c.constraint_type
                                        separator '\n,'
                                    )
                                )    as index_definitions
                    from        (
                                select      table_schema
                                ,           table_name
                                ,           index_name
                                ,           index_type
                                ,           non_unique
                                ,           concat(
                                                '('
                                            ,   group_concat(
                                                    '`',column_name,'`'
                                                ,   if( sub_part is null
                                                    ,   ''
                                                    ,   concat(
                                                            '(',sub_part,')'
                                                        )
                                                    )
                                                    order by seq_in_index
                                                )
                                            ,   ')'
                                            ) index_columns
                                from        p_create_federated_table$statistics
                                where       table_schema = p_remote_schema
                                and         table_name   = p_remote_table
                                and         index_type not in ('FULLTEXT')
                                group by    table_schema
                                ,           table_name
                                ,           index_name
                                ,           index_type
                                ,           non_unique
                                ) index_definitions
                    left join   (
                                select      table_schema
                                ,           table_name
                                ,           constraint_name
                                ,           constraint_type
                                from        p_create_federated_table$table_constraints c
                                where       table_schema    = p_remote_schema
                                and         table_name      = p_remote_table
                                and         constraint_type in (
                                                'PRIMARY KEY'
                                            ,   'UNIQUE'
                                            )
                                group by    table_schema
                                ,           table_name
                                ,           constraint_name
                                ,           constraint_type
                                ) c
                    on          index_definitions.table_schema = c.table_schema
                    and         index_definitions.table_name   = c.table_name
                    and         index_definitions.index_name   = c.constraint_name
                    group by    table_schema
                    ,           table_name
                    ) index_definitions
        on          column_definitions.table_schema = index_definitions.table_schema
        and         column_definitions.table_name = index_definitions.table_name
        ;

        -- Create the actual FEDERATED table by dynamically executing
        -- the generated DDL for the requested FFEDERATED table. 
 select 'Creating FEDERATED table...';

        prepare stmt from @create_table_statement;
        execute stmt;
        deallocate prepare stmt;

        -- Print a friendly message that we succeeded
        select   'Success' completion_type
        ,        concat(
                        'Created FEDERATED table '
                    ,   v_connectstring,'/',p_remote_schema,'/',p_remote_table
                    ) completion_message
        ,        concat(v_local_schema,'.',v_local_table) table_identifier
        ;
    end;

    -- Cleanup: restore the original sql mode 
    set @@sql_mode := v_old_sql_mode;
    -- Cleanup: restore the original GROUP_CONCAT buffer size
    set @@group_concat_max_len := v_old_group_concat_max_len;

    -- Cleanup: drop the temporary federated information_schema tables.
    prepare stmt from @drop_temporary_tables_statement;
    execute stmt;
    deallocate prepare stmt;

    -- Cleanup: reset the user defined variables.
    set @create_table_statment := null
    ,   @drop_temporary_tables_statement := null
    ;
end;
$$

delimiter ;

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!

Tuesday, September 26, 2006

Finding Redundant Indexes using the MySQL Information Schema

Peter Zaitsev's blog entry on Duplicate indexes and redundant indexes certainly made a bit of a stir! It has already led to a new (mini) project by Baron Schwartz, the Duplicate index/foreign key finder which is publicly available on MySQLForge as a perl script. Daniel Schneller has entered the arena as well, devoting an entire blog to his own java implementation to tackle this and other index trouble.

I figured it would be fun to add a pure SQL solution for the problem. This is not too hard to implement with the STATISTICS system view found in the MySQL information_schema database. This solution is limited in that it will only work for MySQL 5.0 (and higher). On the other hand, it has the advantage that it does not require any external programming languages or runtime environments.

The solution I'm presenting here also takes the uniqueness of indexes into account, something that - to the best of my knowledge - has not been discussed by the other authors (although I believe that Daniel Schneller's tool does take uniqueness into account).

Those that don't feel like reading the article, hey - you decide. The code is available on MySQLForge as a snippet. The article just explains a little bit of the background of the problem, and explores some techniques to solve it using a pure SQL solution. It finishes with a detailed explanation of the actual query, which you may or may not find interesting to read.

Redundant Indexes


Here's my short account of the problem addressed by Peter Zaitsev. Read the original article for more details.

A redundant index is an index that can be removed without significantly hurting query performance. MySQL allows creation of multiple indexes that are fully or partially similar in structure. This generally does not have any advantages, but does have disadvantages. Therefore, it is usually a good idea to remove these redundant indexes.

I just mentioned the term index structure. I use this term in a rather loose sense as a particular combination of the following three index characteristics:

The index columns

Each index defines the list of columns that are indexed by the index

The index type

The index type corresponds with the internal algorithm that is used to build and maintain the index

The uniqueness of the index

Whether the index is declared to reject duplicate entries


So how do we find out if there are any redundant indexes? Using these characteristics to compare indexes on one particular table to one another covers much of what we need to determine if we are dealing with redundant indexes.

Index Type


The index type corresponds to the particular kinds of internal algorithms and datastructures used to implement the index. In MySQL, support for a particular index type is dependent upon the storage engine:

BTREE

General purpose indexes. Supported for the MyISAM, InnoDB and MEMORY storage engines.

HASH

General purpose indexes. Supported for the MEMORY and NDB storage engines.

FULLTEXT

Special purpose indexes for text columns, optimized for advanced searching of combinations of words. Supported only for the MyISAM storage engine.

SPATIAL

Special purpose indexes for spatial (geometric) datatypes. Supported only for the MyISAM storage engine.


Not all index types are equally suitable for executing an arbitrary query. Rather, particular access patterns implied by the query statement can only be processed efficiently using an index of a certain type.

What does this mean when comparing indexes to on another? Well, it means that a comparison of two particular indexes only makes sense if they have the same type. Also, the index type determines what method should be used to compare the index columns.

Index Columns


As mentioned, columnlists should be compared in a manner that is dependent upon the index type:

BTREE

A BTREE index is redundant if all of it's columns are also indexed in the same order by another index, and the first indexed column is the same for both these indexes. Another way of putting it is to say that the columnlist of the index is the leftmost prefix of the columnlist of the other index.

HASH

A HASH index is redundant if each of it's columns match all of the columns in the same order of another HASH index. Another way of putting it is to say that the columnlists of these index are duplicates of oneanother.

SPATIAL

In MySQL, SPATIAL indexes can have at most one column. So By definition, a SPATIAL index is redundant if there exists another SPATIAL index for the indexed column, that is, if there exists a duplicate.

FULLTEXT

A FULLTEXT index is redundant if all of the indexed columns are already indexed by another FULLTEXT index, regardless of the order of the columns.


A few notes:

  • The criterion for comparing columnlists of HASH indexes is a special case of the criterion used for comparing the columnlists of BTREE indexes. That's because for HASH indexes, both columnlists must have exactly the same number of members.

  • The criterion for comparing columnlists of SPATIAL indexes is a special case of the criterion for comparing the columnlists of HASH indexes. That's because SPATIAL indexes happen to always have just one column.

  • The criterion for comparing columnlists of FULLTEXT indexes is the only case where the ordering of the columns in the columnlist is not at all important for the comparison. The other cases implicitly or explicitly require that both the names and the ordinal positions of the columns match, and that the indexes have the same column at the first ordinal position.


From the mentioned cases BTREE indexes are by far the most abundant. Peter's article is mainly focused on BTREE indexes and redundancy caused by matching left prefixes.

Uniqueness


Uniqueness is a property of an index that tells the database it should not allow duplicate entries. That is, each combination of values in the indexed columns can occur at most once in the entire table.

The uniqueness of an index does not influence the structure of the index as such. However, uniqueness is of major importance to the behaviour applications expect from such an index. Even if an index appears to be redundant according to a comparison based on index type and the columnlist, we should not conclude that we can always remove such seemingly redundant indexes. Doing so could cause a unique index to be dropped, changing the database's rules that validate input.

Because FULLTEXT and SPATIAL indexes cannot be declared to be UNIQUE, uniqueness needs tobe taken into account only when looking for redundant BTREE or HASH indexes.

Index Metadata


MySQL Offers several ways to inspect the indexes in the database.

First of all, you can use the SHOW CREATE TABLE statement. This is just a general utility statement to quickly inspect the structure of a particular table. The output is a DDL statement that could be used to (re)create the table's structure, including index definitions.

For example, take a look at this example from Daniel Schneller's blog:

mysql> show create table people
-> \G
*************************** 1. row ***************************
Table: people
Create Table: CREATE TABLE `people` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`firstname` varchar(32) DEFAULT NULL,
`lastname` varchar(32) DEFAULT NULL,
`birthday` date DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `idx_reversename` (`lastname`,`firstname`),
KEY `idx_id_birth_first` (`id`,`birthday`,`firstname`),
KEY `idx_full` (`firstname`,`lastname`),
KEY `idx_first` (`firstname`),
KEY `idx_id_first` (`id`,`firstname`),
KEY `idx_id_birth` (`id`,`birthday`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

(By the way - I will be using this table definition in the following examples.)

The second way is to use the specialized SHOW INDEX statement, which is especially designed to inspect indexes. This statement does not return DDL, rather, it returns a row for each column for all of the indexes in a particular table, along with more detailed information about the index data such as the cardinality (the number of index entries).

For this table, the result looks like this:

mysql> show index from people;
+--------+------------+--------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+--------+------------+--------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| people | 0 | PRIMARY | 1 | id | A | 0 | NULL | NULL | | BTREE | |
| people | 1 | idx_reversename | 1 | lastname | A | 0 | NULL | NULL | YES | BTREE | |
| people | 1 | idx_reversename | 2 | firstname | A | 0 | NULL | NULL | YES | BTREE | |
| people | 1 | idx_id_birth_first | 1 | id | A | 0 | NULL | NULL | | BTREE | |
| people | 1 | idx_id_birth_first | 2 | birthday | A | 0 | NULL | NULL | YES | BTREE | |
| people | 1 | idx_id_birth_first | 3 | firstname | A | 0 | NULL | NULL | YES | BTREE | |
| people | 1 | idx_full | 1 | firstname | A | 0 | NULL | NULL | YES | BTREE | |
| people | 1 | idx_full | 2 | lastname | A | 0 | NULL | NULL | YES | BTREE | |
| people | 1 | idx_first | 1 | firstname | A | 0 | NULL | NULL | YES | BTREE | |
| people | 1 | idx_id_first | 1 | id | A | 0 | NULL | NULL | | BTREE | |
| people | 1 | idx_id_first | 2 | firstname | A | 0 | NULL | NULL | YES | BTREE | |
| people | 1 | idx_id_birth | 1 | id | A | 0 | NULL | NULL | | BTREE | |
| people | 1 | idx_id_birth | 2 | birthday | A | 0 | NULL | NULL | YES | BTREE | |
+--------+------------+--------------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
13 rows in set (0.00 sec)

The third way is to use the STATISTICS system view in the information_schema database. This offers exactly the same information as the SHOW INDEX statement. However, the STATISTICS system view can be used just as any other table in an arbitrary query, offering possibilities to filter, group, sort, join and whatnot.

For example, output equivalent to that returned by SHOW INDEX statement can be retrieved using the following statement:

SELECT non_unique
, index_name
, seq_in_index
, column_name
, collation
, cardinality
, sub_part
, packed
, nullable
, index_type
, comment
FROM information_schema.STATISTICS
WHERE table_schema = schema()
AND table_name = 'people'
ORDER BY index_name
, seq_in_index

(I think that -despite the explanation given in the manual- it is a bit strange that this system view should be called STATISTICS. A name like INDEX_COLUMNS would better describe the data it exposes, as the system view contains one row for each index column per index.)

Using the STATISTICS system view


As mentioned before, the STATISTICS system view in the information_schema database contains information about index columns rather than indexes. Now how can we use it to compare indexes to each other?

Well, according to the reasoning regarding index comparisons, we know that we should compare indexes appearing in one table to each other, matching at least index type and columns. We could try an see what we can achieve with a self-join of the STATISTICS, matching allmost all identifying columns with the exception of the index name (as a particular index would surely match itself).

Using the GROUP BY operation, we can avoid to report a row for each matched column. Also, this allows us to use GROUP_CONCAT to make a list of the matching columns.

SELECT s1.table_schema idx_schema
, s1.table_name idx_table
, s1.index_type idx_type
, s1.index_name idx_name1
, s2.index_name idx_name2
, group_concat(
i.column_name
order by i.seq_in_index
) idx_columns -- matching index columns
FROM information_schema.STATISTICS s1
JOIN information_schema.STATISTICS s2
ON s1.table_schema = s2.table_schema
AND s1.table_name = s2.table_name
AND s1.index_type = s2.index_type
AND s1.index_name != s2.index_name
AND s1.seq_in_index = s2.seq_in_index
AND s1.column_name = s2.column_name
WHERE s1.table_schema = schema()
AND s1.table_name = 'people'
GROUP BY s1.table_schema
, s1.table_name
, s1.index_type
, s1.index_name
, s2.index_name

Altough it might seem this kind of query is a step into the right direction, the result is not quite what we need at all. Just create the people table if you haven't done so already, try this query, and see if the result makes sense to you.

What is particularly lacking is the fact we do not ascertain that we are matching all the columns of one of the indexes: JOIN will match the columns if a match is possible, and those columns that do match will be in the result. The columns that don't match, but that are in fact part of the index are simply absent from the result.

Effectively, the query reports all indexes for wich parts of the columnlists match without checking at which ordinal position they match and without checking if all the columns of one particular index are matched.

Now these setbacks are of course not impregnable: because we are using GROUP BY we can use the COUNT function to count the number of matched columns. We can choose one of the STATISTICS instances to play the role of the redundant index. The number of matching columns should equal the total number of columns in the instance that plays the 'redundant' role. By definition, the total number of columns in the other instance is than more than (or equal to) the number of matching columns.

SELECT i.table_schema idx_schema
, i.table_name idx_table
, i.index_name idx_name
, r.index_name redundant_idx_name
, group_concat(
i.column_name
order by i.seq_in_index
) idx_columns -- matching index columns
FROM information_schema.STATISTICS i -- i for index
JOIN information_schema.STATISTICS r -- r for redundant
ON i.table_schema = r.table_schema
AND i.table_name = r.table_name
AND i.index_type = r.index_type
AND i.index_name != r.index_name
AND i.seq_in_index = r.seq_in_index
AND i.column_name = r.column_name
WHERE i.table_schema = schema()
AND i.table_name = 'people'
GROUP BY i.table_schema
, i.table_name
, i.index_type
, i.index_name
, r.index_name
HAVING count(r.seq_in_index) = (
-- check if we matched all columns of the 'redundant' index
SELECT count(1)
FROM information_schema.STATISTICS
WHERE table_schema = idx_schema
AND table_name = idx_table
AND index_name = redundant_idx_name
)

Phew.... Now, let's take a look at the result:

+------------+-----------+--------------------+--------------------+-------------+
| idx_schema | idx_table | idx_name | redundant_idx_name | idx_columns |
+------------+-----------+--------------------+--------------------+-------------+
| test | people | idx_full | idx_first | firstname |
| test | people | idx_id_birth | PRIMARY | id |
| test | people | idx_id_birth_first | idx_id_birth | id,birthday |
| test | people | idx_id_birth_first | PRIMARY | id |
| test | people | idx_id_first | PRIMARY | id |
+------------+-----------+--------------------+--------------------+-------------+

Well, at least, we do get a list of the redundant indexes, but the same index is reported multiple times.

Now we could go on in this manner in order to get a list of unique redundant indexes. We can also try another JOIN solution. Joining on complete concatenated columnlists is for exmpple an approach that might seem a bit strange but that does actually have some advantages over this method.

However, the solution that I tend to favour right now is one that uses no JOINs at all.

Finding redundant indexes


We just discussed how we could use a JOIN to compare the column lists of two indexes. Up to a certain extend, GROUP BY can be used to drive comparison too.

It seems strange to think of GROUP BY, but what we are trying to do is to compare indexes according columnlist prefixes. However, when you think of it as making groups of a part of the columnlist, it should begin to make sense. Without further ado, here's the solution I eventually came up with:

select table_name
, index_type
, min(column_names) column_names
, trim(',' FROM
case index_type
when 'BTREE' then
replace(
-- report all but the last one
-- (the last one is the longest one)
substring_index(
group_concat(
'`',index_name,'`'
order by column_count asc
, non_unique asc
, index_name desc
separator ','
)
, ','
, count(*) - 1
)
-- get the first one
-- (the first one is the smallest unique one)
, concat(
'`'
, substring_index(
group_concat(
if( non_unique = 0
, index_name
, ''
)
order by non_unique asc
, column_count asc
, index_name asc
separator ','
)
, ','
, 1
)
, '`'
)
, ''
)
when 'HASH' then
substring_index(
group_concat(
'`',index_name,'`'
order by non_unique asc
, index_name asc
separator ','
)
, ','
, 1 - count(*)
)
when 'SPATIAL' then
substring_index(
group_concat(
'`',index_name,'`'
order by index_name asc
separator ','
)
, ','
, 1 - count(*)
)
else 'unexpected type - not implemented'
end
) redundant_indexes
from (
select table_name
, index_name
, index_type
, non_unique
, count(seq_in_index) as column_count
, group_concat(
if(seq_in_index=1,column_name,'')
separator ''
) as column_name
, group_concat(
column_name
order by seq_in_index
separator ','
) as column_names
from information_schema.statistics s
where s.table_schema = schema()
and s.index_type != 'FULLTEXT'
group by table_name
, index_name
, index_type
, non_unique
) as s
group by table_name
, index_type
, if(index_type='HASH',column_names,column_name)
having redundant_indexes != ''

Explanation


Lets start with the straighforward bit. We already mentioned that the STATISTICS table returns index columns rather than indexes. Lets first make a query that returns a row for each index rather than for each index column:

select table_name
, index_name
, count(seq_in_index) as column_count
, group_concat(
if(seq_in_index=1,column_name,'')
separator ''
) as column_name
, group_concat(
column_name
order by seq_in_index
) as column_names
from information_schema.statistics s
where s.table_schema = schema()
and s.index_type != 'FULLTEXT'
group by table_name
, index_name

The GROUP BY is used to group identifying properties of an index: the table name and the index name. The table_schema is also partially identifying, but the query requires that only indexes are queried that reside within the current schema, so that is why the schema_name column appears in the WHERE clause and thus need not be part of the GROUP BY list:

where s.table_schema = schema()

We've also excluded FULLTEXT indexes, just for convenience.

and s.index_type != 'FULLTEXT'

In the SELECT-list, we calculate a few aggregates. The column_count expression is pretty self-explanatory, it counts the number columns in the index:

count(seq_in_index) as column_count

We won't dwell on this now, but it will prove to be useful later on.

There is one special aggregate: column_name:

group_concat(
if(seq_in_index=1,column_name,'')
separator ''
) as column_name

The intention of this expression is to report only the first of the columns in the columnlist, meaning: the column with ordinal postion equal to one. So, we are aggregating over an IF expression that returns the columnname only if it appears as the first column seq_in_index=1) in the index. Otherwise, it returns the empty string.

This expression is evaluated for each of the columns for the index that is grouped by the GROUP BY, seperating the entries by again, the empty string. The condition will be true for just one of the columns that are grouped together. The entire expression this will give us that one column name, concatenated to lots of empty strings, wich of course amounts to just the one column name.

The column_names expression concatenates all columns of the index ordered by ordinal position:

group_concat(
column_name
order by seq_in_index
) as column_names

In this case, no separator is specified so the default, a comma, will be used. The result of this expression allows an easy confirmation that the column_name indeed reports only the first column of the index.

The column_name expression is important because it allows us to make groups of indexes according to a column prefix of their columnlists. By definition, all indexes that have the same columnlist prefix must have the same column as first column. So, we don't need to group using the largest common prefix, rather, we are using the smallest thinkable common prefix. This works even if the index with the smalles columnlist has more than just one column.

We need the column prefix to compare BTREE indexes to each other. However, as mentioned in the introduction, a prefix comparison is not enough for HASH indexes. For HASH indexes, the entire columnlist should be used. So, somehow, we need to switch the grouping expression, depending upon whether or not the index type is HASH or not.

This leads us to another little issue we have to take care of. In the introduction we mentioned that it is only useful to compare indexes of the same index type. So, in addition to the previous query, we now also introduce the index_type column: only within the group of indexes of a particular type do we want to make groups of a common column prefix.

Adding index_type to the GROUP BY list of the previous query will not affect the number of returned rows. That's because the grouping in the previous query was per index, and since a particular index has only one index type, adding the column to the GROUP BY cannot give rise to subgroups beyond the index level.

However, it can (and does) once we start grouping indexes themselves:

select table_name
, index_type
, column_name
, group_conat(
index_name
) index_names
from (
select table_name
, index_name
, index_type
, count(seq_in_index) as column_count
, group_concat(
if(seq_in_index=1,column_name,'')
separator ''
) as column_name
, group_concat(
column_name
order by seq_in_index
separator ','
) as column_names
from information_schema.statistics s
where s.table_schema = schema()
and s.index_type != 'FULLTEXT'
group by table_name
, index_name
, index_type
) as s
group by table_name
, index_type
, if(index_type='HASH',column_names,column_name)

Note that we are not just grouping by the columnlist prefix in all cases. Because indexes of the HASH type are only equivalent when there is a match for the entire columnlist, we need to take that into account in the GROUP BY expression:

if(index_type='HASH',column_names,column_name)

So, if we are dealing with a HASH index, then group by the entire columnlist, else group by the (smallest) prefix only.

The SELECT list contains an expression to produce a comma-separated list of all the indexes that we consider in the comparison:

group_conat(
index_name
) index_names

Some of the indexes that appear in this list will be redundant, but some of them are essential: removing them will certainly affect the performance of certain queries. If we could somehow remove the essential indexes from the list, we would end up with a list of redundant indexes, which is what we set out to do.

How can we go about this? Well, let's stick to the case for BTREE's for a while. Remember that for this index type, we are primarily interested in the index with the longest columnlist: we consider that to be the most essential index. It is essential because it offers an access path that is not offered by indexes with shorter columnlists, and the access path offered by the other indexes is already contained within the one with the longest columnlist.

(We really can safely forget about other index types for a while. In case of HASH and SPATIAL indexes, we are dealing with identical columnlists, so by definition, all columnlists are 'the longest'. That means that whatever solution we come up with for BTREE's applies automatically to these index types although it may be possible that a simpler solution is available for these index types.)

Now, only if we were able to extract the index_name with te largest number of columns from the list...

We actually know already how many columns each index has, because we computed that already in the subquery as the column_count expression. But how do we use that information? Well, we can use the optional ORDER BY clause of the GROUP_CONCAT() function. Using that, we could sort our index names according to the number of columns in the index:

group_conat(
index_name
order by column_count
) index_names

This ensures that the indexes with the largest number of columns in the columnlist are queued up at the end of the list. Once it is sitting there, it is not too hard to extract it: we can use the SUBSTRING_INDEX() function for that, like so:

substring_index(
group_concat(
index_name
order by column_count
separator ','
)
, ','
, count(*) - 1
)

What happens here is that the comma separated list of index names, ordered according to the number of columns in the index, is generated first. (For clarity the SEPARATOR clause is included in the GROUP BY.) Then, SUBSTRING_INDEX takes only a part from it, namely the part up to the last comma in the list. The last comma is conveniently calculated by taking the count of indexes that are used to generate te list, and substracting one (because the indexes in the list are separated by a comma, there is exaclty on comma less than the number of indexes). So the last index, the essential index, is cut off, and what then remains is the list of redundant indexes.

Having explained the technique, we can now discuss a few minor improvements. First of all, what happens when there is not just one 'essential index' but two, or even more? It is quite possible that there is not just one index with the maximum number of columns for the given prefix. Well, in that case, since we are dealing with duplicates, we will simply elect the index with the 'smallest' index name.

This is easy enough to implement. We simply have to add a new sort key within the column_count. Because we have arranged for SUBSTRING_INDEX() to discard the last entry of the list, we must order by index_name in descending order:

substring_index(
group_concat(
index_name
order by column_count
, index_name desc
separator ','
)
, ','
, count(*) - 1
)

Ok, so far so good. Now there is really one thing we've consistenly ignored all the time, and that is unicity. What do we do when our list of 'redundant' indexes contains on or more unique indexes? Well, if we were to remove this from the schema, we could be in big trouble! Input that would have been rejected because it violated a unique index would suddenly be allowed, and this is certainly not our intention. This simply means that our concept of a redundant index is incomplete. It doesn't take an important feauture of the indexes not into account, namely the unicity.

So what do we need to do in case we really do have UNIQUE indexes? Well, we should look for the UNIQUE index with the least number of columns. Just as the index with the largest number of columns provides an essential acces path, the unique index with the smallest number of columns provides an essential unicity rule. Any other unique indexs with the same prefix that have more columns are redundant: they cannot make their indexed data 'more unique'.

Luckily, this improvement is not more complicated than what we've seen sofar. What we can do is set up an entire new list of only the unique indexes:

substring_index(
group_concat(
if( non_unique = 0
, index_name
, ''
)
order by non_unique asc
, column_count asc
, index_name asc
separator ','
)
, ','
, 1
)

Using the same techniques we used before, we constructed an expression that generates a list of only UNIQUE indexes, sorted on the number of columns. If there is at least one UNIQUE index, that will be in front of the list. Using SUBSTRING_INDEX() we can cut the first UNIQUE index of the list: this will be the one with the smallest number of columns, because we included the column_count expression in the ORDER BY clause.

Now, all we need to do is remove the index name of the unique index with the smallest number of columns from our list of 'redundant indexes'. This is easily done by the REPLACE() function. Putting it alltogether, we get something like this:

replace(
substring_index(
group_concat(
'`',index_name,'`'
order by column_count asc
, non_unique asc
, index_name desc
separator ','
)
, ','
, count(*) - 1
)
, concat(
'`'
, substring_index(
group_concat(
if( non_unique = 0
, index_name
, ''
)
order by non_unique asc
, column_count asc
, index_name asc
separator ','
)
, ','
, 1
)
, '`'
)
, ''
)

That's about it really. We do need to do a little more effort to ascertain that REPLACE() will only remove complete index names, but that is not too hard. Also, we all this cutting and replacing might leave a few stray commas behind: those must be cleaned up as well.

Limitations


This solution certainly has it's limitations. I've made a list of the most important ones:

  • Relies on Information schema: this solution is not available in MySQL <= 5.0, and it might be slow

  • FULLTEXT indexes are ignored

  • Column prefixes are ignored.


If you have any comments, suggestions, or whatsoever, don't hesitate to post a comment, please do. Remember, the code will remain available as a snippet at MySQLForge.

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,...