~ubuntu-branches/ubuntu/wily/sqlite3/wily

onfocus="entersearch()" onblur="leavesearch()" style="width:24ex;padding:1px 1ex; border:solid white 1px; font-size:0.9em ; font-style:italic;color:#044a64;" value="Search SQLite Docs...">

112

113

</form>

114

</div>

115

</table>

116

</div></div></div></div>

117

</td></tr></table>

118

119

120

121

122

123

124

The SQLite Database File Format

125

</h1>

126

127

<p>This document describes and defines the on-disk database file

128

format used by SQLite.</p>

129

130

<h2>1.0 The Database File</h2>

131

132

<p>The complete state of an SQLite database is usually

133

contained a single file on disk called the "main database file".</p>

134

135

<p>During a transaction, SQLite stores additional information

136

in a second file called the "rollback journal", or if SQLite is in

137

<a href="wal.html">WAL mode</a>, a write-ahead log file.

138

If the application or

139

host computer crashes before the transaction completes, then the rollback

140

journal or write-ahead log contains critical state information needed

141

to restore the main database file to a consistent state. When a rollback

142

journal or write-ahead log contains information necessary for recovering

143

the state of the database, they are called a "hot journal" or "hot WAL file".

144

Hot journals and WAL files are only a factor during error recovery

145

scenarios and so are uncommon, but they are part of the state of an SQLite

146

database and so cannot be ignored. This document defines the format

147

of a rollback journal and the write-ahead log file, but the focus is

148

on the main database file.</p>

149

150

<h3>1.1 Pages</h3>

151

152

<p>The main database file consists of one or more pages. The size of a

153

page is a power of two between 512 and 65536 inclusive. All pages within

154

the same database are the same size. The page size for a database file

155

is determined by the 2-byte integer located at an offset of

156

16 bytes from the beginning of the database file.</p>

157

158

<p>Pages are numbered beginning with 1. The maximum page number is

159

2147483646 (2<sup><small>31</small></sup> - 2). The minimum size

160

SQLite database is a single 512-byte page.

161

The maximum size database would be 2147483646 pages at 65536 bytes per

162

page or 140,737,488,224,256 bytes (about 140 terabytes). Usually SQLite will

163

hit the maximum file size limit of the underlying filesystem or disk

164

hardware size limit long before it hits its own internal size limit.</p>

165

166

<p>In common use, SQLite databases tend to range in size from a few kilobytes

167

to a few gigabytes.</p>

168

169

<p>At any point in time, every page in the main database has a single

170

use which is one of the following:

171

<ul>

172

<li>The lock-byte page

173

<li>A freelist page

174

<ul>

175

<li>A freelist trunk page

176

<li>A freelist leaf page

177

</ul>

178

<li>A b-tree page

179

<ul>

180

<li>A table b-tree interior page

181

<li>A table b-tree leaf page

182

<li>An index b-tree interior page

183

<li>An index b-tree leaf page

184

</ul>

185

<li>A payload overflow page

186

<li>A pointer map page

187

</ul>

188

</p>

189

190

<p>All reads from and writes to the main database file begin at a page

191

boundary and all writes are an integer number of pages in size. Reads

192

are also usually an integer number of pages in size, with the one exception

193

that when the database is first opened, the first 100 bytes of the

194

database file (the database file header) are read as a sub-page size unit.</p>

195

196

<p>Before any information-bearing page of the database is modified,

197

the original unmodified content of that page is written into the

198

rollback journal. If a transaction is interrupted and needs to be

199

rolled back, the rollback journal can then be used to restore the

200

database to its original state. Freelist leaf pages bear no

201

information that would need to be restored on a rollback and so they

202

are not written to the journal prior to modification, in order to

203

reduce disk I/O.</p>

204

205

206

207

<h3>1.2 The Database Header</h3>

208

209

<p>The first 100 bytes of the database file comprise the database file

210

header. The database file header is divided into fields as shown by

211

the table below. All multibyte fields in the database file header are

212

stored with the most significant byte first (big-endian).</p>

213

214

215

<i>Database Header Format</i><br>

216

217

<tr><th>Offset<th>Size<th>Description

218

219

The header string: "SQLite format 3\000"

220

221

The database page size in bytes. Must be a power of two between 512

222

and 32768 inclusive, or the value 1 representing a page size of 65536.

223

224

File format write version. 1 for legacy; 2 for <a href="wal.html">WAL</a>.

225

226

File format read version. 1 for legacy; 2 for <a href="wal.html">WAL</a>.

227

228

Bytes of unused "reserved" space at the end of each page. Usually 0.

229

230

Maximum embedded payload fraction. Must be 64.

231

232

Minimum embedded payload fraction. Must be 32.

233

234

Leaf payload fraction. Must be 32.

235

236

File change counter.

237

238

Size of the database file in pages. The "in-header database size".

239

240

Page number of the first freelist trunk page.

241

242

Total number of freelist pages.

243

244

The schema cookie.

245

246

The schema format number. Supported schema formats are 1, 2, 3, and 4.

247

248

Default page cache size.

249

250

The page number of the largest root b-tree page when in auto-vacuum or

251

incremental-vacuum modes, or zero otherwise.

252

253

The database text encoding. A value of 1 means UTF-8. A value of 2

254

means UTF-16le. A value of 3 means UTF-16be.

255

256

The "user version" as read and set by the <a href="pragma.html#pragma_schema_version">user_version pragma</a>.

257

258

True (non-zero) for incremental-vacuum mode. False (zero) otherwise.

259

260

Reserved for expansion. Must be zero.

261

262

The <a href="fileformat2.html#validfor">version-valid-for number</a>.

263

264

<a href="c3ref/c_source_id.html">SQLITE_VERSION_NUMBER</a>

265

</table></center>

266

267

<h4>1.2.1 Magic Header String</h4>

268

269

<p>Every valid SQLite database file begins with the following 16 bytes

270

(in hex): 53 51 4c 69 74 65 20 66 6f 72 6d 61 74 20 33 00. This byte sequence

271

corresponds to the UTF-8 string "SQLite format 3" including the nul

272

terminator character at the end.</p>

273

274

275

276

<p>The two-byte value beginning at offset 16 determines the page size of

277

the database. For SQLite versions 3.7.0.1 and earlier, this value is

278

interpreted as a big-endian integer and must be a power of two between

279

512 and 32768, inclusive. Beginning with SQLite version 3.7.1, a page

280

size of 65536 bytes is supported. The value 65536 will not fit in a

281

two-byte integer, so to specify a 65536-byte page size, the value is

282

at offset 16 is 0x00 0x01.

283

This value can be interpreted as a big-endian

284

1 and thought of is as a magic number to represent the 65536 page size.

285

Or one can view the two-byte field as a little endian number and say

286

that it represents the page size divided by 256. These two

287

interpretations of the page-size field are equivalent.</p>

288

289

<h4>1.2.3 File format version numbers</h4>

290

291

<p>The file format write version and file format read version at offsets

292

18 and 19 are intended to allow for enhancements of the file format

293

in future versions of SQLite. In current versions of SQLite, both of

294

these values are 1 for rollback journalling modes and 2 for <a href="wal.html">WAL</a>

295

journalling mode. If a version of SQLite coded to the current

296

file format specification encounters a database file where the read

297

version is 1 or 2 but the write version is greater than 2, then the database

298

file must be treated as read-only. If a database file with a read version

299

greater than 2 is encounter, then that database cannot be read or written.</p>

300

301

<h4>1.2.4 Reserved bytes per page</h4>

302

303

<p>SQLite has the ability to set aside a small number of extra bytes at

304

the end of every page for use by extensions. These extra bytes are

305

used, for example, by the SQLite Encryption Extension to store a nonce

306

and/or cryptographic checksum associated with each page. The

307

"reserved space" size in the 1-byte integer at offset 20 is the number

308

of bytes of space at the end of each page to reserve for extensions.

309

This value is usually 0. The value can be odd.</p>

310

311

312

313

<p>The "usable size" of a database page is the page size specify by the

314

2-byte integer at offset 16 in the header less the "reserved" space size

315

recorded in the 1-byte integer at offset 20 in the header. The usable

316

size of a page might be an odd number. However, the usable size is not

317

allowed to be less than 480. In other words, if the page size is 512,

318

then the reserved space size cannot exceed 32.</p>

319

320

<h4>1.2.5 Payload fractions</h4>

321

322

<p>The maximum and minimum embedded payload fractions and the leaf

323

payload fraction values must be 64, 32, and 32. These values were

324

originally intended to as tunable parameters that could be used to

325

modify the storage format of the b-tree algorithm. However, that

326

functionality is not supported and there are no current plans to add

327

support in the future. Hence, these three bytes are fixed at the

328

values specified.</p>

329

330

<h4>1.2.6 File change counter</h4>

331

332

333

334

<p>The file change counter is a 4-byte big-endian integer which is

335

incremented whenever the database file is unlocked after having

336

been modified.

337

When two or more processes are reading the same database file, each

338

process can detect database changes from other processes by monitoring

339

the change counter.

340

A process will normally want to flush its database page cache when

341

another process modified the database, since the cache has become stale.

342

The file change counter facilitates this.</p>

343

344

<p>In WAL mode, changes to the database are detected using the wal-index

345

and so the change counter is not needed. Hence, the change counter might

