CODEWITHSUNDEEP
mysqlalgorithmmariadbmysql-5.6taocp
abelard2008
abelard2008

Reputation: 2084

How to understand the algorithm of mysql's gen_lex_hash.cc?

I am reading the mysql's gen_lex_hash.cc, but I don't know the explanation:

The idea of presented algorithm see in "The Art of Computer Programming" by Donald E. Knuth Volume 3 "Sorting and searching" (chapter 6.3 "Digital searching" - name and number of chapter is back translation from Russian edition :)) 

as illustration of data structures, imagine next table:

static SYMBOL symbols[] = {
  { "ADD",              SYM(ADD),0,0},
  { "AND",              SYM(AND),0,0},
  { "DAY",              SYM(DAY_SYM),0,0},
};

for this structure, presented program generate next searching-structure:

+-----------+-+-+-+
|       len |1|2|3|
+-----------+-+-+-+
|first_char |0|0|a|
|last_char  |0|0|d|
|link       |0|0|+|
                 |
                 V
   +----------+-+-+-+--+
   |    1 char|a|b|c|d |
   +----------+-+-+-+--+
   |first_char|d|0|0|0 |
   |last_char |n|0|0|-1|
   |link      |+|0|0|+ |
               |     |
               |     V
               |  symbols[2] ( "DAY" )
               V
+----------+--+-+-+-+-+-+-+-+-+-+--+
|    2 char|d |e|f|j|h|i|j|k|l|m|n |
+----------+--+-+-+-+-+-+-+-+-+-+--+
|first_char|0 |0|0|0|0|0|0|0|0|0|0 |
|last_char |-1|0|0|0|0|0|0|0|0|0|-1|
|link      |+ |0|0|0|0|0|0|0|0|0|+ |
            |                    |
            V                    V
        symbols[0] ( "ADD" )  symbols[1] ( "AND" )

for optimization, link is the 16-bit index in 'symbols'
or search-array..

From the above flow, I can not understand the details and I can not find any detailed explanation.

For understanding this, I debugged the program gen_lex_hash, but it help nothing, such as:

  1. 0,-1 means what?

Any advice will be appreciated!

Upvotes: 1

Views: 95

Answers (1)

Michael - sqlbot
Michael - sqlbot

Reputation: 178956

This appears to be an implementation of the "trie search" algorithm from The Art of Computer Programming, Vol 3: Sorting and Searching by Donald Knuth, Chapter 6.3 (starting on page 492).

It seems to be used to efficiently identify SQL keywords within a query.

https://dev.mysql.com/doc/internals/en/sql-directory.html

Upvotes: 1

Related Questions