quill_sql/utils/
util.rs

1use crate::buffer::PAGE_SIZE;
2use crate::error::{QuillSQLError, QuillSQLResult};
3use crate::execution::physical_plan::PhysicalPlan;
4use crate::plan::logical_plan::LogicalPlan;
5use crate::storage::index::btree_index::BPlusTreeIndex;
6use comfy_table::Cell;
7use std::collections::VecDeque;
8
9use crate::storage::page::BPlusTreePage;
10use crate::storage::tuple::Tuple;
11
12pub fn pretty_format_tuples(tuples: &Vec<Tuple>) -> comfy_table::Table {
13    let mut table = comfy_table::Table::new();
14    table.load_preset("||--+-++|    ++++++");
15
16    if tuples.is_empty() {
17        return table;
18    }
19
20    let schema = &tuples[0].schema;
21
22    let mut header = Vec::new();
23    for column in schema.columns.iter() {
24        header.push(Cell::new(column.name.clone()));
25    }
26    table.set_header(header);
27
28    for tuple in tuples {
29        let mut cells = Vec::new();
30        for value in tuple.data.iter() {
31            cells.push(Cell::new(format!("{value}")));
32        }
33        table.add_row(cells);
34    }
35
36    table
37}
38
39pub fn pretty_format_logical_plan(plan: &LogicalPlan) -> String {
40    pretty_format_logical_plan_recursively(plan, 0)
41}
42
43fn pretty_format_logical_plan_recursively(plan: &LogicalPlan, indent: usize) -> String {
44    let mut result = format!("{:indent$}{}", "", plan);
45
46    for input in plan.inputs() {
47        result.push('\n');
48        result.push_str(&pretty_format_logical_plan_recursively(input, indent + 2));
49    }
50    result
51}
52
53pub fn pretty_format_physical_plan(plan: &PhysicalPlan) -> String {
54    pretty_format_physical_plan_recursively(plan, 0)
55}
56
57fn pretty_format_physical_plan_recursively(plan: &PhysicalPlan, indent: usize) -> String {
58    let mut result = format!("{:indent$}{}", "", plan);
59
60    for input in plan.inputs() {
61        result.push('\n');
62        result.push_str(&pretty_format_physical_plan_recursively(input, indent + 2));
63    }
64    result
65}
66
67pub fn page_bytes_to_array(bytes: &[u8]) -> [u8; PAGE_SIZE] {
68    let mut data = [0u8; PAGE_SIZE];
69    data.copy_from_slice(bytes);
70    data
71}
72
73pub(crate) fn pretty_format_index_tree(index: &BPlusTreeIndex) -> QuillSQLResult<String> {
74    let mut display = String::new();
75
76    if index.is_empty()? {
77        display.push_str("Empty tree.");
78        return Ok(display);
79    }
80    // 层序遍历
81    let mut curr_queue = VecDeque::new();
82    curr_queue.push_back(index.get_root_page_id()?);
83
84    let mut level_index = 1;
85    loop {
86        if curr_queue.is_empty() {
87            return Ok(display);
88        }
89        let mut next_queue = VecDeque::new();
90
91        // 打印当前层
92        display.push_str(&format!("B+ Tree Level No.{}:\n", level_index));
93
94        let mut level_table = comfy_table::Table::new();
95        level_table.load_preset("||--+-++|    ++++++");
96        let mut level_header = vec![];
97        let mut level_row = vec![];
98
99        while let Some(page_id) = curr_queue.pop_front() {
100            let (_, curr_page) = index
101                .buffer_pool
102                .fetch_tree_page(page_id, index.key_schema.clone())?;
103
104            match curr_page {
105                BPlusTreePage::Internal(internal_page) => {
106                    // build page table
107                    let mut page_table = comfy_table::Table::new();
108                    page_table.load_preset("||--+-++|    ++++++");
109                    let mut page_header = Vec::new();
110                    let mut page_row = Vec::new();
111                    for (tuple, page_id) in internal_page.array.iter() {
112                        page_header.push(Cell::new(
113                            tuple
114                                .data
115                                .iter()
116                                .map(|v| format!("{v}"))
117                                .collect::<Vec<_>>()
118                                .join(", "),
119                        ));
120                        page_row.push(Cell::new(page_id));
121                    }
122                    page_table.set_header(page_header);
123                    page_table.add_row(page_row);
124
125                    level_header.push(Cell::new(format!(
126                        "page_id={}, size: {}/{}",
127                        page_id, internal_page.header.current_size, internal_page.header.max_size
128                    )));
129                    level_row.push(Cell::new(page_table));
130
131                    next_queue.extend(internal_page.values());
132                }
133                BPlusTreePage::Leaf(leaf_page) => {
134                    let mut page_table = comfy_table::Table::new();
135                    page_table.load_preset("||--+-++|    ++++++");
136                    let mut page_header = Vec::new();
137                    let mut page_row = Vec::new();
138                    for (tuple, rid) in leaf_page.array.iter() {
139                        page_header.push(Cell::new(
140                            tuple
141                                .data
142                                .iter()
143                                .map(|v| format!("{v}"))
144                                .collect::<Vec<_>>()
145                                .join(", "),
146                        ));
147                        page_row.push(Cell::new(format!("{}-{}", rid.page_id, rid.slot_num)));
148                    }
149                    page_table.set_header(page_header);
150                    page_table.add_row(page_row);
151
152                    level_header.push(Cell::new(format!(
153                        "page_id={}, size: {}/{}, next_page_id={}",
154                        page_id,
155                        leaf_page.header.current_size,
156                        leaf_page.header.max_size,
157                        leaf_page.header.next_page_id
158                    )));
159                    level_row.push(Cell::new(page_table));
160                }
161            }
162        }
163        level_table.set_header(level_header);
164        level_table.add_row(level_row);
165        display.push_str(&format!("{level_table}\n"));
166
167        level_index += 1;
168        curr_queue = next_queue;
169    }
170}
171
172pub fn time() -> u128 {
173    std::time::SystemTime::now()
174        .duration_since(std::time::UNIX_EPOCH)
175        .unwrap()
176        .as_nanos()
177}
178
179/// Compute the minimal contiguous diff window between two equal-length slices.
180/// Returns Some((start, end)) where [start, end) is the changed window; None if identical.
181pub fn find_contiguous_diff(a: &[u8], b: &[u8]) -> Option<(usize, usize)> {
182    if a.len() != b.len() {
183        return None;
184    }
185    let mut start = 0usize;
186    while start < a.len() && a[start] == b[start] {
187        start += 1;
188    }
189    if start == a.len() {
190        return None;
191    }
192    let mut end = a.len();
193    while end > start && a[end - 1] == b[end - 1] {
194        end -= 1;
195    }
196    Some((start, end))
197}
198
199/// Apply a delta to dst at given offset, returns false if OOB.
200pub fn apply_delta_checked(dst: &mut [u8], offset: usize, data: &[u8]) -> bool {
201    if offset >= dst.len() {
202        return false;
203    }
204    match offset.checked_add(data.len()) {
205        Some(end) if end <= dst.len() => {
206            dst[offset..end].copy_from_slice(data);
207            true
208        }
209        _ => false,
210    }
211}
212
213pub fn extract_id_from_filename(entry: &std::path::PathBuf) -> QuillSQLResult<u128> {
214    entry
215        .extension()
216        .ok_or_else(|| {
217            QuillSQLError::Internal(format!("Missing extension (ie. not in format: data.<id>)"))
218        })?
219        .to_str()
220        .ok_or_else(|| {
221            QuillSQLError::Internal("Failed to convert extension to string".to_string())
222        })?
223        .parse::<u128>()
224        .map_err(|e| QuillSQLError::Internal(format!("Failed to parse id: {}", e)))
225}
quill_sql/utils/util.rs

quill_sql/utils/
util.rs