346

not be incremented on each transaction in WAL mode.</p>

347

348

<h4>1.2.7 In-header database size</h4>

349

350

351

352

<p>The 4-byte big-endian integer at offset 28 into the header

353

stores the size of the database file in pages. If this in-header

354

datasize size is not valid (see the next paragraph), then the database

355

size is computed by looking

356

at the actual size of the database file. Older versions of SQLite

357

ignored the in-header database size and used the actual file size

358

exclusively. Newer versions of SQLite use the in-header database

359

size if it is available but fall back to the actual file size if

360

the in-header database size is not valid.</p>

361

362

<p>The in-header database size is only considered to be valid if

363

it is non-zero and if the 4-byte <a href="fileformat2.html#chngctr">change counter</a> at offset 24

364

exactly matches the 4-byte <a href="fileformat2.html#validfor">version-valid-for number</a> at offset 92.

365

The in-header database size is always valid

366

when the database is only modified using recent versions of SQLite

367

(versions 3.7.0 and later).

368

If a legacy version of SQLite writes to the database, it will not

369

know to update the in-header database size and so the in-header

370

database size could be incorrect. But legacy versions of SQLite

371

will also leave the version-valid-for number at offset 92 unchanged

372

so it will not match the change-counter. Hence, invalid in-header

373

database sizes can be detected (and ignored) by observing when

374

the change-counter does not match the version-valid-for number.</p>

375

376

377

378

<p>Unused pages in the database file are stored on a freelist. The

379

4-byte big-endian integer at offset 32 stores the page number of

380

the first page of the freelist, or zero if the freelist is empty.

381

The 4-byte big-endian integer at offset 36 stores stores the total

382

number of pages on the freelist.</p>

383

384

<h4>1.2.9 Schema cookie</h4>

385

386

<p>The schema cookie is a 4-byte big-endian integer at offset 40

387

that is incremented whenever the database schema changes. A

388

prepared statement is compiled against a specific version of the

389

database schema. Whenever the database schema changes, the statement

390

must be reprepared. Whenever a prepared statement runs, it first checks

391

the schema cookie to make sure the value is the same as when the statement

392

was prepared and if the schema cookie has changed, the statement aborts

393

in order to force the statement to be reprepared.</p>

394

395

396

397

<h4>1.2.10 Schema format number</h4>

398

399

<p>The schema format number is a 4-byte big-endian integer at offset 44.

400

The schema format number is similar to the file format read and write

401

version numbers at offsets 18 and 19 except that the schema format number

402

refers to the high-level SQL formatting rather than the low-level b-tree

403

formatting. Four schema format numbers are currently defined:</p>

404

405

<ol>

406

<li value=1>Format 1 is understood by all versions of SQLite back to

407

version 3.0.0.</li>

408

<li value=2>Format 2 adds the ability of rows within the same table

409

to have a varying number of columns, in order to support the

410

<a href="lang_altertable.html">ALTER TABLE ... ADD COLUMN</a> functionality. Support for

411

reading and writing format 2 was added in SQLite version 3.1.3

412

on 2005-02-19.</li>

413

<li value=3>Format 3 adds the ability of extra columns added by

414

<a href="lang_altertable.html">ALTER TABLE ... ADD COLUMN</a> to have non-NULL default

415

values. This capability was added in SQLite version 3.1.4

416

on 2005-03-11.</li>

417

<li value=4>Format 4 causes SQLite to respect the

418

<a href="lang_createindex.html#descidx">DESC keyword</a> on

419

index declarations. (The DESC keyword is ignored in indices for

420

formats 1, 2, and 3.)

421

Format 4 also adds two new boolean record type values (<a href="fileformat2.html#serialtype">serial types</a>

422

8 and 9.) Support for format 4 was added in SQLite 3.3.0 on

423

2006-01-10.</li>

424

</ol>

425

426

<p>New database files created by SQLite use format 4 by default.

427

The <a href="pragma.html#pragma_legacy_file_format">legacy_file_format pragma</a> can be used to cause SQLite

428

to create new database files using format 1.

429

The format version number can be made to default to 1 instead of 4 by

430

setting <a href="compile.html#default_file_format">SQLITE_DEFAULT_FILE_FORMAT</a>=1 at compile-time.

431

</p>

432

433

<h4>1.2.11 Suggested cache size</h4>

434

435

<p>The 4-byte big-endian signed integer at offset 48 is the suggested

436

cache size in pages for the database file. The value is a suggestion

437

only and SQLite is under no obligation to honor it. The absolute value

438

of the integer is used as the suggested size. The suggested cache size

439

can be set using the <a href="pragma.html#pragma_default_cache_size">default_cache_size pragma</a>.</p>

440

441

<h4>1.2.12 Incremental vacuum settings</h4>

442

443

<p>The two 4-byte big-endian integers at offsets 52 and 64 are used

444

to manage the <a href="pragma.html#pragma_auto_vacuum">auto_vacuum</a> and <a href="pragma.html#pragma_incremental_vacuum">incremental_vacuum</a> modes. If

445

the integer at offset 52 is zero then pointer-map (ptrmap) pages are

446

omitted from the database file and neither auto_vacuum nor

447

incremental_vacuum are supported. If the integer at offset 52 is

448

non-zero then it is the page number of the largest root page in the

449

database file, the database file will contain ptrmap pages, and the

450

mode must be either auto_vacuum or incremental_vacuum. In this latter

451

case, the integer at offset 64 is true for incremental_vacuum and

452

false for auto_vacuum. If the integer at offset 52 is zero then

453

the integer at offset 64 must also be zero.</p>

454

455

<h4>1.2.13 Text encoding</h4>

456

457

<p>The 4-byte big-endian integer at offset 56 determines the encoding

458

used for all text strings stored in the database. A value of 1 means

459

UTF-8. A value of 2 means UTF-16le. A value of 3 means UTF-16be.

460

No other values are allowed.</p>

461

462

<h4>1.2.14 User version number</h4>

463

464

<p>The 4-byte big-endian integer at offset 60 is the user version which

465

is set and queried by the <a href="pragma.html#pragma_schema_version">user_version pragma</a>. The user version is

466

not used by SQLite.</p>

467

468

469

470

<h4>1.2.15 Write library version number and version-valid-for number</h4>

471

472

<p>The 4-byte big-endian integer at offset 96 stores the

473

<a href="c3ref/c_source_id.html">SQLITE_VERSION_NUMBER</a> value for the SQLite library that most

474

recently modified the database file. The 4-byte big-endian integer at

475

offset 92 is the value of the <a href="fileformat2.html#chngctr">change counter</a> when the version number

476

was stored. The integer at offset 92 indicates which transaction

477

the version number is valid for and is sometimes called the

478

"version-valid-for number".

479

480

<h4>1.2.16 Header space reserved for expansion</h4>

481

482

<p>All other bytes of the database file header are reserved for

483

future expansion and must be set to zero.</p>

484

485

486

487

<p>The lock-byte page is the single page of the database file

488

that contains the bytes at offsets between 1073741824 and 1073742335,

489

inclusive. A database file that is less than or equal to 1073741824 bytes

490

in size contains no lock-byte page. A database file larger than

491

1073741824 contains exactly one lock-byte page.

492

</p>

493

494

<p>The lock-byte page is set aside for use by the operating-system specific

495

<a href="vfs.html">VFS</a> implementation in implementing the database file locking primitives.

496

SQLite does not use the lock-byte page. The SQLite core

497

will never read or write the lock-byte page,

498

though operating-system specific <a href="vfs.html">VFS</a>

499

implementations may choose to read or write bytes on the lock-byte

500

page according to the

501

needs and proclivities of the underlying system. The unix and win32

502

<a href="vfs.html">VFS</a> implementations that come built into SQLite do not write to the

503

lock-byte page, but third-party VFS implementations for

504

other operating systems might.</p>

505

506

507

508

<h3>1.4 The Freelist</h3>

509

510

<p>A database file might contain one or more pages that are not in

511

active use. Unused pages can come about, for example, when information

512

is deleted from the database. Unused pages are stored on the freelist

513

and are reused when additional pages are required.</p>

514

515

<p>The freelist is organized as a linked list of freelist trunk pages

516

with each trunk pages containing page numbers for zero or more freelist

517

leaf pages.</p>

518

519

<p>A freelist trunk page consists of an array of 4-byte big-endian integers.

520

The size of the array is as many integers as will fit in the usable space

521

of a page. The minimum usable space is 480 bytes so the array will always

522

be at least 120 entries in length. The first integer in the array

523

is the page number of the next freelist trunk page in the list or zero

524

if this is the last freelist trunk page. The second integer in the array

525

is the number of leaf page pointers to follow. Call the second integer L.

526

If L is greater than zero then integers with array indexes between 2 and

527

L+1 inclusive contain page numbers for freelist leaf pages.</p>

528

529

<p>Freelist leaf pages contain no information. SQLite avoids reading or

530

writing freelist leaf pages in order to reduce disk I/O.</p>

531

532

<p>A bug in SQLite versions prior to 3.6.0 caused the database to be

533

reported as corrupt if any of the last 6 entries in the freelist trunk page

534

array contained non-zero values. Newer versions of SQLite do not have

535

this problem. However, newer versions of SQLite still avoid using the

536

last six entries in the freelist trunk page array in order that database

