~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

<h1 align="center">Query Planning</h1>

123

124

<p>

125

The best feature of SQL (in <u>all</u> its implementations, not just SQLite)

126

is that it is a <i>declarative</i> language, not a <i>procedural</i>

127

language. When programming in SQL you tell the system <i>what</i> you

128

want to compute, not <i>how</i> to compute it. The task of figuring out

129

the <i>how</i> is delegated to the <i>query planner</i> subsystem within

130

the SQL database engine.

131

Relieving the programmer from the chore of designing specific

132

query algorithms reduces the workload on the programmer and

133

reduces the number of opportunities for the

134

programmer to make mistakes.

135

</p>

136

137

<p>

138

Most of the time, the query planner in SQLite does a good job on its

139

own and without outside help.

140

However, the query planner needs indices to

141

work with and it usually falls to the programmer to add indices to the

142

schema that are sufficient for the query planner to accomplish its task.

143

</p>

144

145

<p>

146

This document is intended to provide programmers who are new to SQL

147

with background information to help them understand

148

what is going on behind the scenes with SQLite, which in turn should make

149

it easier for programmers to create the indices that will help the SQLite

150

query planner to pick the best plans.

151

</p>

152

153

154

155

<h2>1.0 Searching</h2>

156

157

<h3>1.1 Tables Without Indices</h3>

158

159

<p>

160

Every table in SQLite consists of zero or more rows with a unique integer

161

key (the <a href="lang_createtable.html#rowid">rowid</a> or <a href="lang_createtable.html#rowid">INTEGER PRIMARY KEY</a>) followed by content. The rows

162

are logically stored in order of increasing rowid. As an example, this

163

article uses a table named "FruitsForSale" which relates various fruits

164

to the state

165

where they are grown and their unit price at market. The schema is this:

166

</p>

167

168

169

CREATE TABLE FruitsForSale(

170

Fruit TEXT,

171

State TEXT,

172

Price REAL

173

);

174

</pre></table></center>

175

176

177

<p>

178

With some (arbitrary) data, such a table might be logically stored on disk

179

as shown in figure 1:

180

</p>

181

182

183

184

Figure 1: Logical Layout Of Table "FruitsForSale"

185

</center></p>

186

187

188

<p>

189

The key features to notice in this example is that the rowids are not

190

consecutive but they are ordered. SQLite usually creates rowids beginning

191

with one and increasing by one with each added row. But if rows are

192

deleted, gaps can appear in the sequence. And the application can control

193

the rowid assigned if desired, so that rows are not necessarily inserted

194

at the bottom. But regardless of what happens, the rowids are always

195

unique and in strictly ascending order.

196

</p>

197

198

<p>

199

Now suppose you want to look up the price of peaches. The query would

200

be as follows:

201

</p>

202

203

204

SELECT price FROM fruitsforsale WHERE fruit='Peach';

205

</pre></table></center>

206

207

208

<p>

209

In order to satisfy this query, SQLite has to read every row out of the

210

table, check to see if the "fruit" column has the value of "Peach" and if

211

so, output the "price" column from that row. The process is illustrated

212

by <a href="#fig2">figure 2</a> below.

213

This is called a <i>full table scan</i> since the entire content of the

214

table must be read and examined in order to find the one row of interest.

215

With a table of only 7 rows, this is not a big deal, but if your table

216

contained 7 million rows, a full table scan might read megabytes of content in order to find a single 8-byte number. For that reason, one normally

217

tries to avoid full table scans.

218

</p>

219

220

221

222

Figure 2: Full Table Scan

223

</center></p>

224

225

226

<h3>1.2 Lookup By Rowid</h3>

227

228

<p>

229

One technique for avoiding a full table scan is to do lookups by

230

rowid (or by the equivalent INTEGER PRIMARY KEY). To lookup the

231

price of peaches, one would query for the entry with a rowid of 4:

232

</p>

233

234

235

SELECT price FROM fruitsforsale WHERE rowid=4;

236

</pre></table></center>

237

238

239

<p>

240

Since the information is stored in the table in rowid order, SQLite

241

can find the correct row using doing a binary search on the rowid.

242

If the table contains N element, the time required to look up the

243

desired row is proportional to logN rather than being proportional

244

to N as in a full table scan. If the table contains 10 million elements,

245

that means the query will be on the order of N/logN or about 1 million

246

times faster!

247

</p>

248

249

