ProxySQL Binary Search Solution for Rules

We sometimes receive challenging requests… this is a story about one of those times.

The customer has implemented a sharding solution and would like us to review alternatives or improvements. We analyzed the possibility of using ProxySQL as it looked to be a simple implementation. However, as we had 200 shards we had to implement 200 rules — the first shard didn’t have much overload, but the latest one had to go through 200 rules and took longer.

My first idea was to use FLAGIN and FLAGOUT creating a B-Tree, but the performance was the same. Reviewing the code, I realized that the rules were implemented as a list, which means that, in the end, all the rules were going to be processed until hit with the right one and FLAGIN is used just to filter out.

At that point, I asked, what could I do? Is it possible to implement it differently? What is the performance impact?

One Problem, Two Solutions

I think that it would be worthy to clarify again that I have to change the code because I found no performance gain with the current implementation. This means that writing the rules to take the advantage of the binary search took me halfway, and implementing the rules with Map allowed the performance gain expected, as now we are jumping to the right rule chain and skipping the others.


I decided to change the ProxySQL code to use a different structure (Map) to store the rules and when the FLAGOUT is there, start that path. This is 100% proof of concept, do not use the code in this repo on production as it is not thoroughly tested and might have several bugs. However, we can trust the behavior and results of the test under the scenario that I’m presenting.

Base case

Using ProxySQL without any change and with 1 rule per shard will be our base case. This means, that it is going to evaluate 1 rule for shard-1 but 200 evaluations need to be made to reach the rule for shard-200.

In this case, the rules will be like this:

insert into mysql_query_rules (active,match_pattern,apply,destination_hostgroup) values (1,'\/\* 000',1,0);
insert into mysql_query_rules (active,match_pattern,apply,destination_hostgroup) values (1,'\/\* 001',1,0);
insert into mysql_query_rules (active,match_pattern,apply,destination_hostgroup) values (1,'\/\* 002',1,0);
insert into mysql_query_rules (active,match_pattern,apply,destination_hostgroup) values (1,'\/\* 003',1,0);

Binary search use case

In order to reduce the number of evaluations, I decided to use the divide and conquer idea. I created the rules in this way:

replace into mysql_query_rules (active,match_pattern,flagIN,flagOUT,apply,destination_hostgroup) values (1,'\/\* [0-1]',0,01,0,999);
replace into mysql_query_rules (active,match_pattern,flagIN,flagOUT,apply,destination_hostgroup) values (1,'\/\* 0' ,01, 0,1, 0);
replace into mysql_query_rules (active,match_pattern,flagIN,flagOUT,apply,destination_hostgroup) values (1,'\/\* 1' ,01, 0,1, 1);
replace into mysql_query_rules (active,match_pattern,flagIN,flagOUT,apply,destination_hostgroup) values (1,'\/\* 2' , 0, 0,1, 2);
replace into mysql_query_rules (active,match_pattern,flagIN,flagOUT,apply,destination_hostgroup) values (1,'\/\* 3' , 0, 0,1, 3);

will be more rules to write but the number of evaluations are less and evenly distributed:

Shard | Amount of Evaluations
0     | 2
1     | 3
2     | 2
3     | 3

Rule evaluation

Take into account that evaluating a rule means basically reading the parameters and comparing them. This might not be hard work if you have a few amounts of rules, but we had 200 shards, so we need at least 200 rules. Let’s compare how many evaluations are being made on each case:

root@ProxySQL_git:~/git/proxysql# grep "Evaluating rule_id" /var/lib/proxysql/proxysql.log | wc -l
root@ProxySQL_git:~/git/proxysql# grep "Evaluating rule_id" /var/lib/proxysql/proxysql.log | wc -l

The first number is the number of evaluations that ProxySQL needs using the List, the second is using the B-Tree solution and Map. As you can see, we are evaluating 5.3 times less.


For the test, I created 3 EC2 instances with these roles:

  • App simulator which is going to run a script that simulates 32 threads running 2M queries like this:
/* 000 */ select 'test' from dual;

  • ProxySQL Server which is going to run both version with the best solution each.
  • Percona Server

The original version of ProxySQL was able to execute 36k of queries per second and using Map and B-Tree was able to execute 61k of queries per second, a 40% increase in throughput.

Another thing to consider is the load in the ProxySQL server for both tests:

