Bug #30333 Performance, expressions lists in the parser
Submitted: 9 Aug 2007 14:47 Modified: 9 Oct 2007 17:01
Reporter: Marc ALFF Email Updates:
Status: Closed Impact on me:
None 
Category:MySQL Server: Parser Severity:S5 (Performance)
Version:4.0, 4.1, 5.0, 5.1 OS:Any
Assigned to: Marc ALFF CPU Architecture:Any

[9 Aug 2007 14:47] Marc ALFF
Description:
This bug is reported as a finding related to Bug#29921

In sql/sql_yacc.yy, the implementation of the following rules:
- udf_expr_list
- expr_list
- ident_list
uses Select->expr_list to maintain manually a stack,
instead of using the bison internal stack ($$).

This is inefficient, as the calls to Select->expr_list push/pop
are slower, due to memory allocation.

Found by code review, verified in 4.0, 4.1, 5.0, 5.1

How to repeat:
Code review

Suggested fix:
Do not use Select->expr_list,
use the bison stack instead.
[9 Aug 2007 18:27] Bugs System
A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/32326

ChangeSet@1.2512, 2007-08-09 12:25:48-06:00, malff@weblab.(none) +1 -0
  Bug#30333 (Performance, expressions lists in the parser)
  
  Before this patch, the parser would execute:
  - Select->expr_list.push_front()
  - Select->expr_list.pop()
  when parsing expressions lists, in the following rules:
  - udf_expr_list
  - expr_list
  - ident_list
  
  This is unnecessary, and introduces overhead due to the memory allocations
  performed with Select->expr_list
  
  With this patch, this code has been removed.
  The list being parsed is maintained in the parser stack instead.
  
  Also, 'udf_expr_list' has been renamed 'opt_udf_expr_list', since this
  production can be empty.
  
  Simplification of the grammar around these lists also reduced the
  parser complexity:
  
  /* YYLAST -- Last index in YYTABLE.  */
  #define YYLAST   43481 --> 43048 [-433]
  /* YYNTOKENS -- Number of terminals.  */
  #define YYNTOKENS  570 --> 570 [0]
  /* YYNNTS -- Number of nonterminals.  */
  #define YYNNTS  674 --> 668 [-6]
  /* YYNRULES -- Number of rules.  */
  #define YYNRULES  2026 --> 2020 [-6]
  /* YYNRULES -- Number of states.  */
  #define YYNSTATES  3672 --> 3666 [-6]
[22 Aug 2007 16:35] Konstantin Osipov
Approved over email.
[22 Aug 2007 21:38] Bugs System
A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/32925

ChangeSet@1.2572, 2007-08-22 15:38:32-06:00, malff@weblab.(none) +3 -0
  Bug#30333 (Performance, expressions lists in the parser)
  
  Before this patch, the parser would execute:
  - Select->expr_list.push_front()
  - Select->expr_list.pop()
  when parsing expressions lists, in the following rules:
  - udf_expr_list
  - expr_list
  - ident_list
  
  This is unnecessary, and introduces overhead due to the memory allocations
  performed with Select->expr_list
  
  With this patch, this code has been removed.
  The list being parsed is maintained in the parser stack instead.
  
  Also, 'udf_expr_list' has been renamed 'opt_udf_expr_list', since this
  production can be empty.
[7 Sep 2007 8:09] Bugs System
Pushed into 5.1.23-beta
[9 Oct 2007 17:01] Paul DuBois
Noted in 5.1.23 changelog.

Server parser performance was improved for identifier lists,
expression lists, and UDF expression lists.