<?xml version="1.0" encoding="utf-8"?>
<!-- Copyright (c) 2007-2010 Nokia Corporation and/or its subsidiary(-ies) All rights reserved. -->
<!-- This component and the accompanying materials are made available under the terms of the License 
"Eclipse Public License v1.0" which accompanies this distribution, 
and is available at the URL "http://www.eclipse.org/legal/epl-v10.html". -->
<!-- Initial Contributors:
    Nokia Corporation - initial contribution.
Contributors: 
-->
<!DOCTYPE concept
  PUBLIC "-//OASIS//DTD DITA Concept//EN" "concept.dtd">
<concept id="GUID-ACCCB148-DAF9-59EC-B585-8EF632B9BF04" xml:lang="en"><title>SQL Joins</title><shortdesc>This guide explains how to use CROSS JOIN phrases to override the
optimizer's ordering of tables.</shortdesc><prolog><metadata><keywords/></metadata></prolog><conbody>
<section id="GUID-C6BDCE52-468D-459F-980C-A9041B56BDF1"><title>Introduction</title> <p>SQLite uses the “CROSS JOIN” phrase
as a means to override the table reordering decisions of the query optimizer.
The CROSS JOIN connector is rarely needed and should probably never be used
prior to the final performance tuning phase of application development. Even
then, SQLite usually gets the order of tables in a join right without any
extra help. But on those rare occasions when SQLite gets it wrong, the CROSS
JOIN connector is an invaluable way of tweaking the optimizer to do what you
want. </p> <p><b>Intended
audience:</b> </p> <p>This document is intended to be used by Symbian platform
licensees and third party application developers. </p> </section>
<section id="GUID-8B5F579E-B94D-527C-9530-367B5B0729C9"><title>Use CROSS JOIN
to Force a Particular Join Ordering</title> <p>The SQLite query optimizer
will attempt to reorder the tables in a join in order to find the most efficient
way to evaluate the join. The optimizer usually does this job well, but occasionally
it will make a bad choice. When that happens, it might be necessary to override
the optimizer's choice by explicitly specifying the order of tables in the
SELECT statement. </p> <p>To illustrate the problem, consider the following
schema: </p> <codeblock id="GUID-8B2D4E3C-7231-5D63-B8CD-CD687750CD1E" xml:space="preserve">
CREATE TABLE node(
    id INTEGER PRIMARY KEY,
    name TEXT
);

CREATE INDEX node_idx ON node(name);

CREATE TABLE edge(
    orig INTEGER REFERENCES node,
    dest INTEGER REFERENCES node,
    PRIMARY KEY(orig, dest)
);

CREATE INDEX edge_idx ON edge(dest,orig);
</codeblock> <p>This schema defines a directed graph with the ability to store
a name on each node of the graph. Similar designs (though usually more complicated)
arise frequently in application development. Now consider a three-way join
against the above schema: </p> <codeblock id="GUID-61383F86-E84F-58F4-B2B1-81CD25635B88" xml:space="preserve">
SELECT e.*
FROM edge AS e,
 node AS n1,
 node AS n2
WHERE n1.name = 'alice'
 AND n2.name = 'bob'
 AND e.orig = n1.id
 AND e.dest = n2.id;
</codeblock> <p>This query asks for information about all edges that go from
nodes labelled “alice” over to nodes labelled “bob”. </p> <p>There are many
ways that the optimizer might choose to implement this query, but they all
boil down to two basic designs. The first option looks for edges between all
pairs of nodes. The following pseudocode illustrates: </p> <codeblock id="GUID-19A9F537-D791-5894-9FA9-E205B3768CF7" xml:space="preserve">
foreach n1 where n1.name='alice' do:
    foreach n2 where n2.name='bob' do:
        foreach e where e.orig=n1.id and e.dest=n2.id do:
            return e.*
        end
    end
end
</codeblock> <p>The second design is to loop over all 'alice' nodes and follow
edges off of those nodes looking for nodes named 'bob'. (The roles of 'alice'
and 'bob' might be reversed here without changing the fundamental character
or the algorithm): </p> <codeblock id="GUID-02A72F7B-D5AB-5306-95F9-9832EF05FB25" xml:space="preserve">
foreach n1 where n1.name='alice' do:
    foreach e where e.orig=n1.id do:
        foreach n2 where n2.id=e.dest and n2.name='bob' do:
            return e.*
        end
    end
