自己实现一个SQL解析引擎(二)

NODEKIND枚举了所有可能出现的节点类型.其定义为

typedef enum NODEKIND{
    N_MIN,
    /* const node*/
    N_INT,    //int or long
    N_FLOAT,  //float
    N_STRING, //string
    N_BOOL,   //true or false or unknown
    N_NULL,   //null
    /* var node*/
    N_COLUMN, // colunm name
    //其他类型
    /*stmt node*/    
    N_SELECT,
    N_INSERT,
    N_REPLACE,
    N_DELETE,
    N_UPDATE,
    //其他类型
    N_MAX
} NODEKIND;

在语法树中，分析树的叶子节点为数字，字符串，属性等，其他为内部节点。因此有些数据库的实现中将语法树的节点定义为如下的ParseNode结构。

typedef struct _ParseNode
{
  ObItemType   type_;//节点的类型，如T_STRING,T_SELECT等

  /* 终止符节点，具有实际的值 */
  int64_t      value_;
  const char*  str_value_;

  /* 非终止符节点，拥有多个孩子 */
  int32_t      num_child_;//子节点的个数
  struct _ParseNode** children_;//子节点指针链

} ParseNode;

逻辑计划结构

逻辑计划的内部节点是算子，叶子节点是关系.

typedef struct plannode{

    PLANNODEKIND kind;

    union{
        /*stmt node*/
        struct {
            struct plannode *plan;
        }SELECT;

        /*op node*/
        struct {
            struct plannode *rel;
            struct plannode *filters; //list of filter
        }SCAN;
        struct {
            struct plannode *rel;
            NODE *expr_filter; //list of compare expr
        }FILTER;
        struct {
            struct plannode *rel;
            NODE *select_list;    
        }PROJECTION;
        struct {
            struct plannode *left;
            struct plannode *right;
        }JOIN;
        /*leaf node*/
        struct {
            NODE *table;
        }FILESCAN;
        //其他类型节点    
    }u;
}PLANNODE;

逻辑计划节点的类型PLANNODEKIND的枚举值如下：

typedef enum PLANNODEKIND{
    /*stmt node tags*/
    PLAN_SELECT,
    PLAN_INSERT,
    PLAN_DELETE,
    PLAN_UPDATE,
    PLAN_REPLACE,
    /*op node tags*/
    PLAN_FILESCAN, /* Relation     关系，叶子节点 */
    PLAN_SCAN,       
    PLAN_FILTER,   /* Selection  选择   */
    PLAN_PROJ,     /* Projection 投影*/
    PLAN_JOIN,     /* Join       连接 ，指等值连接*/
    PLAN_DIST,     /* Duplicate elimination( Distinct) 消除重复*/
    PLAN_GROUP,    /* Grouping   分组(包含了聚集)*/
    PLAN_SORT,     /* Sorting    排序*/
    PLAN_LIMIT,
    /*support node tags*/
    PLAN_LIST    
}PLANNODEKIND;

物理计划结构

物理逻辑计划中关系扫描运算符为叶子节点，其他运算符为内部节点。拥有3个迭代器函数open,close,get_next_row。其定义如下：

typedef int (*IntFun)(PhyOperator *);
typedef int (*RowFun)(Row &row,PhyOperator *);
struct phyoperator{
    PHYOPNODEKIND kind;

    IntFun open;
    IntFun close;
    RowFun get_next_row;//迭代函数

    union{
        struct {
            struct phyoperator *inner;
            struct phyoperator *outter;
            Row one_row;
        }NESTLOOPJOIN;
        struct {
            struct phyoperator *inner;
            struct phyoperator *outter;
        }HASHJOIN;
        struct {
            struct phyoperator *inner;
        }TABLESCAN;
        struct {
            struct phyoperator *inner;
            NODE * expr_filters;
        }INDEXSCAN;
        //其他类型的节点
    }u;
}PhyOperator;

物理查询计划的节点类型PHYOPNODEKIND枚举如下：

typedef enum PHYOPNODEKIND{
    /*stmt node tags*/
    PHY_SELECT,
    PHY_INSERT,
    PHY_DELETE,
    PHY_UPDATE,
    PHY_REPLACE,
    /*phyoperator node tags*/
    PHY_TABLESCAN,
    PHY_INDEXSCAN,
    PHY_FILESCAN,
    PHY_NESTLOOPJOIN,
    PHY_HASHJOIN,
    PHY_FILTER,
    PHY_SORT,
    PHY_DIST,
    PHY_GROUP,
    PHY_PROJECTION,
    PHY_LIMIT
}PHYOPNODEKIND;

节点内存池

可以看到分析树，逻辑计划树和物理查询树都是以指针为主的结构体，如果每次都动态从申请的话，会比较耗时。需要使用内存池的方式，一次性申请多个节点内存，供以后调用。下面是一种简单的方式，每次创建节点时都使用newnode函数即可。程序结束时再释放内存池即可。

static NODE *nodepool = NULL;
static int MAXNODE = 256;
static int nodeptr = 0;

NODE *newnode(NODEKIND kind)
{
    //首次使用时申请MAXNODE个节点
    if(nodepool == NULL){
        nodepool = (NODE *)malloc(sizeof(NODE)*MAXNODE);
        assert(nodepool);
    }

    assert(nodeptr <= MAXNODE);
    //当节点个数等于MAXNODE时realloc扩展为原来的两倍节点
    if (nodeptr == MAXNODE){
        MAXNODE *= 2;
        NODE *newpool = 
(NODE *)realloc(nodepool,sizeof(NODE)*MAXNODE) ; 
        assert(newpool);
        nodepool = newpool;
    }

    NODE *n = nodepool + nodeptr;
    n->kind = kind ;
    ++nodeptr;

    return n;