boolean-chains

https://orunge.org/boolean-chains/

Progress database format (results.sqlite3)

The progress binary writes results to a SQLite database (results.sqlite3 by default, overridable via the --db CLI argument). The schema has three tables.

files

One row per output file scanned.

Column	Type	Notes
id	INTEGER	Primary key
path	TEXT	Absolute or relative path; unique
corrupt	INTEGER	Boolean — file contains at least one corrupt chunk
ignore	INTEGER	Boolean — manually set to indicate that the file should be ignored

chunks

One row per valid chunk found inside an output file.

Column	Type	Notes
id	INTEGER	Primary key
file_id	INTEGER	Foreign key → files.id
chunk_id	TEXT	Space-joined arg integers, e.g. "0 10 23 26 70"
total_chains	INTEGER	Total chains explored (also used for dedup checks)
secs	REAL	Wall-clock time reported by the run
bad	INTEGER	Boolean — manually flagged as a bad result
corrupt	INTEGER	Boolean — detected corrupt during parsing
ignore	INTEGER	Boolean — manually set to indicate that the file should be ignored
verified	INTEGER	Boolean — manually set to indicate that the result was verified
wrong	INTEGER	Boolean — manually set to indicate that the result is wrong

An index on chunk_id supports fast lookup when comparing runs of the same chunk across multiple files.

A covering index on (ignore, corrupt, chunk_id, total_chains) supports the verified/wrong population queries with a pure index scan.

An index on (chunk_id, verified) supports fast lookup of verified results by chunk ID when populating the wrong flag.

An index on (ignore, corrupt) in the files table supports fast filtering on both columns. As ignore is the leftmost column, it also covers queries that filter on ignore alone.

chunk_matrix

One row per chain-length entry in a chunk’s stats matrix. The avg from the raw output is omitted — it is derivable as sum / n.

Column	Type	Notes
id	INTEGER	Primary key
chunk_row_id	INTEGER	Foreign key → chunks.id
chain_length	INTEGER	The n value from the matrix header
n	INTEGER	Count of new expressions at this length
sum	INTEGER	Sum of expression counts
min	INTEGER	Minimum expression count
max	INTEGER	Maximum expression count

(chunk_row_id, chain_length) is unique. Only rows where sum > 0 are stored; all-zero chain-length entries from the raw output are omitted.

Queries

Update ignore flag at chunks level

UPDATE chunks
SET ignore = (
    SELECT f.ignore
    FROM files f
    WHERE f.id = chunks.file_id
);

Set verified and wrong flags

-- verified
UPDATE chunks
SET verified = 1
WHERE ignore = 0
  AND corrupt = 0
  AND verified = 0
  AND EXISTS (
      SELECT 1 FROM chunks c2
      WHERE c2.chunk_id = chunks.chunk_id
        AND c2.total_chains = chunks.total_chains
        AND c2.ignore = 0
        AND c2.corrupt = 0
        AND c2.id != chunks.id
  );

-- wrong
UPDATE chunks
SET wrong = 1
WHERE ignore = 0
  AND corrupt = 0
  AND verified = 0
  AND EXISTS (
      SELECT 1 FROM chunks c2
      WHERE c2.chunk_id = chunks.chunk_id
        AND c2.verified = 1
        AND c2.ignore = 0
        AND c2.corrupt = 0
        AND c2.total_chains != chunks.total_chains
  );

Find unverified files

SELECT COUNT(*) AS unverified_files
FROM files f
WHERE f.ignore = 0
  AND f.corrupt = 0
  AND EXISTS (
      SELECT 1 FROM chunks c
      WHERE c.file_id = f.id
  )
  AND NOT EXISTS (
      SELECT 1 FROM chunks c
      WHERE c.file_id = f.id
        AND c.verified = 1
  );

Set files.ignore = 1 if at least one chunk was wrong

