QOT

In the last few months we’ve got couple of bugs with the PBXT read/write locking code. One of the problems was directly in the lock/grant algorithm. It was strange to find such kind of error after quite long time of various testing and real-life usage. From the point of view of QA it was clear that manual code review was not efficient in this case.

Given all this I decided to try formal verification of the code. The specifics of the PBXT locking code is that it’s relatively small (about 100 LOC) but quite complex. The algorithm itself is not that trivial but the major source of complexity is concurrent execution of its parts. So if I had to manually create a finite state table for it then it would be essentially a cartesian product of states of all concurrent threads. In numbers that is if there is about 20-30 states per thread and there are 3 threads (empirically I estimated that threads beyond 3 don’t add more states) then I would get between 8000 and 27000 of states to check - quite a bit of work to do on a piece of paper (and a very good example of multithread complexity).

So I decided to try a verification tool. After some evaluation I picked SPIN. Verification with SPIN bascially consists of 2 steps: 1) build SPIN model 2) run verification and/or simulation.

I built 2 models - the buggy one and (presumably) fixed one. The buggy version triggered an assertion after a second of simulation (compare that to months of C code testing!) while the fixed one successfully passed both simulation and verfication.

Does this mean the code is bug-free? The answer is - the SPIN model is bug free. But given that it fairly close resembles the code chances are very high that the code is bug-free as well. Knowing this will save us some debugging time in future.

This was my first practical experience with formal verification. If you use formal verification in your work then please let me know which tools do you use, what kind of code do you check, general considerations, etc…

Thanks

Last weekend I’ve reached a milestone in my work on the statistical index analysis for QOT. The code is available on Launchpad.

An example is worth a thousand words, so I start with one (once again I’m using employees-db):

$ ./qot –info –host=192.168.200.1 –analyse=possible –schema=employees –query=”select * from dept_emp where (dept_no = ‘d005′ or dept_no = ‘d006′) and (emp_no = 10010 or emp_no = 10011)”

/* Output produced by qot 0.1.6 GPL */
/*
Query: select * from dept_emp where (dept_no = ‘d005′ or dept_no = ‘d006′) and (emp_no = 10010 or emp_no = 10011)

selectivity:
all rows

used tables:
dept_emp (all rows)

ordering:
no ordering

related existing indexes:

dept_emp.PRIMARY(emp_no, dept_no): lookup
predicate statistics:

[emp_no = ? AND dept_no = ?] rows
avg/min/max/avg %: 1 / 1 / 1 / 0.000301565
25/50/75 perc: 1 / 1 / 1
stddev: 0
distinct values: 331603

[emp_no = 10010 AND dept_no = ‘d005′] rows/%: 0 / 0
[emp_no = 10011 AND dept_no = ‘d005′] rows/%: 0 / 0
[emp_no = 10010 AND dept_no = ‘d006′] rows/%: 1 / 0.000301565
[emp_no = 10011 AND dept_no = ‘d006′] rows/%: 0 / 0

dept_emp.emp_no(emp_no): lookup
predicate statistics:

[emp_no = ?] rows
avg/min/max/avg %: 1.10525 / 1 / 2 / 0.000333307
25/50/75 perc: 1 / 1 / 1
stddev: 0.306882
distinct values: 300024

[emp_no = 10010] rows/%: 2 / 0.000603131
[emp_no = 10011] rows/%: 1 / 0.000301565

dept_emp.dept_no(dept_no): lookup
predicate statistics:

[dept_no = ?] rows
avg/min/max/avg %: 36844.8 / 17346 / 85707 / 11.1111
25/50/75 perc: 20117 / 21126 / 52245
stddev: 25144.4
distinct values: 9

[dept_no = ‘d005′] rows/%: 85707 / 25.8463
[dept_no = ‘d006′] rows/%: 20117 / 6.06659
*/

In short, the tool now performs index selectivity analysis in respect to the predicates of given query. Before the analysis the WHERE expression is transformed into disjunctive normal form (DNF) and then individual predicates (conjunctions) are analysed in the context of existing relevant indexes.

In this example QOT has found 3 relevant indexes: PRIMARY, dept_no and emp_no. For every index QOT made a query to the server and calculated 2 kinds of predicate selectivity statistics: general predicate selectivity independent of used constant values and selectivity with the constants used in the query. For the general selectivity the following metrics are calculated: average/min/max number of rows (average row count value and % from the total row count), 25, 50 and 75 percentiles, standard deviation from the average value and number of distinct values. For constants the number of rows is calculated (represented as absolute value and % from the total row count).

In particular you can see that the primary key average selectivity is 1 row and standard deviation is 0, i.e. every primary key value is present exactly once in the table (using this property you can for example easily find candidate keys).

