I’m stuck on Stage #nz8
Ive tried following the comment below the actual stage first finding the matched rows using the index nodes, I successfully found those but when I look for those rows by traversing the leaf nodes, it fail to be found. I confirm the row numbers are correct, from cross-checking with the test cases
Here are my logs:
remote: [tester::#NZ8] Running tests for Stage #NZ8 (Retrieve data using an index)
remote: [tester::#NZ8] $ ./your_program.sh test.db "SELECT id, name FROM companies WHERE country = 'north korea'"
remote: [your_program]
remote: [your_program] === Starting Query Execution ===
remote: [your_program] Table: companies
remote: [your_program] Query type: SELECT
remote: [your_program]
remote: [your_program] === Finding Table and Index Info ===
remote: [your_program] Looking for table: companies
remote: [your_program] Index column (if any): ry
remote: [your_program] Reading sqlite_schema (page 1), found 3 entries
remote: [your_program]
remote: [your_program] Examining entry 0: Type='table' -> Found target table!
remote: [your_program] Table root page: 2
remote: [your_program]
remote: [your_program] Examining entry 1: Type='table'
remote: [your_program] Examining entry 2: Type='index' Checking index SQL: CREATE INDEX idx_companies_country
remote: [your_program] on companies (country)
remote: [your_program] -> Found matching index! Root page: 223839
remote: [your_program]
remote: [your_program] Search complete - Table root: 2, Index root: 223839
remote: [your_program] Root page: 2
remote: [your_program] Index root page: 223839
remote: [your_program] Table schema: CREATE TABLE companies
remote: [your_program] (
remote: [your_program] id integer primary key autoincrement
remote: [your_program] , name text, domain text, year_founded text, industry text, "size range" text, locality text,
country text, current_employees text, total_employees text)
remote: [your_program] Selected columns: id name
remote: [your_program]
remote: [your_program] === Using Index Scan ===
remote: [your_program] WHERE clause: ry = 'north korea'
remote: [your_program] Collecting matching rowids from index...
remote: [your_program] Found 6 matching rows in index
remote: [your_program]
remote: [your_program] === Fetching Matching Rows ===
remote: [your_program] Fetching row with rowid: 986681
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 986681 ===
remote: [your_program] Examining interior page with 1 cells
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 986681 ===
remote: [your_program] Examining interior page with 360 cells
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 986681 ===
remote: [your_program] Examining interior page with 441 cells
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 986681 ===
remote: [your_program] Examining leaf page with 18 cells
remote: [your_program] not found
remote: [your_program] Fetching row with rowid: 1573653
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 1573653 ===
remote: [your_program] Examining interior page with 1 cells
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 1573653 ===
remote: [your_program] Examining interior page with 360 cells
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 1573653 ===
remote: [your_program] Examining interior page with 441 cells
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 1573653 ===
remote: [your_program] Examining leaf page with 18 cells
remote: [your_program] not found
remote: [your_program] Fetching row with rowid: 2828420
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 2828420 ===
remote: [your_program] Examining interior page with 1 cells
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 2828420 ===
remote: [your_program] Examining interior page with 360 cells
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 2828420 ===
remote: [your_program] Examining interior page with 441 cells
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 2828420 ===
remote: [your_program] Examining leaf page with 28 cells
remote: [your_program] not found
remote: [your_program] Fetching row with rowid: 3485462
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 3485462 ===
remote: [your_program] Examining interior page with 1 cells
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 3485462 ===
remote: [your_program] Examining interior page with 360 cells
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 3485462 ===
remote: [your_program] Examining interior page with 441 cells
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 3485462 ===
remote: [your_program] Examining leaf page with 35 cells
remote: [your_program] not found
remote: [your_program] Fetching row with rowid: 3969653
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 3969653 ===
remote: [your_program] Examining interior page with 1 cells
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 3969653 ===
remote: [your_program] Examining interior page with 360 cells
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 3969653 ===
remote: [your_program] Examining interior page with 396 cells
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 3969653 ===
remote: [your_program] Examining leaf page with 37 cells
remote: [your_program] not found
remote: [your_program] Fetching row with rowid: 4271599
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 4271599 ===
remote: [your_program] Examining interior page with 1 cells
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 4271599 ===
remote: [your_program] Examining interior page with 360 cells
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 4271599 ===
remote: [your_program] Examining interior page with 396 cells
remote: [your_program]
remote: [your_program] === Fetching Record by RowID 4271599 ===
remote: [your_program] Examining leaf page with 30 cells
remote: [your_program] not found
remote: [your_program]
remote: [your_program] === Query Execution Complete ===
remote: [tester::#NZ8] Expected exactly 6 lines of output, got: 118
remote: [tester::#NZ8] Test failed
And here’s a snippet of my code:
static TableInfo *find_table_and_index_info(Database *db,
const char *table_name,
const char *index_column) {
printf("\n=== Finding Table and Index Info ===\n");
printf("Looking for table: companies\n");
printf("Index column (if any): %s\n", index_column ? index_column : "none");
TableInfo *info = malloc(sizeof(TableInfo));
info->index_root_page = 0;
info->root_page = 0; // Initialize root_page
BTreePage *schema_page =
btree_page_read(db->file_handle, 1, db->header.page_size);
printf("Reading sqlite_schema (page 1), found %d entries\n",
schema_page->header.cell_count);
for (int i = 0; i < schema_page->header.cell_count; i++) {
BTreeCell *cell = &schema_page->cells[i];
BTreeRecord *record =
record_parse(cell->leaf_table.payload, cell->leaf_table.payload_size,
cell->leaf_table.row_id);
ColumnValue *type_col = record_get_column(record, 0);
printf("\nExamining entry %d: ", i);
if (!type_col || type_col->type != TYPE_TEXT) {
printf("Invalid type column\n");
record_free(record);
continue;
}
printf("Type='%.*s' ", (int)type_col->value.text_or_blob.size,
(char *)type_col->value.text_or_blob.data);
// Check if this is the target table
if (match_table_name(record, table_name) &&
strncmp((char *)type_col->value.text_or_blob.data, "table",
type_col->value.text_or_blob.size) == 0) {
printf("-> Found target table!\n");
extract_table_info(record, info);
printf("Table root page: %u\n", info->root_page);
}
// Check if this is the target index
if (index_column &&
strncmp((char *)type_col->value.text_or_blob.data, "index",
type_col->value.text_or_blob.size) == 0) {
ColumnValue *sql_col = record_get_column(record, 4);
printf("Checking index SQL: %.*s\n",
(int)sql_col->value.text_or_blob.size,
(char *)sql_col->value.text_or_blob.data);
if (sql_col &&
strstr((char *)sql_col->value.text_or_blob.data, index_column)) {
ColumnValue *rootpage_col = record_get_column(record, 3);
info->index_root_page = rootpage_col->value.int_value;
printf("-> Found matching index! Root page: %u\n",
info->index_root_page);
}
}
record_free(record);
}
printf("\nSearch complete - Table root: %u, Index root: %u\n",
info->root_page, info->index_root_page);
btree_page_free(schema_page);
return info;
}
static BTreeRecord *fetch_record_by_rowid(Database *db, uint32_t page_num,
int64_t rowid) {
printf("\n=== Fetching Record by RowID %ld ===\n", rowid);
BTreePage *page =
btree_page_read(db->file_handle, page_num, db->header.page_size);
if (!page) {
return NULL;
}
// Handle interior pages (type 0x05)
if (page->header.page_type == PAGE_TYPE_INTERIOR_TABLE) {
printf("Examining interior page with %d cells\n", page->header.cell_count);
int lo = 0;
int hi = page->header.cell_count - 1;
// Binary search through interior cells
while (lo <= hi) {
int mid = (lo + hi) / 2;
// Check if we're at the rightmost entry
if (mid == page->header.cell_count - 1) {
lo = mid;
break;
}
int64_t key = page->cells[mid].interior_table.rowid;
if (key == rowid) {
lo = mid;
break;
} else if (rowid < key) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
// Get the child page to traverse
uint32_t child_page;
if (lo >= page->header.cell_count) {
child_page = page->rightmost_pointer;
} else {
child_page = page->cells[lo].interior_table.left_child_page;
}
btree_page_free(page);
return fetch_record_by_rowid(db, child_page, rowid);
}
// Handle leaf pages (type 0x0D)
else if (page->header.page_type == PAGE_TYPE_LEAF_TABLE) {
printf("Examining leaf page with %d cells\n", page->header.cell_count);
int lo = 0;
int hi = page->header.cell_count - 1;
// Binary search through leaf cells
while (lo <= hi) {
int mid = (lo + hi) / 2;
int64_t current_rowid = page->cells[mid].leaf_table.row_id;
if (current_rowid == rowid) {
BTreeRecord *record =
record_parse(page->cells[mid].leaf_table.payload,
page->cells[mid].leaf_table.payload_size, rowid);
btree_page_free(page);
return record;
} else if (rowid < current_rowid) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
btree_page_free(page);
return NULL;
}
printf("Unexpected page type: %d\n", page->header.page_type);
btree_page_free(page);
return NULL;
}