UPDATE files
SET ignore = 1
WHERE id IN (
    SELECT DISTINCT file_id
    FROM chunks
    WHERE verified = 0
      AND wrong = 1
);

UPDATE chunks
SET ignore = (
    SELECT f.ignore
    FROM files f
    WHERE f.id = chunks.file_id
);

List processed chunks

sqlite3 results.sqlite3 "SELECT DISTINCT chunk_id FROM chunks WHERE ignore = 0 AND corrupt = 0 ORDER BY chunk_id;" > processed-chunks.txt

Delete specific file

DELETE FROM chunk_matrix
WHERE chunk_row_id IN (
    SELECT id FROM chunks WHERE file_id IN (
)
);
DELETE FROM chunks WHERE file_id IN (
);
DELETE FROM files WHERE id IN (
);

Pick a random chunk of all unverified files

sqlite3 results.sqlite3 "SELECT (
    SELECT c.chunk_id FROM chunks c
    WHERE c.file_id = f.id
    ORDER BY RANDOM() LIMIT 1
) AS chunk_id
FROM files f
WHERE f.ignore = 0
  AND f.corrupt = 0
  AND EXISTS (
      SELECT 1 FROM chunks c
      WHERE c.file_id = f.id
  )
  AND NOT EXISTS (
      SELECT 1 FROM chunks c2
      WHERE c2.file_id = f.id
        AND c2.verified = 1
  );
" > unverified.txt

Find total runtime of the FIRST non-wrong chunk results

SELECT SUM(secs) AS total_secs, SUM(total_chains) AS total_chains
FROM chunks
WHERE id IN (
    SELECT MIN(id)
    FROM chunks
    WHERE wrong = 0
      AND ignore = 0
      AND corrupt = 0
    GROUP BY chunk_id
);

Find total runtime of verified chunk results

SELECT SUM(secs) AS total_secs, SUM(total_chains) AS total_chains
FROM chunks
WHERE id IN (
    SELECT MAX(id)
    FROM chunks
    WHERE wrong = 0
      AND ignore = 0
      AND corrupt = 0
      AND verified = 1
    GROUP BY chunk_id
);

Find unverified mismatching chunks

-- this isn't perfect; it might find a case where we have results A, A, B, C, so
-- A and A would be verified, but we still have two mismatching ones
SELECT chunk_id, COUNT(*) AS run_count, COUNT(DISTINCT total_chains) AS distinct_results
FROM chunks
WHERE verified = 0
  AND ignore = 0
  AND corrupt = 0
GROUP BY chunk_id
HAVING COUNT(*) > 1
ORDER BY chunk_id;

-- safer version to verify that there are no verified rows, but it takes 2.5x as long
SELECT chunk_id, COUNT(*) AS run_count, COUNT(DISTINCT total_chains) AS distinct_results
FROM chunks
WHERE verified = 0
  AND ignore = 0
  AND corrupt = 0
  AND NOT EXISTS (
      SELECT 1 FROM chunks c2
      WHERE c2.chunk_id = chunks.chunk_id
        AND c2.verified = 1
  )
GROUP BY chunk_id
HAVING COUNT(*) > 1
ORDER BY chunk_id;

Verify corrupt solutions

• [X] 0 36 48 58 67
• [X] 4 8 25 32 40
• [X] 7 25 29 41 56
• [X] 7 30 37 43 67
• [X] 16 21 27 28 45
• [X] 3 6 11 12 19
• [X] 6 12 13 29 41

Results for 16-22-third

• first run:
  • 14204277943 secs ~ 450 years
  • total number of chains: 2567815524926566380
  • ~180777618 chains per second
• verification:
  • 4132558326 secs ~ 131 years
  • total number of chains: 736285265774600386
  • ~178166939 chains per second
• total, including double verification, corrupt chunks, etc.
  • 18601288154 secs ~ 589 years
  • total number of chains: 3344213169302670015
  • ~179783956 chains per second