emp_no is not unique but has very high selectivity close to 1. Unlike primary key this index doesn’t include all fields used in WHERE-clause but it’s twice shorter than the primary key and thus requires less memory and less disk reads which means chances are the query will be executed faster with this index than with the primary key.

On the other hand dept_no has very low selectivity in general (only 9 distinct values for > 300 000 rows!)  and in particular for values dept_no = ‘d005′ and dept_no = ‘d006′ (25% and 6% respectively). So you usually don’t want to use dept_no index in this kind of query.

Assume you have a table with about 300 000 rows, and an indexed column ‘col1′ with only 9 distinct values. Now you got a query like ’select * from t1 where col1 = const’. The questions are

- when the index is faster to full table scan and vice versa?
- does MySQL use the optimal plan by default?

These questions became very relevant now that QOT got server access and is able to gather various table metrics including selectivity. Besides index selectivity the threshold value obviously depends on the storage engine used, so for me it is also interesting to see how our PBXT engine compares to others in this aspect. Namely to InnoDB - an engine with similar transactional properties and MyISAM - a very fast engine for read-only scenarios.

For the test I took the employees test database. The database contains dept_emp table which serves to maintain a many-to-many relation between departments and employees - there could be many employees in a department and an employee at different times can work in different departments. The query would be to select all employees who ever worked in a given department.

mysql> show create table dept_emp \G
*************************** 1. row ***************************
Table: dept_emp
Create Table: CREATE TABLE `dept_emp` (
`emp_no` int(11) NOT NULL,
`dept_no` char(4) NOT NULL,
`from_date` date NOT NULL,
`to_date` date NOT NULL,
PRIMARY KEY (`emp_no`,`dept_no`),
KEY `emp_no` (`emp_no`),
KEY `dept_no` (`dept_no`),
CONSTRAINT `FOREIGN_1` FOREIGN KEY (`emp_no`) REFERENCES `employees` (`emp_no`) ON DELETE CASCADE,
CONSTRAINT `FOREIGN_2` FOREIGN KEY (`dept_no`) REFERENCES `departments` (`dept_no`) ON DELETE CASCADE
) DEFAULT CHARSET=latin1
1 row in set (0.00 sec)


the only index that can be theoretically used here is dept_no. It’s selectivity:

mysql> select dept_no, count(*) from dept_emp group by dept_no with rollup;
+---------+----------+
| dept_no | count(*) |
+---------+----------+
| d001    |    20211 |
| d002    |    17346 |
| d003    |    17786 |
| d004    |    73485 |
| d005    |    85707 |
| d006    |    20117 |
| d007    |    52245 |
| d008    |    21126 |
| d009    |    23580 |
| NULL    |   331603 |
+---------+----------+
10 rows in set (0.17 sec)


For the query I will use the least selective index value ‘d005′. The query and the default plan:

mysql> explain select * from dept_emp where dept_no = 'd005' \G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: dept_emp
type: ref
possible_keys: dept_no
key: dept_no
key_len: 4
ref: const
rows: 86069
Extra: Using where
1 row in set (0.00 sec)


For all 3 engines MySQL returns different selectivity estimates but always prefers ref access to full scan. This is a bit strange as the index is non-covering. The index-less query and plan:


mysql> explain select * from dept_emp ignore index (dept_no) where dept_no = 'd005' \G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: dept_emp
type: ALL
possible_keys: NULL
key: NULL
key_len: NULL
ref: NULL
rows: 331603
Extra: Using where
1 row in set (0.00 sec)


Test results:

Quite predictably index ref access is slower for all engines as it requires more random disk reads which eat considerable amount of time. So the default MySQL plan is sub-optimal.

Another interesting result is that MyISAM index scan is much slower that the others (doesn’t MyISAM have leaf-to-leaf pointers?). Quite predictably InnoDB table and index times make much less diference than for others. I’m pleased to notice that PBXT shows the best reading time both in table and index scan. I believe main reasons for this are the PBXT’s fixed record format and memory-mapped file access.

Memory-bound case is much more interesting. MyISAM table scan is the fastest one here. But remember to achieve it you will need to explicitly disable index access and this is what QOT will soon detect and do for you . What’s much more interesting is that for PBXT index ref access is faster than table scan and is almost as fast as MyISAM table scan. As we are not touching disk random reads don’t anymore make any difference to sequential scans and here come into play other factors. For example PBXT indexes keep direct pointers to records (i.e. not to rows), so version resolution path for them is shorter than for table scans. (hmm, can we avoid row-index file read if the sweeper has no work to do?). Another interesting detail (provided that the engines have very different architecures) is that InnoDB and PBXT table scans take the same time.