537

files created by newer versions of SQLite can be read by older versions

538

of SQLite.</p>

539

540

<p>The number of freelist pages is stored as a 4-byte big-endian integer

541

in the database header at an offset of 36 from the beginning of the file.

542

The database header also stores the page number of the first freelist trunk

543

page as a 4-byte big-endian integer at an offset of 32 from the beginning

544

of the file.</p>

545

546

<h3>1.5 B-tree Pages</h3>

547

548

<p>A b-tree page is either an interior page or a leaf page.

549

A leaf page contains keys and in the case of a table b-tree each

550

key has associated content. An interior page contains

551

K keys without content but with K+1 pointers to child b-tree pages.

552

A "pointer" in an interior b-tree page is just the 31-bit integer

553

page number of the child page.</p>

554

555

556

<p>Define the depth

557

of a leaf b-tree to be 1 and the depth of any interior b-tree to be one

558

more than the maximum depth of any of its children. In a well-formed

559

database, all children of any one interior b-tree have the same depth.</p>

560

561

<p>In an interior b-tree page, the pointers and keys logically alternate

562

with a pointer on both ends. (The previous sentence is to be understood

563

conceptually - the actual layout of the keys and

564

pointers within the page is more complicated and will be described in

565

the sequel.) All keys within the same page are unique and are logically

566

organized in ascending order from left to right. (Again, this ordering

567

is logical, not physical. The actual location of keys within the page

568

is arbitrary.) For any key X, pointers to the left

569

of a X refer to b-tree pages on which all keys are less than or equal to X.

570

Pointers to the right of X refer to pages where all keys are

571

greater than X.</p>

572

573

<p>Within an interior b-tree page, each key and the pointer to its

574

immediate left are combined into a structure called a "cell". The

575

right-most pointer is held separately. A leaf b-tree page has no

576

pointers, but it still uses the cell structure to hold keys for

577

index b-trees or keys and content for table b-trees.</p>

578

</p>

579

580

<p>Every b-tree page has at most one parent b-tree page.

581

A b-tree page without a parent is called a root page. A root b-tree page

582

together with the closure of its children form a complete b-tree.

583

It is possible (and in fact rather common) to have a complete b-tree

584

that consists of a single page that is both a leaf and the root.

585

Because there are pointers from parents to children, every page of a

586

complete b-tree can be located if only the root page is known. Hence,

587

b-trees are identified by their root page number.</p>

588

589

<p>A b-tree page is either a table b-tree page or an index b-tree page.

590

All pages within each complete b-tree are of the same type: either table

591

or index. There is a one-to-one mapping from table b-trees in the database

592

file to (non-virtual) tables in the database schema, including system tables

593

such as sqlite_master. There is one-to-one mapping between index b-trees

594

in the database file and indices in the schema, including implied indices

595

created by uniqueness constraints. The b-tree corresponding to the

596

sqlite_master table always has its root page on a page number of 1.

597

The sqlite_master table contains the root page number for every other

598

table and index in the database file.</p>

599

600

<p>Each entry in a table b-tree consists of a 64-bit signed integer key

601

and up to 2147483647 bytes of arbitrary data. Interior table b-trees

602

hold only keys and pointers to children. All data is contained in the

603

table b-tree leaves.</p>

604

605

<p>Each entry in an index b-tree consists of an arbitrary key of up

606

to 2147483647 bytes in length and no data.</p>

607

608

609

610

<p>Define the "payload" of a cell to be the arbitrary length section

611

of the cell. For an index b-tree, the key is always arbitrary in length

612

and hence the payload is the key. There are no arbitrary length elements

613

in the cells of interior table b-tree pages and so those cells have no

614

payload. Table b-tree leaf pages contain arbitrary length content and

615

so for cells on those pages the payload is the content.

616

<p>When the size of payload for a cell exceeds a certain threshold (to

617

be defined later) then only the first few bytes of the payload

618

are stored on the b-tree page and the balance is stored in a linked list

619

of content overflow pages.</p>

620

621

<p>A b-tree page is divided into regions in the following order:

622

623

<ol>

624

<li>The 100-byte database file header (found on page 1 only)

625

<li>The 8 or 12 byte b-tree page header

626

<li>The cell pointer array

627

<li>Unallocated space

628

<li>The cell content area

629

<li>The reserved region.

630

</ol>

631

</p>

632

633

<p>The 100-byte database file header is found only on page 1, which is

634

always a table b-tree page. All other b-tree pages in the database file

635

omit this 100-byte header.</p>

636

637

<p>The reserved region is an area of unused space at the end of every

638

page (except the locking page) that extensions can use to hold per-page

639

information. The size of the reserved region is determined by the one-byte

640

unsigned integer found at an offset of 20 into the database file header.

641

The size of the reserved region is usually zero.</p>

642

643

<p>The b-tree page header is 8 bytes in size for leaf pages and 12

644

bytes for interior pages. All multibyte values in the page header

645

are big-endian.

646

The b-tree page header is composed of the following fields:</p>

647

648

649

<i>B-tree Page Header Format</i><br>

650

651

<tr><th>Offset<th>Size<th>Description

652

653

A flag indicating the b-tree page type

654

A value of 2 means the page is an interior index b-tree page.

655

A value of 5 means the page is an interior table b-tree page.

656

A value of 10 means the page is a leaf index b-tree page.

657

A value of 13 means the page is a leaf table b-tree page.

658

Any other value for the b-tree page type is an error.

659

660

Byte offset into the page of the first freeblock

661

662

Number of cells on this page

663

664

Offset to the first byte of the cell content area. A zero value is used to represent an offset of 65536, which occurs on an empty root page when using a 65536-byte page size.

665

666

Number of fragmented free bytes within the cell content area

667

668

The right-most pointer (interior b-tree pages only)

669

</table></blockquote></center>

670

671

<p>The cell pointer array of a b-tree page immediately follows the b-tree

672

page header. Let K be the number of cells on the btree. The cell pointer

673

array consists of K 2-byte integer offsets to the cell contents. The

674

cell pointers are arranged in key order with left-most cell (the cell with the

675

smallest key) first and the right-most cell (the cell with the largest

676

key) last.</p>

677

678

<p>Cell content is stored in the cell content region of the b-tree page.

679

SQLite strives to place cells as far toward the end of the b-tree page as

680

it can, in order to leave space for future growth of the cell pointer array.

681

The area in between the last cell pointer array entry and the beginning of

682

the first cell is the unallocated region.

683

</p>

684

685

<p>If a page contains no cells (which is only possible for a root page

686

of a table that contains no rows) then the offset to the cell content

687

area will equal the page size minus the bytes of reserved space. If

688

the database uses a 65536-byte page size and the reserved space is zero

689

(the usual value for reserved space) then the cell content offset of an

690

empty page wants to be 65536.

691

However, that integer is too large to be stored in a

692

2-byte unsigned integer, so a value of 0 is used in its place.

693

694

<p>A freeblock is a structure used to identify unallocated space within

695

a b-tree page. Freeblocks are organized as a chain. The first 2 bytes of

696

a freeblock are a big-endian integer which is the offset in the b-tree page

697

of the next freeblock in the chain, or zero if the freeblock is the last on

698

the chain. The third and fourth bytes of each freeblock form

699

a big-endian integer which is the size of the freeblock in bytes, including

700

the 4-byte header. Freeblocks are always connected in order

701

of increasing offset. The second field of the b-tree page header is the

702

offset of the first freeblock, or zero if there are no freeblocks on the

703

page. In a well-formed b-tree page, there will always be at least one cell

704

before the first freeblock.</p>

705

706

<p>A freeblock requires at least 4 bytes of space. If there is an isolated

707

group of 1, 2, or 3 unused bytes within the cell content area, those bytes

708

comprise a fragment. The total number of bytes in all fragments is stored

709

in the fifth field of the b-tree page header. In a well-formed b-tree page,

710

the total number of bytes in fragments may not exceed 60.</p>

711

712

<p>The total amount of free space on a b-tree page consists of the size

713

of the unallocated region plus the total size of all freeblocks plus the

714

number of fragmented free bytes. SQLite may from time to time reorganize

715

a b-tree page so that there are no freeblocks or fragment bytes, all

716

unused bytes are contained in the unallocated space region, and all

717

cells are packed tightly at the end of the page. This is called

718

"defragmenting" the b-tree page.</p>

719

720

721

722

723

<p>A variable-length integer or "varint" is a static Huffman encoding

724

of 64-bit twos-complement integers that uses less space for small positive

725

values.

726

A varint is between 1 and 9 bytes in length. The varint consists of either

727

zero or more byte which have the high-order bit set followed by a single byte

728

with the high-order bit clear, or nine bytes, whichever is shorter.

729

The lower seven bits of each of the first eight bytes and all 8 bits of

730

the ninth byte are used to reconstruct the 64-bit twos-complement integer.

731

Varints are big-endian: bits taken from the earlier byte of the varint

732

are the more significant and bits taken from the later bytes. </p>

733

734

<p>The format of a cell depends on which kind of b-tree page the cell

735

appears on. The following table shows the elements of a cell, in

736

order of appearance, for the various b-tree page types.</p>

737

738

739

<dt><p>Table B-Tree Leaf Cell:</p></dt>

740

741

<li>A varint which is the total number of bytes of payload, including any

