# Failing to find rows by index

**URL:** <https://forum.codecrafters.io/t/failing-to-find-rows-by-index/4440>\
**Category:** Challenges\
**Tags:** challenge:sqlite\
**Created:** [January 24, 2025, 2:10pm UTC](https://forum.codecrafters.io/t/failing-to-find-rows-by-index/4440 "2025-01-24T14:10:36Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![botirk38](https://yyz1.discourse-cdn.com/flex003/user_avatar/forum.codecrafters.io/botirk38/32/4495_2.png) [@botirk38](https://forum.codecrafters.io/u/botirk38)\
**Post date:** [January 24, 2025, 2:10pm UTC](https://forum.codecrafters.io/t/failing-to-find-rows-by-index/4440/1 "2025-01-24T14:10:37Z")

</div>

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:

```auto
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:

```c
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;
}

```

---

<div class="post-metadata">

**Author:** ![andy1li](https://yyz1.discourse-cdn.com/flex003/user_avatar/forum.codecrafters.io/andy1li/32/10_2.png) [@andy1li](https://forum.codecrafters.io/u/andy1li)\
**Post date:** [March 31, 2025, 4:32pm UTC](https://forum.codecrafters.io/t/failing-to-find-rows-by-index/4440/4 "2025-03-31T16:32:03Z")

</div>

Hey @botirk38, sorry for the delayed response!

Since `scanIndex` is correctly returning the right `rowids`, the issue must lie within `findRow`:

 ![image](https://canada1.discourse-cdn.com/flex003/uploads/codecrafters/original/2X/d/daace4d7da0ccdc9387aa779908a36cddac7dddf.png)

TBH, it was a bit tricky to debug, so I used AI to help rewrite the logic:

```auto
    // Check if target is less than first key
    if (target_rowid < cells[0].interior_row_id) {
      findRow(cells[0].left_pointer, target_rowid, column_positions, results);
      return;
    }

    // Linear search through cells
    for (size_t i = 0; i < cells.size(); i++) {
      if (target_rowid <= cells[i].interior_row_id) {
        // If we found a key >= target, follow the left pointer
        // of the current cell
        findRow(cells[i].left_pointer, target_rowid, column_positions, results);
        return;
      }
    }

    // If we get here, target is > all keys, follow rightmost pointer
    findRow(page.getHeader().right_most_pointer, target_rowid,
            column_positions, results);
  } else {

```

And here’s an alternative using binary search:

```auto
    if (cells.empty() || target_rowid < cells[0].interior_row_id) {
      findRow(cells[0].left_pointer, target_rowid, column_positions, results);
      return;
    }

    auto it = std::lower_bound(cells.begin(), cells.end(), target_rowid,
                              [](const auto &cell, uint64_t rowid) {
                                return cell.interior_row_id < rowid;
                              });

    if (it == cells.end()) {
      findRow(page.getHeader().right_most_pointer, target_rowid, column_positions, results);
    } else {
      findRow(it->left_pointer, target_rowid, column_positions, results);
    }
  }

```

---

<div class="post-metadata">

**Author:** ![andy1li](https://yyz1.discourse-cdn.com/flex003/user_avatar/forum.codecrafters.io/andy1li/32/10_2.png) [@andy1li](https://forum.codecrafters.io/u/andy1li)\
**Post date:** [April 6, 2025, 4:17pm UTC](https://forum.codecrafters.io/t/failing-to-find-rows-by-index/4440/6 "2025-04-06T16:17:03Z")

</div>

Closing this thread due to inactivity. If you still need assistance, feel free to reopen or start a new discussion!

---

<div class="post-metadata">

**Author:** ![system](https://canada1.discourse-cdn.com/flex003/uploads/codecrafters/original/3X/7/0/700657133935c15703e22c7c8870394f6e6dc27d.svg) [@system](https://forum.codecrafters.io/u/system)\
**Post date:** [April 11, 2025, 4:18pm UTC](https://forum.codecrafters.io/t/failing-to-find-rows-by-index/4440/7 "2025-04-11T16:18:02Z")

</div>

This topic was automatically closed 5 days after the last reply. New replies are no longer allowed.