The bottom line is that in disk-bound scenario table scan is predictably faster. Unlike other engines in memory-bound case PBXT’s index ref access is faster than table scan providing optimal performance for the default MySQL plan. For other engines you have to watch your selectivity and query plans to achieve optimal results. For those who’s lazy enough to do it him/her self there’s a new version of QOT coming out soon that will evaluate the optimal execution plan.

Working on server-based index analysis I once again recalled a topic I wanted to write about for many times. The topic is redundant “Using where” in query plans. Suppose we have a table like this:

mysql> show create table t1 \G
*************************** 1. row ***************************
Table: t1
Create Table: CREATE TABLE `t1` (
`a` int(11) NOT NULL DEFAULT ‘0′,
`b` int(11) NOT NULL AUTO_INCREMENT,
PRIMARY KEY (`a`,`b`)
) ENGINE=PBXT AUTO_INCREMENT=25651 DEFAULT CHARSET=latin1
1 row in set (0.02 sec)

now let’s try to analyse 2 simple queries with EXPLAIN SELECT:

1. SELECT a FROM t1 WHERE a>1;
2. SELECT a FROM t1 WHERE a>1 AND b>1;

mysql> explain select * from t1 where a>1 \G
*************************** 1. row ***********
id: 1
select_type: SIMPLE
table: t1
type: range
possible_keys: PRIMARY
key: PRIMARY
key_len: 4
ref: NULL
rows: 200
Extra: Using where; Using index
1 row in set (0.03 sec)

mysql> explain select * from t1 where a>1 and b>1 \G
*************************** 1. row ******************
id: 1
select_type: SIMPLE
table: t1
type: range
possible_keys: PRIMARY
key: PRIMARY
key_len: 4
ref: NULL
rows: 200
Extra: Using where; Using index
1 row in set (0.00 sec)

Let’s shortly look at execution paths of the queries. The first one is a typical range scan. MySQL asks storage engine to position the cursor right after the key with value “a=1″, and performs scan in range (1, +inf] returning to client all rows as returned by storage engine. What’s important here is that MySQL is free to send to client all rows as returned by storage engine and no further check is need to ensure that a row matches the WHERE-clause. Now the second query. The major difference from the previous case is that although PRIMARY KEY adjacently includes both fields “a” and “b” the WHERE condition is not anymore a single contiguous open-ended row range. This means that MySQL needs either to scan multiple ranges (for all keys with a>1 fetch subrange with b>1) or fetch the range “a>1″ and do some post-processing then. In any case MySQL needs to check every row returned by storage engine to match the WHERE-condition. This additional filtering is indicated in EXPLAIN with “Using where”. This also implies that for the first query you shouldn’t see “Using where” - it’s just not needed. But as you can see MySQL indicates “Using where” in both cases. I stepped through the query execution code and I can confirm that it is really performed for the first query.

This might be not as big problem as for example bad query plan, but this still hurts performance. For example checking a condition like “a>1″ implies at least 3 virtual function calls for every row…

Using QOT you can easily check whether the WHERE condition can be fully transformed into an index range scan or not:

/*
Query: select a from t1 where a>1
…

related existing indexes:
t1.PRIMARY(a, b): lookup, covering
*/

/*
Query: select a from t1 where a>1 and b>1
…

related existing indexes:
t1.PRIMARY(a, b): lookup (partial), covering
*/

As you can see for the second query QOT indicates that the index can be used to resolve WHERE condition only partially.

Finally QOT development has reached an important milestone - all the tests were migrated to the new testing framework. The latest changes can be found at Launchpad - lp:qot. This switches the green light to the development of new features.

The first thing to be implemented is data schema reading from server so it is no more necessary to provide a script with DDL. Basically the code is already written but not yet well tested and the documentation is yet to be updated. Command line options are similar to MySQL (–host, –port, –user, –password). So far only TCP connections are supported, but of course I’m planning to add Unix sockets and Windows pipes. For those who would like to give it an early try I have pushed the code to a separate branch: lp:~vkolesnikov/qot/qot-server-connections

Based on the server connections implementation I have also started the work on index efficiency estimator. There’s no much code yet, but I have run some benchmarks and got some very interesting results in terms of different storage engines. I’m going to make a separate post with more details on this.

Last week (or rather last weekend) was quite productive. I was able to make a good progress migrating to the new mysql-test based testing framework. Reviewing the tests I was able to find and fix some bugs. For example there was a bug that ignored some columns while detecting index capabilities. As I mentioned earlier I also started to rework the output format. Here’s an example:

/*

Query:

select sum(col2) from t2 group by col1selectivity:

all rows

used tables:

t2 (all rows)

used aggregate functions:

sum ( col2 )

ordering:

implicit

related existing indexes:

t2.ix123(col1, col2, col3): covering, optimizes ORDER BY, optimizes GROUP BY

*/

As you can see now the tool reports used aggregate functions, if any. This is very convenient for manual query analysis, especially in non-trivial cases.