742

overflow

743

<li>A varint which is the integer key, a.k.a. "rowid"

744

<li>The initial portion of the payload that does not spill to overflow

745

pages.

746

<li>A 4-byte big-endian integer page number for the first page of the

747

overflow page list - omitted if all payload fits on the b-tree page.

748

</ul></p></dd>

749

750

<dt><p>Table B-Tree Interior Cell:</p></dt>

751

752

<li>A 4-byte big-endian page number which is the left child pointer.

753

<li>A varint which is the integer key

754

</ul></p></dd>

755

756

<dt><p>Index B-Tree Leaf Cell:</p></dt>

757

758

<li>A varint which is the total number of bytes of key payload, including any

759

overflow

760

<li>The initial portion of the payload that does not spill to overflow

761

pages.

762

<li>A 4-byte big-endian integer page number for the first page of the

763

overflow page list - omitted if all payload fits on the b-tree page.

764

</ul></p></dd>

765

766

<dt><p>Index B-Tree Interior Cell:</p></dt>

767

768

<li>A 4-byte big-endianpage number which is the left child pointer.

769

<li>A varint which is the total number of bytes of key payload, including any

770

overflow

771

<li>The initial portion of the payload that does not spill to overflow

772

pages.

773

<li>A 4-byte big-endian integer page number for the first page of the

774

overflow page list - omitted if all payload fits on the b-tree page.

775

</ul></p></dd>

776

</dl></blockquote>

777

778

<p>The information above can be recast into a table format as follows:</p>

779

780

781

782

783

<i>B-tree Cell Format</i>

784

785

<tr><th rowspan=2>Datatype

786

<th colspan=4>Appears in...

787

<th rowspan=2>Description

788

<tr><th>Table Leaf

789

<th>Table Interior

790

<th>Index Leaf

791

<th>Index Interior

792

<tr><td align=center valign=top>4-byte integer

793

794

<td align=center valign=top>✔

795

796

<td align=center valign=top>✔

797

<td align=left>Page number of left child

798

<tr><td align=center valign=top>varint

799

<td align=center valign=top>✔

800

801

<td align=center valign=top>✔

802

<td align=center valign=top>✔

803

<td align=left>Number of bytes of payload

804

<tr><td align=center valign=top>varint

805

<td align=center valign=top>✔

806

<td align=center valign=top>✔

807

808

809

<td align=left>Rowid

810

<tr><td align=center valign=top>byte array

811

<td align=center valign=top>✔

812

813

<td align=center valign=top>✔

814

<td align=center valign=top>✔

815

<td align=left>Payload

816

<tr><td align=center valign=top>4-byte integer

817

<td align=center valign=top>✔

818

819

<td align=center valign=top>✔

820

<td align=center valign=top>✔

821

<td align=left>Page number of first overflow page

822

</table></center>

823

824

825

826

827

828

<p>The amount of payload that spills onto overflow pages also depends on

829

the page type. For the following computations, let U be the usable size

830

of a database page, the total page size less the reserved space at the

831

end of each page. And let P be the payload size.</p>

832

833

834

<dt>Table B-Tree Leaf Cell:</dt>

835

<dd><p>

836

If the payload size P is less than or equal to U-35 then

837

the entire payload is stored on the b-tree leaf page.

838

Let M be ((U-12)*32/255)-23. If P is greater than U-35

839

then the number of byte stored on the b-tree leaf page is the smaller of

840

M+((P-M)%(U-4)) and U-35.

841

Note that number of bytes stored on the leaf page is never less than M.

842

</p></dd>

843

844

<dt>Table B-Tree Interior Cell:</dt>

845

<dd><p>

846

Interior pages of table b-trees have no payload and so there is never

847

any payload to spill.

848

</p></dd>

849

850

<dt>Index B-Tree Leaf Or Interior Cell:</dt>

851

<dd><p>

852

Let X be ((U-12)*64/255)-23). If the payload size P is less than

853

or equal to X then the entire payload is stored on the b-tree page.

854

Let M be ((U-12)*32/255)-23. If P is greater than X then the number

855

of byte stored on the b-tree page is the smaller of

856

M+((P-M)%(U-4)) and X.

857

Note that number of bytes stored on the index page is never less than M.

858

</p></dd>

859

</dl></blockquote>

860

861

<p>The overflow thresholds are designed to give a minimum fanout of

862

4 for index b-trees and to make sure enough of the payload

863

is on the b-tree page that the record header can usually be accessed

864

without consulting an overflow page. In hindsight, the designers of

865

the SQLite b-tree logic realize that these thresholds could have been

866

made much simpler. However, the computations cannot be changed

867

without resulting in an incompatible file format. And the current computations

868

work well, even if they are a little complex.</p>

869

870

871

872

<h3>1.6 Cell Payload Overflow Pages</h3>

873

874

<p>When the payload of a b-tree cell is too large for the b-tree page,

875

the surplus is spilled onto overflow pages. Overflow pages form a linked

876

list. The first four bytes of each overflow page are a big-endian

877

integer which is the page number of the next page in the chain, or zero

878

for the final page in the chain. The fifth byte through the last usable

879

byte are used to hold overflow content.</p>

880

881

<h3>1.7 Pointer Map or Ptrmap Pages</h3>

882

883

<p>Pointer map or ptrmap pages are extra pages inserted into the database

884

to make the operation of <a href="pragma.html#pragma_auto_vacuum">auto_vacuum</a> and <a href="pragma.html#pragma_incremental_vacuum">incremental_vacuum</a> modes

885

more efficient. Other page types in the database typically have pointers

886

from parent to child. For example, an interior b-tree page contains pointers

887

to its child b-tree pages and an overflow chain has a pointer

888

from earlier to later links in the chain. A ptrmap page contains linkage

889

information going in the opposite direction, from child to parent.</p>

890

891

<p>Ptrmap pages must exist in any database file which has a non-zero

892

largest root b-tree page value at offset 52 in the database header.

893

If the largest root b-tree page value is zero, then the database must not

894

contain ptrmap pages.</p>

895

896

<p>In a database with ptrmap pages, the first ptrmap page is page 2.

897

A ptrmap page consists of an array of 5-byte entries. Let J be the

898

number of 5-byte entries that will fit in the usable space of a page.

899

(In other words, J=U/5.) The first ptrmap page will contain back pointer

900

information for pages 3 through J+2, inclusive. The second pointer map

901

page will be on page J+3 and that ptrmap page will provide back pointer

902

information for pages J+4 through 2*J+3 inclusive. And so forth for

903

the entire database file.</p>

904

905

<p>In a database that uses ptrmap pages, all pages at locations identified

906

by the computation in the previous paragraph must be ptrmap page and no

907

other page may be a ptrmap page. Except, if the byte-lock page happens to

908

fall on the same page number as a ptrmap page, then the ptrmap is moved

909

to the following page for that one case.</p>

910

911

<p>Each 5-byte entry on a ptrmap page provides back-link information about

912

one of pages that immediately follow the pointer map. If page B is a

913

ptrmap page then back-link information about page B+1 is provided by

914

the first entry on the pointer map. Information about page B+2 is

915

provided by the second entry. And so forth.</p>

916

917

<p>Each 5-byte ptrmap entry consists of one byte of "page type" information

918

followed by a 4-byte big-endian page number. Five page types are recognized:

919

</p>

920

921

<ol>

922

<li>A b-tree root page. The

923

page number should be zero.

924

<li>A freelist page. The page number should be

925

zero.

926

<li>The first page of a

927

cell payload overflow chain. The page number is the b-tree page that

928

contains the cell whose content has overflowed.

929

<li>A page in an overflow chain

930

other than the first page. The page number is the prior page of the

931

overflow chain.

932

<li>A non-root b-tree page. The

933

page number is the parent b-tree page.

934

</ol>

935

936

<p>In any database file that contains ptrmap pages, all b-tree root pages

937

must come before any non-root b-tree page, cell payload overflow page, or

938

freelist page. This restriction ensures that a root page will never

939

be moved during an auto-vacuum or incremental-vacuum. The auto-vacuum

940

logic does not know how to update the root_page field of the sqlite_master

941

table and so it is necessary to prevent root pages from being moved

942

during an auto-vacuum in order to preserve the integrity of the

943

sqlite_master table. Root pages are moved to the beginning of the

944

database file by the CREATE TABLE, CREATE INDEX, DROP TABLE, and

945

DROP INDEX operations.</p>

946

947

<h2>2.0 Schema Layer</h2>

948

949

<p>The foregoing text describes low-level aspects of the SQLite file

950

format. The b-tree mechanism provides a powerful and efficient means of

951

accessing a large data set. This section will describe how the

952

low-level b-tree layer is used to implement higher-level SQL

953

capabilities.</p>

954

955

956

957

<h3>2.1 Record Format</h3>

958

959

<p>The content of a table b-tree leaf page and the key

960

of any index b-tree page was characterized above

961

as an arbitrary sequence of bytes.

962

The prior discussion mentioned one key being less than another, but

963

did not define what "less than" meant. The current section will address

964

these omissions.</p>

965

966

<p>Payload, either table content or index keys, is always in the "record

967

format". The record format defines a sequence of values corresponding

968

to columns in a table or index. The record format specifies the number

969

of columns, the datatype of each column, and the content of each column.</p>

970

971