250

251

Figure 3: Lookup By Rowid

252

</center></p>

253

254

255

<h3>1.3 Lookup By Index</h3>

256

<p>

257

The problem with looking up information by rowid is that you probably

258

do not care what the price of "item 4" is - you want to know the price

259

of peaches. And so a rowid lookup is not helpful.

260

</p>

261

262

<p>

263

To make the original query more efficient, we can add an index on the

264

"fruit" column of the "fruitsforsale" table like this:

265

</p>

266

267

268

CREATE INDEX idx1 ON fruitsforsale(fruit);

269

</pre></table></center>

270

271

272

<p>

273

An index is another table similar to the original "fruitsforsale" table

274

but with the content (the fruit column in this case) stored in front of the

275

rowid and with all rows in content order.

276

<a href="#fig4">Figure 4</a> gives a logical view of the Idx1 index.

277

The "fruit" column is the primary key used to order the elements of the

278

table and the "rowid" is the secondary key used to break the tie when

279

two or more rows have the same "fruit". In the example, the rowid

280

has to be used as a tie-breaker for the "Orange" rows.

281

Notice that since the rowid

282

is always unique over all elements of the original table, the composite key

283

of "fruit" followed by "rowid" will be unique over all elements of the index.

284

</p>

285

286

287

288

Figure 4: An Index On The Fruit Column

289

</center></p>

290

291

292

<p>

293

With the new index in place, we can devise an alternative plan for the

294

original "Price of Peaches" query.

295

</p>

296

297

298

SELECT price FROM fruitsforsale WHERE fruit='Peach';

299

</pre></table></center>

300

301

302

<p>

303

The query starts by doing a binary search on the Idx1 index for entries

304

that have fruit='Peach'. SQLite can do this binary search on the Idx1 index

305

but not on the original FruitsForSale table because the rows in Idx1 are sorted

306

by the "fruit" column. Having found a row in the Idx1 index that has

307

fruit='Peach', the database engine can extract the rowid for that row,

308

then do a separate binary search on the original FruitsForSale table to find the

309

original row that contains fruit='Peach'. From the row in the FruitsForSale table,

310

SQLite can extract the value of the price column.

311

This procedure is illustrated by <a href="#fig5">figure 5</a>.

312

</p>

313

314

315

316

Figure 5: Indexed Lookup For The Price Of Peaches

317

</center></p>

318

319

320

<p>

321

SQLite has to do two binary searches to find the price of peaches using

322

the method show above. But for a table with a large number of rows, this

323

is still much faster than doing a full table scan.

324

</p>

325

326

<h3>1.4 Multiple Result Rows</h3>

327

328

<p>

329

In the previous query the fruit='Peach' constraint narrowed the result

330

down to a single row. But the same technique works even if multiple

331

rows are obtained. Suppose we looked up the price of Oranges instead

332

Peaches:

333

</p>

334

335

336

SELECT price FROM fruitsforsale WHERE fruit='Orange'

337

</pre></table></center>

338

339

340

Figure 6: Indexed Lookup For The Price Of Oranges

341

</center></p>

342

343

344

<p>

345

In this case, SQLite still does a single binary search to find the first

346

entry of the index where fruit='Orange'. Then it extracts the rowid from

347

the index and uses that rowid to lookup the original table entry via

348

binary search and output the price from the original table. But instead

349

of quitting, the database engine then advances to the next row of index

350

to repeat the process for next fruit='Orange' entry. Advancing to the

351

next row of an index (or table) is much less costly than doing a binary

352

search since the next row is often located on the same database page as

353

the current row. In fact, the cost of advancing to the next row is so

354

cheap in comparison to a binary search that we usually ignore it. So

355

our estimate for the total cost of this query is 3 binary searches.

356

If the number of rows of output is K and the number of rows in the table

357

is N, then in general the cost of doing the query proportional

358

to (K+1)*logN.

359

</p>

360

361

<h3>1.5 Multiple AND-Connected WHERE-Clause Terms</h3>

362

363

<p>

364

Next, suppose that you want to look up the price of not just any orange,

365

but specifically California-grown oranges. The appropriate query would

366

be as follows:

367

</p>

368

369

370

SELECT price FROM fruitsforsale WHERE fruit='Orange' AND state='CA'

371

</pre></table></center>

372

373

374

Figure 7: Indexed Lookup Of California Oranges

375

</center></p>

376

377