end
</codeblock> <p>The first algorithm above corresponds to a join order of n1-n2-e.
The second algorithm corresponds to a join order of n1-e-n2. </p> <p>The question
the optimizer has to answer is which of these two algorithms is likely to
give the fastest result, and it turns out that the answer depends on the nature
of the data stored in the database. </p> <p>Let the number of alice nodes
be M and the number of bob nodes be N. Consider two scenarios: In the first
scenario, M and N are both 2 but there are thousands of edges on each node.
In this case, the first algorithm is preferred. With the first algorithm,
the inner loop checks for the existence of an edge between a pair of nodes
and outputs the result if found. But because there are only 2 alice and bob
nodes each, the inner loop only has to run 4 times and the query is very quick. </p> <p>The
second algorithm would take much longer here. The outer loop of the second
algorithm only executes twice, but because there are a large number of edges
leaving each 'alice' node, the middle loop has to iterate many thousands of
times. So in the first scenario, we prefer to use the first algorithm. </p> <p>Now
consider the case where M and N are both 3500. But suppose each of these nodes
is connected by only one or two edges. In this case, the second algorithm
is preferred. </p> <p>With the second algorithm, the outer loop still has
to run 3500 times, but the middle loop only runs once or twice for each outer
loop and the inner loop will only run once for each middle loop, if at all.
So the total number of iterations of the inner loop is around 7000. </p> <p>The
first algorithm, on the other hand, has to run both its outer loop and its
middle loop 3500 times each, resulting in 12 million iterations of the middle
loop. Thus in the second scenario, second algorithm is nearly 2000 times faster
than the first. </p> <p>In this particular example, if you run ANALYZE on
your database to collect statistics on the tables, the optimizer will be able
to figure out the best algorithm to use. But if you do not want to run ANALYZE
or if you do not want to waste database space storing the SQLITE_STAT1 statistics
table that ANALYZE generates, you can manually override the decision of the
optimizer by specifying a particular order for tables in a join. You do this
by substituting the keyword phrase “CROSS JOIN” in place of commas in the
FROM clause. </p> <p>The “CROSS JOIN” phrase forces the table to the left
to be used before the table to the right. For example, to force the first
algorithm, write the query this way: </p> <codeblock id="GUID-E0FE82CE-0D32-535F-A4F7-EF582BFA7AE9" xml:space="preserve">
SELECT *
FROM node AS n1 CROSS JOIN
 node AS n2 CROSS JOIN
 edge AS e
WHERE n1.name = 'alice'
 AND n2.name = 'bob'
 AND e.orig = n1.id
 AND e.dest = n2.id;
</codeblock> <p>And to force the second algorithm, write the query like this: </p> <codeblock id="GUID-33AD25F2-E58E-5018-BE0C-025FC2116643" xml:space="preserve">
SELECT *
FROM node AS n1 CROSS JOIN
 edge AS e CROSS JOIN
 node AS n2
WHERE n1.name = 'alice'
 AND n2.name = 'bob'
 AND e.orig = n1.id
 AND e.dest = n2.id;
</codeblock> <p>The CROSS JOIN keyword phrase is perfectly valid SQL syntax
according to the SQL standard, but it is syntax that is rarely if ever used
in real-world SQL statements. Because it is so rarely used otherwise, SQLite
has appropriated the phrase as a means to override the table reordering decisions
of the query optimizer. </p> <p>The CROSS JOIN connector is rarely needed
and should probably never be used prior to the final performance tuning phase
of application development. Even then, SQLite usually gets the order of tables
in a join right without any extra help. But on those rare occasions when SQLite
gets it wrong, the CROSS JOIN connector is an invaluable way of tweaking the
optimizer to do what you want. </p> </section>
</conbody><related-links>
<link href="GUID-22844C28-AB5B-5A6F-8863-7269464684B4.dita"><linktext>SQL Overview</linktext>
</link>
<link href="GUID-78773BCA-ADF6-53E6-AC80-5CB2AE1F8BCC.dita"><linktext>SQL Server
Guide</linktext></link>
<link href="GUID-1F12E3F5-45B2-55EC-B021-00338277C608.dita"><linktext>SQL DB Overview</linktext>
</link>
<link href="GUID-43CA02E7-0101-5824-B91B-E15EE20C829A.dita"><linktext>Avoid Transient
Tables</linktext></link>
<link href="GUID-49A3419F-D20A-5C5D-B2FF-51724EF37704.dita"><linktext>Prevent Datafile
Corruption</linktext></link>
<link href="GUID-C2FAEBB2-4A1A-5BB0-9670-4801525CBC6A.dita"><linktext>SQL Index
Tips</linktext></link>
<link href="GUID-B994E6F7-228A-5433-B87F-91857C5D93D6.dita"><linktext>SQL Insertion
Tips</linktext></link>
<link href="GUID-4FC23DB7-4758-5DA4-81FF-0DAB169E2757.dita"><linktext>SQL Schema
Tips</linktext></link>
<link href="GUID-2A2920E0-5D40-5358-BC0C-8572CEFE078C.dita"><linktext>SQL Expressions</linktext>
</link>
<link href="GUID-126FCCCC-0E7D-59AE-959A-2F94A7319C4B.dita"><linktext>SQL Statement
Tips</linktext></link>
<link href="GUID-B7E978C1-45CA-554C-8028-D901B97BA2E0.dita"><linktext> ANALYZE
Command</linktext></link>
<link href="GUID-AF5A75D7-0687-546C-87B2-0B7DF7D33217.dita"><linktext> SQL WHERE
CLause Tips</linktext></link>
</related-links></concept>