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
73#[allow(dead_code)]
74pub(crate) fn pretty_format_index_tree(index: &BPlusTreeIndex) -> QuillSQLResult<String> {
75    let mut display = String::new();
76
77    if index.is_empty()? {
78        display.push_str("Empty tree.");
79        return Ok(display);
80    }
81    // 层序遍历
82    let mut curr_queue = VecDeque::new();
83    curr_queue.push_back(index.get_root_page_id()?);
84
85    let mut level_index = 1;
86    loop {
87        if curr_queue.is_empty() {
88            return Ok(display);
89        }
90        let mut next_queue = VecDeque::new();
91
92        // 打印当前层
93        display.push_str(&format!("B+ Tree Level No.{}:\n", level_index));
94
95        let mut level_table = comfy_table::Table::new();
96        level_table.load_preset("||--+-++|    ++++++");
97        let mut level_header = vec![];
98        let mut level_row = vec![];
99
100        while let Some(page_id) = curr_queue.pop_front() {
101            let (_, curr_page) = index
102                .buffer_pool
103                .fetch_tree_page(page_id, index.key_schema.clone())?;
104
105            match curr_page {
106                BPlusTreePage::Internal(internal_page) => {
107                    // build page table
108                    let mut page_table = comfy_table::Table::new();
109                    page_table.load_preset("||--+-++|    ++++++");
110                    let mut page_header = Vec::new();
111                    let mut page_row = Vec::new();
112                    for (tuple, page_id) in internal_page.array.iter() {
113                        page_header.push(Cell::new(
114                            tuple
115                                .data
116                                .iter()
117                                .map(|v| format!("{v}"))
118                                .collect::<Vec<_>>()
119                                .join(", "),
120                        ));
121                        page_row.push(Cell::new(page_id));
122                    }
123                    page_table.set_header(page_header);
124                    page_table.add_row(page_row);
125
126                    level_header.push(Cell::new(format!(
127                        "page_id={}, size: {}/{}",
128                        page_id, internal_page.header.current_size, internal_page.header.max_size
129                    )));
130                    level_row.push(Cell::new(page_table));
131
132                    next_queue.extend(internal_page.values());
133                }
134                BPlusTreePage::Leaf(leaf_page) => {
135                    let mut page_table = comfy_table::Table::new();
136                    page_table.load_preset("||--+-++|    ++++++");
137                    let mut page_header = Vec::new();
138                    let mut page_row = Vec::new();
139                    for (tuple, rid) in leaf_page.array.iter() {
140                        page_header.push(Cell::new(
141                            tuple
142                                .data
143                                .iter()
144                                .map(|v| format!("{v}"))
145                                .collect::<Vec<_>>()
146                                .join(", "),
147                        ));
148                        page_row.push(Cell::new(format!("{}-{}", rid.page_id, rid.slot_num)));
149                    }
150                    page_table.set_header(page_header);
151                    page_table.add_row(page_row);
152
153                    level_header.push(Cell::new(format!(
154                        "page_id={}, size: {}/{}, next_page_id={}",
155                        page_id,
156                        leaf_page.header.current_size,
157                        leaf_page.header.max_size,
158                        leaf_page.header.next_page_id
159                    )));
160                    level_row.push(Cell::new(page_table));
161                }
162            }
163        }
164        level_table.set_header(level_header);
165        level_table.add_row(level_row);
166        display.push_str(&format!("{level_table}\n"));
167
168        level_index += 1;
169        curr_queue = next_queue;
170    }
171}
172
173pub fn time() -> u128 {
174    std::time::SystemTime::now()
175        .duration_since(std::time::UNIX_EPOCH)
176        .unwrap()
177        .as_nanos()
178}
179
180/// Compute the minimal contiguous diff window between two equal-length slices.
181/// Returns Some((start, end)) where [start, end) is the changed window; None if identical.
182pub fn find_contiguous_diff(a: &[u8], b: &[u8]) -> Option<(usize, usize)> {
183    if a.len() != b.len() {
184        return None;
185    }
186    let mut start = 0usize;
187    while start < a.len() && a[start] == b[start] {
188        start += 1;
189    }
190    if start == a.len() {
191        return None;
192    }
193    let mut end = a.len();
194    while end > start && a[end - 1] == b[end - 1] {
195        end -= 1;
196    }
197    Some((start, end))
198}
199
200/// Apply a delta to dst at given offset, returns false if OOB.
201pub fn apply_delta_checked(dst: &mut [u8], offset: usize, data: &[u8]) -> bool {
202    if offset >= dst.len() {
203        return false;
204    }
205    match offset.checked_add(data.len()) {
206        Some(end) if end <= dst.len() => {
207            dst[offset..end].copy_from_slice(data);
208            true
209        }
210        _ => false,
211    }
212}
213
214pub fn extract_id_from_filename(entry: &std::path::PathBuf) -> QuillSQLResult<u128> {
215    entry
216        .extension()
217        .ok_or_else(|| {
218            QuillSQLError::Internal(format!("Missing extension (ie. not in format: data.<id>)"))
219        })?
220        .to_str()
221        .ok_or_else(|| {
222            QuillSQLError::Internal("Failed to convert extension to string".to_string())
223        })?
224        .parse::<u128>()
225        .map_err(|e| QuillSQLError::Internal(format!("Failed to parse id: {}", e)))
226}
quill_sql/utils/util.rs

quill_sql/utils/
util.rs