378

<p>

379

One approach to this query is to use the fruit='Orange' term of the WHERE

380

clause to find all rows dealing with oranges, then filter those rows

381

by rejecting any that are from states other than California. This

382

process is shown by <a href="#fig7">figure 7</a> above. This is a perfectly

383

reasonable approach in most cases. Yes, the database engine did have

384

to do an extra binary search for the Florida orange row that was

385

later rejected, so it was not as efficient as we might hope, though

386

for many applications it is efficient enough.

387

</p>

388

389

<p>

390

Suppose that in addition to the index on "fruit" there was also

391

an index on "state".

392

</p>

393

394

395

CREATE INDEX Idx2 ON fruitsforsale(state);

396

</pre></table></center>

397

398

399

Figure 8: Index On The State Column

400

</center></p>

401

402

403

<p>

404

The "state" index works just like the "fruit" index in that it is a

405

new table with an extra column in front of the rowid and sorted by

406

that extra column as the primary key. The only difference is that

407

in Idx2, the first column is "state" instead of "fruit" as it is with

408

Idx1. In our example data set, the is more redundancy in the "state"

409

column and so they are more duplicate entries. The ties are still

410

resolved using the rowid.

411

</p>

412

413

<p>

414

Using the new Idx2 index on "state", SQLite has another option for

415

lookup up the price of California oranges: it can look up every row

416

that contains fruit from California and filter out those rows that

417

are not oranges.

418

</p>

419

420

421

422

Figure 9: Indexed Lookup Of California Oranges

423

</center></p>

424

425

426

<p>

427

Using Idx2 instead of Idx1 causes SQLite to examine a different set of

428

rows, but it gets the same answer in the end (which is very important -

429

remember that indices should never change the answer, only help SQLite to

430

get to the answer more quickly) and it does the same amount of work.

431

So the Idx2 index did not help performance in this case.

432

</p>

433

434

<p>

435

The last two queries take the same amount of time, in our example.

436

So which index, Idx1 or Idx2, will SQLite choose? If the

437

<a href="lang_analyze.html">ANALYZE</a> command has been run on the database, so that SQLite has

438

had an opportunity to gather statistics about the available indices,

439

then SQLite will know that the Idx1 table usually narrows the search

440

down to a single item (our example of fruit='Orange' is the exception

441

to this rule) where as the Idx table will normally only narrow the

442

search down to two rows. So, if all else is equal, SQLite will

443

choose Idx1 with the hope of narrowing the search to as small

444

a number of rows as possible. This choice is only possible because

445

of the statistics provided by <a href="lang_analyze.html">ANALYZE</a>. If <a href="lang_analyze.html">ANALYZE</a> has not been

446

run then the choice of which index to use is arbitrary.

447

</p>

448

449

<h3>1.6 Multi-Column Indices</h3>

450

451

<p>

452

To get the maximum performance out of a query with multiple AND-connected

453

terms in the WHERE clause, you really want a multi-column index with

454

columns for each of the AND terms. In this case we create a new index

455

on the "fruit" and "state" columns of FruitsForSale:

456

</p>

457

458

459

CREATE INDEX Idx3 ON FruitsForSale(fruit, state);

460

</pre></table></center>

461

462

463

Figure 1: A Two-Column Index

464

</center></p>

465

466

467

<p>

468

A multi-column index follows the same pattern as a single-column index;

469

the indexed columns are added in front of the rowid. The only difference

470

is that now multiple columns are added. The left-most column is the

471

primary key used for ordering the rows in the index. The second column is

472

used to break ties in the left-most column. If there were a third column,

473

it would be used to break ties for the first to columns. And so forth for

474

as many columns as their are in the index. Because rowid is guaranteed

475

to be unique, every row of the index will be unique even if all of the

476

content columns for two rows are the same. That case does not happen

477

in our sample data, but there is one case (fruit='Orange') where there

478

is a tie on the first column which must be broken by the second column.

479

</p>

480

481

<p>

482

Given the new multi-column Idx3 index, it is now possible for SQLite

483

to find the price of California oranges using only 2 binary searches:

484

</p>

485

486

487

SELECT price FROM fruitsforsale WHERE fruit='Orange' AND state='CA'

488

</pre></table></center>

489

490

491

Figure 11: Lookup Using A Two-Column Index

492

</center></p>

493

494

495

<p>

496

With the Idx3 index on both columns that are constrained by the WHERE clause,