<p>The record format makes extensive use of the

972

<a href="fileformat2.html#varint">variable-length integer</a> or <a href="fileformat2.html#varint">varint</a>

973

representation of 64-bit signed integers defined above.</p>

974

975

976

977

<p>A record contains a header and a body, in that order.

978

The header begins with a single varint which determines the total number

979

of bytes in the header. The varint value is the size of the header in

980

bytes including the size varint itself. Following the size varint are

981

one or more additional varints, one per column. These additional varints

982

are called "serial type" numbers and

983

determine the datatype of each column, according to the following chart:</p>

984

985

986

<i>Serial Type Codes Of The Record Format</i><br>

987

988

<tr><th>Serial Type<th>Content Size<th>Meaning

989

990

NULL

991

992

8-bit twos-complement integer

993

994

Big-endian 16-bit twos-complement integer

995

996

Big-endian 24-bit twos-complement integer

997

998

Big-endian 32-bit twos-complement integer

999

1000

Big-endian 48-bit twos-complement integer

1001

1002

Big-endian 64-bit twos-complement integer

1003

1004

Big-endian IEEE 754-2008 64-bit floating point number

1005

1006

Integer constant 0. Only available for schema format 4 and higher.

1007

1008

Integer constant 1. Only available for schema format 4 and higher.

1009

<tr><td valign=top align=center>10,11

1010

1011

<i>Not used. Reserved for expansion.</i>

1012

<tr><td valign=top align=center>N≥12 and even

1013

1014

A BLOB that is (N-12)/2 bytes in length

1015

<tr><td valign=top align=center>N≥13 and odd

1016

1017

A string in the database encoding and (N-13)/2 bytes in length.

1018

The nul terminator is omitted.

1019

</table></center>

1020

1021

<p>Note that because of the way varints are defined, the header size varint

1022

and serial type varints will usually consist of a single byte. The

1023

serial type varints for large strings and BLOBs might extend to two or three

1024

byte varints, but that is the exception rather than the rule.

1025

The varint format is very efficient at coding the record header.</p>

1026

1027

<p>The values for each column in the record immediately follow the header.

1028

Note that for serial types 0, 8, 9, 12, and 13, the value is zero bytes in

1029

length. If all columns are of these types then the body section of the

1030

record is empty.</p>

1031

1032

<h3>2.2 Record Sort Order</h3>

1033

1034

<p>The order of keys in an index b-tree is determined by the sort order of

1035

the records that the keys represent. Record comparison progresses column

1036

by column. Columns of a record are examined from left to right. The

1037

first pair of columns that are not equal determines the relative order

1038

of the two records. The sort order of individual columns is as

1039

follows:</p>

1040

1041

<ol>

1042

<li>NULL values (serial type 0) sort first.

1043

<li>Numeric values (serial types 1 through 9) sort after NULLs

1044

and in numeric order.

1045

<li>Text values (odd serial types 13 and larger) sort after numeric

1046

values in the order determined by the columns <a href="datatype3.html#collation">collating function</a>.

1047

<li>BLOB values (even serial types 12 and larger) sort last and in the order

1048

determined by memcmp().

1049

</ol>

1050

1051

<p>A <a href="datatype3.html#collation">collating function</a> for each column is necessary in order to compute

1052

the order of text fields.

1053

SQLite defines three built-in collating functions:

1054

</p>

1055

1056

1057

<tr><td valign=top>BINARY

1058

<td>Strings are compared byte by byte using the memcmp() function

1059

from the standard C library.

1060

<tr><td valign=top>NOCASE

1061

<td>Like BINARY except that uppercase ASCII characters ('A' through 'Z')

1062

are folded into their lowercase equivalents prior to running the

1063

comparison. Note that only ASCII characters are case-folded. NOCASE

1064

does not implement a general purpose unicode caseless comparison.

1065

<tr><td valign=top>RTRIM

1066

<td>Like BINARY except that spaces at the end of the string are elided

1067

prior to comparison.

1068

</table></blockquote>

1069

1070

<p>Additional application-specific collating functions can be added to

1071

SQLite using the <a href="c3ref/create_collation.html">sqlite3_create_collation()</a> interface.</p>

1072

1073

<p>The default collating function for all strings is BINARY.

1074

Alternative collating functions for table columns can be specified in the

1075

<a href="lang_createtable.html">CREATE TABLE</a> statement using the COLLATE clause on the <a href="lang_createtable.html#tablecoldef">column definition</a>.

1076

When a column is indexed, the same collating function specified in the

1077

<a href="lang_createtable.html">CREATE TABLE</a> statement is used for the column in the index, by default,

1078

though this can be overridden using a COLLATE clause in the

1079

<a href="lang_createindex.html">CREATE INDEX</a> statement.

1080

1081

<h3>2.3 Representation Of SQL Tables</h3>

1082

1083

<p>Each ordinary SQL table in the database schema is represented on disk

1084

by a table b-tree. Each entry in the table b-tree corresponds to a row

1085

of the SQL table. The <a href="lang_createtable.html#rowid">rowid</a> of the SQL table is the 64-bit signed

1086

integer key for each entry in the table b-tree.</p>

1087

1088

<p>The content of each SQL table row is stored in the database file by

1089

first combining the values in the various columns into a byte array

1090

in the record format, then storing that byte array as the payload in

1091

an entry in the table b-tree. The order of values in the record is

1092

the same as the order of columns in the SQL table definition.

1093

When an SQL table that includes an

1094

<a href="lang_createtable.html#rowid">INTEGER PRIMARY KEY</a> column (which aliases the <a href="lang_createtable.html#rowid">rowid</a>) then that

1095

column appears in the record as a NULL value. SQLite will always use

1096

the table b-tree key rather than the NULL value when referencing the

1097

<a href="lang_createtable.html#rowid">INTEGER PRIMARY KEY</a> column.</p>

1098

1099

<p>If the <a href="datatype3.html#affinity">affinity</a> of a column is REAL and that column contains a

1100

value that can be converted to an integer without loss of information

1101

(if the value contains no fractional part and is not too large to be

1102

represented as an integer) then the column may be stored in the record

1103

as an integer. SQLite will convert the value back to floating

1104

point when extracting it from the record.</p>

1105

1106

1107

<h3>2.4 Representation Of SQL Indices</h3>

1108

1109

<p>Each SQL index, whether explicitly declared via a <a href="lang_createindex.html">CREATE INDEX</a> statement

1110

or implied by a UNIQUE constraint, corresponds to an index b-tree in the

1111

database file.

1112

There is one entry in index b-tree for each row in the corresponding table.

1113

The key to an index b-tree is

1114

a record composed of the columns that are being indexed followed by the

1115

<a href="lang_createtable.html#rowid">rowid</a> of the table row. Because every row in a table has a unique

1116

rowid and all keys in an index contain the rowid, all keys in an index

1117

are unique.</p>

1118

1119

<p>There is a one-to-one mapping between rows in a table and

1120

entries in each index associated with that table.

1121

Corresponding rows int the index and table b-trees share the same rowid

1122

value, and contain the same value for all indexed columns.</p>

1123

1124

1125

1126

<h3>2.5 Storage Of The SQL Database Schema</h3>

1127

1128

<p>Page 1 of a database file is the root page of a table b-tree that

1129

holds a special table named "sqlite_master" (or "sqlite_temp_master" in

1130

the case of a TEMP database) which stores the complete

1131

database schema. The structure of the sqlite_master table is as

1132

if it had been created using the following SQL:</p>

1133

1134

1135

CREATE TABLE sqlite_master(

1136

type text,

1137

name text,

1138

tbl_name text,

1139

rootpage integer,

1140

sql text

1141

);

1142

</pre></blockquote>

1143

1144

<p>The sqlite_master table contains one row for each table, index, view,

1145

and trigger (collectively "objects") in the database schema, except there

1146

is no entry for the sqlite_master table itself. The sqlite_master table

1147

contains entries for <a href="fileformat2.html#intschema">internal schema objects</a> in addition to application-

1148

and programmer-defined objects.

1149

1150

1151

<p>The sqlite_master.type column will be one

1152

of the following text strings: 'table', 'index', 'view', or 'trigger'

1153

according to the type of object defined. The 'table' string is used

1154

for both ordinary and <a href="vtab.html">virtual tables</a>.</p>

1155

1156

</p>The sqlite_master.name column will hold the name of the object.

1157

<a href="lang_createtable.html#uniqueconst">UNIQUE</a> and <a href="lang_createtable.html#primkeyconst">PRIMARY KEY</a> constraints on tables cause SQLite to create

1158

<a href="fileformat2.html#intschema">internal indices</a> with names of the form "sqlite_autoindex_TABLE_N"

1159

where TABLE is replaced by the name of the table that contains the

1160

constraint and N is an integer beginning with 1 and increasing by one

1161

with each constraint seen in the table definition.</p>

1162

1163

<p>The sqlite_master.tbl_name column holds the name of a table or view

1164

that the object is associated with. For a table or view, the

1165

tbl_name column is a copy of the name column. For an index, the tbl_name

1166

is the name of the table that is indexed. For a trigger, the tbl_name

1167

column stores the name of the table or view that causes the trigger

1168

to fire.</p>

1169

1170

<p>The sqlite_master.rootpage column stores the page number of the root

1171