In the first picture, we see that the server is reaching 90% of CPU usage but using Map and B-Tree is less than 60%.


I think this proof of concept showed 3 important facts:

  1. That ProxySQL is an amazing tool that is still growing.
  2. The performance penalty using a large number of rules could be reduced.
  3. Writing rules taking into account the binary search might not be only a solution for sharding, could be used for queries hashes for Read-Write splitting.

cscope: Searching Code Efficiently


In this post, we will discuss how to search code with the help of cscope. Let’s begin by checking its description and capabilities (quoting directly from

Cscope is a developer’s tool for browsing source code.

  • Allows searching code for:
    • all references to a symbol
    • global definitions
    • functions called by a function
    • functions calling a function
    • text string
    • regular expression pattern
    • a file
    • files including a file
  • Curses based (text screen)
  • An information database is generated for faster searches and later reference
  • The fuzzy parser supports C, but is flexible enough to be useful for C++ and Java, and for use as a generalized ‘grep database’ (use it to browse large text documents!)

Of course, developers aren’t the only ones browsing the code (as implied by the tool’s description). In the Support team, we find ourselves having to check code many times. This tool is a great aid in doing so. As you can imagine already, this tool can replace find and grep -R "<keyword(s)>" *, and will even add more functionality! Not only this, but our searches run faster (since they are indexed).

The main focus of this post is to explore cscope’s searching capabilities regarding code, but note that you can also use it for text searches that aren’t linked to function names or symbols (supporting regular expressions) and for file searches. This also means that even if the tool doesn’t recognize a function name, you can still use the text search as a fallback.

There is an online manual page, for quick reference:

To install it under RHEL/CentOS, simply issue:

shell> yum install cscope

You can use cscope with MySQL, Percona Server for MySQL or MariaDB code alike. In my case, I had a VM with Percona Server for MySQL 5.7.18 already available, so I’ve used that for demonstration purposes.

We should first get the source code for the exact version we are working with, and build the cscope database (used by the tool to perform searches):

shell> wget
shell> tar xzf percona-server-5.7.18-15.tar.gz
shell> cd percona-server-5.7.18-15
shell> cscope -bR

-b will build the database only, without accessing the CLI; -R will recursively build the symbol database from the directory it’s executed, down. We can also add -q for fast symbol lookup, at the expense of a larger database (we’ll check how much more below).

Now that we have built the cscope database, we will see a new file created: cscope.out. If we used -q, we will also see: and cscope.po.out. Their sizes depend on the size of the codebase in question. Here are the sizes before and after building the cscope database (with -q):

shell> du -d 1 -h ..
615M ../percona-server-5.7.18-15
shell> cscope -bqR
shell> du -h cscope.*
69M cscope.out
103M cscope.po.out
shell> du -d 1 -h ..
794M ../percona-server-5.7.18-15

This gives around 30% increase in size while using -q, and around 10% increase without it. Your mileage may vary: be aware of this if you are using it on a test server with many different versions, or if the project size is considerably larger. It shouldn’t be much of a problem, but it’s something to take into account.

Ok, enough preamble already, let’s see it in action! To access the CLI, we can use cscope -d.

A picture is worth a thousand words. The following output corresponds to searching for the MAX_MAX_ALLOWED_PACKET symbol:


If there are multiple potential matches, the tool lists them for our review. If there is only one match, it will automatically open the file, with the cursor at the appropriate position. To check a match, either select it with the arrow keys and hit enter, or use the number/letter listed. When you are done and need to get back to cscope to continue checking other matches, simply exit the text editor (which can be defined by using CSCOPE_EDITOR). To get back to the main menu to modify the search, press CTRL-f. To exit the tool press CTRL-d. Lastly, CTRL-c toggles case insensitive mode on and off.

To show how the tool displays searches with many hits, let’s search for functions that call printf:


We can now see that letters are also used to list options, and that we can hit space to page down for more matches (from a total of 4508).

Lastly, as mentioned before if everything else fails and you are not able to find the function or symbol you need (due to limitations or bugs), you can use the “Find this text string” and “Find this egrep pattern” functionality.

I hope this brief tour of cscope has been useful, and helps you get you started using it. Note that you can use it for other projects, and it can be handy if you need to dive into the Linux kernel too.


For even more power, you can read this vim tutorial (, or set up ctags ( along with cscope.

Powered by WordPress | Theme: Aeros 2.0 by