497

SQLite can do a single binary search against Idx3 to find the one rowid

498

for California oranges, then do a single binary search to find the price

499

for that item in the original table. There are no dead-ends and no

500

wasted binary searches. This is a more efficient query.

501

</p>

502

503

<p>

504

Note that Idx3 contains all the same information as the original

505

<a href="#fig3">Idx1</a>. And so if we have Idx3, we do not really need Idx1

506

any more. The "price of peaches" query can be satisfied using Idx3

507

by simply ignoring the "state" column of Idx3:

508

</p>

509

510

511

SELECT price FROM fruitsforsale WHERE fruit='Peach'

512

</pre></table></center>

513

514

515

Figure 12: Single-Column Lookup On A Multi-Column Index

516

</center></p>

517

518

519

<p>

520

Hence, a good rule of thumb is that your database schema should never

521

contain two indices where one index is a prefix of the other. Drop the

522

index with fewer columns. SQLite will still be able to do efficient

523

lookups with the longer index.

524

</p>

525

526

527

528

<h3>1.7 Covering Indices</h3>

529

530

<p>

531

The "price of California oranges" query was made more efficient through

532

the use of a two-column index. But SQLite can do even better with a

533

three-column index that also includes the "price" column:

534

</p>

535

536

537

CREATE INDEX Idx4 ON FruitsForSale(fruit, state, price);

538

</pre></table></center>

539

540

541

Figure 13: A Covering Index

542

</center></p>

543

544

545

<p>

546

This new index contains all the columns of the original FruitsForSale table that

547

are used by the query - both the search terms and the output. We call

548

this a "covering index". Because all of the information needed is in

549

the covering index, SQLite never needs to consult the original table

550

in order to find the price.

551

</p>

552

553

554

SELECT price FROM fruitsforsale WHERE fruit='Orange' AND state='CA';

555

</pre></table></center>

556

557

558

Figure 14: Query Using A Covering Index

559

</center></p>

560

561

562

<p>

563

Hence, by adding extra "output" columns onto the end of an index, one

564

can avoid having to reference the original table and thereby

565

cut the number of binary searches for a query in half. This is a

566

constant-factor improvement in performance (roughly a doubling of

567

the speed). But on the other hand, it is also just a refinement;

568

A two-fold performance increase is not nearly as dramatic as the

569

one-million-fold increase seen when the table was first indexed.

570

And for most queries, the difference between 1 microsecond and

571

2 microseconds is unlikely to be noticed.

572

</p>

573

574

575

576

<h3>1.8 OR-Connected Terms In The WHERE Clause</h3>

577

578

<p>

579

Multi-column indices only work if the constraint terms in the WHERE

580

clause of the query are connected by AND.

581

So Idx3 and Idx4 are helpful when the search is for items that

582

are both Oranges and grown in California, but neither index would

583

be that useful if we wanted all items that were either oranges

584

<i>or</i> are grown in California.

585

</p>

586

587

588

SELECT price FROM FruitsForSale WHERE fruit='Orange' OR state='CA';

589

</pre></table></center>

590

591

592

<p>

593

When confronted with OR-connected terms in a WHERE clause, SQLite

594

examines each OR term separately and tries to use an index to

595

find the rowids associated with each term.

596

It then takes the union of the resulting rowid sets to find

597

the end result. The following figure illustrates this process:

598

</p>

599

600

601

602

Figure 15: Query With OR Constraints

603

</center></p>

604

605

606

<p>

607

The diagram above implies that SQLite computes all of the rowids first

608

and then combines them with a union operation before starting to do

609

rowid lookups on the original table. In reality, the rowid lookups

610

are interspersed with rowid computations. SQLite uses one index at

611

a time to find rowids while remembering which rowids it has seen

612

before so as to avoid duplicates. That is just an implementation

613

detail, though. The diagram, while not 100% accurate, provides a good

614

overview of what is happening.

615

</p>

616

617

<p>

618

In order for the OR-by-UNION technique shown above to be useful, there

619

must be an index available that helps resolve every OR-connected term

620

in the WHERE clause. If even a single OR-connected term is not indexed,

621

then a full table scan would have to be done in order to find the rowids

622

generated by the one term, and if SQLite has to do a full table scan, it

623

might as well do it on the original table and get all of the results in

624

a single pass without having to mess with union operations and follow-on

625

binary searches.

626