b-tree page for tables and indices. For rows that define views, triggers,

1172

and virtual tables, the rootpage column is 0 or NULL.</p>

1173

1174

<p>The sqlite_master.sql column stores SQL text that describes the

1175

object. This SQL text is a <a href="lang_createtable.html">CREATE TABLE</a>, <a href="lang_createvtab.html">CREATE VIRTUAL TABLE</a>,

1176

<a href="lang_createindex.html">CREATE INDEX</a>,

1177

<a href="lang_createview.html">CREATE VIEW</a>, or <a href="lang_createtrigger.html">CREATE TRIGGER</a> statement that if evaluated against

1178

the database file when it is the main database of a <a href="c3ref/sqlite3.html">database connection</a>

1179

would recreated the object. The text is usually a copy of the original

1180

statement used to create the object but with normalizations applied so

1181

that the text conforms to the following rules:

1182

1183

<ul>

1184

<li>The CREATE, TABLE, VIEW, TRIGGER, and INDEX keywords at the beginning

1185

of the statement are converted to all upper case letters.

1186

<li>The TEMP or TEMPORARY keyword is removed if it occurs after the

1187

initial CREATE keyword.

1188

<li>Any database name qualifier that occurs prior to the name of the

1189

object being created is removed.

1190

<li>Leading spaces are removed.

1191

<li>All spaces following the first two keywords are converted into a single

1192

space.

1193

</ul>

1194

1195

<p>The text in the sqlite_master.sql column is a copy of the original

1196

CREATE statement text that created the object, except normalized as

1197

described above and as modified by subsequent <a href="lang_altertable.html">ALTER TABLE</a> statements.

1198

The sqlite_master.sql is NULL for the <a href="fileformat2.html#intschema">internal indices</a> that are

1199

automatically created by <a href="lang_createtable.html#uniqueconst">UNIQUE</a> or <a href="lang_createtable.html#primkeyconst">PRIMARY KEY</a> constraints.</p>

1200

1201

1202

1203

1204

<h4>2.5.1 Internal Schema Objects</h4>

1205

1206

<p>In addition to the tables, indices, views, and triggers created by

1207

the application and/or the developer using CREATE statements SQL, the

1208

sqlite_master table may contain zero or more entries for

1209

<i>internal schema objects</i> that are created by SQLite for its

1210

own internal use. The names of internal schema objects

1211

always begin with "sqlite_" and any table, index, view, or trigger

1212

whose name begins with "sqlite_" is an internal schema object.

1213

SQLite prohibits applications from creating objects whose names begin

1214

with "sqlite_".

1215

1216

<p>Internal schema objects used by SQLite may include the following:

1217

1218

<ul>

1219

<li><p>Indices with names of the form "sqlite_autoindex_TABLE_N" that

1220

are used to implement <a href="lang_createtable.html#uniqueconst">UNIQUE</a> and <a href="lang_createtable.html#primkeyconst">PRIMARY KEY</a> constraints on

1221

ordinary tables.

1222

1223

<li><p>A table with the name "sqlite_sequence" that is used to keep track

1224

of the maximum historical <a href="lang_createtable.html#rowid">INTEGER PRIMARY KEY</a> for a table that

1225

using <a href="autoinc.html">AUTOINCREMENT</a>.

1226

1227

<li><p>Tables with names of the form "sqlite_statN" where N is an integer.

1228

Such tables store database statistics gathered by the <a href="lang_analyze.html">ANALYZE</a>

1229

command and used by the query planner to help determine the best

1230

algorithm to use for each query.

1231

</ul>

1232

1233

<p>Additional internal schema objects names, always beginning with "sqlite_",

1234

may be added to the SQLite file format in future releases.

1235

1236

1237

1238

<h4>2.5.2 The sqlite_sequence table</h4>

1239

1240

<p>The sqlite_sequence table is an internal table used to help implement

1241

<a href="autoinc.html">AUTOINCREMENT</a>. The sqlite_sequence table is created automatically

1242

whenever any ordinary table with an AUTOINCREMENT integer primary

1243

key is created. Once created, the sqlite_sequence table exists in the

1244

sqlite_master table forever; it cannot be dropped.

1245

The schema for the sqlite_sequence table is:

1246

1247

1248

CREATE TABLE sqlite_sequence(name,seq);

1249

</pre></blockquote>

1250

1251

<p>There is a single row in the sqlite_sequence table for each ordinary

1252

table that uses AUTOINCREMENT. The name of the table (as it appears in

1253

sqlite_master.name) is in the sqlite_sequence.main field and the largest

1254

<a href="lang_createtable.html#rowid">INTEGER PRIMARY KEY</a> ever used by that table is in the sqlite_sequence.seq

1255

field. New automatically generated integer primary keys for AUTOINCREMENT

1256

tables are guaranteed to be larger than the sqlite_sequence.seq field for

1257

that table.

1258

If the sqlite_sequence.seq field of an AUTOINCREMENT table is already at

1259

the largest integer value (9223372036854775807) then attempts to add new

1260

rows to that table with an automatically generated integer primary will fail

1261

with an <a href="c3ref/c_abort.html">SQLITE_FULL</a> error.

1262

The sqlite_sequence.seq field is automatically updated if required when

1263

new entries are added to an AUTOINCREMENT table.

1264

The sqlite_sequence row for an AUTOINCREMENT table is automatically deleted

1265

when the table is dropped.

1266

If the sqlite_sequence row for an AUTOINCREMENT table does not exist when

1267

the AUTOINCREMENT table is updated, then a new sqlite_sequence row is created.

1268

If the sqlite_sequence.seq value for an AUTOINCREMENT table is manually

1269

set to something other than an integer and there is a subsequent attempt to

1270

insert the or update the AUTOINCREMENT table, then the behavior is undefined.

1271

1272

<p>Application code is allowed to modify the sqlite_sequence table, to add

1273

new rows, to delete rows, or to modify existing rows. However, application

1274

code cannot create the sqlite_sequence table if it does not already exist.

1275

Application code can delete all entries from the sqlite_sequence table,

1276

but application code cannot drop the sqlite_sequence table.

1277

1278

1279

1280

<h4>2.5.3 The sqlite_stat1 table</h4>

1281

1282

<p>The sqlite_stat1 is an internal table created by the <a href="lang_analyze.html">ANALYZE</a> command

1283

and used to hold supplemental information about tables and indices that the

1284

query planner can use to help it find better ways of performing queries.

1285

Applications can update, delete from, insert into or drop the sqlite_stat1

1286

table, but may not create or alter the sqlite_stat1 table.

1287

The schema of the sqlite_stat1 table is as follows:

1288

1289

1290

CREATE TABLE sqlite_stat1(tbl,idx,stat);

1291

</pre></blockquote>

1292

1293

<p>There is normally one row per index, with the index identified by the

1294

name in the sqlite_stat1.idx column. The sqlite_stat1.tbl column is

1295

the name of the table to which the index belongs. In each such row,

1296

the sqlite_stat.stat column will be

1297

a string consisting of a list of integers. The first integer in this

1298

list is the number of rows in the index and in the table. The second

1299

integer is the average number of rows in the index that have the same

1300

value in the first column of the index. The third integer is the average

1301

number of rows in the index that have the same value for the first two

1302

columns. The N-th integer (for N>1) is the average number of rows in

1303

the index which have the same value for the first N-1 columns. For

1304

a K-column index, there will be K+1 integers in the stat column. If

1305

the index is unique, then the last integer will be 1.

1306

1307

<p>The list of integers in the stat column can optionally be followed

1308

by the keyword "unordered". The "unordered" keyword, if it is present,

1309

must be separated from the last integer by a single space. If the

1310

"unordered" keyword is present, then the query planner assumes that

1311

the index is unordered and will not use the index for a range query.

1312

1313

<p>If the sqlite_stat1.idx column is NULL, then the sqlite_stat1.stat

1314

column contains a single integer which is the (estimated) number of

1315

rows in the table identified by sqlite_stat1.tbl.

1316

1317

1318

1319

<h4>2.5.4 The sqlite_stat2 table</h4>

1320

1321

<p>The sqlite_stat2 is only created and is only used if SQLite is compiled

1322

with SQLITE_ENABLE_STAT2 and if the SQLite version number is between

1323

3.6.18 and 3.7.8. The sqlite_stat2 table is neither read nor written by any

1324

version of SQLite before 3.6.18 nor after 3.7.8.

1325

The sqlite_stat2 table contains additional information

1326

about the distribution of keys within an index.

1327

The schema of the sqlite_stat2 table is as follows:

1328

1329

1330

CREATE TABLE sqlite_stat2(tbl,idx,sampleno,sample);

1331

</pre></blockquote>

1332

1333

<p>The sqlite_stat2.idx column and the sqlite_stat2.tbl column in each

1334

row of the sqlite_stat2 table identify an index described by that row.

1335

There are usually 10 rows in the sqlite_stat2

1336

table for each index.

1337

1338

<p>The sqlite_stat2 entries for an index that have sqlite_stat2.sampleno

1339

between 0 and 9 inclusive are samples of the left-most key value in the

1340

index taken at evenly spaced points along the index.

1341

Let C be the number of rows in the index.

1342

Then the sampled rows are given by

1343

1344

1345

rownumber = (i*C*2 + C)/20

1346

</blockquote>

1347

1348

