查询处理 第16课 / 共25课
查询处理是数据库从接收SQL到返回结果的全过程。本课聚焦前两个阶段：SQL解析(词法分析→语法分析→语义分析)和查询计划生成。我们将实现一个完整的SQL解析器，将SQL文本转换为结构化的查询计划树。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_TOKENS 64
#define MAX_TOKEN_LEN 64
#define MAX_COLS 16
#define MAX_TABLES 8
// Token类型
typedef enum {
TOK_SELECT, TOK_FROM, TOK_WHERE, TOK_INSERT, TOK_INTO,
TOK_VALUES, TOK_UPDATE, TOK_SET, TOK_DELETE, TOK_AND,
TOK_OR, TOK_NOT, TOK_ORDER, TOK_BY, TOK_ASC, TOK_DESC,
TOK_GROUP, TOK_HAVING, TOK_JOIN, TOK_ON, TOK_LEFT, TOK_RIGHT,
TOK_INNER, TOK_LIMIT, TOK_OFFSET, TOK_CREATE, TOK_TABLE,
TOK_DROP, TOK_INDEX, TOK_IDENT, TOK_INTEGER, TOK_STRING,
TOK_COMMA, TOK_DOT, TOK_SEMICOLON, TOK_LPAREN, TOK_RPAREN,
TOK_EQ, TOK_NEQ, TOK_LT, TOK_GT, TOK_LE, TOK_GE,
TOK_PLUS, TOK_MINUS, TOK_STAR, TOK_EOF, TOK_UNKNOWN
} TokenType;
const char* token_type_str[] = {
"SELECT","FROM","WHERE","INSERT","INTO","VALUES","UPDATE","SET",
"DELETE","AND","OR","NOT","ORDER","BY","ASC","DESC","GROUP",
"HAVING","JOIN","ON","LEFT","RIGHT","INNER","LIMIT","OFFSET",
"CREATE","TABLE","DROP","INDEX","IDENT","INTEGER","STRING",
"COMMA","DOT","SEMI","LPAREN","RPAREN",
"EQ","NEQ","LT","GT","LE","GE","PLUS","MINUS","STAR","EOF","UNK"
};
typedef struct {
TokenType type;
char value[MAX_TOKEN_LEN];
} Token;
typedef struct {
Token tokens[MAX_TOKENS];
int count;
int pos;
} TokenStream;
// 词法分析器
int is_keyword(const char* word) {
const char* keywords[] = {"SELECT","FROM","WHERE","INSERT","INTO","VALUES",
"UPDATE","SET","DELETE","AND","OR","NOT","ORDER","BY","ASC","DESC",
"GROUP","HAVING","JOIN","ON","LEFT","RIGHT","INNER","LIMIT","OFFSET",
"CREATE","TABLE","DROP","INDEX",NULL};
for (int i = 0; keywords[i]; i++) {
if (strcasecmp(word, keywords[i]) == 0) return i;
}
return -1;
}
TokenType keyword_to_type(const char* word) {
if (strcasecmp(word,"SELECT")==0) return TOK_SELECT;
if (strcasecmp(word,"FROM")==0) return TOK_FROM;
if (strcasecmp(word,"WHERE")==0) return TOK_WHERE;
if (strcasecmp(word,"INSERT")==0) return TOK_INSERT;
if (strcasecmp(word,"INTO")==0) return TOK_INTO;
if (strcasecmp(word,"VALUES")==0) return TOK_VALUES;
if (strcasecmp(word,"UPDATE")==0) return TOK_UPDATE;
if (strcasecmp(word,"SET")==0) return TOK_SET;
if (strcasecmp(word,"DELETE")==0) return TOK_DELETE;
if (strcasecmp(word,"AND")==0) return TOK_AND;
if (strcasecmp(word,"OR")==0) return TOK_OR;
if (strcasecmp(word,"NOT")==0) return TOK_NOT;
if (strcasecmp(word,"ORDER")==0) return TOK_ORDER;
if (strcasecmp(word,"BY")==0) return TOK_BY;
if (strcasecmp(word,"ASC")==0) return TOK_ASC;
if (strcasecmp(word,"DESC")==0) return TOK_DESC;
if (strcasecmp(word,"GROUP")==0) return TOK_GROUP;
if (strcasecmp(word,"JOIN")==0) return TOK_JOIN;
if (strcasecmp(word,"ON")==0) return TOK_ON;
if (strcasecmp(word,"LIMIT")==0) return TOK_LIMIT;
if (strcasecmp(word,"CREATE")==0) return TOK_CREATE;
if (strcasecmp(word,"TABLE")==0) return TOK_TABLE;
return TOK_UNKNOWN;
}
TokenStream tokenize(const char* sql) {
TokenStream ts = {.count = 0, .pos = 0};
const char* p = sql;
while (*p && ts.count < MAX_TOKENS) {
while (*p && isspace(*p)) p++;
if (!*p) break;
Token* t = &ts.tokens[ts.count];
if (isalpha(*p) || *p == '_') {
int i = 0;
while (*p && (isalnum(*p) || *p == '_') && i < MAX_TOKEN_LEN - 1)
t->value[i++] = *p++;
t->value[i] = '\0';
int ki = is_keyword(t->value);
t->type = (ki >= 0) ? keyword_to_type(t->value) : TOK_IDENT;
} else if (isdigit(*p)) {
int i = 0;
while (*p && isdigit(*p) && i < MAX_TOKEN_LEN - 1)
t->value[i++] = *p++;
t->value[i] = '\0';
t->type = TOK_INTEGER;
} else if (*p == '\'') {
p++;
int i = 0;
while (*p && *p != '\'' && i < MAX_TOKEN_LEN - 1)
t->value[i++] = *p++;
if (*p == '\'') p++;
t->value[i] = '\0';
t->type = TOK_STRING;
} else {
t->value[0] = *p; t->value[1] = '\0';
switch (*p) {
case ',': t->type = TOK_COMMA; break;
case '.': t->type = TOK_DOT; break;
case ';': t->type = TOK_SEMICOLON; break;
case '(': t->type = TOK_LPAREN; break;
case ')': t->type = TOK_RPAREN; break;
case '=': t->type = TOK_EQ; break;
case '+': t->type = TOK_PLUS; break;
case '-': t->type = TOK_MINUS; break;
case '*': t->type = TOK_STAR; break;
case '<': p++;
if (*p == '=') { t->type = TOK_LE; t->value[1] = '='; t->value[2] = '\0'; p++; }
else if (*p == '>') { t->type = TOK_NEQ; t->value[1] = '>'; t->value[2] = '\0'; p++; }
else { t->type = TOK_LT; }
break;
case '>': p++;
if (*p == '=') { t->type = TOK_GE; t->value[1] = '='; t->value[2] = '\0'; p++; }
else { t->type = TOK_GT; }
break;
default: t->type = TOK_UNKNOWN; break;
}
if (t->type != TOK_LT && t->type != TOK_GT && t->type != TOK_NEQ
&& t->type != TOK_LE && t->type != TOK_GE) p++;
}
ts.count++;
}
ts.tokens[ts.count].type = TOK_EOF;
return ts;
}
// AST节点类型
typedef enum {
NODE_SELECT, NODE_INSERT, NODE_UPDATE, NODE_DELETE,
NODE_COLUMN, NODE_TABLE, NODE_COMPARE, NODE_AND_EXPR,
NODE_OR_EXPR, NODE_VALUE, NODE_ORDER_BY
} NodeType;
typedef struct ASTNode ASTNode;
struct ASTNode {
NodeType type;
char value[MAX_TOKEN_LEN];
ASTNode* left;
ASTNode* right;
ASTNode* children[8];
int num_children;
};
ASTNode* ast_create(NodeType type, const char* value) {
ASTNode* n = calloc(1, sizeof(ASTNode));
n->type = type;
if (value) strncpy(n->value, value, MAX_TOKEN_LEN - 1);
return n;
}
// 递归下降解析器
Token* peek(TokenStream* ts) { return &ts->tokens[ts->pos]; }
Token* advance(TokenStream* ts) { return &ts->tokens[ts->pos++]; }
int match(TokenStream* ts, TokenType type) {
if (peek(ts)->type == type) { advance(ts); return 1; }
return 0;
}
ASTNode* parse_expression(TokenStream* ts);
ASTNode* parse_and_expr(TokenStream* ts);
ASTNode* parse_primary(TokenStream* ts) {
Token* t = peek(ts);
if (t->type == TOK_IDENT) {
advance(ts);
return ast_create(NODE_COLUMN, t->value);
} else if (t->type == TOK_INTEGER) {
advance(ts);
return ast_create(NODE_VALUE, t->value);
} else if (t->type == TOK_STRING) {
advance(ts);
return ast_create(NODE_VALUE, t->value);
} else if (t->type == TOK_LPAREN) {
advance(ts);
ASTNode* expr = parse_expression(ts);
match(ts, TOK_RPAREN);
return expr;
}
return NULL;
}
ASTNode* parse_comparison(TokenStream* ts) {
ASTNode* left = parse_primary(ts);
if (!left) return NULL;
Token* op = peek(ts);
if (op->type >= TOK_EQ && op->type <= TOK_GE) {
advance(ts);
ASTNode* node = ast_create(NODE_COMPARE, op->value);
node->left = left;
node->right = parse_primary(ts);
return node;
}
return left;
}
ASTNode* parse_and_expr(TokenStream* ts) {
ASTNode* left = parse_comparison(ts);
while (peek(ts)->type == TOK_AND) {
advance(ts);
ASTNode* node = ast_create(NODE_AND_EXPR, "AND");
node->left = left;
node->right = parse_comparison(ts);
left = node;
}
return left;
}
ASTNode* parse_expression(TokenStream* ts) {
ASTNode* left = parse_and_expr(ts);
while (peek(ts)->type == TOK_OR) {
advance(ts);
ASTNode* node = ast_create(NODE_OR_EXPR, "OR");
node->left = left;
node->right = parse_and_expr(ts);
left = node;
}
return left;
}
ASTNode* parse_select(TokenStream* ts) {
ASTNode* select = ast_create(NODE_SELECT, "SELECT");
// 列列表
while (peek(ts)->type == TOK_IDENT || peek(ts)->type == TOK_STAR) {
Token* col = advance(ts);
select->children[select->num_children++] = ast_create(NODE_COLUMN, col->value);
if (peek(ts)->type == TOK_COMMA) advance(ts);
else break;
}
// FROM
if (!match(ts, TOK_FROM)) { printf(" 语法错误: 缺少FROM\n"); return select; }
Token* table = advance(ts);
select->children[select->num_children++] = ast_create(NODE_TABLE, table->value);
// WHERE
if (match(ts, TOK_WHERE)) {
select->children[select->num_children++] = parse_expression(ts);
}
// ORDER BY
if (match(ts, TOK_ORDER) && match(ts, TOK_BY)) {
Token* col = advance(ts);
ASTNode* order = ast_create(NODE_ORDER_BY, col->value);
if (peek(ts)->type == TOK_ASC) { advance(ts); }
else if (peek(ts)->type == TOK_DESC) { advance(ts); }
select->children[select->num_children++] = order;
}
// LIMIT
if (match(ts, TOK_LIMIT)) {
Token* lim = advance(ts);
// 简化: 存到select节点的value
}
return select;
}
ASTNode* parse(TokenStream* ts) {
Token* t = peek(ts);
if (t->type == TOK_SELECT) { advance(ts); return parse_select(ts); }
printf(" 不支持的SQL类型\n");
return NULL;
}
// 打印AST
void print_ast(ASTNode* node, int depth) {
if (!node) return;
const char* type_str[] = {"SELECT","INSERT","UPDATE","DELETE",
"COLUMN","TABLE","COMPARE","AND","OR","VALUE","ORDER_BY"};
printf("%*s[%s] %s\n", depth*2, "", type_str[node->type],
node->value[0] ? node->value : "");
if (node->left) print_ast(node->left, depth + 1);
if (node->right) print_ast(node->right, depth + 1);
for (int i = 0; i < node->num_children; i++)
print_ast(node->children[i], depth + 1);
}
int main() {
printf("╔══════════════════════════════════════╗\n");
printf("║ SQL解析器 ║\n");
printf("╚══════════════════════════════════════╝\n\n");
const char* sqls[] = {
"SELECT name, age FROM users WHERE age > 20 ORDER BY age",
"SELECT * FROM products WHERE price >= 100 AND category = 'electronics'",
"SELECT id, name FROM orders WHERE status = 'pending' OR priority > 5"
};
for (int i = 0; i < 3; i++) {
printf("--- SQL: %s ---\n", sqls[i]);
TokenStream ts = tokenize(sqls[i]);
printf("Tokens: ");
for (int j = 0; j < ts.count; j++)
printf("%s ", token_type_str[ts.tokens[j].type]);
printf("\n");
ts.pos = 0;
ASTNode* ast = parse(&ts);
if (ast) {
printf("AST:\n");
print_ast(ast, 0);
}
printf("\n");
}
printf("✅ SQL解析器运行完成\n");
return 0;
}
"""
完整的SQL解析与执行引擎
支持: SELECT, INSERT, UPDATE, DELETE
"""
import re
from dataclasses import dataclass, field
from typing import List, Optional, Dict, Any, Tuple
# ===== 词法分析 =====
@dataclass
class Token:
type: str
value: str
KEYWORDS = {"SELECT","FROM","WHERE","INSERT","INTO","VALUES","UPDATE","SET",
"DELETE","AND","OR","NOT","ORDER","BY","ASC","DESC","LIMIT",
"CREATE","TABLE","DROP","INDEX","JOIN","ON","LEFT","RIGHT","INNER",
"GROUP","HAVING","AS","DISTINCT","NULL","IS","IN","BETWEEN","LIKE","COUNT","SUM","AVG","MIN","MAX"}
def tokenize(sql: str) -> List[Token]:
tokens = []
i = 0
while i < len(sql):
if sql[i].isspace(): i += 1; continue
if sql[i:i+2] in ("<=", ">=", "<>", "!="):
op = sql[i:i+2]
tokens.append(Token("OP", "<>" if op == "!=" else op))
i += 2; continue
if sql[i] in "<>=<>!":
tokens.append(Token("OP", sql[i]))
i += 1; continue
if sql[i] in "(),;.*+-/":
tokens.append(Token(sql[i], sql[i]))
i += 1; continue
if sql[i] == "'":
j = i + 1
while j < len(sql) and sql[j] != "'": j += 1
tokens.append(Token("STRING", sql[i+1:j]))
i = j + 1; continue
if sql[i].isdigit():
j = i
while j < len(sql) and (sql[j].isdigit() or sql[j] == '.'): j += 1
tokens.append(Token("NUMBER", sql[i:j]))
i = j; continue
if sql[i].isalpha() or sql[i] == '_':
j = i
while j < len(sql) and (sql[j].isalnum() or sql[j] == '_'): j += 1
word = sql[i:j]
if word.upper() in KEYWORDS:
tokens.append(Token(word.upper(), word.upper()))
else:
tokens.append(Token("IDENT", word))
i = j; continue
i += 1
tokens.append(Token("EOF", ""))
return tokens
# ===== AST节点 =====
@dataclass
class Expr:
pass
@dataclass
class Column(Expr):
name: str
table: Optional[str] = None
@dataclass
class Literal(Expr):
value: Any
@dataclass
class BinaryOp(Expr):
op: str
left: Expr
right: Expr
@dataclass
class SelectStmt:
columns: List[Expr]
table: str
where: Optional[Expr] = None
order_by: Optional[Tuple[str, str]] = None
limit: Optional[int] = None
@dataclass
class InsertStmt:
table: str
columns: List[str]
values: List[Any]
@dataclass
class UpdateStmt:
table: str
assignments: List[Tuple[str, Any]]
where: Optional[Expr] = None
@dataclass
class DeleteStmt:
table: str
where: Optional[Expr] = None
# ===== 解析器 =====
class Parser:
def __init__(self, tokens: List[Token]):
self.tokens = tokens
self.pos = 0
def peek(self) -> Token: return self.tokens[self.pos]
def advance(self) -> Token: t = self.tokens[self.pos]; self.pos += 1; return t
def match(self, type_: str) -> bool:
if self.peek().type == type_: self.advance(); return True
return False
def parse(self):
t = self.peek()
if t.type == "SELECT": return self.parse_select()
if t.type == "INSERT": return self.parse_insert()
if t.type == "UPDATE": return self.parse_update()
if t.type == "DELETE": return self.parse_delete()
raise SyntaxError(f"Unknown statement: {t.type}")
def parse_select(self) -> SelectStmt:
self.match("SELECT")
columns = self.parse_column_list()
self.match("FROM")
table = self.advance().value
where = None
if self.match("WHERE"):
where = self.parse_expression()
order_by = None
if self.match("ORDER"):
self.match("BY")
col = self.advance().value
direction = "ASC"
if self.match("DESC"): direction = "DESC"
elif self.match("ASC"): pass
order_by = (col, direction)
limit = None
if self.match("LIMIT"):
limit = int(self.advance().value)
return SelectStmt(columns, table, where, order_by, limit)
def parse_insert(self) -> InsertStmt:
self.match("INSERT"); self.match("INTO")
table = self.advance().value
cols = []
if self.match("("):
cols = [t.value for t in self.parse_ident_list()]
self.match(")")
self.match("VALUES"); self.match("(")
vals = self.parse_value_list()
self.match(")")
return InsertStmt(table, cols, vals)
def parse_update(self) -> UpdateStmt:
self.match("UPDATE")
table = self.advance().value
self.match("SET")
assignments = self.parse_assignments()
where = None
if self.match("WHERE"): where = self.parse_expression()
return UpdateStmt(table, assignments, where)
def parse_delete(self) -> DeleteStmt:
self.match("DELETE"); self.match("FROM")
table = self.advance().value
where = None
if self.match("WHERE"): where = self.parse_expression()
return DeleteStmt(table, where)
def parse_column_list(self) -> List[Expr]:
if self.match("*"): return [Column("*")]
cols = [Column(self.advance().value)]
while self.match(","):
cols.append(Column(self.advance().value))
return cols
def parse_ident_list(self) -> List[Token]:
idents = [self.advance()]
while self.match(","): idents.append(self.advance())
return idents
def parse_value_list(self) -> List[Any]:
vals = [self.parse_literal()]
while self.match(","): vals.append(self.parse_literal())
return vals
def parse_literal(self):
t = self.advance()
if t.type == "NUMBER": return float(t.value) if '.' in t.value else int(t.value)
if t.type == "STRING": return t.value
if t.type == "NULL": return None
raise SyntaxError(f"Expected value, got {t.type}")
def parse_assignments(self):
asgn = []
while True:
col = self.advance().value
self.match("OP") # =
val = self.parse_literal()
asgn.append((col, val))
if not self.match(","): break
return asgn
def parse_expression(self) -> Expr:
return self.parse_or()
def parse_or(self) -> Expr:
left = self.parse_and()
while self.peek().type == "OR":
self.advance()
left = BinaryOp("OR", left, self.parse_and())
return left
def parse_and(self) -> Expr:
left = self.parse_comparison()
while self.peek().type == "AND":
self.advance()
left = BinaryOp("AND", left, self.parse_comparison())
return left
def parse_comparison(self) -> Expr:
left = self.parse_primary()
if self.peek().type == "OP":
op = self.advance().value
right = self.parse_primary()
return BinaryOp(op, left, right)
return left
def parse_primary(self) -> Expr:
t = self.peek()
if t.type == "IDENT": self.advance(); return Column(t.value)
if t.type == "NUMBER": self.advance(); return Literal(int(t.value) if '.' not in t.value else float(t.value))
if t.type == "STRING": self.advance(); return Literal(t.value)
if t.type == "NULL": self.advance(); return Literal(None)
if self.match("("):
expr = self.parse_expression()
self.match(")")
return expr
raise SyntaxError(f"Unexpected: {t.type} {t.value}")
# ===== 简易执行引擎 =====
class Database:
def __init__(self):
self.tables: Dict[str, List[Dict]] = {}
def execute(self, sql: str) -> List[Dict]:
tokens = tokenize(sql)
parser = Parser(tokens)
stmt = parser.parse()
if isinstance(stmt, SelectStmt):
return self._exec_select(stmt)
elif isinstance(stmt, InsertStmt):
return self._exec_insert(stmt)
elif isinstance(stmt, UpdateStmt):
return self._exec_update(stmt)
elif isinstance(stmt, DeleteStmt):
return self._exec_delete(stmt)
return []
def _exec_select(self, stmt: SelectStmt) -> List[Dict]:
rows = self.tables.get(stmt.table, [])
if stmt.where:
rows = [r for r in rows if self._eval(stmt.where, r)]
if stmt.order_by:
col, direction = stmt.order_by
rows = sorted(rows, key=lambda r: r.get(col, 0), reverse=(direction == "DESC"))
if stmt.limit:
rows = rows[:stmt.limit]
if any(c.name == "*" for c in stmt.columns):
return rows
cols = [c.name for c in stmt.columns]
return [{c: r.get(c) for c in cols} for r in rows]
def _exec_insert(self, stmt: InsertStmt) -> List[Dict]:
if stmt.table not in self.tables:
self.tables[stmt.table] = []
row = dict(zip(stmt.columns, stmt.values)) if stmt.columns else {}
self.tables[stmt.table].append(row)
return [{"affected": 1}]
def _exec_update(self, stmt: UpdateStmt) -> List[Dict]:
rows = self.tables.get(stmt.table, [])
count = 0
for r in rows:
if stmt.where is None or self._eval(stmt.where, r):
for col, val in stmt.assignments:
r[col] = val
count += 1
return [{"affected": count}]
def _exec_delete(self, stmt: DeleteStmt) -> List[Dict]:
if stmt.table not in self.tables: return [{"affected": 0}]
before = len(self.tables[stmt.table])
self.tables[stmt.table] = [r for r in self.tables[stmt.table]
if stmt.where is None or not self._eval(stmt.where, r)]
return [{"affected": before - len(self.tables[stmt.table])}]
def _eval(self, expr: Expr, row: Dict) -> bool:
if isinstance(expr, BinaryOp):
left = self._eval_expr(expr.left, row)
right = self._eval_expr(expr.right, row)
if expr.op == "AND": return left and right
if expr.op == "OR": return left or right
if expr.op == "=": return left == right
if expr.op in ("<>", "!="): return left != right
if expr.op == "<": return left < right
if expr.op == ">": return left > right
if expr.op == "<=": return left <= right
if expr.op == ">=": return left >= right
return bool(self._eval_expr(expr, row))
def _eval_expr(self, expr: Expr, row: Dict):
if isinstance(expr, Column): return row.get(expr.name)
if isinstance(expr, Literal): return expr.value
if isinstance(expr, BinaryOp):
if expr.op in ("AND", "OR"): return self._eval(expr, row)
return self._eval_expr(expr.left, row)
return None
# 测试
db = Database()
db.execute("INSERT INTO users (name, age, city) VALUES (Alice, 30, Beijing)")
db.execute("INSERT INTO users (name, age, city) VALUES (Bob, 25, Shanghai)")
db.execute("INSERT INTO users (name, age, city) VALUES (Charlie, 35, Shenzhen)")
db.execute("INSERT INTO users (name, age, city) VALUES (Diana, 28, Hangzhou)")
db.execute("INSERT INTO users (name, age, city) VALUES (Eve, 32, Beijing)")
print("=== SELECT * FROM users ===")
for r in db.execute("SELECT * FROM users"): print(f" {r}")
print("\n=== SELECT name, age FROM users WHERE age > 28 ===")
for r in db.execute("SELECT name, age FROM users WHERE age > 28"): print(f" {r}")
print("\n=== SELECT name FROM users WHERE city = Beijing ORDER BY age DESC ===")
for r in db.execute("SELECT name FROM users WHERE city = Beijing ORDER BY age DESC"): print(f" {r}")
print("\n=== UPDATE users SET age = 31 WHERE name = Alice ===")
print(db.execute("UPDATE users SET age = 31 WHERE name = Alice"))
print("\n=== DELETE FROM users WHERE age < 30 ===")
print(db.execute("DELETE FROM users WHERE age < 30"))
print("\n=== SELECT * FROM users ===")
for r in db.execute("SELECT * FROM users"): print(f" {r}")
print("\n✅ SQL引擎运行完成")
掌握SQL解析与计划生成，你已理解查询处理的前端流水线！
✅ 词法分析 · ✅ 语法分析 · ✅ AST生成 · ✅ 逻辑计划