</p>

627

628

<p>

629

One can see how the OR-by-UNION technique could also be leveraged to

630

use multiple indices on queries where the WHERE clause has terms connected

631

by AND, by using an intersect operator in place of union. Many SQL

632

database engines will do just that. But the performance gain over using

633

just a single index is slight and so SQLite does not implement that technique

634

at this time. However, a future version SQLite might be enhanced to support

635

AND-by-INTERSECT.

636

</p>

637

638

639

640

<h2>2.0 Sorting</h2>

641

642

<p>

643

SQLite (like all other SQL database engines) can also use indices to

644

satisfy the ORDER BY clauses in a query, in addition to expediting

645

lookup. In other words, indices can be used to speed up sorting as

646

well as searching.

647

</p>

648

649

<p>

650

When no appropriate indices are available, a query with an ORDER BY

651

clause must be sorted as a separate step. Consider this query:

652

</p>

653

654

655

SELECT * FROM fruitsforsale ORDER BY fruit;

656

</pre></table></center>

657

658

659

<p>

660

SQLite processes this by gather all the output of query and then

661

running that output through a sorter.

662

</p>

663

664

665

666

Figure 16: Sorting Without An Index

667

</center></p>

668

669

670

<p>

671

If the number of output rows is K, then the time needed to sort is

672

proportional to KlogK. If K is small, the sorting time is usually

673

not a factor, but in a query such as the above where K==N, the time

674

needed to sort can be much greater than the time needed to do a

675

full table scan. Furthermore, the entire output is accumulated in

676

temporary storage (which might be either in main memory or on disk,

677

depending on various compile-time and run-time settings)

678

which can mean that a lot of temporary storage is required to complete

679

the query.

680

</p>

681

682

<h3>2.1 Sorting By Rowid</h3>

683

684

<p>

685

Because sorting can be expensive, SQLite works hard to convert ORDER BY

686

clauses into no-ops. If SQLite determines that output will

687

naturally appear in the order specified, then no sorting is done.

688

So, for example, if you request the output in rowid order, no sorting

689

will be done:

690

</p>

691

692

693

SELECT * FROM fruitsforsale ORDER BY rowid;

694

</pre></table></center>

695

696

697

Figure 17: Sorting By Rowid

698

</center></p>

699

700

701

<p>

702

You can also request a reverse-order sort like this:

703

</p>

704

705

706

SELECT * FROM fruitsforsale ORDER BY rowid DESC;

707

</pre></table></center>

708

709

710

<p>

711

SQLite will still omit the sorting step. But in order for output to

712

appear in the correct order, SQLite will do the table scan starting at

713

the end and working toward the beginning, rather than starting at the

714

beginning and working toward the end as shown in

715

<a href="#fig17">figure 17</a>.

716

</p>

717

718

<h3>2.2 Sorting By Index</h3>

719

720

<p>

721

Of course, ordering the output of a query by rowid is seldom useful.

722

Usually one wants to order the output by some other column.

723

</p>

724

725

<p>

726

If an index is available on the ORDER BY column, that index can be used

727

for sorting. Consider the request for all items sorted by "fruit":

728

</p>

729

730

731

SELECT * FROM fruitsforsale ORDER BY fruit;

732

</pre></table></center>

733

734

735

736

737

Figure 18: Sorting With An Index

738

</center></p>

739

740

741

<p>

742

The Idx1 index is scanned from top to bottom (or from bottom to top if

743

"ORDER BY fruit DESC" is used) in order to find the rowids for each item

744

in order by fruit. Then for each rowid, a binary search is done to lookup

745

and output that row. In this way, the output appears in the requested order

746

with the need to gather then entire output and sort it using a separate step.

747

</p>

748

749

<p>

750

But does this really save time? The number of steps in the

751

<a href="#fig16">original indexless sort</a> is proportional to NlogN since

752

that is how much time it takes to sort N rows. But when we use Idx1 as

753

shown here, we have to do N rowid lookups which take logN time each, so

754

the total time of NlogN is the same!

755

</p>

756

757

<p>

758

SQLite uses a cost-based query planner. When there are two or more ways

759

of solving the same query, SQLite tries to estimate the total amount of

760

time needed to run the query using each plan, and then uses the plan with

761

the lowest estimated cost. A cost is computed mostly from the estimated

762

time, and so this case could go either way depending on the table size and

763

what WHERE clause constraints were available, and so forth. But generally