<p>The variable i in the previous expression varies between 0 and 9.

1349

Conceptually, the index space is divided into

1350

10 uniform buckets and the samples are the middle row from each bucket.

1351

1352

<p>The format for sqlite_stat2 is recorded here for legacy reference.

1353

Recent versions of SQLite no longer support sqlite_stat2 and the

1354

sqlite_stat2 table, it is exists, is simply ignored.

1355

1356

1357

1358

<h4>2.5.5 The sqlite_stat3 table</h4>

1359

1360

<p>The sqlite_stat3 is only created and is only used if SQLite is compiled

1361

with <a href="compile.html#enable_stat3">SQLITE_ENABLE_STAT3</a> and if the SQLite version number is

1362

3.7.9 or greater. The sqlite_stat3 table is neither read nor written by any

1363

version of SQLite before 3.6.9.

1364

The sqlite_stat3 table contains additional information

1365

about the distribution of keys within an index, information that the

1366

query planner can use to devise better and faster query algorithms.

1367

The schema of the sqlite_stat3 table is as follows:

1368

1369

1370

CREATE TABLE sqlite_stat3(tbl,idx,nEq,nLt,nDLt,sample);

1371

</pre></blockquote>

1372

1373

<p>There are usually multiple entries in the sqlite_stat3 table for each index.

1374

The sqlite_stat3.sample column holds the value of the left-most field of an

1375

index identified by the sqlite_stat3.idx and the sqlite_stat3.tbl columns.

1376

If the sqlite_stat3.idx and sqlite_stat3.tbl

1377

columns hold the same value, then that row contains a sample from

1378

the <a href="lang_createtable.html#rowid">INTEGER PRIMARY KEY</a> of the table.

1379

The sqlite_stat3.nEq column holds the approximate

1380

number of entries in the index whose left-most column exactly matches

1381

the sample.

1382

The sqlite_stat3.nLt holds the approximate number of entries in the

1383

index whose left-most column is less than the sample.

1384

The sqlite_stat3.nDLt column holds the approximate

1385

number of distinct left-most entries in the index that are less than

1386

the sample.

1387

1388

<p>Future versions of SQLite might change to store a string containing

1389

multiple integers values in the sqlite_stat3.nDLt column, a string in which

1390

the first integer will be the number of prior index entries that are

1391

distinct in the left-most column, the second integer is the number of

1392

prior index entries that are distinct in the first two columns, the

1393

third integer is the number of prior index entries that are distinct

1394

in the first three columns, and so forth With such an extension, the

1395

nDLt field will become similar in function to the sqlite_stat1.stat field.

1396

1397

<p>There can be an arbitrary number of sqlite_stat3 entries per index.

1398

The <a href="lang_analyze.html">ANALYZE</a> command will typically generate sqlite_stat3 tables

1399

that contain between 10 and 40 samples that are distributed across

1400

the key space and with large nEq values.

1401

1402

1403

1404

<h2>3.0 The Rollback Journal</h2>

1405

1406

<p>The rollback journal is a file associated with each SQLite database

1407

file that hold information used to restore the database file to its initial

1408

state during the course of a transaction.

1409

The rollback journal file is always located in the same

1410

directory as the database

1411

file and has the same name as the database file but with the string

1412

"<tt>-journal</tt>" appended. There can only be a single rollback journal

1413

associated with a give database and hence there can only be one write

1414

transaction open against a single database at one time.</p>

1415

1416

<p>If a transaction is aborted due to an application crash, an operating

1417

system crash, or a hardware power failure or crash, then the database may

1418

be left in an inconsistent state. The next time SQLite attempts to open

1419

the database file, the presence of the rollback journal file will be

1420

detected and the journal will be automatically played back to restore the

1421

database to its state at the start of the incomplete transaction.</p>

1422

1423

<p>A rollback journal is only considered to be valid if it exists and

1424

contains a valid header. Hence a transaction can be committed in one

1425

of three ways:

1426

<ol>

1427

<li>The rollback journal file can be deleted,

1428

<li>The rollback journal file can be truncated to zero length, or

1429

<li>The header of the rollback journal can be overwritten with

1430

invalid header text (for example, all zeros).

1431

</ol>

1432

These three ways of committing a transaction correspond to the DELETE,

1433

TRUNCATE, and PERSIST settings, respectively, of the <a href="pragma.html#pragma_journal_mode">journal_mode pragma</a>.

1434

</p>

1435

1436

1437

<p>A valid rollback journal begins with a header in the following format:</p>

1438

1439

1440

<i>Rollback Journal Header Format</i><br>

1441

1442

<tr><th>Offset<th>Size<th>Description

1443

<tr><td valign=top align=center>0

1444

<td valign=top align=center>8

1445

<td>Header string: 0xd9, 0xd5, 0x05, 0xf9, 0x20, 0xa1, 0x63, 0xd7

1446

<tr><td valign=top align=center>8

1447

<td valign=top align=center>4

1448

<td>The "Page Count" - The number of pages in the next segment of the

1449

journal, or -1 to

1450

mean all content to the end of the file

1451

<tr><td valign=top align=center>12

1452

<td valign=top align=center>4

1453

<td>A random nonce for the checksum

1454

<tr><td valign=top align=center>16

1455

<td valign=top align=center>4

1456

<td>Initial size of the database in pages

1457

<tr><td valign=top align=center>20

1458

<td valign=top align=center>4

1459

<td>Size of a disk sector assumed by the process that wrote this

1460

journal.

1461

<tr><td valign=top align=center>24

1462

<td valign=top align=center>4

1463

<td>Size of pages in this journal.

1464

</table>

1465

</center>

1466

1467

<p>A rollback journal header is padded with zeros out to the size of a

1468

single sector (as defined by the sector size integer at offset 20).

1469

The header is in a sector by itself so that if a power loss occurs while

1470

writing the sector, information that follows the header will be

1471

(hopefully) undamaged.</p>

1472

1473

<p>After the header and zero padding are zero or more page records. Each

1474

page record stores a copy of the content of a page from the database file

1475

before it was changed. The same page may not appear more than once

1476

within a single rollback journal.

1477

To rollback an incomplete transaction, a process

1478

has merely to read the rollback journal from beginning to end and

1479

write pages found in the journal back into the database file at the

1480

appropriate location.</p>

1481

1482

<p>Let the database page size (the value of the integer at offset 24

1483

in the journal header) be N.

1484

Then the format of a page record is as follows:</p>

1485

1486

1487

<i>Rollback Journal Page Record Format</i><br>

1488

1489

<tr><th>Offset<th>Size<th>Description

1490

<tr><td valign=top align=center>0

1491

<td valign=top align=center>4

1492

<td>The page number in the database file

1493

<tr><td valign=top align=center>4

1494

<td valign=top align=center>N

1495

<td>Original content of the page prior to the start of the transaction

1496

<tr><td valign=top align=center>N+4

1497

<td valign=top align=center>4

1498

<td>Checksum

1499

</table>

1500

</center>

1501

1502

1503

<p>The checksum is an unsigned 32-bit integer computed as follows:</p>

1504

1505

<ol>

1506

<li>Initialize the checksum to the checksum nonce value found in the

1507

journal header at offset 12.

1508