Next, the “ordering” now can be “implicit”. This is reported for the cases when there’s a GROUP BY clause and no ORDER BY clause.  As you remember in such cases MySQL automatically adds ordering by the columns used in the GROUP BY. This is a non-standard behavior and in some cases it could hurt the performance so I decided to add this reminder (If you want to disable implicit ordering add ORDER BY NULL to the query).

Next, as you might have noticed I changed index information output format. Below the “related existing indexes” the tool prints information about all the indexes that can be used by MySQL server to execute this query. For every index the tool specifies how the index can be used with thhis query. The following options are possible:

“lookup” - the index can be used to fully resolve the WHERE clause (if any);
“lookup (partial)” - can be used to resolve the WHERE only partially.  This could be because the index doens’t contain all the fields used in the WHERE clause, or the fields order in the index doesn’t match the order required by the WHERE clause. In general this means that MySQL is unlikely to use this index unless it has a very high estimated selectivity. Both “lookup” and “lookup (partial)” indexes are listed under the “possible keys” section in the output of EXPLAIN SELECT command.
“covering” - means the entire query can be resolved using this index (without table or other index access at all);
“optimizes ORDER BY” - means MySQL can use this index to avoid filesort in ORDER BY;
“optimizes GROUP BY” - means MySQL can use this index to avoid temporary table creation in GROUP BY;

So far that’s it. See you next week

 With this post I want to start the practice of writing short weekly summaries of QOT activities.

This week I was able to work on some bug reports: #12 #13 #14 #15. Some trivial crashes, some of which were already fixed before. As I wrote in my previous post, I have changed the way I do the releases so if you want to have all the latest features and fixes be sure to use the latest Launchpad version of QOT.

Besides the bugs I started to rework my testing environment. Earlier I had a set of C++ - based unit-tests. I used while-box approach which was very convenient when the project had a smaller codebase and it was important to make core features work without having a defined user interface yet. But now it takes more and more time to write tests this way. That’s why I started to migrate to the MySQL Test Framework. It’s a very powerful tool based on very simple idea - you run the program, collect its output and compare to a pre-saved correct value. A test case there is a script consisting of SQL, shell and other commands. This way it becomes very easy for example to make QOT to generate an index and check if the index is really used by server. The work still in progress, but one interesting thing I noticed is that inside the tool I have lot more useful information than I show in output so now I’m also thinking about extending the QOT report format.

So far that’s it! See you next week

General

Being quite busy with my full-time job at PrimeBase Technologies and quite limited in time for QOT development I was looking for ways to optimize the process around QOT.

I came to a conclusion that instead of preparing and releasing milestone binary releases it will be more optimal to declare the main project trunk to be the permanent release place and “release” the new features and bug-fixes by simply pushing them to the main trunk. This way I will be able to make individual features and bug fixes available as soon as possible. So

to install QOT for the first time you do:

1. install Bazaar

2. run “bzr branch lp:qot” from the shell to get the latest stable QOT sources

3. follow the usual QOT build/install procedure

to update to a new version:

1. run “bzr pull lp:qot” to update sources to the latest stable version

2. follow the usual QOT build/install procedure

Below I will point out the most important consequences of this model.

Code stability

Code stability will not degrade in particular because QOT is quite a small project where most of the testing is automatic and running the full test suite even daily is easy. In fact the “average” code stability should even increase as the new bug fixes will be available as soon as they are implemented!

Binary builds

This is something I cannot do very often, just because currently this process is manual. However this shoudn’t be a problem for Unix/Linux users where GNU C compiler is available by default. On Windows I use MS Visual Studio. You will need the free version of the IDE and Windows SDK 6.0.

I’m still planning to do binary releases but on a more rare basis, depending on the amount of newly added code/bug fixes.

Bug tracking, Feature Requests and Participation

Launchpad has convenient facilities for submitting bug reports and feature requests. You are encouraged to use them to report bugs/make feature requests. Bug fixes can be tracked by binding bug reports to source branches.

For those who considers adding some custom features to QOT Launchpad offers a very flexible parallel development model which is very well exalained here:

part 1
part 2

Basically you can either fork the trunk and maintain your own version and periodically pull updates from the trunk or do the full cycle by proposing your changes back to the trunk.

Final Word

I hope these changes will help optimize the QOT development process, improve the quality and increase development dynamics. Your questions and suggestions are welcome!

I had to disable write access for anonymous mantis account because of the spam in comments. Will enable it one I add some kind of protection. For now - please register to report a bug. Thanks.

I moved all the QOT code to Launchpad. This includes code for the tool, tests and a small experimental utility qot-predictor, which based on query analysis tries to predict which queries are likely to be executed next. Project URL for branching is lp:qot. If you want to push your own changes just create a new project branch.