764

speaking, the indexed sort would probably be chosen, if for no other

765

reason, because it does not need to accumulate the entire result set in

766

temporary storage before sorting and thus uses much less temporary storage.

767

</p>

768

769

<h3>2.3 Sorting By Covering Index</h3>

770

771

<p>

772

If a covering index can be used for a query, then the multiple rowid lookups

773

can be avoided and the cost of the query drops dramatically.

774

</p>

775

776

777

778

Figure 19: Sorting With A Covering Index

779

</center></p>

780

781

782

<p>

783

With a covering index, SQLite can simply walk the index from one end to the

784

other and deliver the output in time proportional to N and without having

785

allocate a large buffer to hold the result set.

786

</p>

787

788

<h2>3.0 Searching And Sorting At The Same Time</h2>

789

790

<p>

791

The previous discussion has treated searching and sorting as separate

792

topics. But in practice, it is often the case that one wants to search

793

and sort at the same time. Fortunately, it is possible to do this

794

using a single index.

795

</p>

796

797

<h3>3.1 Searching And Sorting With A Multi-Column Index</h3>

798

799

<p>

800

Suppose we want to find the prices of all kinds of oranges sorted in

801

order of the state where they are grown. The query is this:

802

</p>

803

804

805

SELECT price FROM fruitforsale WHERE fruit='Orange' ORDER BY state

806

</pre></table></center>

807

808

809

<p>

810

The query contains both a search restriction in the WHERE clause

811

and a sort order in the ORDER BY clause. Both the search and the sort

812

can be accomplished at the same time using the two-column index Idx3.

813

</p>

814

815

816

817

Figure 20: Search And Sort By Multi-Column Index

818

</center></p>

819

820

821

<p>

822

The query does a binary search on the index to find the subset of rows

823

that have fruit='Orange'. (Because the fruit column is the left-most column

824

of the index and the rows of the index are in sorted order, all such

825

rows will be adjacent.) Then it scans the matching index rows from top to

826

bottom to get the rowids for the original table, and for each rowid does

827

a binary search on the original table to find the price.

828

</p>

829

830

<p>

831

You will notice that there is no "sort" box anywhere in the above diagram.

832

The ORDER BY clause of the query has become a no-op. No sorting has to be

833

done here because the output order is by the state column and the state

834

column also happens to be the first column after the fruit column in the

835

index. So, if we scan entries of the index that have the same value for

836

the fruit column from top to bottom, those index entries are guaranteed to

837

be ordered by the state column.

838

</p>

839

840

841

842

<h3>3.2 Searching And Sorting With A Covering Index</h3>

843

844

<p>

845

A <a href="queryplanner.html#covidx">covering index</a> can also be used to search and sort at the same time.

846

Consider the following:

847

</p>

848

849

850

SELECT * FROM fruitforsale WHERE fruit='Orange' ORDER BY state

851

</pre></table></center>

852

853

854

Figure 21: Search And Sort By Covering Index

855

</center></p>

856

857

858

<p>

859

As before, SQLite does single binary search

860

for the range of rows in the covering

861

index that satisfy the WHERE clause, the scans that range from top to

862

bottom to get the desired results.

863

The rows that satisfy the WHERE clause are guaranteed to be adjacent

864

since the WHERE clause is an equality constraint on the left-most

865

column of the index. And by scanning the matching index rows from

866

top to bottom, the output is guaranteed to be ordered by state since the

867

state column is the very next column to the right of the fruit column.

868

And so the resulting query is very efficient.

869

</p>

870

871

<p>

872

SQLite can pull a similar trick for a descending ORDER BY:

873

</p>

874

875

876

SELECT * FROM fruitforsale WHERE fruit='Orange' ORDER BY state DESC

877

</pre></table></center>

878

879

880

<p>

881

The same basic algorithm is followed, except this time the matching rows

882

of the index are scanned from bottom to top instead of from top to bottom,

883

so that the states will appear in descending order.

884

</p>

885

886

<h2>To Be Continued...</h2>

887

888

<p>Further topics:</p>

889

890

<p><ul>

891

<li>How to construct a good index

892

<li>Joins and join-order

893

<li>Automatic transient indices

894

<li>How to determine what query plan SQLite is using

895

<li>Automatic detection of inefficient query plans

896

<li>Techniques for influencing what query plan SQLite chooses

897

</ul>

898

</p>

899