<li>Initialize index X to be N-200 (where N is the size of a database page

1509

in bytes.

1510

<li>Interpret the four bytes at offset X into the page as a 4-byte big-endian

1511

unsigned integer. Add the value of that integer to the checksum.

1512

<li>Subtrace 200 from X.

1513

<li>If X is greater than or equal to zero, go back to step 3.

1514

</ol>

1515

1516

<p>The checksum value is used to guard against incomplete writes of

1517

a journal page record following a power failure. A different random nonce

1518

is used each time a transaction is started in order to minimize the risk

1519

that unwritten sectors might by chance contain data from the same page

1520

that was a part of prior journals. By changing the nonce for each

1521

transaction, stale data on disk will still generate an incorrect checksum

1522

and be detected with high probability. The checksum only uses a sparse sample

1523

of 32-bit words from the data record for performance reasons - design studies

1524

during the planning phases of SQLite 3.0.0 showed

1525

a significant performance hit in checksumming the entire page.</p>

1526

1527

<p>Let the page count value at offset 8 in the journal header be M.

1528

If M is greater than zero then after M page records the journal file

1529

may be zero padded out to the next multiple of the sector size and another

1530

journal header may be inserted. All journal headers within the same

1531

journal must contain the same database page size and sector size.</p>

1532

1533

<p>If M is -1 in the initial journal header, then the number of page records

1534

that follow is computed by computing how many page records will fit in

1535

the available space of the remainder of the journal file.</p>

1536

1537

1538

1539

<h2>4.0 The Write-Ahead Log</h2>

1540

1541

<p>Beginning with <a href="releaselog/3_7_0.html">version 3.7.0</a>, SQLite supports a new transaction

1542

control mechanism called "<a href="wal.html">write-ahead log</a>" or "<a href="wal.html">WAL</a>".

1543

When a database is in WAL mode, all connections to that database must

1544

use the WAL. A particular database will use either a rollback journal

1545

or a WAL, but not both at the same time.

1546

The WAL is always located in the same directory as the database

1547

file and has the same name as the database file but with the string

1548

"<tt>-wal</tt>" appended.</p>

1549

1550

<h3>4.1 WAL File Format</h4>

1551

1552

<p>A WAL file consists of a header followed by zero or more "frames".

1553

Each frame records the revised content of a single page from the

1554

database file. All changes to the database are recorded by writing

1555

frames into the WAL. Transactions commit when a frame is written that

1556

contains a commit marker. A single WAL can and usually does record

1557

multiple transactions. Periodically, the content of the WAL is

1558

transferred back into the database file in an operation called a

1559

"checkpoint".</p>

1560

1561

<p>A single WAL file can be reused multiple times. In other words, the

1562

WAL can fill up with frames and then be checkpointed and then new

1563

frames can overwrite the old ones. A WAL always grows from beginning

1564

toward the end. Checksums and counters attached to each frame are

1565

used to determine which frames within the WAL are valid and which

1566

are leftovers from prior checkpoints.</p>

1567

1568

<p>The WAL header is 32 bytes in size and consists of the following eight

1569

big-endian 32-bit unsigned integer values:</p>

1570

1571

1572

<i>WAL Header Format</i><br>

1573

1574

<tr><th>Offset<th>Size<th>Description

1575

<tr><td valign=top align=center>0<td valign=top align=center>4

1576

<td>Magic number. 0x377f0682 or 0x377f0683

1577

<tr><td valign=top align=center>4<td valign=top align=center>4

1578

<td>File format version. Currently 3007000.

1579

<tr><td valign=top align=center>8<td valign=top align=center>4

1580

<td>Database page size. Example: 1024

1581

<tr><td valign=top align=center>12<td valign=top align=center>4

1582

<td>Checkpoint sequence number

1583

<tr><td valign=top align=center>16<td valign=top align=center>4

1584

<td>Salt-1: random integer incremented with each checkpoint

1585

<tr><td valign=top align=center>20<td valign=top align=center>4

1586

<td>Salt-2: a different random number for each checkpoint

1587

<tr><td valign=top align=center>24<td valign=top align=center>4

1588

<td>Checksum-1: First part of a checksum on the first 24 bytes of header

1589

<tr><td valign=top align=center>28<td valign=top align=center>4

1590

<td>Checksum-2: Second part of the checksum on the first 24 bytes of header

1591

</table>

1592

</center>

1593

1594

<p>Immediately following the wal-header are zero or more frames. Each

1595

frame consists of a 24-byte frame-header followed by a <i>page-size</i> bytes

1596

of page data. The frame-header is six big-endian 32-bit unsigned

1597

integer values, as follows:

1598

1599

1600

<i>WAL Frame Header Format</i><br>

1601

1602

<tr><th>Offset<th>Size<th>Description

1603

<tr><td valign=top align=center>0<td valign=top align=center>4

1604

<td>Page number

1605

<tr><td valign=top align=center>4<td valign=top align=center>4

1606

<td>For commit records, the size of the database file in pages

1607

after the commit. For all other records, zero.

1608

<tr><td valign=top align=center>8<td valign=top align=center>4

1609

<td>Salt-1 copied from the WAL header

1610

<tr><td valign=top align=center>12<td valign=top align=center>4

1611

<td>Salt-2 copied from the WAL header

1612

<tr><td valign=top align=center>16<td valign=top align=center>4

1613

<td>Checksum-1: Cumulative checksum up through and including this page

1614

<tr><td valign=top align=center>20<td valign=top align=center>4

1615

<td>Checksum-2: Second half of the cumulative checksum.

1616

</table>

1617

</center>

1618

1619

<p>A frame is considered valid if and only if the following conditions are

1620

true:</p>

1621

1622

<ol>

1623

<li><p>The salt-1 and salt-2 values in the frame-header match

1624

salt values in the wal-header</p></li>

1625

1626

<li><p>The checksum values in the final 8 bytes of the frame-header

1627

exactly match the checksum computed consecutively on the

1628

WAL header and the first 8 bytes and the content of all frames

1629

up to and including the current frame.</p></li></li>

1630

</ol>

1631

1632

1633

1634

<h3>4.2 Checksum Algorithm</h3>

1635

1636

<p>The checksum is computed by interpreting the input as

1637

an even number of unsigned 32-bit integers: x(0) through x(N).

1638

The 32-bit integers are big-endian if the

1639

magic number in the first 4 bytes of the WAL header is 0x377f0683 and

1640

the integers are little-endian if the magic number is 0x377f0682.

1641

The checksum values are always stored in the frame header in a

1642

big-endian format regardless of which byte order is used to compute

1643

the checksum.</p>

1644

1645

<p>The checksum algorithm only works for content which is a multiple of

1646

8 bytes in length. In other words, if the inputs are x(0) through x(N)

1647

then N must be odd.

1648

The checksum algorithm is as follows:

1649

1650

1651

s0 = s1 = 0

1652

for i from 0 to n-1 step 2:

1653

s0 += x(i) + s1;

1654

s1 += x(i+1) + s0;

1655

endfor

1656

# result in s0 and s1

1657

</pre></blockquote>

1658

1659

<p>The outputs s0 and s1 are both weighted checksums using Fibonacci weights

1660

in reverse order. (The largest Fibonacci weight occurs on the first element

1661

of the sequence being summed.) The s1 value spans all 32-bit integer

1662

terms of the sequence whereas s0 omits the final term.</p>

1663

1664

<h3>4.3 Checkpoint Algorithm</h3>

1665

1666

<p>On a <a href="wal.html#ckpt">checkpoint</a>, the WAL is first flushed to persistent storage using

1667

the xSync method of the <a href="c3ref/io_methods.html">VFS</a>.

1668

Then valid content of the WAL is transferred into the database file.

1669

Finally, the database is flushed to persistent storage using another

1670

xSync method call.

1671

The xSync operations serve as write barriers - all writes launched

1672

before the xSync must complete before any write that launches after the

1673

xSync begins.</p>

1674

1675

<p>After each checkpoint, the WAL header salt-1 value is incremented and the

1676

salt-2 value is randomized. This prevents old and new frames in the WAL from

1677

being considered valid at the same time and being checkpointing together

1678

following a crash.</p>

1679

1680

1681

1682

<h3>4.4 Reader Algorithm</h3>

1683

1684

<p>To read a page from the database (call it page number P), a reader

1685

first checks the WAL to see if it contains page P. If so, then the

1686

last valid instance of page P that is followed by a commit frame

1687

or is a commit frame itself becomes the value read. If the WAL

1688

contains no copies of page P that are valid and which are a commit

1689

frame or are followed by a commit frame, then page P is read from

1690

the database file.</p>

1691

1692

<p>To start a read transaction, the reader records the index of the last

1693

valid frame in the WAL. The reader uses this recorded "mxFrame" value

1694

for all subsequent read operations. New transactions can be appended

1695

to the WAL, but as long as the reader uses its original mxFrame value

1696

and ignores subsequently appended content, the reader will see a

1697

consistent snapshot of the database from a single point in time.

1698

This technique allows multiple concurrent readers to view different

1699

versions of the database content simultaneously.</p>

1700

1701

<p>The reader algorithm in the previous paragraphs works correctly, but

1702

because frames for page P can appear anywhere within the WAL, the

1703

reader has to scan the entire WAL looking for page P frames. If the

1704

WAL is large (multiple megabytes is typical) that scan can be slow,

1705

and read performance suffers. To overcome this problem, a separate

1706

data structure called the wal-index is maintained to expedite the

1707

search for frames of a particular page.</p>

1708

1709

1710

1711

<h3>4.5 WAL-Index Format</h3>

1712

1713

<p>Conceptually, the wal-index is shared memory, though the current

1714

VFS implementations use a mmapped file for the wal-index. The mmapped

1715

file is in the same directory as the database and has the same name

1716

as the database with a "<tt>-shm</tt>" suffix appended. Because

1717

the wal-index is shared memory, SQLite does not support

1718

<a href="pragma.html#pragma_journal_mode">journal_mode=WAL</a>

1719

on a network filesystem when clients are on different machines.

1720

All users of the database must be able to share the same memory.</p>

1721

1722

<p>The purpose of the wal-index is to answer this question quickly:</p>

1723

1724

1725

Given a page number P and a maximum WAL frame index M,

1726

return the largest WAL frame index for page P that does not exceed M,

1727

or return NULL if there are no frames for page P that do not exceed M.

1728

</i></blockquote>

1729

1730

<p>The <i>M</i> value in the previous paragraph is the "mxFrame" value

1731

defined in <a href="fileformat2.html#walread">section 4.4</a> that is read at the start

1732

of a transaction and which defines the maximum frame from the WAL that

1733

the reader will use.</p>

1734

1735

<p>The wal-index is transient. After a crash, the wal-index is

1736

reconstructed from the original WAL file. The VFS is required

1737

to either truncate or zero the header of the wal-index when the last

1738

connection to it closes. Because the wal-index is transient, it can

1739

use an architecture-specific format; it does not have to be cross-platform.

1740

Hence, unlike the database and WAL file formats which store all values

1741

as big endian, the wal-index stores multi-byte values in the native

1742

byte order of the host computer.</p>

1743

1744

<p>This document is concerned with the persistent state of the database

1745

file, and since the wal-index is a transient structure, no further

1746

information about the format of the wal-index will be provided here.

1747

Complete details on the format of the wal-index are contained within

1748

comments in SQLite source code.</p>

1749