OUG Ireland Conference 2018

I submitted an abstract for the OUG Ireland 2018 conference, which was accepted for inclusion last Friday. The conference takes place on 22 and 23 March 2018 in the Gresham hotel on O'Connell Street in Dublin, where I presented at last year's conference. I'll link to the agenda when it is public next Monday (and here it is, a day late but never mind 🙂 OUG Ireland 2018 Conference - Agenda ).

Twitter hashtag: #ukoug_ire






Design Patterns for Database API Testing 4: REF Cursor Getter

In TRAPIT - TRansactional API Testing in Oracle, I supplied installation scripts for a new Oracle PL/SQL API testing framework, together with working example API test programs for four use cases against Oracle's HR demo schema. I linked to articles describing three of these example test programs, and the current article describes the fourth example.

The four examples were designed to cover the general categories of getting and setting data in batch or real time mode. This fourth example covers getting data in real time via a REF cursor, such as would often be used as the source for a web service.

Requirement Summary

Modern Oracle SQL is very powerful and can apply complex logic within a single statement, reducing the need for more complex procedural code. In order to show how to API test SQL that might be used in a batch getter module, we previously devised a test view, HR_Test_V, having a range of features that we might want to test in general. We can use similar SQL to demonstrate API testing of a real time getter procedure that might be used by a web service, where reference cursors are often used as output parameters. The following list of features to test is taken, in slightly modified form, from Design Patterns for Database API Testing 2: Views 1 - Design

  • Inner joins suppress driving records where there is no joining record
  • Outer joins return driving records where there is no joining record
  • Analytic functions that partition by some key, and return aggregates on the returned record set
  • Functions based on aggregates over records that include those not in the returned record set
  • Constraints based on aggregates over records that include those not in the returned record set
  • Constraints on column values

The SQL functionality can be described in words as:

  • Selected values
    • Employee name, department name, and salary
    • Manager's name
    • Ratio of employee's salary to the department average (returned employees only)
    • Ratio of employee's salary to the average salary of all employees
  • Constraints
    • Exclude employees in job 'AD_ASST'
    • Return employees for a department passed as a bind parameter
    • Do not return any records if the total salary of all employees is below 1600
  • Outer join
    • Include employees both with and without a manager

The REF cursor SQL is:

  WITH all_emps AS (
        SELECT Avg (salary) avg_sal, SUM (salary) sal_tot_g
          FROM employees e
)
SELECT e.last_name, d.department_name, m.last_name manager, e.salary,
       Round (e.salary / Avg (e.salary) OVER (PARTITION BY e.department_id), 2) sal_rat,
       Round (e.salary / a.avg_sal, 2) sal_rat_g
  FROM all_emps a
 CROSS JOIN employees e
  JOIN departments d
    ON d.department_id = e.department_id
  LEFT JOIN employees m
    ON m.employee_id = e.manager_id
 WHERE e.job_id != 'AD_ASST'
   AND a.sal_tot_g >= 1600
   AND d.department_id = :1

Notes on API Testing REF Cursor Procedures

  • A new utility function has been added to UT_Utils, Cursor_to_Array, that converts an open reference cursor to a delimited list of strings (created from an initial stand-alone procedure: A Utility for Reading REF Cursors into a List of Delimited Strings)
    • Using this utility, very little code needs to be written once the test data has been set up: One call to return the reference cursor, and a second to return the actual values in a list, to be passed at the end in a single call to the library results checker
  • The entire body section of the procedure is given below
    • Notice that c_scenario_ds_lis holds pointers to datasets to allow re-use for multiple scenarios (with different parameter data)
  l_timer_set := UT_Utils.Init (c_proc_name);
  l_act_2lis.EXTEND (c_exp_2lis.COUNT);
  l_inp_3lis.EXTEND (c_exp_2lis.COUNT);

  FOR i IN 1..c_exp_2lis.COUNT LOOP

    l_inp_3lis (i) := L2_chr_arr();
    l_inp_3lis (i).EXTEND(2);

    Setup (c_scenario_ds_lis (i), l_inp_3lis (i)(1));

    l_inp_3lis (i)(2) := L1_chr_arr (c_dep_lis(i));
    Timer_Set.Increment_Time (l_timer_set, UT_Utils.c_setup_timer);

    Emp_WS.AIP_Get_Dept_Emps (p_dep_id  => c_dep_lis(i),
                              x_emp_csr => l_emp_csr);
    l_act_2lis(i) := UT_Utils.List_or_Empty 
    (UT_Utils.Cursor_to_Array (x_csr => l_emp_csr));
    Timer_Set.Increment_Time (l_timer_set, UT_Utils.c_call_timer);
    ROLLBACK;

  END LOOP;

  UT_Utils.Check_UT_Results (c_proc_name, c_scenario_lis, l_inp_3lis, l_act_2lis, c_exp_2lis, l_timer_set, c_ms_limit,
                             c_inp_group_lis, c_inp_field_2lis, c_out_group_lis, c_out_field_2lis);

ERD

unit-testing-three-erd_rc

Design Pattern Groups

The API testing framework is centred around the concept of input and output groups, representing the data sets that respectively form the inputs to, and outputs from, the program. The records in each group are printed by the framework with column headers for each scenario. These groups are identified by the developer, and in this case they are as noted below.

Input Groups

  • Employees Table
  • Department Parameter

Output Groups

  • Select results
  • Timing of average call

Test Scenarios

The scenario descriptions start with a data set code, followed by a verbal description.

  1. DS-1, testing inner, outer joins, analytic over dep, and global ratios with 1 dep (10) - pass dep 10
  2. DS-2, testing same as 1 but with extra emp in another dep (20) - pass dep 10
  3. DS-2, as second scenario, but - pass dep 20
  4. DS-2, as second scenario, but - pass null dep
  5. DS-3, Salaries total 1500 (< threshold of 1600, so return nothing) - pass dep 10

Code Structure Diagram

unit-testing-three-csd_rc

Call Structure Table - UT_Emp_WS.ut_AIP_Get_Dept_Emps

Level 1 Level 2 Package
List_Delim Utils
Init UT_Utils
Setup UT_Emp_WS
Heading Utils
Col_Headers Utils
Ins_Emp DML_API_UT_HR
Pr_List_As_Line Utils
Increment_Time Timer_Set
AIP_Get_Dept_Emps Emp_WS
Cursor_to_Array UT_Utils
List_or_Empty UT_Utils
Check_UT_Results UT_Utils
Write_Other_Error Utils

Test Output

UNIT TEST for UT_Emp_WS.ut_AIP_Get_Dept_Emps
============================================

Employees created in setup: DS-1 - 4 emps, 1 dep (10), emp-3 has no dep, emp-4 has bad job
==========================================================================================

#  Employee id  Department id     Manager  Job id          Salary
-  -----------  -------------  ----------  ----------  ----------
1         1658             10              IT_PROG           1000
2         1659             10        1658  IT_PROG           2000
3         1660                       1658  IT_PROG           3000
4         1661             10        1658  AD_ASST           4000

Employees created in setup: DS-2 - As dataset 1 but with extra emp-5, in second dep (20)
========================================================================================

#  Employee id  Department id     Manager  Job id          Salary
-  -----------  -------------  ----------  ----------  ----------
1         1662             10              IT_PROG           1000
2         1663             10        1662  IT_PROG           2000
3         1664                       1662  IT_PROG           3000
4         1665             10        1662  AD_ASST           4000
5         1666             20        1662  IT_PROG           5000

Employees created in setup: DS-2 - As dataset 1 but with extra emp-5, in second dep (20)
========================================================================================

#  Employee id  Department id     Manager  Job id          Salary
-  -----------  -------------  ----------  ----------  ----------
1         1667             10              IT_PROG           1000
2         1668             10        1667  IT_PROG           2000
3         1669                       1667  IT_PROG           3000
4         1670             10        1667  AD_ASST           4000
5         1671             20        1667  IT_PROG           5000

Employees created in setup: DS-2 - As dataset 1 but with extra emp-5, in second dep (20)
========================================================================================

#  Employee id  Department id     Manager  Job id          Salary
-  -----------  -------------  ----------  ----------  ----------
1         1672             10              IT_PROG           1000
2         1673             10        1672  IT_PROG           2000
3         1674                       1672  IT_PROG           3000
4         1675             10        1672  AD_ASST           4000
5         1676             20        1672  IT_PROG           5000

Employees created in setup: DS-3 - As dataset 2 but with salaries * 0.1, total below reporting threshold of 1600
================================================================================================================

#  Employee id  Department id     Manager  Job id          Salary
-  -----------  -------------  ----------  ----------  ----------
1         1677             10              IT_PROG            100
2         1678             10        1677  IT_PROG            200
3         1679                       1677  IT_PROG            300
4         1680             10        1677  AD_ASST            400
5         1681             20        1677  IT_PROG            500

SCENARIO 1: DS-1, testing inner, outer joins, analytic over dep, and global ratios with 1 dep (10) - pass dep 10 {
==================================================================================================================

    INPUTS
    ======

        GROUP Employee {
        ================

            Employee Id  Last Name  Email  Hire Date    Job      Salary  Manager Id  Department Id  Updated
            -----------  ---------  -----  -----------  -------  ------  ----------  -------------  -----------
                   1658  LN_1       EM_1   01-OCT-2016  IT_PROG    1000                         10  01-OCT-2016
                   1659  LN_2       EM_2   01-OCT-2016  IT_PROG    2000        1658             10  01-OCT-2016
                   1660  LN_3       EM_3   01-OCT-2016  IT_PROG    3000        1658                 01-OCT-2016
                   1661  LN_4       EM_4   01-OCT-2016  AD_ASST    4000        1658             10  01-OCT-2016

        }
        =

        GROUP Department Parameter {
        ============================

            Department Id
            -------------
                       10

        }
        =

    OUTPUTS
    =======

        GROUP Select results: Actual = 2, Expected = 2 {
        ================================================

            F?  Name  Department      Manager  Salary  Salary Ratio (dep)  Salary Ratio (overall)
            --  ----  --------------  -------  ------  ------------------  ----------------------
                LN_1  Administration             1000                 .67                      .4
                LN_2  Administration  LN_1       2000                1.33                      .8

        } 0 failed, of 2: SUCCESS
        =========================

} 0 failed, of 2: SUCCESS
=========================

SCENARIO 2: DS-2, testing same as 1 but with extra emp in another dep (20) - pass dep 10 {
==========================================================================================

    INPUTS
    ======

        GROUP Employee {
        ================

            Employee Id  Last Name  Email  Hire Date    Job      Salary  Manager Id  Department Id  Updated
            -----------  ---------  -----  -----------  -------  ------  ----------  -------------  -----------
                   1662  LN_1       EM_1   01-OCT-2016  IT_PROG    1000                         10  01-OCT-2016
                   1663  LN_2       EM_2   01-OCT-2016  IT_PROG    2000        1662             10  01-OCT-2016
                   1664  LN_3       EM_3   01-OCT-2016  IT_PROG    3000        1662                 01-OCT-2016
                   1665  LN_4       EM_4   01-OCT-2016  AD_ASST    4000        1662             10  01-OCT-2016
                   1666  LN_5       EM_5   01-OCT-2016  IT_PROG    5000        1662             20  01-OCT-2016

        }
        =

        GROUP Department Parameter {
        ============================

            Department Id
            -------------
                       10

        }
        =

    OUTPUTS
    =======

        GROUP Select results: Actual = 2, Expected = 2 {
        ================================================

            F?  Name  Department      Manager  Salary  Salary Ratio (dep)  Salary Ratio (overall)
            --  ----  --------------  -------  ------  ------------------  ----------------------
                LN_1  Administration             1000                 .67                     .33
                LN_2  Administration  LN_1       2000                1.33                     .67

        } 0 failed, of 2: SUCCESS
        =========================

} 0 failed, of 2: SUCCESS
=========================

SCENARIO 3: DS-2, as second scenario, but - pass dep 20 {
=========================================================

    INPUTS
    ======

        GROUP Employee {
        ================

            Employee Id  Last Name  Email  Hire Date    Job      Salary  Manager Id  Department Id  Updated
            -----------  ---------  -----  -----------  -------  ------  ----------  -------------  -----------
                   1667  LN_1       EM_1   01-OCT-2016  IT_PROG    1000                         10  01-OCT-2016
                   1668  LN_2       EM_2   01-OCT-2016  IT_PROG    2000        1667             10  01-OCT-2016
                   1669  LN_3       EM_3   01-OCT-2016  IT_PROG    3000        1667                 01-OCT-2016
                   1670  LN_4       EM_4   01-OCT-2016  AD_ASST    4000        1667             10  01-OCT-2016
                   1671  LN_5       EM_5   01-OCT-2016  IT_PROG    5000        1667             20  01-OCT-2016

        }
        =

        GROUP Department Parameter {
        ============================

            Department Id
            -------------
                       20

        }
        =

    OUTPUTS
    =======

        GROUP Select results: Actual = 1, Expected = 1 {
        ================================================

            F?  Name  Department  Manager  Salary  Salary Ratio (dep)  Salary Ratio (overall)
            --  ----  ----------  -------  ------  ------------------  ----------------------
                LN_5  Marketing   LN_1       5000                   1                    1.67

        } 0 failed, of 1: SUCCESS
        =========================

} 0 failed, of 1: SUCCESS
=========================

SCENARIO 4: DS-2, as second scenario, but - pass null dep {
===========================================================

    INPUTS
    ======

        GROUP Employee {
        ================

            Employee Id  Last Name  Email  Hire Date    Job      Salary  Manager Id  Department Id  Updated
            -----------  ---------  -----  -----------  -------  ------  ----------  -------------  -----------
                   1672  LN_1       EM_1   01-OCT-2016  IT_PROG    1000                         10  01-OCT-2016
                   1673  LN_2       EM_2   01-OCT-2016  IT_PROG    2000        1672             10  01-OCT-2016
                   1674  LN_3       EM_3   01-OCT-2016  IT_PROG    3000        1672                 01-OCT-2016
                   1675  LN_4       EM_4   01-OCT-2016  AD_ASST    4000        1672             10  01-OCT-2016
                   1676  LN_5       EM_5   01-OCT-2016  IT_PROG    5000        1672             20  01-OCT-2016

        }
        =

        GROUP Department Parameter {
        ============================

            Department Id
            -------------


        }
        =

    OUTPUTS
    =======

        GROUP Select results: Actual = 0, Expected = 0: SUCCESS
        =======================================================

} 0 failed, of 1: SUCCESS
=========================

SCENARIO 5: DS-3, Salaries total 1500 (< threshold of 1600, so return nothing) - pass dep 10 {
==============================================================================================

    INPUTS
    ======

        GROUP Employee {
        ================

            Employee Id  Last Name  Email  Hire Date    Job      Salary  Manager Id  Department Id  Updated
            -----------  ---------  -----  -----------  -------  ------  ----------  -------------  -----------
                   1677  LN_1       EM_1   01-OCT-2016  IT_PROG     100                         10  01-OCT-2016
                   1678  LN_2       EM_2   01-OCT-2016  IT_PROG     200        1677             10  01-OCT-2016
                   1679  LN_3       EM_3   01-OCT-2016  IT_PROG     300        1677                 01-OCT-2016
                   1680  LN_4       EM_4   01-OCT-2016  AD_ASST     400        1677             10  01-OCT-2016
                   1681  LN_5       EM_5   01-OCT-2016  IT_PROG     500        1677             20  01-OCT-2016

        }
        =

        GROUP Department Parameter {
        ============================

            Department Id
            -------------
                       10

        }
        =

    OUTPUTS
    =======

        GROUP Select results: Actual = 0, Expected = 0: SUCCESS
        =======================================================

} 0 failed, of 1: SUCCESS
=========================

TIMING: Actual = 7, Expected <= 1: FAILURE
==========================================

SUMMARY for UT_Emp_WS.ut_AIP_Get_Dept_Emps
==========================================

Scenario                                                                                              # Failed  # Tests  Status
----------------------------------------------------------------------------------------------------  --------  -------  -------
DS-1, testing inner, outer joins, analytic over dep, and global ratios with 1 dep (10) - pass dep 10         0        2  SUCCESS
DS-2, testing same as 1 but with extra emp in another dep (20) - pass dep 10                                 0        2  SUCCESS
DS-2, as second scenario, but - pass dep 20                                                                  0        1  SUCCESS
DS-2, as second scenario, but - pass null dep                                                                0        1  SUCCESS
DS-3, Salaries total 1500 (< threshold of 1600, so return nothing) - pass dep 10                             0        1  SUCCESS
Timing                                                                                                       1        1  FAILURE
----------------------------------------------------------------------------------------------------  --------  -------  -------
Total                                                                                                        1        8  FAILURE
----------------------------------------------------------------------------------------------------  --------  -------  -------

Timer Set: UT_Emp_WS.ut_AIP_Get_Dept_Emps, Constructed at 01 Oct 2016 09:14:12, written at 09:14:13
===================================================================================================
[Timer timed: Elapsed (per call): 0.03 (0.000034), CPU (per call): 0.03 (0.000030), calls: 1000, '***' denotes corrected line below]

Timer       Elapsed         CPU         Calls       Ela/Call       CPU/Call
-------  ----------  ----------  ------------  -------------  -------------
Setup          0.08        0.05             5        0.01660        0.01000
Caller         0.03        0.01             5        0.00680        0.00200
(Other)        0.10        0.10             1        0.09500        0.10000
-------  ----------  ----------  ------------  -------------  -------------
Total          0.21        0.16            11        0.01927        0.01455
-------  ----------  ----------  ------------  -------------  -------------






 

Design Patterns for Database API Testing 3: Batch Loading of Flat Files

In TRAPIT - TRansactional API Testing in Oracle, I supplied installation scripts for a new Oracle PL/SQL unit testing framework, together with working example unit test programs for four use cases against Oracle's HR demo schema. I linked to articles describing two of these example test programs, and the current article describes the third example, with the fourth to follow shortly.

The four examples were designed to cover the general categories of getting and setting data in batch or real time mode. This third example covers batch loading of data into a database table from file by means of external tables. There are many possible variants of this kind of interface, and I tried to combine the features from past projects that seemed to work best. In particular:

  • The load procedure is assumed to be executed from an operating system script (normally Unix) that manages the input files, copying from source files into a single file for reading by the external table, looping over multiple files where necessary, and archiving processed files
    • It is possible to dynamically map the external table to multiple files, but that approach involves executing DDL and seems to be generally more complex
    • The idea is to do the different types of processing at the level most appropriate, so avoiding excessive file processing within the database
  • SQL operations are performed at set level, rather than within a loop, and the set concerned comprises the entire contents of the external table
    • This assumes that the Oracle internal working space requirements (such as size of TEMP tablespace) are not exceeded
    • The alternative approach of fetching batches of records into arrays for loading tends to be more complex, and less efficient
    • It may be preferable to restrict the size of the input files where necessary instead, either at the source end, or from the controlling operating system script
    • Where loading occurs from staging tables (which is not in scope here) the use of the DBMS_Parallel_Execute package to control transaction size looks an attractive modern approach (from v11, DBMS_PARALLEL_EXECUTE)
  • Metadata tables are used for specifying job control parameters, and for recording run statistics
    • Run statistics include job status and numbers of records succeeding and failing at both external table and database level
    • A percentage threshold is included in the job control table, that causes the job to fail if a higher percentage of records fails
  • Oracle's DML LOG ERRORS clause is used to divert failing records into an errors table, while processing the other records normally
    • While simpler than other approaches to error handling, prior to v12.1 this clause had a significant performance overhead, but from v12.1 this is no longer the case (see DML Error Logging in Oracle 10g Database Release 2 - it has a table of comparative timings up to v12.1 at the end)
    • The standard Oracle err$ table structure is used, with the addition of two columns, one to identify the associated job run, and the other the utid column used by the framework to identify unit test data
    • In a replication environment a unique identifier would be needed, but is not included here
    • The table is also used to capture records that fail custom validation (here when a record passed as an update does not match an existing record)

Requirement Summary

  • The procedure reads employee records from a single flat file
  • Employee id is an optional field, and if passed the record is treated as an update, otherwise it is an insert
  • A job statistics table is populated with a record on each run, and stores numbers of successful and failed records etc.
  • Records that fail at the database level are inserted into an errors table, extended from Oracle's err$ table format
  • The external table has all fields defined as 4000 bytes character fields to minimise records failing to be read from the external table
  • An audit date column is included, and is set to the current date if any change is made in a record; if an unchanged record is detected no update should be made
  • The load program takes two parameters that would be passed in by an operating system calling script:
    • An identifier for the file, that may be a timestamped original file name (but the external table file has a fixed name)
    • A line count for the file
  • The passed file identifier is saved in the job statistics table, and a repeat identifier will only be accepted if previous records all have failed status
  • A job control table stores an error percentage threshold, above which the run is considered unsuccessfull, and an exception is raised

Notes on Unit Testing Flat File Loads

  • It is considered best practice to keep unit testing code as self-contained as possible, and in order to avoid dependence on external data files, Oracle's UTL_File package is used to delete and create the test files from arrays within the unit test code
    • The Utils package contains two wrapper procedures to facilitate this: Delete_File and Write_File

Extended ERD

unit-testing-two-ff-erd-h

Design Pattern Groups

The unit testing framework is centred around the concept of input and output groups, representing the data sets that respectively form the inputs to, and outputs from, the program. The records in each group are printed by the framework with column headers for each scenario. These groups are identified by the developer, and in this case they are as noted below.

Input Groups

  • Parameters
  • Input File
  • Batch Job Table
  • Job Statistics Table
  • Employees Table

Output Groups

  • Employees Table
  • Errors Table
  • Job Statistics Table
  • Exception
  • Timing of average call

Test Scenarios

Key
The scenario descriptions start with two sets of counts, followed by a verbal description. The first set is on the records coming in from file:

  • NV - new valid records
  • OV - old valid records
  • OU - old unchanged records
  • NI - new invalid records
  • OI - old valid records
  • EI - external table invalid records

The second set is on the existing records in job statistics and employees (other than are in the input file; these are counted as old records in the first set of counts):

  • J - job statistics records
  • E - employees records

Scenario List

  1. NV/OV/OU/NI/OI/EI: 1/0/0/0/0/0. Existing J/E: 0/0. [1 valid new record from scratch]
  2. NV/OV/OU/NI/OI/EI: 1/1/1/0/0/0. Existing J/E: 1/0. [3 valid records of each kind]
  3. NV/OV/OU/NI/OI/EI: 0/0/0/0/1/0. Existing J/E: 1/1. Uid not found [1 invalid old - exception]
  4. NV/OV/OU/NI/OI/EI: 0/0/0/1/0/0. Existing J/E: 1/1. Email too long [1 invalid new - exception]
  5. NV/OV/OU/NI/OI/EI: 1/0/0/0/1/0. Existing J/E: 1/1. Name too long [1 valid new, 1 invalid old - no exception]
  6. NV/OV/OU/NI/OI/EI: 0/0/0/1/0/0. Existing J/E: 1/1. Invalid job [1 invalid new - exception]
  7. NV/OV/OU/NI/OI/EI: 0/1/0/1/1/0. Existing J/E: 1/2. 2 invalid jobs [1 valid old, 2 invalid: old and new - no exception]
  8. NV/OV/OU/NI/OI/EI: 0/1/0/0/0/1. Existing J/E: 1/2. Name 4001ch [1 valid old, 1 invalid new for external table - no exception; also file had previously failed]
  9. NV/OV/OU/NI/OI/EI: 0/0/0/1/0/0. Existing J/E: 1/1. [File already processed - exception]

Code Structure Diagram

unit-testing-two-ff-csd-h

Call Structure Table - UT_Emp_Batch.ut_AIP_Load_Emps

Level 1 Level 2 Level 3 Package
Init UT_Utils
Setup UT_Emp_Batch
Replace_Seq_Offset UT_Emp_Batch
Ins_jbs DML_API_UT_Bren
Ins_Emp DML_API_UT_HR
Delete_File Utils
Write_File Utils
Increment_Time Timer_Set
Call_Proc UT_Emp_Batch
Init_Time Timer_Set
AIP_Load_Emps Emp_Batch
Increment_Time Timer_Set
Get_Tab_Lis UT_Emp_Batch
List_Delim Utils
Get_Err_Lis UT_Emp_Batch
List_Delim Utils
Get_Jbs_Lis UT_Emp_Batch
List_Delim Utils
List_or_Empty UT_Utils
Check_UT_Results UT_Utils
Write_Other_Error Utils

Test Output

UNIT TEST for UT_Emp_Batch.ut_AIP_Load_Emps
===========================================
employees.dat was not present to delete!

SCENARIO 1: NV/OV/OU/NI/OI/EI: 1/0/0/0/0/0. Existing J/E: 0/0. [1 valid new record from scratch] {
==================================================================================================

    INPUTS
    ======

        GROUP Parameter {
        =================

            File Name               Count
            ----------------------  -----
            employees_20160801.dat      1

        }
        =

        GROUP File {
        ============

            Line
            ------------------------------------
            ,LN 1,EM 1,01-JAN-2010,IT_PROG,10000

        }
        =

        GROUP Batch Job Table {
        =======================

            Name       Fail Percent
            ---------  ------------
            LOAD_EMPS            70

        }
        =

        GROUP Statistics Table (No records)
        ===================================

        GROUP Employees Table (No records)
        ==================================

    OUTPUTS
    =======

        GROUP Employee: Actual = 1, Expected = 1 {
        ==========================================

            F?  Employee Id  Name  Email  Hired        Job      Salary  Updated
            --  -----------  ----  -----  -----------  -------  ------  -----------
                       1627  LN 1  EM 1   01-JAN-2010  IT_PROG  10000   11-SEP-2016

        } 0 failed, of 1: SUCCESS
        =========================

        GROUP Error: Actual = 0, Expected = 0: SUCCESS
        ==============================================

        GROUP Job Statistic: Actual = 1, Expected = 1 {
        ===============================================

            F?  Job Statistic Id  Batch job Id  File Name               Records Loaded  Records Failed ET  Records Failed DB  Start Time   End Time     Status
            --  ----------------  ------------  ----------------------  --------------  -----------------  -----------------  -----------  -----------  ------
                               3  LOAD_EMPS     employees_20160801.dat               1                  0                  0  11-SEP-2016  11-SEP-2016  S

        } 0 failed, of 1: SUCCESS
        =========================

        GROUP Exception: Actual = 0, Expected = 0: SUCCESS
        ==================================================

} 0 failed, of 4: SUCCESS
=========================

SCENARIO 2: NV/OV/OU/NI/OI/EI: 1/1/1/0/0/0. Existing J/E: 1/0. [3 valid records of each kind] {
===============================================================================================

    INPUTS
    ======

        GROUP Parameter {
        =================

            File Name               Count
            ----------------------  -----
            employees_20160801.dat      3

        }
        =

        GROUP File {
        ============

            Line
            -----------------------------------------
            ,LN 1,EM 1,01-JAN-2010,IT_PROG,10000
            1629,LN 2,EM 2,01-JAN-2010,IT_PROG,20000
            1630,LN 3U,EM 3,01-JAN-2010,IT_PROG,30000

        }
        =

        GROUP Batch Job Table {
        =======================

            Name       Fail Percent
            ---------  ------------
            LOAD_EMPS            70

        }
        =

        GROUP Statistics Table {
        ========================

            Job Statistic Id  Batch job Id  File Name               Records Loaded  Records Failed ET  Records Failed DB  Start Time   End Time     Status
            ----------------  ------------  ----------------------  --------------  -----------------  -----------------  -----------  -----------  ------
                           5  LOAD_EMPS     employees_20160101.dat              10                  0                  2  01-JAN-2010  01-JAN-2010  S

        }
        =

        GROUP Employees Table {
        =======================

            Employee Id  Name  Email  Hired        Job      Salary  Manager Id  Department Id  Updated
            -----------  ----  -----  -----------  -------  ------  ----------  -------------  -----------
                   1629  LN 2  EM 2   01-JAN-2010  IT_PROG   20000                             01-JAN-2010
                   1630  LN 3  EM 3   01-JAN-2010  IT_PROG   30000                             01-JAN-2010

        }
        =

    OUTPUTS
    =======

        GROUP Employee: Actual = 3, Expected = 3 {
        ==========================================

            F?  Employee Id  Name   Email  Hired        Job      Salary  Updated
            --  -----------  -----  -----  -----------  -------  ------  -----------
                       1629  LN 2   EM 2   01-JAN-2010  IT_PROG  20000   01-JAN-2010
                       1630  LN 3U  EM 3   01-JAN-2010  IT_PROG  30000   11-SEP-2016
                       1631  LN 1   EM 1   01-JAN-2010  IT_PROG  10000   11-SEP-2016

        } 0 failed, of 3: SUCCESS
        =========================

        GROUP Error: Actual = 0, Expected = 0: SUCCESS
        ==============================================

        GROUP Job Statistic: Actual = 2, Expected = 2 {
        ===============================================

            F?  Job Statistic Id  Batch job Id  File Name               Records Loaded  Records Failed ET  Records Failed DB  Start Time   End Time     Status
            --  ----------------  ------------  ----------------------  --------------  -----------------  -----------------  -----------  -----------  ------
                               5  LOAD_EMPS     employees_20160101.dat              10                  0                  2  01-JAN-2010  01-JAN-2010  S
                               6  LOAD_EMPS     employees_20160801.dat               2                  0                  0  11-SEP-2016  11-SEP-2016  S

        } 0 failed, of 2: SUCCESS
        =========================

        GROUP Exception: Actual = 0, Expected = 0: SUCCESS
        ==================================================

} 0 failed, of 7: SUCCESS
=========================

SCENARIO 3: NV/OV/OU/NI/OI/EI: 0/0/0/0/1/0. Existing J/E: 1/1. Uid not found [1 invalid old - exception] {
==========================================================================================================

    INPUTS
    ======

        GROUP Parameter {
        =================

            File Name               Count
            ----------------------  -----
            employees_20160801.dat      1

        }
        =

        GROUP File {
        ============

            Line
            --------------------------------------
            99,LN 1,EM 1,01-JAN-2010,IT_PROG,10000

        }
        =

        GROUP Batch Job Table {
        =======================

            Name       Fail Percent
            ---------  ------------
            LOAD_EMPS            70

        }
        =

        GROUP Statistics Table {
        ========================

            Job Statistic Id  Batch job Id  File Name               Records Loaded  Records Failed ET  Records Failed DB  Start Time   End Time     Status
            ----------------  ------------  ----------------------  --------------  -----------------  -----------------  -----------  -----------  ------
                           8  LOAD_EMPS     employees_20160101.dat              10                  0                  2  01-JAN-2010  01-JAN-2010  S

        }
        =

        GROUP Employees Table {
        =======================

            Employee Id  Name  Email  Hired        Job      Salary  Manager Id  Department Id  Updated
            -----------  ----  -----  -----------  -------  ------  ----------  -------------  -----------
                   1633  LN 2  EM 2   01-JAN-2010  IT_PROG   20000                             01-JAN-2010

        }
        =

    OUTPUTS
    =======

        GROUP Employee: Actual = 1, Expected = 1 {
        ==========================================

            F?  Employee Id  Name  Email  Hired        Job      Salary  Updated
            --  -----------  ----  -----  -----------  -------  ------  -----------
                       1633  LN 2  EM 2   01-JAN-2010  IT_PROG  20000   01-JAN-2010

        } 0 failed, of 1: SUCCESS
        =========================

        GROUP Error: Actual = 1, Expected = 1 {
        =======================================

            F?  Job Statistic Id  ORA_ERR_TAG$  ORA_ERR_MESG$       ORA_ERR_OPTYP$  Employee Id  Name  Email  Hired        Job      Salary
            --  ----------------  ------------  ------------------  --------------  -----------  ----  -----  -----------  -------  ------
                               9                Employee not found  PK                       99  LN 1  EM 1   01-JAN-2010  IT_PROG  10000

        } 0 failed, of 1: SUCCESS
        =========================

        GROUP Job Statistic: Actual = 2, Expected = 2 {
        ===============================================

            F?  Job Statistic Id  Batch job Id  File Name               Records Loaded  Records Failed ET  Records Failed DB  Start Time   End Time     Status
            --  ----------------  ------------  ----------------------  --------------  -----------------  -----------------  -----------  -----------  ------
                               8  LOAD_EMPS     employees_20160101.dat              10                  0                  2  01-JAN-2010  01-JAN-2010  S
                               9  LOAD_EMPS     employees_20160801.dat               0                  0                  1  11-SEP-2016  11-SEP-2016  F

        } 0 failed, of 2: SUCCESS
        =========================

        GROUP Exception: Actual = 1, Expected = 1 {
        ===========================================

            F?  Message
            --  ------------------------------------------------------
                ORA-20001: Batch failed with too many invalid records!

        } 0 failed, of 1: SUCCESS
        =========================

} 0 failed, of 5: SUCCESS
=========================

SCENARIO 4: NV/OV/OU/NI/OI/EI: 0/0/0/1/0/0. Existing J/E: 1/1. Email too long [1 invalid new - exception] {
===========================================================================================================

    INPUTS
    ======

        GROUP Parameter {
        =================

            File Name               Count
            ----------------------  -----
            employees_20160801.dat      1

        }
        =

        GROUP File {
        ============

            Line
            ------------------------------------------------------------------
            ,LN 1,EM 1123456789012345678901234567890,01-JAN-2010,IT_PROG,10000

        }
        =

        GROUP Batch Job Table {
        =======================

            Name       Fail Percent
            ---------  ------------
            LOAD_EMPS            70

        }
        =

        GROUP Statistics Table {
        ========================

            Job Statistic Id  Batch job Id  File Name               Records Loaded  Records Failed ET  Records Failed DB  Start Time   End Time     Status
            ----------------  ------------  ----------------------  --------------  -----------------  -----------------  -----------  -----------  ------
                          11  LOAD_EMPS     employees_20160101.dat              10                  0                  2  01-JAN-2010  01-JAN-2010  S

        }
        =

        GROUP Employees Table {
        =======================

            Employee Id  Name  Email  Hired        Job      Salary  Manager Id  Department Id  Updated
            -----------  ----  -----  -----------  -------  ------  ----------  -------------  -----------
                   1635  LN 2  EM 2   01-JAN-2010  IT_PROG   20000                             01-JAN-2010

        }
        =

    OUTPUTS
    =======

        GROUP Employee: Actual = 1, Expected = 1 {
        ==========================================

            F?  Employee Id  Name  Email  Hired        Job      Salary  Updated
            --  -----------  ----  -----  -----------  -------  ------  -----------
                       1635  LN 2  EM 2   01-JAN-2010  IT_PROG  20000   01-JAN-2010

        } 0 failed, of 1: SUCCESS
        =========================

        GROUP Error: Actual = 1, Expected = 1 {
        =======================================

            F?  Job Statistic Id  ORA_ERR_TAG$  ORA_ERR_MESG$                                                                             ORA_ERR_OPTYP$  Employee Id  Name  Email                               Hired        Job      Salary
            --  ----------------  ------------  ----------------------------------------------------------------------------------------  --------------  -----------  ----  ----------------------------------  -----------  -------  ------
                              12                ORA-12899: value too large for column "HR"."EMPLOYEES"."EMAIL" (actual: 34, maximum: 25)  I                      1636  LN 1  EM 1123456789012345678901234567890  01-JAN-2010  IT_PROG  10000

        } 0 failed, of 1: SUCCESS
        =========================

        GROUP Job Statistic: Actual = 2, Expected = 2 {
        ===============================================

            F?  Job Statistic Id  Batch job Id  File Name               Records Loaded  Records Failed ET  Records Failed DB  Start Time   End Time     Status
            --  ----------------  ------------  ----------------------  --------------  -----------------  -----------------  -----------  -----------  ------
                              11  LOAD_EMPS     employees_20160101.dat              10                  0                  2  01-JAN-2010  01-JAN-2010  S
                              12  LOAD_EMPS     employees_20160801.dat               0                  0                  1  11-SEP-2016  11-SEP-2016  F

        } 0 failed, of 2: SUCCESS
        =========================

        GROUP Exception: Actual = 1, Expected = 1 {
        ===========================================

            F?  Message
            --  ------------------------------------------------------
                ORA-20001: Batch failed with too many invalid records!

        } 0 failed, of 1: SUCCESS
        =========================

} 0 failed, of 5: SUCCESS
=========================

SCENARIO 5: NV/OV/OU/NI/OI/EI: 1/0/0/0/1/0. Existing J/E: 1/1. Name too long [1 valid new, 1 invalid old - no exception] {
==========================================================================================================================

    INPUTS
    ======

        GROUP Parameter {
        =================

            File Name               Count
            ----------------------  -----
            employees_20160801.dat      2

        }
        =

        GROUP File {
        ============

            Line
            ----------------------------------------------------------------------
            1638,LN 1123456789012345678901234567890,EM 1,01-JAN-2010,IT_PROG,10000
            ,LN 3,EM 3,01-JAN-2010,IT_PROG,30000

        }
        =

        GROUP Batch Job Table {
        =======================

            Name       Fail Percent
            ---------  ------------
            LOAD_EMPS            70

        }
        =

        GROUP Statistics Table {
        ========================

            Job Statistic Id  Batch job Id  File Name               Records Loaded  Records Failed ET  Records Failed DB  Start Time   End Time     Status
            ----------------  ------------  ----------------------  --------------  -----------------  -----------------  -----------  -----------  ------
                          14  LOAD_EMPS     employees_20160101.dat              10                  0                  2  01-JAN-2010  01-JAN-2010  S

        }
        =

        GROUP Employees Table {
        =======================

            Employee Id  Name  Email  Hired        Job      Salary  Manager Id  Department Id  Updated
            -----------  ----  -----  -----------  -------  ------  ----------  -------------  -----------
                   1638  LN 2  EM 2   01-JAN-2010  IT_PROG   20000                             01-JAN-2010

        }
        =

    OUTPUTS
    =======

        GROUP Employee: Actual = 2, Expected = 2 {
        ==========================================

            F?  Employee Id  Name  Email  Hired        Job      Salary  Updated
            --  -----------  ----  -----  -----------  -------  ------  -----------
                       1638  LN 2  EM 2   01-JAN-2010  IT_PROG  20000   01-JAN-2010
                       1639  LN 3  EM 3   01-JAN-2010  IT_PROG  30000   11-SEP-2016

        } 0 failed, of 2: SUCCESS
        =========================

        GROUP Error: Actual = 1, Expected = 1 {
        =======================================

            F?  Job Statistic Id  ORA_ERR_TAG$  ORA_ERR_MESG$                                                                                 ORA_ERR_OPTYP$  Employee Id  Name                                Email  Hired        Job      Salary
            --  ----------------  ------------  --------------------------------------------------------------------------------------------  --------------  -----------  ----------------------------------  -----  -----------  -------  ------
                              15                ORA-12899: value too large for column "HR"."EMPLOYEES"."LAST_NAME" (actual: 34, maximum: 25)  U                      1638  LN 1123456789012345678901234567890  EM 1   01-JAN-2010  IT_PROG  10000

        } 0 failed, of 1: SUCCESS
        =========================

        GROUP Job Statistic: Actual = 2, Expected = 2 {
        ===============================================

            F?  Job Statistic Id  Batch job Id  File Name               Records Loaded  Records Failed ET  Records Failed DB  Start Time   End Time     Status
            --  ----------------  ------------  ----------------------  --------------  -----------------  -----------------  -----------  -----------  ------
                              14  LOAD_EMPS     employees_20160101.dat              10                  0                  2  01-JAN-2010  01-JAN-2010  S
                              15  LOAD_EMPS     employees_20160801.dat               1                  0                  1  11-SEP-2016  11-SEP-2016  S

        } 0 failed, of 2: SUCCESS
        =========================

        GROUP Exception: Actual = 0, Expected = 0: SUCCESS
        ==================================================

} 0 failed, of 6: SUCCESS
=========================

SCENARIO 6: NV/OV/OU/NI/OI/EI: 0/0/0/1/0/0. Existing J/E: 1/1. Invalid job [1 invalid new - exception] {
========================================================================================================

    INPUTS
    ======

        GROUP Parameter {
        =================

            File Name               Count
            ----------------------  -----
            employees_20160801.dat      1

        }
        =

        GROUP File {
        ============

            Line
            ------------------------------------
            ,LN 1,EM 1,01-JAN-2010,NON_JOB,10000

        }
        =

        GROUP Batch Job Table {
        =======================

            Name       Fail Percent
            ---------  ------------
            LOAD_EMPS            70

        }
        =

        GROUP Statistics Table {
        ========================

            Job Statistic Id  Batch job Id  File Name               Records Loaded  Records Failed ET  Records Failed DB  Start Time   End Time     Status
            ----------------  ------------  ----------------------  --------------  -----------------  -----------------  -----------  -----------  ------
                          17  LOAD_EMPS     employees_20160101.dat              10                  0                  2  01-JAN-2010  01-JAN-2010  S

        }
        =

        GROUP Employees Table {
        =======================

            Employee Id  Name  Email  Hired        Job      Salary  Manager Id  Department Id  Updated
            -----------  ----  -----  -----------  -------  ------  ----------  -------------  -----------
                   1641  LN 2  EM 2   01-JAN-2010  IT_PROG   20000                             01-JAN-2010

        }
        =

    OUTPUTS
    =======

        GROUP Employee: Actual = 1, Expected = 1 {
        ==========================================

            F?  Employee Id  Name  Email  Hired        Job      Salary  Updated
            --  -----------  ----  -----  -----------  -------  ------  -----------
                       1641  LN 2  EM 2   01-JAN-2010  IT_PROG  20000   01-JAN-2010

        } 0 failed, of 1: SUCCESS
        =========================

        GROUP Error: Actual = 1, Expected = 1 {
        =======================================

            F?  Job Statistic Id  ORA_ERR_TAG$  ORA_ERR_MESG$                                                                    ORA_ERR_OPTYP$  Employee Id  Name  Email  Hired        Job      Salary
            --  ----------------  ------------  -------------------------------------------------------------------------------  --------------  -----------  ----  -----  -----------  -------  ------
                              18                ORA-02291: integrity constraint (HR.EMP_JOB_FK) violated - parent key not found  I                      1642  LN 1  EM 1   01-JAN-2010  NON_JOB  10000

        } 0 failed, of 1: SUCCESS
        =========================

        GROUP Job Statistic: Actual = 2, Expected = 2 {
        ===============================================

            F?  Job Statistic Id  Batch job Id  File Name               Records Loaded  Records Failed ET  Records Failed DB  Start Time   End Time     Status
            --  ----------------  ------------  ----------------------  --------------  -----------------  -----------------  -----------  -----------  ------
                              17  LOAD_EMPS     employees_20160101.dat              10                  0                  2  01-JAN-2010  01-JAN-2010  S
                              18  LOAD_EMPS     employees_20160801.dat               0                  0                  1  11-SEP-2016  11-SEP-2016  F

        } 0 failed, of 2: SUCCESS
        =========================

        GROUP Exception: Actual = 1, Expected = 1 {
        ===========================================

            F?  Message
            --  ------------------------------------------------------
                ORA-20001: Batch failed with too many invalid records!

        } 0 failed, of 1: SUCCESS
        =========================

} 0 failed, of 5: SUCCESS
=========================

SCENARIO 7: NV/OV/OU/NI/OI/EI: 0/1/0/1/1/0. Existing J/E: 1/2. 2 invalid jobs [1 valid old, 2 invalid: old and new - no exception] {
====================================================================================================================================

    INPUTS
    ======

        GROUP Parameter {
        =================

            File Name               Count
            ----------------------  -----
            employees_20160801.dat      3

        }
        =

        GROUP File {
        ============

            Line
            -----------------------------------------
            ,LN 1,EM 1,01-JAN-2010,NON_JOB,10000
            1644,LN 2,EM 2,01-JAN-2010,NON_JOB,20000
            1645,LN 3U,EM 3,01-JAN-2010,IT_PROG,30000

        }
        =

        GROUP Batch Job Table {
        =======================

            Name       Fail Percent
            ---------  ------------
            LOAD_EMPS            70

        }
        =

        GROUP Statistics Table {
        ========================

            Job Statistic Id  Batch job Id  File Name               Records Loaded  Records Failed ET  Records Failed DB  Start Time   End Time     Status
            ----------------  ------------  ----------------------  --------------  -----------------  -----------------  -----------  -----------  ------
                          20  LOAD_EMPS     employees_20160101.dat              10                  0                  2  01-JAN-2010  01-JAN-2010  S

        }
        =

        GROUP Employees Table {
        =======================

            Employee Id  Name  Email  Hired        Job      Salary  Manager Id  Department Id  Updated
            -----------  ----  -----  -----------  -------  ------  ----------  -------------  -----------
                   1644  LN 2  EM 2   01-JAN-2010  IT_PROG   20000                             01-JAN-2010
                   1645  LN 3  EM 3   01-JAN-2010  IT_PROG   30000                             01-JAN-2010

        }
        =

    OUTPUTS
    =======

        GROUP Employee: Actual = 2, Expected = 2 {
        ==========================================

            F?  Employee Id  Name   Email  Hired        Job      Salary  Updated
            --  -----------  -----  -----  -----------  -------  ------  -----------
                       1644  LN 2   EM 2   01-JAN-2010  IT_PROG  20000   01-JAN-2010
                       1645  LN 3U  EM 3   01-JAN-2010  IT_PROG  30000   11-SEP-2016

        } 0 failed, of 2: SUCCESS
        =========================

        GROUP Error: Actual = 2, Expected = 2 {
        =======================================

            F?  Job Statistic Id  ORA_ERR_TAG$  ORA_ERR_MESG$                                                                    ORA_ERR_OPTYP$  Employee Id  Name  Email  Hired        Job      Salary
            --  ----------------  ------------  -------------------------------------------------------------------------------  --------------  -----------  ----  -----  -----------  -------  ------
                              21                ORA-02291: integrity constraint (HR.EMP_JOB_FK) violated - parent key not found  U                      1644  LN 2  EM 2   01-JAN-2010  NON_JOB  20000
                              21                ORA-02291: integrity constraint (HR.EMP_JOB_FK) violated - parent key not found  I                      1646  LN 1  EM 1   01-JAN-2010  NON_JOB  10000

        } 0 failed, of 2: SUCCESS
        =========================

        GROUP Job Statistic: Actual = 2, Expected = 2 {
        ===============================================

            F?  Job Statistic Id  Batch job Id  File Name               Records Loaded  Records Failed ET  Records Failed DB  Start Time   End Time     Status
            --  ----------------  ------------  ----------------------  --------------  -----------------  -----------------  -----------  -----------  ------
                              20  LOAD_EMPS     employees_20160101.dat              10                  0                  2  01-JAN-2010  01-JAN-2010  S
                              21  LOAD_EMPS     employees_20160801.dat               1                  0                  2  11-SEP-2016  11-SEP-2016  S

        } 0 failed, of 2: SUCCESS
        =========================

        GROUP Exception: Actual = 0, Expected = 0: SUCCESS
        ==================================================

} 0 failed, of 7: SUCCESS
=========================

SCENARIO 8: NV/OV/OU/NI/OI/EI: 0/1/0/0/0/1. Existing J/E: 1/2. Name 4001ch [1 valid old, 1 invalid new for external table - no exception; also file had previously failed] {
============================================================================================================================================================================

    INPUTS
    ======

        GROUP Parameter {
        =================

            File Name               Count
            ----------------------  -----
            employees_20160801.dat      2

        }
        =

        GROUP File {
        ============

            Line
            --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
            ,123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567
            1649,LN 3U,EM 3,01-JAN-2010,IT_PROG,30000

        }
        =

        GROUP Batch Job Table {
        =======================

            Name       Fail Percent
            ---------  ------------
            LOAD_EMPS            70

        }
        =

        GROUP Statistics Table {
        ========================

            Job Statistic Id  Batch job Id  File Name               Records Loaded  Records Failed ET  Records Failed DB  Start Time   End Time     Status
            ----------------  ------------  ----------------------  --------------  -----------------  -----------------  -----------  -----------  ------
                          23  LOAD_EMPS     employees_20160801.dat               0                  0                  2  01-JAN-2010  01-JAN-2010  F

        }
        =

        GROUP Employees Table {
        =======================

            Employee Id  Name  Email  Hired        Job      Salary  Manager Id  Department Id  Updated
            -----------  ----  -----  -----------  -------  ------  ----------  -------------  -----------
                   1648  LN 2  EM 2   01-JAN-2010  IT_PROG   20000                             01-JAN-2010
                   1649  LN 3  EM 3   01-JAN-2010  IT_PROG   30000                             01-JAN-2010

        }
        =

    OUTPUTS
    =======

        GROUP Employee: Actual = 2, Expected = 2 {
        ==========================================

            F?  Employee Id  Name   Email  Hired        Job      Salary  Updated
            --  -----------  -----  -----  -----------  -------  ------  -----------
                       1648  LN 2   EM 2   01-JAN-2010  IT_PROG  20000   01-JAN-2010
                       1649  LN 3U  EM 3   01-JAN-2010  IT_PROG  30000   11-SEP-2016

        } 0 failed, of 2: SUCCESS
        =========================

        GROUP Error: Actual = 0, Expected = 0: SUCCESS
        ==============================================

        GROUP Job Statistic: Actual = 2, Expected = 2 {
        ===============================================

            F?  Job Statistic Id  Batch job Id  File Name               Records Loaded  Records Failed ET  Records Failed DB  Start Time   End Time     Status
            --  ----------------  ------------  ----------------------  --------------  -----------------  -----------------  -----------  -----------  ------
                              23  LOAD_EMPS     employees_20160801.dat               0                  0                  2  01-JAN-2010  01-JAN-2010  F
                              24  LOAD_EMPS     employees_20160801.dat               1                  1                  0  11-SEP-2016  11-SEP-2016  S

        } 0 failed, of 2: SUCCESS
        =========================

        GROUP Exception: Actual = 0, Expected = 0: SUCCESS
        ==================================================

} 0 failed, of 6: SUCCESS
=========================

SCENARIO 9: NV/OV/OU/NI/OI/EI: 0/0/0/1/0/0. Existing J/E: 1/1. [File already processed - exception] {
=====================================================================================================

    INPUTS
    ======

        GROUP Parameter {
        =================

            File Name               Count
            ----------------------  -----
            employees_20160801.dat      1

        }
        =

        GROUP File {
        ============

            Line
            ------------------------------------
            ,LN 1,EM 1,01-JAN-2010,NON_JOB,10000

        }
        =

        GROUP Batch Job Table {
        =======================

            Name       Fail Percent
            ---------  ------------
            LOAD_EMPS            70

        }
        =

        GROUP Statistics Table {
        ========================

            Job Statistic Id  Batch job Id  File Name               Records Loaded  Records Failed ET  Records Failed DB  Start Time   End Time     Status
            ----------------  ------------  ----------------------  --------------  -----------------  -----------------  -----------  -----------  ------
                          26  LOAD_EMPS     employees_20160801.dat              10                  0                  2  01-JAN-2010  01-JAN-2010  S

        }
        =

        GROUP Employees Table {
        =======================

            Employee Id  Name  Email  Hired        Job      Salary  Manager Id  Department Id  Updated
            -----------  ----  -----  -----------  -------  ------  ----------  -------------  -----------
                   1651  LN 2  EM 2   01-JAN-2010  IT_PROG   20000                             01-JAN-2010

        }
        =

    OUTPUTS
    =======

        GROUP Employee: Actual = 1, Expected = 1 {
        ==========================================

            F?  Employee Id  Name  Email  Hired        Job      Salary  Updated
            --  -----------  ----  -----  -----------  -------  ------  -----------
                       1651  LN 2  EM 2   01-JAN-2010  IT_PROG  20000   01-JAN-2010

        } 0 failed, of 1: SUCCESS
        =========================

        GROUP Error: Actual = 0, Expected = 0: SUCCESS
        ==============================================

        GROUP Job Statistic: Actual = 1, Expected = 1 {
        ===============================================

            F?  Job Statistic Id  Batch job Id  File Name               Records Loaded  Records Failed ET  Records Failed DB  Start Time   End Time     Status
            --  ----------------  ------------  ----------------------  --------------  -----------------  -----------------  -----------  -----------  ------
                              26  LOAD_EMPS     employees_20160801.dat              10                  0                  2  01-JAN-2010  01-JAN-2010  S

        } 0 failed, of 1: SUCCESS
        =========================

        GROUP Exception: Actual = 1, Expected = 1 {
        ===========================================

            F?  Message
            --  --------------------------------------------------------
                ORA-20002: File has already been processed successfully!

        } 0 failed, of 1: SUCCESS
        =========================

} 0 failed, of 4: SUCCESS
=========================

TIMING: Actual = 306, Expected <= 2: FAILURE
============================================

SUMMARY for UT_Emp_Batch.ut_AIP_Load_Emps
=========================================

Scenario                                                                                                                                                        # Failed  # Tests  Status
--------------------------------------------------------------------------------------------------------------------------------------------------------------  --------  -------  -------
NV/OV/OU/NI/OI/EI: 1/0/0/0/0/0. Existing J/E: 0/0. [1 valid new record from scratch]                                                                                   0        4  SUCCESS
NV/OV/OU/NI/OI/EI: 1/1/1/0/0/0. Existing J/E: 1/0. [3 valid records of each kind]                                                                                      0        7  SUCCESS
NV/OV/OU/NI/OI/EI: 0/0/0/0/1/0. Existing J/E: 1/1. Uid not found [1 invalid old - exception]                                                                           0        5  SUCCESS
NV/OV/OU/NI/OI/EI: 0/0/0/1/0/0. Existing J/E: 1/1. Email too long [1 invalid new - exception]                                                                          0        5  SUCCESS
NV/OV/OU/NI/OI/EI: 1/0/0/0/1/0. Existing J/E: 1/1. Name too long [1 valid new, 1 invalid old - no exception]                                                           0        6  SUCCESS
NV/OV/OU/NI/OI/EI: 0/0/0/1/0/0. Existing J/E: 1/1. Invalid job [1 invalid new - exception]                                                                             0        5  SUCCESS
NV/OV/OU/NI/OI/EI: 0/1/0/1/1/0. Existing J/E: 1/2. 2 invalid jobs [1 valid old, 2 invalid: old and new - no exception]                                                 0        7  SUCCESS
NV/OV/OU/NI/OI/EI: 0/1/0/0/0/1. Existing J/E: 1/2. Name 4001ch [1 valid old, 1 invalid new for external table - no exception; also file had previously failed]         0        6  SUCCESS
NV/OV/OU/NI/OI/EI: 0/0/0/1/0/0. Existing J/E: 1/1. [File already processed - exception]                                                                                0        4  SUCCESS
Timing                                                                                                                                                                 1        1  FAILURE
--------------------------------------------------------------------------------------------------------------------------------------------------------------  --------  -------  -------
Total                                                                                                                                                                  1       50  FAILURE
--------------------------------------------------------------------------------------------------------------------------------------------------------------  --------  -------  -------

Timer Set: UT_Emp_Batch.ut_AIP_Load_Emps, Constructed at 11 Sep 2016 16:10:46, written at 16:10:49
==================================================================================================
[Timer timed: Elapsed (per call): 0.04 (0.000036), CPU (per call): 0.03 (0.000030), calls: 1000, '***' denotes corrected line below]

Timer           Elapsed         CPU         Calls       Ela/Call       CPU/Call
-----------  ----------  ----------  ------------  -------------  -------------
Setup              1.10        0.30             9        0.12189        0.03333
Caller             1.53        1.16             5        0.30560        0.23200
Get_Tab_Lis        0.75        0.49             9        0.08378        0.05444
Get_Err_Lis        0.02        0.03             9        0.00244        0.00333
Get_Jbs_Lis        0.00        0.00             9        0.00011        0.00000
(Other)            0.34        0.35             1        0.33500        0.35000
-----------  ----------  ----------  ------------  -------------  -------------
Total              3.74        2.33            42        0.08898        0.05548
-----------  ----------  ----------  ------------  -------------  -------------

Suite Summary
=============

Package.Procedure                  Tests  Fails         ELA         CPU
---------------------------------  -----  -----  ----------  ----------
UT_Emp_WS.ut_AIP_Save_Emps            17      3        0.10        0.09
UT_Emp_WS.ut_AIP_Get_Dept_Emps         7      1        0.11        0.12
UT_View_Drivers.ut_HR_Test_View_V      9      0        0.12        0.12
UT_Emp_Batch.ut_AIP_Load_Emps         50      1        3.74        2.33
---------------------------------  -----  -----  ----------  ----------
Total                                 83      5        4.07        2.66
---------------------------------  -----  -----  ----------  ----------
Others error in (): ORA-20001: Suite BRENDAN returned error status: ORA-06512: at "DP_1.UT_UTILS", line 151
ORA-06512: at "DP_1.UT_UTILS", line 818
ORA-06512: at line 5






 

A Utility for Reading REF Cursors into a List of Delimited Strings

This is a generic utility function that I wrote for use in unit testing web services that return REF cursors. It takes as input an open REF cursor and an optional filter string and returns the output as an array of delimited strings matching the filter. This can then be used to assert against expected output records.

The initial technical difficulty I had with making this generic was in getting the structure of the cursor. This is resolved by translating the REF cursor into a cursor that can be managed by the package DBMS_SQL, using DBMS_SQL.To_Cursor_Number.

As I am using it for unit testing the function does not need to be scalable. For other uses involving large volumes it could be made scalable by, for example, converting to a pipelined function.

Data Types

The cursor needs to return a flat projection, and columns accounted for currently are:

  • NUMBER
  • VARCHAR2
  • DATE
  • TIMESTAMP

Custom Dependencies

  • L1_chr_arr - custom array type, equivalent to SYS.ODCIVarchar2List
  • Utils.List_Delim - function that turns an array of strings into one delimited string, included in my unit test framework, Brendan's Database Unit Testing Framework

Code

The function wiil (shortly) be packaged within my unit testing package UT_Utils, but for demo purposes, here is a script that has a driving anonymous block with the function declared locally within that block.

DECLARE
  l_csr         SYS_REFCURSOR;
  l_res_lis     L1_chr_arr;
  c_query_1     CONSTANT VARCHAR2(4000) := 'SELECT * FROM employees ORDER BY employee_id';
 
  PROCEDURE Write_Log (p_line VARCHAR2) IS
  BEGIN
    DBMS_Output.Put_Line (p_line);
  END Write_Log;
 
FUNCTION Cursor_to_Array (p_csr IN OUT SYS_REFCURSOR, p_filter VARCHAR2 DEFAULT NULL) RETURN L1_chr_arr IS
 
  c_chr_type    CONSTANT PLS_INTEGER := 1; --DBMS_Types.TYPECODE_* do not seem to quite work
  c_num_type    CONSTANT PLS_INTEGER := 2;
  c_dat_type    CONSTANT PLS_INTEGER := 12;
  c_stp_type    CONSTANT PLS_INTEGER := 180;
  l_csr_id      PLS_INTEGER;
  l_n_cols      PLS_INTEGER;
  l_desctab     DBMS_SQL.DESC_TAB;
  l_chr_val     VARCHAR2(4000);
  l_num_val     NUMBER;
  l_dat_val     DATE;
  l_stp_val     TIMESTAMP;
  l_val_lis     L1_chr_arr;
  l_res_lis     L1_chr_arr := L1_chr_arr();
  l_rec         VARCHAR2(4000);
 
BEGIN
 
  l_csr_id := DBMS_SQL.To_Cursor_Number (p_csr);
  DBMS_SQL.Describe_Columns (l_csr_id, l_n_cols, l_desctab);
 
  FOR i IN 1..l_n_cols LOOP
 
    CASE l_desctab(i).col_type
 
      WHEN c_chr_type THEN
        DBMS_SQL.Define_Column (l_csr_id, i, l_chr_val, 4000);
      WHEN c_num_type THEN
        DBMS_SQL.Define_Column (l_csr_id, i, l_num_val);
      WHEN c_dat_type THEN
        DBMS_SQL.Define_Column (l_csr_id, i, l_dat_val);
      WHEN c_stp_type THEN
         DBMS_SQL.Define_Column (l_csr_id, i, l_stp_val);
     ELSE
        Write_Log ('Col type ' || l_desctab(i).col_type || ' not accounted for!');
 
    END CASE;
 
  END LOOP;
 
  WHILE DBMS_SQL.Fetch_Rows (l_csr_id) > 0 LOOP
 
    l_val_lis := L1_chr_arr();
    l_val_lis.EXTEND (l_n_cols);
    FOR i IN 1 .. l_n_cols LOOP
 
      CASE l_desctab(i).col_type
 
        WHEN c_chr_type THEN
          DBMS_SQL.Column_Value (l_csr_id, i, l_chr_val);
          l_val_lis(i) := l_chr_val;
        WHEN c_num_type THEN
          DBMS_SQL.Column_Value (l_csr_id, i, l_num_val);
          l_val_lis(i) := l_num_val;
        WHEN c_dat_type THEN
          DBMS_SQL.Column_Value (l_csr_id, i, l_dat_val);
          l_val_lis(i) := l_dat_val;
        WHEN c_stp_type THEN
          DBMS_SQL.Column_Value (l_csr_id, i, l_stp_val);
          l_val_lis(i) := l_stp_val;
 
      END CASE;
 
    END LOOP;
 
    l_rec := Utils.List_Delim (l_val_lis);
    IF l_rec LIKE '%' || p_filter || '%' THEN
      l_res_lis.EXTEND;
      l_res_lis (l_res_lis.COUNT) := l_rec;
    END IF;
 
  END LOOP;
 
  DBMS_SQL.Close_Cursor (l_csr_id);
  RETURN l_res_lis;
 
END Cursor_to_Array;
 
BEGIN
 
  OPEN l_csr FOR c_query_1;
 
  l_res_lis := Cursor_to_Array (l_csr, 'SA_REP');
 
  FOR i IN 1..l_res_lis.COUNT LOOP
    Write_Log (i || ': ' || l_res_lis(i));
  END LOOP;
 
END;
/

 
Output for Cursor against HR.employees

1: 150|Peter|Tucker|PTUCKER|011.44.1344.129268|30-JAN-05|SA_REP|10000|.3|145|80|
2: 151|David|Bernstein|DBERNSTE|011.44.1344.345268|24-MAR-05|SA_REP|9500|.25|145|80|
3: 152|Peter|Hall|PHALL|011.44.1344.478968|20-AUG-05|SA_REP|9000|.25|145|80|
4: 153|Christopher|Olsen|COLSEN|011.44.1344.498718|30-MAR-06|SA_REP|8000|.2|145|80|
5: 154|Nanette|Cambrault|NCAMBRAU|011.44.1344.987668|09-DEC-06|SA_REP|7500|.2|145|80|
6: 155|Oliver|Tuvault|OTUVAULT|011.44.1344.486508|23-NOV-07|SA_REP|7000|.15|145|80|
7: 156|Janette|King|JKING|011.44.1345.429268|30-JAN-04|SA_REP|10000|.35|146|80|
8: 157|Patrick|Sully|PSULLY|011.44.1345.929268|04-MAR-04|SA_REP|9500|.35|146|80|
9: 158|Allan|McEwen|AMCEWEN|011.44.1345.829268|01-AUG-04|SA_REP|9000|.35|146|80|
10: 159|Lindsey|Smith|LSMITH|011.44.1345.729268|10-MAR-05|SA_REP|8000|.3|146|80|
11: 160|Louise|Doran|LDORAN|011.44.1345.629268|15-DEC-05|SA_REP|7500|.3|146|80|
12: 161|Sarath|Sewall|SSEWALL|011.44.1345.529268|03-NOV-06|SA_REP|7000|.25|146|80|
13: 162|Clara|Vishney|CVISHNEY|011.44.1346.129268|11-NOV-05|SA_REP|10500|.25|147|80|
14: 163|Danielle|Greene|DGREENE|011.44.1346.229268|19-MAR-07|SA_REP|9500|.15|147|80|
15: 164|Mattea|Marvins|MMARVINS|011.44.1346.329268|24-JAN-08|SA_REP|7200|.1|147|80|
16: 165|David|Lee|DLEE|011.44.1346.529268|23-FEB-08|SA_REP|6800|.1|147|80|
17: 166|Sundar|Ande|SANDE|011.44.1346.629268|24-MAR-08|SA_REP|6400|.1|147|80|
18: 167|Amit|Banda|ABANDA|011.44.1346.729268|21-APR-08|SA_REP|6200|.1|147|80|
19: 168|Lisa|Ozer|LOZER|011.44.1343.929268|11-MAR-05|SA_REP|11500|.25|148|80|
20: 169|Harrison|Bloom|HBLOOM|011.44.1343.829268|23-MAR-06|SA_REP|10000|.2|148|80|
21: 170|Tayler|Fox|TFOX|011.44.1343.729268|24-JAN-06|SA_REP|9600|.2|148|80|
22: 171|William|Smith|WSMITH|011.44.1343.629268|23-FEB-07|SA_REP|7400|.15|148|80|
23: 172|Elizabeth|Bates|EBATES|011.44.1343.529268|24-MAR-07|SA_REP|7300|.15|148|80|
24: 173|Sundita|Kumar|SKUMAR|011.44.1343.329268|21-APR-08|SA_REP|6100|.1|148|80|
25: 174|Ellen|Abel|EABEL|011.44.1644.429267|11-MAY-04|SA_REP|11000|.3|149|80|
26: 175|Alyssa|Hutton|AHUTTON|011.44.1644.429266|19-MAR-05|SA_REP|8800|.25|149|80|
27: 176|Jonathon|Taylor|JTAYLOR|011.44.1644.429265|24-MAR-06|SA_REP|8600|.2|149|80|
28: 177|Jack|Livingston|JLIVINGS|011.44.1644.429264|23-APR-06|SA_REP|8400|.2|149|80|
29: 178|Kimberely|Grant|KGRANT|011.44.1644.429263|24-MAY-07|SA_REP|7000|.15|149||
30: 179|Charles|Johnson|CJOHNSON|011.44.1644.429262|04-JAN-08|SA_REP|6200|.1|149|80|
 
PL/SQL procedure successfully completed.






 

SQL for Continuum and Contiguity Grouping

A question was asked some time ago on Oracle's SQL&PL/SQL forum (Solution design and performance - SQL or PL/SQL?), the gist of which the poster specified thus:

I have a set of records which keep track of a status at a given date for a range of points on a given road. Basically, I need the current bits to "shine through".

The thread, despite the open-minded title, gives a nice illustration of the odd preference that people often have for complicated PL/SQL solutions to problems amenable to simpler SQL. I provided an SQL solution in that thread for this problem, and in this article I have taken a simpler, more general form of the problem defined there, and provide SQL solutions with diagrams illustrating how they work.

The class of problem can be characterised as follows:

  • Records have range fields, and we want to aggregate separately at each point within the 1-dimensional range domains (or 'continuum'), independently by grouping key
  • Within the groups we want to aggregate only the first or last records, ordering by some non-key fields

The first point above can be seen as equivalent to adding in to the main grouping key an implicit field specifying the domain leg, i.e. the region between the break points defined by the record ranges, and splitting the records by leg. We might term this form of aggregation continuum aggregation, or perhaps vertical aggregation if we view the range as distance, the internal ordering as by time, and visualise it graphically as in my diagrams below. Once this vertical aggregation is established, it is natural to think of adding a second aggregation, that might be termed contiguity aggregation, or with the same visualisation, horizontal aggregation:

  • Contiguous legs having the same values for the aggregated attributes will be grouped together

Here is an extract on grouping from Oracle® Database SQL Language Reference:

Oracle applies the aggregate functions to each group of rows and returns a single result row for each group.
...
The aggregate functions MIN, MAX, SUM, AVG, COUNT, VARIANCE, and STDDEV, when followed by the KEEP keyword, can be used in conjunction with the FIRST or LAST function to operate on a set of values from a set of rows that rank as the FIRST or LAST with respect to a given sorting specification. Refer to FIRST for more information.

A simple use-case for the KEEP form of grouping is to list contacts with their most recent telephone number when multiple numbers are stored in a separate table. A few years ago, I realised that in most examples that I see developers write their own code instead of using the built-in constructs, and I wrote an article comparing the performance and complexity of the various alternatives for this requirement (as well as alternatives for SQL pivoting), SQL Pivot and Prune Queries - Keeping an Eye on Performance.

Update, 20 November 2013: Added a Postgres version of the SQL solution.

Test Problem

Data Model

We take for our example problem a very simple model consisting of roads and road events where the events occur over a stretch of road at a given time, and event type forms the horizontal grouping attribute.

Road - ERD2

Test Data

Input data - Roads

ROAD_ID ROAD_DESC       START_POINT  END_POINT
------- --------------- ----------- ----------
      1 The Strand                0        200
      2 Piccadilly                0        100

Input data - road_events

ROAD_ID     REV_ID E_TYPE START_POINT  END_POINT E_DATE
------- ---------- ------ ----------- ---------- ---------
      1          1 OPEN             0         10 01-JAN-07
                 2 OPEN            20         50 01-JAN-08
                 3 CLOSED         130        160 01-FEB-08
                 4 CLOSED          55         85 05-JUN-08
                 5 OTHER           45        115 01-JAN-09
                 6 OPEN            60        100 12-FEB-11
                 7 CLOSED         115        145 12-FEB-12
      2          8 CLOSED          10         30 01-JAN-10
                 9 OPEN            40         50 01-JAN-11
                10 OPEN            50         70 01-JAN-12

10 rows selected.

The following diagrams display the data and solutions for our test problem.

Road - Road 1

Road - Road 2

SQL Solution for 'Point' Problem

To start with, here is a standard SQL solution for the 'zero-dimensional' problem, where the most recent record is required for each road:

Zero-Dimensional Solution

ROAD_DESC          R_START      R_END    E_START      E_END E_DATE    E_TYPE
--------------- ---------- ---------- ---------- ---------- --------- ------
Piccadilly               0        100         50         70 01-JAN-12 OPEN
The Strand               0        200        115        145 12-FEB-12 CLOSED

  1  SELECT r.road_desc, r.start_point r_start, r.end_point r_end,
  2         Max (e.start_point) KEEP (DENSE_RANK LAST ORDER BY e.event_date) e_start,
  3         Max (e.end_point) KEEP (DENSE_RANK LAST ORDER BY e.event_date) e_end,
  4         Max (e.event_date) KEEP (DENSE_RANK LAST ORDER BY e.event_date) e_date,
  5         Max (e.event_type) KEEP (DENSE_RANK LAST ORDER BY e.event_date) e_type
  6    FROM road_events e
  7    JOIN roads r
  8      ON r.id = e.road_id
  9   GROUP BY r.road_desc, r.start_point, r.end_point
 10*  ORDER BY 1, 2, 3

The SQL is more complicated for the continuum problem, and we provide two versions, that differ in the final stage, of horizontal grouping by contiguous event type. The first uses a differencing method popular in Oracle 11g and earlier versions for this common type of grouping problem; the second uses a new feature from Oracle 12c, row pattern matching. [I have also used another technique for this type of grouping, in an article on contiguity and other range-based grouping problems in June 2011, Forming Range-Based Break Groups With Advanced SQL.]

SQL Solution for 'Continuum' Problem, Contiguity Grouping by Differences

SQL (Contiguity by Differences)

WITH breaks AS  (
        SELECT road_id, start_point bp FROM road_events
         UNION
        SELECT road_id, end_point FROM road_events
         UNION
        SELECT id, start_point FROM roads
         UNION
        SELECT id, end_point FROM roads
), legs AS (
        SELECT road_id, bp leg_start, Lead (bp) OVER (PARTITION BY road_id ORDER BY bp) leg_end
          FROM breaks
), latest_events AS ( 
        SELECT l.road_id, l.leg_start, l.leg_end,
               Max (e.id) KEEP (DENSE_RANK LAST ORDER BY e.event_date) event_id,
               Nvl (Max (e.event_type) KEEP (DENSE_RANK LAST ORDER BY e.event_date), '(none)') event_type
          FROM legs l
          LEFT JOIN road_events e
            ON e.road_id = l.road_id
           AND e.start_point <= l.leg_start
	   AND e.end_point >= l.leg_end
         WHERE l.leg_end IS NOT NULL
         GROUP BY l.road_id, l.leg_start, l.leg_end
), latest_events_group AS ( 
        SELECT road_id,
               leg_start,
               leg_end,
               event_id,
               event_type,
               Dense_Rank () OVER (PARTITION BY road_id ORDER BY leg_start, leg_end) -
               Dense_Rank () OVER (PARTITION BY road_id, event_type ORDER BY leg_start, leg_end) group_no
          FROM latest_events
)
SELECT l.road_id, r.road_desc,
       Min (l.leg_start)        sec_start,
       Max (l.leg_end)          sec_end,
       l.event_type             e_type,
       l.group_no
  FROM latest_events_group l
  JOIN roads r
    ON r.id = l.road_id
 GROUP BY l.road_id,
        r.road_desc, 
        l.event_type,
        l.group_no
ORDER BY 1, 2, 3
/

ROAD_ID ROAD_DESC        SEC_START    SEC_END E_TYPE   GROUP_NO
------- --------------- ---------- ---------- ------ ----------
      1 The Strand               0         10 OPEN            0
                                10         20 (none)          1
                                20         45 OPEN            1
                                45         60 OTHER           3
                                60        100 OPEN            4
                               100        115 OTHER           5
                               115        160 CLOSED          9
                               160        200 (none)         11
      2 Piccadilly               0         10 (none)          0
                                10         30 CLOSED          1
                                30         40 (none)          1
                                40         70 OPEN            3
                                70        100 (none)          3

13 rows selected.

Query Structure Diagram (Contiguity by Differences)Road, V1.5 - QSD-DiffExecution Plan (Contiguity by Differences)

--------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                       | Name          | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
--------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                |               |      1 |        |     13 |00:00:00.01 |      25 |       |       |          |
|   1 |  SORT ORDER BY                  |               |      1 |      2 |     13 |00:00:00.01 |      25 |  2048 |  2048 | 2048  (0)|
|   2 |   HASH GROUP BY                 |               |      1 |      2 |     13 |00:00:00.01 |      25 |   900K|   900K| 1343K (0)|
|   3 |    MERGE JOIN                   |               |      1 |     24 |     19 |00:00:00.01 |      25 |       |       |          |
|   4 |     TABLE ACCESS BY INDEX ROWID | ROADS         |      1 |      2 |      2 |00:00:00.01 |       2 |       |       |          |
|   5 |      INDEX FULL SCAN            | ROAD_PK       |      1 |      2 |      2 |00:00:00.01 |       1 |       |       |          |
|*  6 |     SORT JOIN                   |               |      2 |     24 |     19 |00:00:00.01 |      23 |  2048 |  2048 | 2048  (0)|
|   7 |      VIEW                       |               |      1 |     24 |     19 |00:00:00.01 |      23 |       |       |          |
|   8 |       WINDOW SORT               |               |      1 |     24 |     19 |00:00:00.01 |      23 |  2048 |  2048 | 2048  (0)|
|   9 |        WINDOW NOSORT            |               |      1 |     24 |     19 |00:00:00.01 |      23 | 73728 | 73728 |          |
|  10 |         SORT GROUP BY           |               |      1 |     24 |     19 |00:00:00.01 |      23 |  4096 |  4096 | 4096  (0)|
|* 11 |          HASH JOIN OUTER        |               |      1 |     24 |     25 |00:00:00.01 |      23 |  1696K|  1696K|  540K (0)|
|* 12 |           VIEW                  |               |      1 |     24 |     19 |00:00:00.01 |      16 |       |       |          |
|  13 |            WINDOW SORT          |               |      1 |     24 |     21 |00:00:00.01 |      16 |  2048 |  2048 | 2048  (0)|
|  14 |             VIEW                |               |      1 |     24 |     21 |00:00:00.01 |      16 |       |       |          |
|  15 |              SORT UNIQUE        |               |      1 |     24 |     21 |00:00:00.01 |      16 |  2048 |  2048 | 2048  (0)|
|  16 |               UNION-ALL         |               |      1 |        |     24 |00:00:00.01 |      16 |       |       |          |
|  17 |                INDEX FULL SCAN  | ROAD_EVENT_N1 |      1 |     10 |     10 |00:00:00.01 |       1 |       |       |          |
|  18 |                INDEX FULL SCAN  | ROAD_EVENT_N3 |      1 |     10 |     10 |00:00:00.01 |       1 |       |       |          |
|  19 |                TABLE ACCESS FULL| ROADS         |      1 |      2 |      2 |00:00:00.01 |       7 |       |       |          |
|  20 |                TABLE ACCESS FULL| ROADS         |      1 |      2 |      2 |00:00:00.01 |       7 |       |       |          |
|  21 |           TABLE ACCESS FULL     | ROAD_EVENTS   |      1 |     10 |     10 |00:00:00.01 |       7 |       |       |          |
--------------------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   6 - access("R"."ID"="L"."ROAD_ID")
       filter("R"."ID"="L"."ROAD_ID")
  11 - access("E"."ROAD_ID"="L"."ROAD_ID")
       filter(("E"."START_POINT"<="L"."LEG_START" AND "E"."END_POINT">="L"."LEG_END"))
  12 - filter("L"."LEG_END" IS NOT NULL)

SQL Solution for 'Continuum' Problem, Contiguity Grouping by 12c Row Pattern Matching

SQL (Contiguity by Pattern Matching)

WITH breaks AS  (
        SELECT road_id, start_point bp FROM road_events
         UNION
        SELECT road_id, end_point FROM road_events
         UNION
        SELECT id, start_point FROM roads
         UNION
        SELECT id, end_point FROM roads
), legs AS (
        SELECT road_id, bp leg_start, Lead (bp) OVER (PARTITION BY road_id ORDER BY bp) leg_end
          FROM breaks
), latest_events AS ( 
        SELECT l.road_id, r.road_desc, l.leg_start, l.leg_end,
               Max (e.id) KEEP (DENSE_RANK LAST ORDER BY e.event_date) event_id,
               Nvl (Max (e.event_type) KEEP (DENSE_RANK LAST ORDER BY e.event_date), '(none)') event_type
          FROM legs l
          JOIN roads r
            ON r.id = l.road_id
          LEFT JOIN road_events e
            ON e.road_id = l.road_id
           AND e.start_point <= l.leg_start
	   AND e.end_point >= l.leg_end
         WHERE l.leg_end IS NOT NULL
         GROUP BY l.road_id, r.road_desc, l.leg_start, l.leg_end
)
SELECT m.road_id, m.road_desc, m.sec_start, m.sec_end, m.event_type e_type
  FROM latest_events
 MATCH_RECOGNIZE (
   PARTITION BY road_id, road_desc
   ORDER BY leg_start, leg_end
   MEASURES FIRST (leg_start) sec_start,
            LAST (leg_end) sec_end,
            LAST (event_type) event_type
   PATTERN (strt sm*)
   DEFINE sm AS PREV(sm.event_type) = sm.event_type
 ) m
ORDER BY 1, 2, 3
/

ROAD_ID ROAD_DESC        SEC_START    SEC_END E_TYPE
------- --------------- ---------- ---------- ------
      1 The Strand               0         10 OPEN
                                10         20 (none)
                                20         45 OPEN
                                45         60 OTHER
                                60        100 OPEN
                               100        115 OTHER
                               115        160 CLOSED
                               160        200 (none)
      2 Piccadilly               0         10 (none)
                                10         30 CLOSED
                                30         40 (none)
                                40         70 OPEN
                                70        100 (none)

13 rows selected.

Query Structure Diagram (Contiguity by Pattern Matching)Road, V1.5 - QSD-MRExecution Plan (Contiguity by Pattern Matching)

-------------------------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                                        | Name          | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
-------------------------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                                 |               |      1 |        |     13 |00:00:00.01 |      25 |       |       |          |
|   1 |  SORT ORDER BY                                   |               |      1 |      2 |     13 |00:00:00.01 |      25 |  2048 |  2048 | 2048  (0)|
|   2 |   VIEW                                           |               |      1 |      2 |     13 |00:00:00.01 |      25 |       |       |          |
|   3 |    MATCH RECOGNIZE SORT DETERMINISTIC FINITE AUTO|               |      1 |      2 |     13 |00:00:00.01 |      25 |  2048 |  2048 | 2048  (0)|
|   4 |     VIEW                                         |               |      1 |      2 |     19 |00:00:00.01 |      25 |       |       |          |
|   5 |      SORT GROUP BY                               |               |      1 |      2 |     19 |00:00:00.01 |      25 |  4096 |  4096 | 4096  (0)|
|*  6 |       HASH JOIN OUTER                            |               |      1 |     24 |     25 |00:00:00.01 |      25 |   987K|   987K|  525K (0)|
|   7 |        MERGE JOIN                                |               |      1 |     24 |     19 |00:00:00.01 |      18 |       |       |          |
|   8 |         TABLE ACCESS BY INDEX ROWID              | ROADS         |      1 |      2 |      2 |00:00:00.01 |       2 |       |       |          |
|   9 |          INDEX FULL SCAN                         | ROAD_PK       |      1 |      2 |      2 |00:00:00.01 |       1 |       |       |          |
|* 10 |         SORT JOIN                                |               |      2 |     24 |     19 |00:00:00.01 |      16 |  2048 |  2048 | 2048  (0)|
|* 11 |          VIEW                                    |               |      1 |     24 |     19 |00:00:00.01 |      16 |       |       |          |
|  12 |           WINDOW SORT                            |               |      1 |     24 |     21 |00:00:00.01 |      16 |  2048 |  2048 | 2048  (0)|
|  13 |            VIEW                                  |               |      1 |     24 |     21 |00:00:00.01 |      16 |       |       |          |
|  14 |             SORT UNIQUE                          |               |      1 |     24 |     21 |00:00:00.01 |      16 |  2048 |  2048 | 2048  (0)|
|  15 |              UNION-ALL                           |               |      1 |        |     24 |00:00:00.01 |      16 |       |       |          |
|  16 |               INDEX FULL SCAN                    | ROAD_EVENT_N1 |      1 |     10 |     10 |00:00:00.01 |       1 |       |       |          |
|  17 |               INDEX FULL SCAN                    | ROAD_EVENT_N3 |      1 |     10 |     10 |00:00:00.01 |       1 |       |       |          |
|  18 |               TABLE ACCESS FULL                  | ROADS         |      1 |      2 |      2 |00:00:00.01 |       7 |       |       |          |
|  19 |               TABLE ACCESS FULL                  | ROADS         |      1 |      2 |      2 |00:00:00.01 |       7 |       |       |          |
|  20 |        TABLE ACCESS FULL                         | ROAD_EVENTS   |      1 |     10 |     10 |00:00:00.01 |       7 |       |       |          |
-------------------------------------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   6 - access("E"."ROAD_ID"="L"."ROAD_ID")
       filter(("E"."START_POINT"<="L"."LEG_START" AND "E"."END_POINT">="L"."LEG_END"))
  10 - access("R"."ID"="L"."ROAD_ID")
       filter("R"."ID"="L"."ROAD_ID")
  11 - filter("L"."LEG_END" IS NOT NULL)

Note
-----
   - this is an adaptive plan

SQL Solution for 'Continuum' Problem, Contiguity Grouping - Postgres

The Oracle v11 (and earlier versions) solution, with contiguity by differences, can be converted to work in Postgres, as shown below.

SQL (Continuum by Row_Number, Contiguity by Differences - Postgres)

WITH breaks AS  (
        SELECT road_id, start_point bp FROM road_events
         UNION
        SELECT road_id, end_point FROM road_events
         UNION
        SELECT id, start_point FROM roads
         UNION
        SELECT id, end_point FROM roads
), legs AS (
        SELECT road_id, bp leg_start, Lead (bp) OVER (PARTITION BY road_id ORDER BY bp) leg_end
          FROM breaks
), ranked_events AS ( 
        SELECT l.road_id, l.leg_start, l.leg_end,
               e.id event_id, Coalesce (e.event_type, '(none)') event_type,
               Row_Number() OVER (PARTITION BY l.road_id, l.leg_start ORDER BY e.event_date DESC) rnk
          FROM legs l
          LEFT JOIN road_events e
            ON e.road_id = l.road_id
           AND e.start_point <= l.leg_start            AND e.end_point >= l.leg_end
         WHERE l.leg_end IS NOT NULL
), latest_events_group AS ( 
        SELECT road_id,
               leg_start,
               leg_end,
               event_id,
               event_type,
               Dense_Rank () OVER (PARTITION BY road_id ORDER BY leg_start, leg_end) -
               Dense_Rank () OVER (PARTITION BY road_id, event_type ORDER BY leg_start, leg_end) group_no
          FROM ranked_events
         WHERE rnk = 1
)
SELECT l.road_id, r.road_desc,
       Min (l.leg_start)        sec_start,
       Max (l.leg_end)          sec_end,
       l.event_type             e_type,
       l.group_no
  FROM latest_events_group l
  JOIN roads r
    ON r.id = l.road_id
 GROUP BY l.road_id,
        r.road_desc, 
        l.event_type,
        l.group_no
ORDER BY 1, 2, 3;

Continuum/contiguity Solution with Row_Number...
 road_id | road_desc  | sec_start | sec_end | e_type | group_no 
---------+------------+-----------+---------+--------+----------
       1 | The Strand |         0 |      10 | OPEN   |        0
       1 | The Strand |        10 |      20 | (none) |        1
       1 | The Strand |        20 |      45 | OPEN   |        1
       1 | The Strand |        45 |      60 | OTHER  |        3
       1 | The Strand |        60 |     100 | OPEN   |        4
       1 | The Strand |       100 |     115 | OTHER  |        5
       1 | The Strand |       115 |     160 | CLOSED |        9
       1 | The Strand |       160 |     200 | (none) |       11
       2 | Piccadilly |         0 |      10 | (none) |        0
       2 | Piccadilly |        10 |      30 | CLOSED |        1
       2 | Piccadilly |        30 |      40 | (none) |        1
       2 | Piccadilly |        40 |      70 | OPEN   |        3
       2 | Piccadilly |        70 |     100 | (none) |        3
(13 rows)

SELECT Version();

Postgres version...
                           version                           
-------------------------------------------------------------
 PostgreSQL 9.3.1, compiled by Visual C++ build 1600, 64-bit
(1 row)

Notes on Conversion of SQL to Postgres

  • Postgres does not have an exact equivalent of Oracle's KEEP/FIRST grouping functionality, but it can be emulated via the analytic function Row_Number within a subquery
  • Coalesce, which is also available in Oracle, replaces Nvl, which does not exist in Postgres
  • Oracle's execution plans were obtained using DBMS_XPlan after running the queries, while the Postgres version was obtained by running the query prefaced by 'EXPLAIN ANALYZE '
  • There is no Postgres equivalent of Oracle v12's row pattern matching

Query Structure Diagram (Continuum by Row_Number, Contiguity by Differences - Postgres) Road, V1.5 - QSD-PGExecution Plan (Continuum by Row_Number, Contiguity by Differences - Postgres)

Prefacing the query with 'EXPLAIN ANALYZE ' gives:

Explaining Continuum/contiguity Solution with Row_Number...
                                                                 QUERY PLAN                                                                  
---------------------------------------------------------------------------------------------------------------------------------------------
 Sort  (cost=619.45..619.47 rows=8 width=270) (actual time=0.235..0.235 rows=13 loops=1)
   Sort Key: l.road_id, r.road_desc, (min(l.leg_start))
   Sort Method: quicksort  Memory: 26kB
   CTE breaks
     ->  HashAggregate  (cost=79.50..95.30 rows=1580 width=8) (actual time=0.013..0.020 rows=21 loops=1)
           ->  Append  (cost=0.00..71.60 rows=1580 width=8) (actual time=0.002..0.006 rows=24 loops=1)
                 ->  Seq Scan on road_events  (cost=0.00..14.80 rows=480 width=8) (actual time=0.001..0.003 rows=10 loops=1)
                 ->  Seq Scan on road_events road_events_1  (cost=0.00..14.80 rows=480 width=8) (actual time=0.000..0.002 rows=10 loops=1)
                 ->  Seq Scan on roads  (cost=0.00..13.10 rows=310 width=8) (actual time=0.000..0.001 rows=2 loops=1)
                 ->  Seq Scan on roads roads_1  (cost=0.00..13.10 rows=310 width=8) (actual time=0.000..0.000 rows=2 loops=1)
   CTE legs
     ->  WindowAgg  (cost=115.54..147.14 rows=1580 width=8) (actual time=0.030..0.041 rows=21 loops=1)
           ->  Sort  (cost=115.54..119.49 rows=1580 width=8) (actual time=0.028..0.029 rows=21 loops=1)
                 Sort Key: breaks.road_id, breaks.bp
                 Sort Method: quicksort  Memory: 25kB
                 ->  CTE Scan on breaks  (cost=0.00..31.60 rows=1580 width=8) (actual time=0.014..0.023 rows=21 loops=1)
   CTE ranked_events
     ->  WindowAgg  (cost=290.71..326.08 rows=1572 width=138) (actual time=0.089..0.104 rows=25 loops=1)
           ->  Sort  (cost=290.71..294.64 rows=1572 width=138) (actual time=0.088..0.089 rows=25 loops=1)
                 Sort Key: l_1.road_id, l_1.leg_start, e.event_date
                 Sort Method: quicksort  Memory: 26kB
                 ->  Hash Left Join  (cost=20.80..207.25 rows=1572 width=138) (actual time=0.044..0.079 rows=25 loops=1)
                       Hash Cond: (l_1.road_id = e.road_id)
                       Join Filter: ((e.start_point <= l_1.leg_start) AND (e.end_point >= l_1.leg_end))
                       Rows Removed by Join Filter: 89
                       ->  CTE Scan on legs l_1  (cost=0.00..31.60 rows=1572 width=12) (actual time=0.031..0.048 rows=19 loops=1)
                             Filter: (leg_end IS NOT NULL)
                             Rows Removed by Filter: 2
                       ->  Hash  (cost=14.80..14.80 rows=480 width=138) (actual time=0.005..0.005 rows=10 loops=1)
                             Buckets: 1024  Batches: 1  Memory Usage: 1kB
                             ->  Seq Scan on road_events e  (cost=0.00..14.80 rows=480 width=138) (actual time=0.001..0.002 rows=10 loops=1)
   CTE latest_events_group
     ->  WindowAgg  (cost=35.79..36.01 rows=8 width=48) (actual time=0.165..0.181 rows=19 loops=1)
           ->  Sort  (cost=35.79..35.81 rows=8 width=48) (actual time=0.164..0.165 rows=19 loops=1)
                 Sort Key: ranked_events.road_id, ranked_events.event_type, ranked_events.leg_start, ranked_events.leg_end
                 Sort Method: quicksort  Memory: 26kB
                 ->  WindowAgg  (cost=35.49..35.67 rows=8 width=48) (actual time=0.124..0.138 rows=19 loops=1)
                       ->  Sort  (cost=35.49..35.51 rows=8 width=48) (actual time=0.123..0.124 rows=19 loops=1)
                             Sort Key: ranked_events.road_id, ranked_events.leg_start, ranked_events.leg_end
                             Sort Method: quicksort  Memory: 26kB
                             ->  CTE Scan on ranked_events  (cost=0.00..35.37 rows=8 width=48) (actual time=0.090..0.117 rows=19 loops=1)
                                   Filter: (rnk = 1)
                                   Rows Removed by Filter: 6
   ->  HashAggregate  (cost=14.72..14.80 rows=8 width=270) (actual time=0.218..0.221 rows=13 loops=1)
         ->  Hash Join  (cost=0.26..14.60 rows=8 width=270) (actual time=0.203..0.207 rows=19 loops=1)
               Hash Cond: (r.id = l.road_id)
               ->  Seq Scan on roads r  (cost=0.00..13.10 rows=310 width=222) (actual time=0.002..0.002 rows=2 loops=1)
               ->  Hash  (cost=0.16..0.16 rows=8 width=52) (actual time=0.192..0.192 rows=19 loops=1)
                     Buckets: 1024  Batches: 1  Memory Usage: 2kB
                     ->  CTE Scan on latest_events_group l  (cost=0.00..0.16 rows=8 width=52) (actual time=0.167..0.190 rows=19 loops=1)
 Total runtime: 0.432 ms
(51 rows)

Code

Here is the code: Road-SQL






Messages from Outer Space

 

I began my career in IT in 1984, before the internet and even before widespread email availability. In those days one learnt about technology and other subjects largely through books and papers, training courses, and one's immediate colleagues. Since then the rise of the internet has transformed the learning process, vastly expanding the material available.

In its earlier years users could be roughly divided into a large group of consumers and a much smaller group of producers; later, and increasingly in recent years, the emergence of what is sometimes called 'Web 2' has enabled many consumers to become producers as well. As Wikipedia (itself a prime example of the phenomenon), Web 2.0, puts it:

"A Web 2.0 site may allow users to interact and collaborate with each other in a social media dialogue as creators of user-generated content in a virtual community..."

For IT developers and other technical people this is hugely important because it expands the pool of available expertise in one's field from a few colleagues and a relatively small group of publishers to potentially everyone working in the field. This means that good ideas and best practices quickly become available to all. Where in the past bad practices or antipatterns could become entrenched in a company through the influence of a small number of people sharing a bad idea, today we can check what the rest of the world thinks. It's a bit like the old scifi motif in which an advanced civilisation comes to share its ideas with Planet Earth :).

et

However, great though this is, it's necessary to make the effort to keep up with best practice in one's own field, and not all developers do that. In my main field, Oracle database development, the resources I find most useful are:

As well as keeping up with the general Oracle community, developers should ideally run their own blog to maximise learning.

The remainder of this article consists of useful links concerning best (or worst) practices that I deem significant in database development, largely in areas where people commonly get it wrong. This article will be an ongoing work in progress.

Database Design

Database Design and the Leaning Tower of Pisa

This article by Rodger Lepinsky notes that database table designs are usually done very quickly and tend not to be re-worked as the application is developed to avoid impacting developers. The problem is that this apparently justifiable reluctance to re-work often results in much additional code to work around inevitable deficiencies in the initial data model, and ultimately a much more complex system: It's short-sighted in other words.

Here's a nice cartoon illustrating a common database design antipattern taken to its logical conclusion 🙂

The EAV Data Model

Design Consistency

Rodger refers to database designs becoming frozen too early in the article mentioned in the previous section. I believe this is a design antipattern that occurs very widely in general. Often a new technology is applied for a new project, one that the developers may not know very well at first; similarly, custom frameworks are often developed, in Unix or Perl, or whatever, and the initial production versions are rarely perfect. However, once something works, the tendency is to freeze it, with all its limitations, for fear of unforeseen impacts, or even purely from the notion that consistency is more important than quality.

I think that this excessive emphasis on 'consistency' is one of the main reasons that so many over-complex, poor quality systems persist indefinitely. It might be better to focus on 'consistently' applying best practice as currently understood.

Data Access Layers

Considering SQL as a Service

The idea of 'modularising' SQL through data access layers is one that comes up frequently on Oracle forums, including the Ask Tom thread above, and is well known to be an antipattern. I deal with it in a wider context here:

SQL and Modularity: Patterns, Anti-Patterns and the Kitchen Sink

Here is another relevant AskTom thread:

Multi-Level Views

"I prefer a SINGLE LEVEL of views. Yes, there will be some repetition in their definition but I don't care about that. You can document that. You can maintain that"

ETL vs ELT

ETL - Using the wrong tool for the job

Companies often use a mix of ETL and ELT with Informatica and Oracle, among other tools. Here is Tom Kyte's pithy summation:

"elt = extract, load and then transform (forget any tools, if you have hundreds of gb's or tb's of data - you'll be doing this down to the wire, not with pretty pictures and push buttons)

etl = extract, transform and then load - without using the database to transform

elt = going light speed

etl = going by boat"

Object Relational Madness (ORM)

Arguments against using an ORM layer - an ammunition stockpile

Brilliant article with collation of links on the subject, including one that compares ORM to the Vietnam war (perhaps understating the case against) 🙂






SQL for the Travelling Salesman Problem

'The travelling salesman problem (TSP) or travelling salesperson problem asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.' - Travelling salesman problem.

['or travelling salesperson problem' - :)]

I posted a couple of articles recently on approximate solution methods for 'hard' combinatorial problems using SQL, SQL for the Balanced Number Partitioning Problem and SQL for the Fantasy Football Knapsack Problem, and I wondered whether similar techniques could be applied to TSP. This article provides my answer.

Updated, 20 February 2016: Added attachment with the input data files, DDL and raw results at the end.

Update, 12 November 2017: I have added all the scripts necessary to run the SQL against the two example datasets to my GitHub repo: Brendan's repo for interesting SQL. I also add a link to a recent useful primer on TSP: The Trials And Tribulations Of The Traveling Salesman.

Test Problems

I used two test problems, the first being a simple constructed example of five towns arranged in an M-shape. The second is a more realistic problem based on 312 towns in USA and Canada, the data for which I found on a university web site.

Test Problem 1: Emland

The first problem is small enough to verify the solutions manually.

The Short Route
TSP, v1.0 - Short

The Long Route
TSP, v1.0 - Long
Test Problem 2: USCA312

I got the second problem here, City Distance Datasets, described thus:
'USCA312 describes 312 cities in the US and Canada. Distances between the city are computed from latitude and longitude, not from road mileage'

I took the distances based on the x-y values given, using the simple Euclidean distance formula. I am aware that this will not give accurate distances, but it seemed the simplest approach as the provided distances were in a format not so easy to load into a database, and I am interested only in the technical aspects.

SQL Solution with Recursive Subquery Factoring

SQL

WITH count_towns AS (
SELECT Count(*) n_towns FROM towns
), dist_from_root AS (/* XTSP  */
SELECT a, b, dst, Row_Number () OVER (ORDER BY :SIGN * dst) rnk_by_dst, Count(DISTINCT a) OVER () + 1 n_towns
  FROM distances
 WHERE b > a
),  rsf (root, root_leg, path_rnk, nxt_id, lev, tot_price, path, n_towns) AS (
SELECT a, a || ' -> ' || b, 0, d.b, 2, d.dst, 
       CAST ('|' || LPad (d.a, 3, '0') || '|' || LPad (d.b, 3, '0') AS VARCHAR2(4000)) path,
       d.n_towns
  FROM dist_from_root d
 WHERE d.rnk_by_dst <= :KEEP_NUM_ROOT
 UNION ALL
SELECT r.root,
       r.root_leg,
       Row_Number() OVER (PARTITION BY r.root_leg ORDER BY :SIGN * (r.tot_price + d.dst)),
       d.b,
       r.lev + 1,
       r.tot_price + d.dst,
       r.path || '|' || LPad (d.b, 3, '0'),
       r.n_towns
  FROM rsf r
  JOIN distances d
    ON d.a = r.nxt_id
   AND r.path NOT LIKE '%' || '|' || LPad (d.b, 3, '0') || '%'
 WHERE r.path_rnk <= :KEEP_NUM
), circuits AS (
SELECT r.root_leg,
       Row_Number() OVER (PARTITION BY r.root_leg ORDER BY :SIGN * (r.tot_price + d.dst)) path_rnk,
       r.tot_price + d.dst tot_price,
       r.path || '|' || LPad (d.b, 3, '0') path
  FROM rsf r
  JOIN distances d
    ON d.a = r.nxt_id
   AND d.b = r.root
 WHERE r.lev = r.n_towns
   AND r.path_rnk <= :KEEP_NUM
), top_n_paths AS (
SELECT root_leg,
       tot_price,
       path,
       path_rnk,
       town_index
  FROM circuits
  CROSS JOIN (SELECT LEVEL town_index FROM count_towns c CONNECT BY LEVEL <= c.n_towns + 1)
 WHERE path_rnk <= :KEEP_NUM
), top_n_sets AS (
SELECT root_leg,
       tot_price,
       path,
       path_rnk,
       town_index,
       To_Number (Substr (path, (town_index - 1) * 4 + 2, 3)) town_id,
       Lag (To_Number (Substr (path, (town_index - 1) * 4 + 2, 3))) OVER (PARTITION BY root_leg, path_rnk ORDER BY town_index) town_id_prior
  FROM top_n_paths
)
SELECT /*+ GATHER_PLAN_STATISTICS */
       top.root_leg,
       top.path_rnk,
       Round (top.tot_price, 2) tot_dist,
       top.town_id,
       twn.name,
       Round (dst.dst, 2) leg_dist,
       Round (Sum (dst.dst) OVER (PARTITION BY root_leg, path_rnk ORDER BY town_index), 2) cum_dist
  FROM top_n_sets top
  JOIN towns twn
    ON twn.id = top.town_id
  LEFT JOIN distances dst
    ON dst.a = top.town_id_prior
   AND dst.b = top.town_id
ORDER BY top.root_leg, top.path_rnk, top.town_index

How It Works

Bind Variables
==============
SIGN - 1 means minimise distance; -1, maximise it
KEEP_NUM_ROOT - number of best anchor records (root legs) to retain (throughout)
KEEP_NUM - number of best records from previous iteration to retain, partitioning by root leg

The solution approach is based on the idea I had in my last article whereby recursive subquery factoring is at the heart of the method, and analytic row numbering is used to reduce searching to manageable proportions at each iteration. The bind variables control the level of searching desired.

  • count_towns subquery - simply counts the total number of towns
  • dist_from_root subquery - gets the distance between each pair of towns, without duplication, and ranks the pairs by distance
  • rsf subquery, anchor branch - selects the KEEP_NUM_ROOT best legs as roots for the recursion
  • rsf subquery, recursive branch - joins up to KEEP_NUM best records from last iteration all possible town via distances table, using pattern matching to exclude towns already visited
  • The recursive branch stores the towns visited in a delimited string
  • Analytic funtion Row_Number is used to rank the recursive branch result set at each iteration, partitioning by root leg for use in the next iteration
  • circuits subquery - completes the circuit by joining the root leg via the distances table, doing the same constraint by rank and analytic ranking as the recursive branch
  • top_n_paths subquery - uses a standard row generator subquery to generate indexed rows for the number of towns in the final path (my where clause looks redundant as I write)
  • top_n_sets subquery - extracts the town id from the path using the index derived in the previous subquery, and gets the previous town id using analytic Lag
  • Main query - joins towns table to get the town name and distances table for leg distances

Results

Test Problem 1: Emland

I used keep values of 5 and 5 and solved the shortest routes problem in 0.14 seconds, and the longest in 0.16 seconds.

Shortest Routes
===============
ROOT_LEG       PATH_RNK   TOT_DIST    TOWN_ID NAME                             LEG_DIST   CUM_DIST
------------ ---------- ---------- ---------- ------------------------------ ---------- ----------
1 -> 2                1      10.94          1 Left Floor
                                            2 Left Peak                            2.24       2.24
                                            4 Right Peak                              2       4.24
                                            5 Right Floor                          2.24       6.47
                                            3 Midfield                             2.24       8.71
                                            1 Left Floor                           2.24      10.94
                      2       11.3          1 Left Floor
                                            2 Left Peak                            2.24       2.24
                                            3 Midfield                             1.41       3.65
                                            4 Right Peak                           1.41       5.06
                                            5 Right Floor                          2.24        7.3
                                            1 Left Floor                              4       11.3
                      3      11.73          1 Left Floor
                                            2 Left Peak                            2.24       2.24
                                            5 Right Floor                          3.61       5.84
                                            4 Right Peak                           2.24       8.08
                                            3 Midfield                             1.41       9.49
                                            1 Left Floor                           2.24      11.73
                      4      11.73          1 Left Floor
                                            2 Left Peak                            2.24       2.24
                                            3 Midfield                             1.41       3.65
                                            5 Right Floor                          2.24       5.89
                                            4 Right Peak                           2.24       8.12
                                            1 Left Floor                           3.61      11.73
                      5      11.89          1 Left Floor
                                            2 Left Peak                            2.24       2.24
                                            4 Right Peak                              2       4.24
                                            3 Midfield                             1.41       5.65
                                            5 Right Floor                          2.24       7.89
                                            1 Left Floor                              4      11.89
2 -> 3                1       11.3          2 Left Peak
                                            3 Midfield                             1.41       1.41
                                            4 Right Peak                           1.41       2.83
                                            5 Right Floor                          2.24       5.06
                                            1 Left Floor                              4       9.06
                                            2 Left Peak                            2.24       11.3
                      2      11.73          2 Left Peak
                                            3 Midfield                             1.41       1.41
                                            5 Right Floor                          2.24       3.65
                                            4 Right Peak                           2.24       5.89
                                            1 Left Floor                           3.61       9.49
                                            2 Left Peak                            2.24      11.73
                      3       13.1          2 Left Peak
                                            3 Midfield                             1.41       1.41
                                            1 Left Floor                           2.24       3.65
                                            4 Right Peak                           3.61       7.26
                                            5 Right Floor                          2.24       9.49
                                            2 Left Peak                            3.61       13.1
                      4      13.26          2 Left Peak
                                            3 Midfield                             1.41       1.41
                                            5 Right Floor                          2.24       3.65
                                            1 Left Floor                              4       7.65
                                            4 Right Peak                           3.61      11.26
                                            2 Left Peak                               2      13.26
                      5      14.04          2 Left Peak
                                            3 Midfield                             1.41       1.41
                                            4 Right Peak                           1.41       2.83
                                            1 Left Floor                           3.61       6.43
                                            5 Right Floor                             4      10.43
                                            2 Left Peak                            3.61      14.04
2 -> 4                1      10.94          2 Left Peak
                                            4 Right Peak                              2          2
                                            5 Right Floor                          2.24       4.24
                                            3 Midfield                             2.24       6.47
                                            1 Left Floor                           2.24       8.71
                                            2 Left Peak                            2.24      10.94
                      2      11.89          2 Left Peak
                                            4 Right Peak                              2          2
                                            3 Midfield                             1.41       3.41
                                            5 Right Floor                          2.24       5.65
                                            1 Left Floor                              4       9.65
                                            2 Left Peak                            2.24      11.89
                      3      11.89          2 Left Peak
                                            4 Right Peak                              2          2
                                            5 Right Floor                          2.24       4.24
                                            1 Left Floor                              4       8.24
                                            3 Midfield                             2.24      10.47
                                            2 Left Peak                            1.41      11.89
                      4      13.26          2 Left Peak
                                            4 Right Peak                              2          2
                                            3 Midfield                             1.41       3.41
                                            1 Left Floor                           2.24       5.65
                                            5 Right Floor                             4       9.65
                                            2 Left Peak                            3.61      13.26
                      5      13.68          2 Left Peak
                                            4 Right Peak                              2          2
                                            1 Left Floor                           3.61       5.61
                                            3 Midfield                             2.24       7.84
                                            5 Right Floor                          2.24      10.08
                                            2 Left Peak                            3.61      13.68
3 -> 4                1       11.3          3 Midfield
                                            4 Right Peak                           1.41       1.41
                                            5 Right Floor                          2.24       3.65
                                            1 Left Floor                              4       7.65
                                            2 Left Peak                            2.24       9.89
                                            3 Midfield                             1.41       11.3
                      2      11.73          3 Midfield
                                            4 Right Peak                           1.41       1.41
                                            5 Right Floor                          2.24       3.65
                                            2 Left Peak                            3.61       7.26
                                            1 Left Floor                           2.24       9.49
                                            3 Midfield                             2.24      11.73
                      3      11.89          3 Midfield
                                            4 Right Peak                           1.41       1.41
                                            2 Left Peak                               2       3.41
                                            1 Left Floor                           2.24       5.65
                                            5 Right Floor                             4       9.65
                                            3 Midfield                             2.24      11.89
                      4       13.1          3 Midfield
                                            4 Right Peak                           1.41       1.41
                                            1 Left Floor                           3.61       5.02
                                            2 Left Peak                            2.24       7.26
                                            5 Right Floor                          3.61      10.86
                                            3 Midfield                             2.24       13.1
                      5      13.26          3 Midfield
                                            4 Right Peak                           1.41       1.41
                                            2 Left Peak                               2       3.41
                                            5 Right Floor                          3.61       7.02
                                            1 Left Floor                              4      11.02
                                            3 Midfield                             2.24      13.26
3 -> 5                1      10.94          3 Midfield
                                            5 Right Floor                          2.24       2.24
                                            4 Right Peak                           2.24       4.47
                                            2 Left Peak                               2       6.47
                                            1 Left Floor                           2.24       8.71
                                            3 Midfield                             2.24      10.94
                      2      11.73          3 Midfield
                                            5 Right Floor                          2.24       2.24
                                            4 Right Peak                           2.24       4.47
                                            1 Left Floor                           3.61       8.08
                                            2 Left Peak                            2.24      10.31
                                            3 Midfield                             1.41      11.73
                      3      11.89          3 Midfield
                                            5 Right Floor                          2.24       2.24
                                            1 Left Floor                              4       6.24
                                            2 Left Peak                            2.24       8.47
                                            4 Right Peak                              2      10.47
                                            3 Midfield                             1.41      11.89
                      4       13.1          3 Midfield
                                            5 Right Floor                          2.24       2.24
                                            2 Left Peak                            3.61       5.84
                                            1 Left Floor                           2.24       8.08
                                            4 Right Peak                           3.61      11.68
                                            3 Midfield                             1.41       13.1
                      5      13.68          3 Midfield
                                            5 Right Floor                          2.24       2.24
                                            2 Left Peak                            3.61       5.84
                                            4 Right Peak                              2       7.84
                                            1 Left Floor                           3.61      11.45
                                            3 Midfield                             2.24      13.68

150 rows selected.

Elapsed: 00:00:00.14
Longest Routes
==============
ROOT_LEG       PATH_RNK   TOT_DIST    TOWN_ID NAME                             LEG_DIST   CUM_DIST
------------ ---------- ---------- ---------- ------------------------------ ---------- ----------
1 -> 2                1       13.1          1 Left Floor
                                            2 Left Peak                            2.24       2.24
                                            5 Right Floor                          3.61       5.84
                                            3 Midfield                             2.24       8.08
                                            4 Right Peak                           1.41       9.49
                                            1 Left Floor                           3.61       13.1
                      2      11.89          1 Left Floor
                                            2 Left Peak                            2.24       2.24
                                            4 Right Peak                              2       4.24
                                            3 Midfield                             1.41       5.65
                                            5 Right Floor                          2.24       7.89
                                            1 Left Floor                              4      11.89
                      3      11.73          1 Left Floor
                                            2 Left Peak                            2.24       2.24
                                            5 Right Floor                          3.61       5.84
                                            4 Right Peak                           2.24       8.08
                                            3 Midfield                             1.41       9.49
                                            1 Left Floor                           2.24      11.73
                      4      11.73          1 Left Floor
                                            2 Left Peak                            2.24       2.24
                                            3 Midfield                             1.41       3.65
                                            5 Right Floor                          2.24       5.89
                                            4 Right Peak                           2.24       8.12
                                            1 Left Floor                           3.61      11.73
                      5      10.94          1 Left Floor
                                            2 Left Peak                            2.24       2.24
                                            4 Right Peak                              2       4.24
                                            5 Right Floor                          2.24       6.47
                                            3 Midfield                             2.24       8.71
                                            1 Left Floor                           2.24      10.94
1 -> 4                1      13.68          1 Left Floor
                                            4 Right Peak                           3.61       3.61
                                            2 Left Peak                               2       5.61
                                            5 Right Floor                          3.61       9.21
                                            3 Midfield                             2.24      11.45
                                            1 Left Floor                           2.24      13.68
                      2      13.26          1 Left Floor
                                            4 Right Peak                           3.61       3.61
                                            2 Left Peak                               2       5.61
                                            3 Midfield                             1.41       7.02
                                            5 Right Floor                          2.24       9.26
                                            1 Left Floor                              4      13.26
                      3       13.1          1 Left Floor
                                            4 Right Peak                           3.61       3.61
                                            5 Right Floor                          2.24       5.84
                                            2 Left Peak                            3.61       9.45
                                            3 Midfield                             1.41      10.86
                                            1 Left Floor                           2.24       13.1
                      4       13.1          1 Left Floor
                                            4 Right Peak                           3.61       3.61
                                            3 Midfield                             1.41       5.02
                                            5 Right Floor                          2.24       7.26
                                            2 Left Peak                            3.61      10.86
                                            1 Left Floor                           2.24       13.1
                      5      11.73          1 Left Floor
                                            4 Right Peak                           3.61       3.61
                                            5 Right Floor                          2.24       5.84
                                            3 Midfield                             2.24       8.08
                                            2 Left Peak                            1.41       9.49
                                            1 Left Floor                           2.24      11.73
1 -> 5                1      14.04          1 Left Floor
                                            5 Right Floor                             4          4
                                            2 Left Peak                            3.61       7.61
                                            3 Midfield                             1.41       9.02
                                            4 Right Peak                           1.41      10.43
                                            1 Left Floor                           3.61      14.04
                      2      13.26          1 Left Floor
                                            5 Right Floor                             4          4
                                            2 Left Peak                            3.61       7.61
                                            4 Right Peak                              2       9.61
                                            3 Midfield                             1.41      11.02
                                            1 Left Floor                           2.24      13.26
                      3      13.26          1 Left Floor
                                            5 Right Floor                             4          4
                                            3 Midfield                             2.24       6.24
                                            2 Left Peak                            1.41       7.65
                                            4 Right Peak                              2       9.65
                                            1 Left Floor                           3.61      13.26
                      4      11.89          1 Left Floor
                                            5 Right Floor                             4          4
                                            4 Right Peak                           2.24       6.24
                                            2 Left Peak                               2       8.24
                                            3 Midfield                             1.41       9.65
                                            1 Left Floor                           2.24      11.89
                      5      11.89          1 Left Floor
                                            5 Right Floor                             4          4
                                            3 Midfield                             2.24       6.24
                                            4 Right Peak                           1.41       7.65
                                            2 Left Peak                               2       9.65
                                            1 Left Floor                           2.24      11.89
2 -> 5                1      14.04          2 Left Peak
                                            5 Right Floor                          3.61       3.61
                                            1 Left Floor                              4       7.61
                                            4 Right Peak                           3.61      11.21
                                            3 Midfield                             1.41      12.63
                                            2 Left Peak                            1.41      14.04
                      2      13.68          2 Left Peak
                                            5 Right Floor                          3.61       3.61
                                            3 Midfield                             2.24       5.84
                                            1 Left Floor                           2.24       8.08
                                            4 Right Peak                           3.61      11.68
                                            2 Left Peak                               2      13.68
                      3      13.26          2 Left Peak
                                            5 Right Floor                          3.61       3.61
                                            1 Left Floor                              4       7.61
                                            3 Midfield                             2.24       9.84
                                            4 Right Peak                           1.41      11.26
                                            2 Left Peak                               2      13.26
                      4       13.1          2 Left Peak
                                            5 Right Floor                          3.61       3.61
                                            4 Right Peak                           2.24       5.84
                                            1 Left Floor                           3.61       9.45
                                            3 Midfield                             2.24      11.68
                                            2 Left Peak                            1.41       13.1
                      5      11.73          2 Left Peak
                                            5 Right Floor                          3.61       3.61
                                            4 Right Peak                           2.24       5.84
                                            3 Midfield                             1.41       7.26
                                            1 Left Floor                           2.24       9.49
                                            2 Left Peak                            2.24      11.73
3 -> 5                1      13.68          3 Midfield
                                            5 Right Floor                          2.24       2.24
                                            2 Left Peak                            3.61       5.84
                                            4 Right Peak                              2       7.84
                                            1 Left Floor                           3.61      11.45
                                            3 Midfield                             2.24      13.68
                      2      13.26          3 Midfield
                                            5 Right Floor                          2.24       2.24
                                            1 Left Floor                              4       6.24
                                            4 Right Peak                           3.61       9.84
                                            2 Left Peak                               2      11.84
                                            3 Midfield                             1.41      13.26
                      3       13.1          3 Midfield
                                            5 Right Floor                          2.24       2.24
                                            2 Left Peak                            3.61       5.84
                                            1 Left Floor                           2.24       8.08
                                            4 Right Peak                           3.61      11.68
                                            3 Midfield                             1.41       13.1
                      4      11.89          3 Midfield
                                            5 Right Floor                          2.24       2.24
                                            1 Left Floor                              4       6.24
                                            2 Left Peak                            2.24       8.47
                                            4 Right Peak                              2      10.47
                                            3 Midfield                             1.41      11.89
                      5      11.73          3 Midfield
                                            5 Right Floor                          2.24       2.24
                                            4 Right Peak                           2.24       4.47
                                            1 Left Floor                           3.61       8.08
                                            2 Left Peak                            2.24      10.31
                                            3 Midfield                             1.41      11.73

150 rows selected.

Elapsed: 00:00:00.16

Summary of Results
Here we list the best solutions found for each root leg. * denotes optimum.

Shortest Routes
===============
ROOT_LEG       PATH_RNK   TOT_DIST
------------ ---------- ----------
1 -> 2                1      10.94*
2 -> 3                1       11.3
2 -> 4                1      10.94*
3 -> 4                1       11.3
3 -> 5                1      10.94*

Longest Routes
==============
ROOT_LEG       PATH_RNK   TOT_DIST
------------ ---------- ----------
1 -> 2                1       13.1
1 -> 4                1      13.68
1 -> 5                1      14.04*
2 -> 5                1      14.04*
3 -> 5                1      13.68

Test Problem 2: USCA312

I used keep values of 2 and 2 and solved the problems in around 85 seconds.

Shortest Routes
===============
ROOT_LEG       PATH_RNK   TOT_DIST    TOWN_ID NAME                             LEG_DIST   CUM_DIST
------------ ---------- ---------- ---------- ------------------------------ ---------- ----------
184 -> 208            1   55744.86        184 Norfolk, VA
                                          208 Portsmouth, VA                       1.19       1.19
                                          294 Washington, DC                     151.18     152.37
                                           18 Baltimore, MD                       40.06     192.43
                                          141 Lancaster, PA                       55.83     248.26
                                          129 Johnstown, PA                       16.64      264.9
                                          217 Reading, PA                          27.2      292.1
                                          302 Wilmington, DE                      48.48     340.58
                                          198 Philadelphia, PA                    30.05     370.63
                                          283 Trenton, NJ                         34.35     404.99
                                           83 Elizabeth, NJ                       48.02     453.01
                                          177 Newark, NJ                           5.61     458.62
                                          128 Jersey City, NJ                      6.57     465.19
                                          181 New York, NY                         5.04     470.23
                                          194 Paterson, NJ                        18.08     488.32
                                          299 White Plains, NY                    29.39     517.71
                                          266 Stamford, CT                        15.36     533.07
                                           39 Bridgeport, CT                      24.55     557.61
                                          179 New Haven, CT                       21.46     579.08
                                          163 Meriden, CT                         17.96     597.04
                                          178 New Britain,CT                       8.71     605.75
                                          117 Hartford, CT                         9.62     615.37
                                          263 Springfield, MA                     24.25     639.62
                                          202 Pittsfield, MA                      51.31     690.93
                                          285 Troy, NY                            36.34     727.27
                                            3 Albany, NY                           6.88     734.16
                                          251 Schenectady, NY                     16.88     751.04
                                          289 Utica, NY                           91.52     842.56
                                          272 Syracuse, NY                        63.31     905.86
                                           29 Binghamtom, NY                      67.49     973.35
                                          301 Wilkes-Barre, PA                    58.97    1032.33
                                            6 Allentown, PA                       51.68       1084
                                          116 Harrisburg, PA                      99.07    1183.07
                                           13 Atlantic City, NJ                  181.31    1364.38
                                           50 Central Islip, NY                  129.74    1494.12
                                          210 Providence, RI                     142.75    1636.87
                                           91 Fall River, MA                      19.72    1656.59
                                           40 Brockton, MA                        28.03    1684.61
                                           34 Boston, MA                          19.21    1703.83
                                           46 Cambridge, MA                        3.36    1707.19
                                          155 Lowell, MA                          23.03    1730.22
                                          145 Lawrence, MA                        11.73    1741.95
                                          159 Manchester, NH                      28.36     1770.3
                                           67 Concord, NH                         15.76    1786.06
                                          307 Worcester, MA                       67.84     1853.9
                                           38 Brattleboro, VT                     66.17    1920.07
                                          171 Montpelier, VT                      97.37    2017.43
                                           43 Burlington, VT                      46.45    2063.89
                                          172 Montreal, QC                        97.19    2161.08
                                          284 Trois-Rivieres, QC                  98.03     2259.1
                                          254 Sherbrooke, QC                      93.08    2352.18
                                          205 Portland, ME                       157.79    2509.97
                                          207 Portsmouth, NH                      53.74    2563.71
                                           15 Augusta, ME                        109.27    2672.99
                                           19 Bangor, ME                          77.07    2750.06
                                           98 Fredericton, NB                    171.89    2921.95
                                          229 Saint John, NB                      58.53    2980.48
                                          169 Moncton, NB                         99.94    3080.42
                                          113 Halifax, NS                        117.55    3197.97
                                           55 Charlottetown, PE                  100.98    3298.95
                                          271 Syndey, NS                         212.55     3511.5
                                          230 Saint John's, NF                   514.07    4025.57
                                          213 Quebec City, QC                   1290.47    5316.03
                                          191 Ottawa, ON                         400.01    5716.04
                                          137 Kingston, ON                        85.39    5801.42
                                           24 Belleville, ON                      49.28    5850.71
                                          197 Peterborough, ON                    72.87    5923.57
                                          282 Toronto, ON                         82.62    6006.19
                                           42 Burlington, ONT                     33.92    6040.11
                                          115 Hamilton, ON                        19.51    6059.62
                                           37 Brantford, ON                       28.55    6088.16
                                          111 Guelph, ON                           29.4    6117.56
                                          138 Kitchener, ON                       10.29    6127.86
                                          152 London, ON                          67.63    6195.49
                                           86 Erie, PA                            97.44    6292.93
                                          310 Youngstown, OH                      81.12    6374.05
                                          267 Steubenville, OH                    50.45     6424.5
                                          297 Wheeling, WV                        21.97    6446.47
                                          201 Pittsburgh, PA                      56.46    6502.93
                                           47 Canton, OH                          98.69    6601.61
                                            2 Akron, OH                            21.8    6623.41
                                           61 Cleveland, OH                       31.35    6654.76
                                          304 Windsor, ON                        102.38    6757.14
                                           76 Detroit, MI                          7.21    6764.35
                                            9 Ann Arbor, MI                       47.21    6811.56
                                          125 Jackson, MI                         46.67    6858.23
                                          142 Lansing, MI                         35.28    6893.51
                                           21 Battle Creek, MI                    51.65    6945.16
                                          132 Kalamazoo, MI                       28.23    6973.39
                                          259 South Bend, IN                      62.16    7035.55
                                          104 Gary, IN                            76.01    7111.56
                                           58 Chicago, IL                         27.47    7139.03
                                          135 Kenosha, WI                         52.13    7191.16
                                          214 Racine, WI                          10.12    7201.28
                                          165 Milwaukee, WI                       23.24    7224.52
                                          224 Rockford, IL                        97.71    7322.22
                                          158 Madison, WI                         59.34    7381.56
                                           78 Dubuque, IA                         95.84     7477.4
                                           49 Cedar Rapids, IA                    75.74    7553.14
                                          124 Iowa City, IA                       25.25    7578.39
                                          295 Waterloo, IA                        80.35    7658.74
                                          222 Rochester, MN                         106    7764.75
                                          233 Saint Paul, MN                      76.94    7841.69
                                          166 Minneapolis, MN                     12.03    7853.72
                                          228 Saint Cloud, MN                     73.94    7927.66
                                           79 Duluth, MN                         165.27    8092.93
                                          270 Superior, WI                         4.32    8097.25
                                           81 Eau Claire, WI                     138.42    8235.67
                                          108 Green Bay, WI                      241.21    8476.87
                                          253 Sheboygan, WI                       57.13       8534
                                          106 Grand Rapids, MI                   151.51     8685.5
                                          226 Saginaw, MI                        122.77    8808.27
                                           22 Bay City, MI                        12.83     8821.1
                                           94 Flint, MI                           42.55    8863.65
                                          280 Toledo, OH                          93.64    8957.28
                                          149 Lima, OH                            74.14    9031.42
                                          265 Springfield, OH                     60.13    9091.56
                                           71 Dayton, OH                          28.81    9120.37
                                          114 Hamilton, OH                        35.63       9156
                                           60 Cincinnati, OH                      17.93    9173.93
                                          147 Lexington, KY                       81.08    9255.01
                                          154 Louisville, KY                      90.44    9345.45
                                           35 Bowling Green, KY                    99.3    9444.76
                                          175 Nashville, TN                       61.65     9506.4
                                          122 Huntsville, AL                     100.13    9606.53
                                          100 Gadsden, AL                         63.64    9670.18
                                           30 Birmingham, AL                       64.7    9734.88
                                          170 Montgomery, AL                      86.96    9821.85
                                           65 Columbus, GA                         90.9    9912.75
                                           12 Atlanta, GA                         98.17   10010.92
                                          157 Macon, GA                           81.64   10092.56
                                           14 Augusta, GA                        122.52   10215.08
                                          110 Greenville, SC                      99.77   10314.85
                                          260 Spartanburg, NC                     32.62   10347.46
                                           54 Charlotte, NC                       77.64   10425.11
                                          306 Winston-Salem, NC                   73.13   10498.24
                                          109 Greensboro, NC                       31.3   10529.54
                                          215 Raleigh, NC                         82.35   10611.89
                                           80 Durham, NC                          23.61    10635.5
                                          221 Roanoke, VA                        113.91   10749.41
                                           53 Charleston, WV                     138.61   10888.02
                                           11 Ashland, KY                         70.03   10958.04
                                          312 Zanesville, OH                     109.84   11067.89
                                           66 Columbus, OH                        68.11   11135.99
                                          174 Muncie, IN                         165.75   11301.74
                                          123 Indianapolis, IN                    60.87   11362.61
                                          276 Terre Haute, IN                     89.24   11451.85
                                          288 Urbana, IL                           70.6   11522.45
                                           51 Champaign, IL                        2.52   11524.98
                                           73 Decatur, IL                         52.73   11577.71
                                           32 Bloomington, IL                     44.57   11622.28
                                          196 Peoria, IL                           43.6   11665.88
                                          262 Springfield, IL                     61.75   11727.63
                                          232 Saint Louis, MO                     89.73   11817.36
                                           63 Columbia, MO                       149.28   11966.64
                                          264 Springfield, MO                    137.23   12103.88
                                          130 Joplin, MO                          84.44   12188.32
                                          287 Tulsa, OK                          120.76   12309.07
                                          188 Oklahoma City, OK                  115.46   12424.54
                                           85 Enid, OK                            68.83   12493.37
                                          300 Wichita, KS                         97.07   12590.44
                                          236 Salina, KS                          81.55   12671.99
                                          281 Topeka, KS                         134.35   12806.34
                                          133 Kansas City, KS                     72.73   12879.07
                                          134 Kansas City, MO                      3.52    12882.6
                                          231 Saint Joseph, MO                    49.79   12932.39
                                          150 Lincoln, NE                        144.56   13076.95
                                          189 Omaha, NE                           59.52   13136.47
                                          257 Sioux City, IA                      91.54   13228.01
                                          258 Sioux Falls, SD                     75.45   13303.46
                                           92 Fargo, ND                          229.97   13533.43
                                          305 Winnipeg, MB                       211.94   13745.38
                                           36 Brandon, MB                        187.08   13932.46
                                          167 Minot, ND                          148.55      14081
                                           31 Bismarck, ND                       104.59   14185.59
                                          200 Pierre, SD                         171.22   14356.81
                                          216 Rapid City, SD                     199.98   14556.79
                                           57 Cheyenne, WY                       230.96   14787.75
                                           74 Denver, CO                          97.46   14885.21
                                           62 Colorado Springs, CO                63.56   14948.77
                                          212 Pueblo, CO                          42.63    14991.4
                                          246 Santa Fe, NM                       199.75   15191.16
                                            4 Albuquerque, NM                     64.52   15255.68
                                          102 Gallup, NM                         147.72    15403.4
                                           93 Flagstaff, AZ                      202.26   15605.66
                                          199 Phoenix, AZ                        124.38   15730.04
                                          286 Tucson, AZ                         116.06    15846.1
                                          311 Yuma, AZ                           257.86   16103.95
                                          240 San Diego, CA                      175.01   16278.97
                                          239 San Bernardino, CA                  96.69   16375.66
                                          193 Pasadena, CA                        59.12   16434.78
                                          153 Los Angeles, CA                      9.51   16444.29
                                          244 Santa Barbara, CA                  103.68   16547.97
                                           17 Bakersfield, CA                     80.84   16628.81
                                           99 Fresno, CA                         108.31   16737.12
                                          242 San Jose, CA                       152.25   16889.37
                                          245 Santa Cruz, CA                      26.93    16916.3
                                          186 Oakland, CA                         59.72   16976.02
                                          241 San Francisco, CA                   10.47   16986.49
                                           26 Berkeley, CA                        12.14   16998.63
                                          268 Stockton, CA                        68.11   17066.74
                                          225 Sacramento, CA                      45.35   17112.09
                                           48 Carson City, NV                    125.92      17238
                                          219 Reno, NV                            25.48   17263.49
                                           88 Eureka, CA                         313.15   17576.64
                                           87 Eugene, OR                         236.57    17813.2
                                          235 Salem, OR                           61.63   17874.84
                                          206 Portland, OR                        47.17   17922.01
                                          273 Tacoma, WA                         120.57   18042.58
                                          252 Seattle, WA                         25.62    18068.2
                                           25 Bellingham, WA                      80.42   18148.62
                                          290 Vancouver, BC                       56.66   18205.28
                                          291 Victoria, BC                        41.45   18246.73
                                          308 Yakima, WA                         246.37    18493.1
                                          293 Walla Walla, WA                    153.98   18647.07
                                          261 Spokane, WA                        127.07   18774.15
                                           33 Boise, ID                          291.99   19066.14
                                          203 Pocatello, ID                      264.67   19330.81
                                          187 Ogden, UT                          118.47   19449.28
                                          237 Salt Lake City, UT                  32.44   19481.72
                                          211 Provo, UT                           39.79   19521.51
                                          105 Grand Junction, CO                 229.45   19750.96
                                          255 Sheridan, WY                       411.17   20162.14
                                           27 Billings, MT                       126.61   20288.75
                                          107 Great Falls, MT                    226.94   20515.69
                                          118 Helena, MT                           80.7   20596.39
                                           44 Butte, MT                           53.31    20649.7
                                          146 Lethbridge, AB                     251.24   20900.94
                                           45 Calgary, AB                        132.75   21033.69
                                           82 Edmonton, AB                       173.35   21207.04
                                          161 Medicine Hat, AB                   312.59   21519.63
                                          248 Saskatoon, SK                      315.13   21834.76
                                          173 Moose Jaw, SK                      149.68   21984.44
                                          218 Regina, SK                          62.04   22046.48
                                           77 Dodge City, KS                     933.12    22979.6
                                            7 Amarillo, TX                       215.16   23194.75
                                          156 Lubbock, TX                        113.61   23308.37
                                            1 Abilene, TX                        166.25   23474.62
                                           97 Ft Worth, TX                       167.57   23642.19
                                           69 Dallas, TX                          36.19   23678.39
                                          292 Waco, TX                            88.57   23766.96
                                           16 Austin, TX                          97.72   23864.68
                                          238 San Antonio, TX                     77.99   23942.67
                                          143 Laredo, TX                         149.89   24092.56
                                           68 Corpus Christi, TX                 147.28   24239.84
                                          121 Houston, TX                        195.26    24435.1
                                          103 Galveston, TX                       50.45   24485.55
                                          204 Port Arthur, TX                     72.86   24558.41
                                           23 Beaumont, TX                        17.62   24576.03
                                          256 Shreveport, LA                     170.28   24746.32
                                          160 Marshall, TX                        42.67   24788.99
                                          277 Texarkana, TX                       64.71    24853.7
                                           95 Ft Smith, AR                       137.64   24991.34
                                          151 Little Rock, AR                    152.27   25143.61
                                          162 Memphis, TN                         157.3   25300.91
                                          192 Paducah, KY                        166.97   25467.88
                                           89 Evansville, IN                      94.86   25562.74
                                          140 Lafayette, IN                      175.16    25737.9
                                           96 Ft Wayne, IN                       130.36   25868.26
                                          139 Knoxville, TN                      366.84    26235.1
                                           10 Asheville, NC                       97.65   26332.75
                                           64 Columbia, SC                       152.46   26485.21
                                           52 Charleston, SC                      113.9   26599.11
                                          250 Savannah, GA                         93.9   26693.01
                                          127 Jacksonville, FL                   126.96   26819.97
                                          101 Gainesville, FL                     65.95   26885.92
                                           72 Daytona Beach, FL                   94.98    26980.9
                                          190 Orlando, FL                         52.58   27033.48
                                          275 Tampa, FL                           85.01   27118.49
                                          234 Saint Petersburg, FL                19.54   27138.03
                                          247 Sarasota, FL                        31.73   27169.75
                                          296 West Palm Beach, FL                176.46   27346.21
                                          164 Miami, FL                           65.75   27411.96
                                          136 Key West, FL                       138.36   27550.32
                                          274 Tallahassee, FL                    441.61   27991.93
                                          195 Pensacola, FL                      202.87    28194.8
                                          168 Mobile, AL                          60.12   28254.92
                                           28 Biloxi, MS                          61.74   28316.66
                                          112 Gulfport, MS                        14.47   28331.13
                                          180 New Orleans, LA                     73.62   28404.74
                                           20 Baton Rouge, LA                     82.09   28486.83
                                          176 Natchez, MS                         78.58   28565.41
                                          126 Jackson, MS                         98.43   28663.84
                                           56 Chattanooga, TN                    386.64   29050.48
                                          303 Wilmington, NC                     512.01   29562.49
                                          220 Richmond, VA                       232.37   29794.87
                                           41 Buffalo, NY                        381.27   30176.14
                                          182 Niagara Falls, ON                   20.54   30196.68
                                          227 Saint Catherines, ON                 8.92   30205.61
                                          223 Rochester, NY                      107.53   30313.14
                                          185 North Bay, ON                      260.14   30573.28
                                          269 Sudbury, ON                            93   30666.28
                                          279 Timmins, ON                        140.17   30806.45
                                          249 Sault Ste Marie, ON                260.02   31066.47
                                          278 Thunder Bay, ON                    357.29   31423.76
                                           75 Des Moines, IA                     553.68   31977.44
                                           84 El Paso, TX                       1119.89   33097.34
                                          144 Las Vegas, NV                      671.08   33768.41
                                          209 Prince Rupert, BC                 1638.53   35406.94
                                          131 Juneau, AK                         390.43   35797.37
                                          298 Whitehorse, YK                     172.32   35969.69
                                           70 Dawson, YT                         362.92   36332.61
                                           90 Fairbanks, AK                         596   36928.62
                                            8 Anchorage, AK                      292.11   37220.72
                                          183 Nome, AK                          1095.15   38315.87
                                          148 Lihue, HI                          2967.4   41283.27
                                          120 Honolulu, HI                        114.5   41397.77
                                          119 Hilo, HI                              176   41573.77
                                          309 Yellowknife, NT                   4111.93    45685.7
                                           59 Churchill, MB                     1431.71   47117.42
                                            5 Alert, NT                         2742.38    49859.8
                                          243 San Juan, PR                      4433.43   54293.23
                                          184 Norfolk, VA                       1451.64   55744.86
                      2   55746.24        184 Norfolk, VA
                                          208 Portsmouth, VA                       1.19       1.19
                                          294 Washington, DC                     151.18     152.37
                                           18 Baltimore, MD                       40.06     192.43
                                          141 Lancaster, PA                       55.83     248.26
                                          129 Johnstown, PA                       16.64      264.9
                                          217 Reading, PA                          27.2      292.1
                                          302 Wilmington, DE                      48.48     340.58
                                          198 Philadelphia, PA                    30.05     370.63
                                          283 Trenton, NJ                         34.35     404.99
                                           83 Elizabeth, NJ                       48.02     453.01
                                          177 Newark, NJ                           5.61     458.62
                                          128 Jersey City, NJ                      6.57     465.19
                                          181 New York, NY                         5.04     470.23
                                          194 Paterson, NJ                        18.08     488.32
                                          299 White Plains, NY                    29.39     517.71
                                          266 Stamford, CT                        15.36     533.07
                                           39 Bridgeport, CT                      24.55     557.61
                                          179 New Haven, CT                       21.46     579.08
                                          163 Meriden, CT                         17.96     597.04
                                          178 New Britain,CT                       8.71     605.75
                                          117 Hartford, CT                         9.62     615.37
                                          263 Springfield, MA                     24.25     639.62
                                          202 Pittsfield, MA                      51.31     690.93
                                          285 Troy, NY                            36.34     727.27
                                            3 Albany, NY                           6.88     734.16
                                          251 Schenectady, NY                     16.88     751.04
                                          289 Utica, NY                           91.52     842.56
                                          272 Syracuse, NY                        63.31     905.86
                                           29 Binghamtom, NY                      67.49     973.35
                                          301 Wilkes-Barre, PA                    58.97    1032.33
                                            6 Allentown, PA                       51.68       1084
                                          116 Harrisburg, PA                      99.07    1183.07
                                           13 Atlantic City, NJ                  181.31    1364.38
                                           50 Central Islip, NY                  129.74    1494.12
                                          210 Providence, RI                     142.75    1636.87
                                           91 Fall River, MA                      19.72    1656.59
                                           40 Brockton, MA                        28.03    1684.61
                                           34 Boston, MA                          19.21    1703.83
                                           46 Cambridge, MA                        3.36    1707.19
                                          155 Lowell, MA                          23.03    1730.22
                                          145 Lawrence, MA                        11.73    1741.95
                                          159 Manchester, NH                      28.36     1770.3
                                           67 Concord, NH                         15.76    1786.06
                                          307 Worcester, MA                       67.84     1853.9
                                           38 Brattleboro, VT                     66.17    1920.07
                                          171 Montpelier, VT                      97.37    2017.43
                                           43 Burlington, VT                      46.45    2063.89
                                          172 Montreal, QC                        97.19    2161.08
                                          284 Trois-Rivieres, QC                  98.03     2259.1
                                          254 Sherbrooke, QC                      93.08    2352.18
                                          205 Portland, ME                       157.79    2509.97
                                          207 Portsmouth, NH                      53.74    2563.71
                                           15 Augusta, ME                        109.27    2672.99
                                           19 Bangor, ME                          77.07    2750.06
                                           98 Fredericton, NB                    171.89    2921.95
                                          229 Saint John, NB                      58.53    2980.48
                                          169 Moncton, NB                         99.94    3080.42
                                          113 Halifax, NS                        117.55    3197.97
                                           55 Charlottetown, PE                  100.98    3298.95
                                          271 Syndey, NS                         212.55     3511.5
                                          230 Saint John's, NF                   514.07    4025.57
                                          213 Quebec City, QC                   1290.47    5316.03
                                          191 Ottawa, ON                         400.01    5716.04
                                          137 Kingston, ON                        85.39    5801.42
                                           24 Belleville, ON                      49.28    5850.71
                                          197 Peterborough, ON                    72.87    5923.57
                                          282 Toronto, ON                         82.62    6006.19
                                           42 Burlington, ONT                     33.92    6040.11
                                          115 Hamilton, ON                        19.51    6059.62
                                           37 Brantford, ON                       28.55    6088.16
                                          111 Guelph, ON                           29.4    6117.56
                                          138 Kitchener, ON                       10.29    6127.86
                                          152 London, ON                          67.63    6195.49
                                           86 Erie, PA                            97.44    6292.93
                                          310 Youngstown, OH                      81.12    6374.05
                                          267 Steubenville, OH                    50.45     6424.5
                                          297 Wheeling, WV                        21.97    6446.47
                                          201 Pittsburgh, PA                      56.46    6502.93
                                           47 Canton, OH                          98.69    6601.61
                                            2 Akron, OH                            21.8    6623.41
                                           61 Cleveland, OH                       31.35    6654.76
                                          304 Windsor, ON                        102.38    6757.14
                                           76 Detroit, MI                          7.21    6764.35
                                            9 Ann Arbor, MI                       47.21    6811.56
                                          125 Jackson, MI                         46.67    6858.23
                                          142 Lansing, MI                         35.28    6893.51
                                           21 Battle Creek, MI                    51.65    6945.16
                                          132 Kalamazoo, MI                       28.23    6973.39
                                          259 South Bend, IN                      62.16    7035.55
                                          104 Gary, IN                            76.01    7111.56
                                           58 Chicago, IL                         27.47    7139.03
                                          135 Kenosha, WI                         52.13    7191.16
                                          214 Racine, WI                          10.12    7201.28
                                          165 Milwaukee, WI                       23.24    7224.52
                                          224 Rockford, IL                        97.71    7322.22
                                          158 Madison, WI                         59.34    7381.56
                                           78 Dubuque, IA                         95.84     7477.4
                                           49 Cedar Rapids, IA                    75.74    7553.14
                                          124 Iowa City, IA                       25.25    7578.39
                                          295 Waterloo, IA                        80.35    7658.74
                                          222 Rochester, MN                         106    7764.75
                                          233 Saint Paul, MN                      76.94    7841.69
                                          166 Minneapolis, MN                     12.03    7853.72
                                          228 Saint Cloud, MN                     73.94    7927.66
                                           79 Duluth, MN                         165.27    8092.93
                                          270 Superior, WI                         4.32    8097.25
                                           81 Eau Claire, WI                     138.42    8235.67
                                          108 Green Bay, WI                      241.21    8476.87
                                          253 Sheboygan, WI                       57.13       8534
                                          106 Grand Rapids, MI                   151.51     8685.5
                                          226 Saginaw, MI                        122.77    8808.27
                                           22 Bay City, MI                        12.83     8821.1
                                           94 Flint, MI                           42.55    8863.65
                                          280 Toledo, OH                          93.64    8957.28
                                          149 Lima, OH                            74.14    9031.42
                                          265 Springfield, OH                     60.13    9091.56
                                           71 Dayton, OH                          28.81    9120.37
                                          114 Hamilton, OH                        35.63       9156
                                           60 Cincinnati, OH                      17.93    9173.93
                                          147 Lexington, KY                       81.08    9255.01
                                          154 Louisville, KY                      90.44    9345.45
                                           35 Bowling Green, KY                    99.3    9444.76
                                          175 Nashville, TN                       61.65     9506.4
                                          122 Huntsville, AL                     100.13    9606.53
                                          100 Gadsden, AL                         63.64    9670.18
                                           30 Birmingham, AL                       64.7    9734.88
                                          170 Montgomery, AL                      86.96    9821.85
                                           65 Columbus, GA                         90.9    9912.75
                                           12 Atlanta, GA                         98.17   10010.92
                                          157 Macon, GA                           81.64   10092.56
                                           14 Augusta, GA                        122.52   10215.08
                                          110 Greenville, SC                      99.77   10314.85
                                          260 Spartanburg, NC                     32.62   10347.46
                                           54 Charlotte, NC                       77.64   10425.11
                                          306 Winston-Salem, NC                   73.13   10498.24
                                          109 Greensboro, NC                       31.3   10529.54
                                          215 Raleigh, NC                         82.35   10611.89
                                           80 Durham, NC                          23.61    10635.5
                                          221 Roanoke, VA                        113.91   10749.41
                                           53 Charleston, WV                     138.61   10888.02
                                           11 Ashland, KY                         70.03   10958.04
                                          312 Zanesville, OH                     109.84   11067.89
                                           66 Columbus, OH                        68.11   11135.99
                                          174 Muncie, IN                         165.75   11301.74
                                          123 Indianapolis, IN                    60.87   11362.61
                                          276 Terre Haute, IN                     89.24   11451.85
                                          288 Urbana, IL                           70.6   11522.45
                                           51 Champaign, IL                        2.52   11524.98
                                           73 Decatur, IL                         52.73   11577.71
                                           32 Bloomington, IL                     44.57   11622.28
                                          196 Peoria, IL                           43.6   11665.88
                                          262 Springfield, IL                     61.75   11727.63
                                          232 Saint Louis, MO                     89.73   11817.36
                                           63 Columbia, MO                       149.28   11966.64
                                          264 Springfield, MO                    137.23   12103.88
                                          130 Joplin, MO                          84.44   12188.32
                                          287 Tulsa, OK                          120.76   12309.07
                                          188 Oklahoma City, OK                  115.46   12424.54
                                           85 Enid, OK                            68.83   12493.37
                                          300 Wichita, KS                         97.07   12590.44
                                          236 Salina, KS                          81.55   12671.99
                                          281 Topeka, KS                         134.35   12806.34
                                          133 Kansas City, KS                     72.73   12879.07
                                          134 Kansas City, MO                      3.52    12882.6
                                          231 Saint Joseph, MO                    49.79   12932.39
                                          150 Lincoln, NE                        144.56   13076.95
                                          189 Omaha, NE                           59.52   13136.47
                                          257 Sioux City, IA                      91.54   13228.01
                                          258 Sioux Falls, SD                     75.45   13303.46
                                           92 Fargo, ND                          229.97   13533.43
                                          305 Winnipeg, MB                       211.94   13745.38
                                           36 Brandon, MB                        187.08   13932.46
                                          167 Minot, ND                          148.55      14081
                                           31 Bismarck, ND                       104.59   14185.59
                                          200 Pierre, SD                         171.22   14356.81
                                          216 Rapid City, SD                     199.98   14556.79
                                           57 Cheyenne, WY                       230.96   14787.75
                                           74 Denver, CO                          97.46   14885.21
                                           62 Colorado Springs, CO                63.56   14948.77
                                          212 Pueblo, CO                          42.63    14991.4
                                          246 Santa Fe, NM                       199.75   15191.16
                                            4 Albuquerque, NM                     64.52   15255.68
                                          102 Gallup, NM                         147.72    15403.4
                                           93 Flagstaff, AZ                      202.26   15605.66
                                          199 Phoenix, AZ                        124.38   15730.04
                                          286 Tucson, AZ                         116.06    15846.1
                                          311 Yuma, AZ                           257.86   16103.95
                                          240 San Diego, CA                      175.01   16278.97
                                          239 San Bernardino, CA                  96.69   16375.66
                                          193 Pasadena, CA                        59.12   16434.78
                                          153 Los Angeles, CA                      9.51   16444.29
                                          244 Santa Barbara, CA                  103.68   16547.97
                                           17 Bakersfield, CA                     80.84   16628.81
                                           99 Fresno, CA                         108.31   16737.12
                                          242 San Jose, CA                       152.25   16889.37
                                          245 Santa Cruz, CA                      26.93    16916.3
                                          186 Oakland, CA                         59.72   16976.02
                                          241 San Francisco, CA                   10.47   16986.49
                                           26 Berkeley, CA                        12.14   16998.63
                                          268 Stockton, CA                        68.11   17066.74
                                          225 Sacramento, CA                      45.35   17112.09
                                           48 Carson City, NV                    125.92      17238
                                          219 Reno, NV                            25.48   17263.49
                                           88 Eureka, CA                         313.15   17576.64
                                           87 Eugene, OR                         236.57    17813.2
                                          235 Salem, OR                           61.63   17874.84
                                          206 Portland, OR                        47.17   17922.01
                                          273 Tacoma, WA                         120.57   18042.58
                                          252 Seattle, WA                         25.62    18068.2
                                           25 Bellingham, WA                      80.42   18148.62
                                          290 Vancouver, BC                       56.66   18205.28
                                          291 Victoria, BC                        41.45   18246.73
                                          308 Yakima, WA                         246.37    18493.1
                                          293 Walla Walla, WA                    153.98   18647.07
                                          261 Spokane, WA                        127.07   18774.15
                                           33 Boise, ID                          291.99   19066.14
                                          203 Pocatello, ID                      264.67   19330.81
                                          187 Ogden, UT                          118.47   19449.28
                                          237 Salt Lake City, UT                  32.44   19481.72
                                          211 Provo, UT                           39.79   19521.51
                                          105 Grand Junction, CO                 229.45   19750.96
                                          255 Sheridan, WY                       411.17   20162.14
                                           27 Billings, MT                       126.61   20288.75
                                          107 Great Falls, MT                    226.94   20515.69
                                          118 Helena, MT                           80.7   20596.39
                                           44 Butte, MT                           53.31    20649.7
                                          146 Lethbridge, AB                     251.24   20900.94
                                           45 Calgary, AB                        132.75   21033.69
                                           82 Edmonton, AB                       173.35   21207.04
                                          161 Medicine Hat, AB                   312.59   21519.63
                                          248 Saskatoon, SK                      315.13   21834.76
                                          173 Moose Jaw, SK                      149.68   21984.44
                                          218 Regina, SK                          62.04   22046.48
                                           77 Dodge City, KS                     933.12    22979.6
                                            7 Amarillo, TX                       215.16   23194.75
                                          156 Lubbock, TX                        113.61   23308.37
                                            1 Abilene, TX                        166.25   23474.62
                                           97 Ft Worth, TX                       167.57   23642.19
                                           69 Dallas, TX                          36.19   23678.39
                                          292 Waco, TX                            88.57   23766.96
                                           16 Austin, TX                          97.72   23864.68
                                          238 San Antonio, TX                     77.99   23942.67
                                          143 Laredo, TX                         149.89   24092.56
                                           68 Corpus Christi, TX                 147.28   24239.84
                                          121 Houston, TX                        195.26    24435.1
                                          103 Galveston, TX                       50.45   24485.55
                                          204 Port Arthur, TX                     72.86   24558.41
                                           23 Beaumont, TX                        17.62   24576.03
                                          160 Marshall, TX                       170.89   24746.92
                                          256 Shreveport, LA                      42.67   24789.59
                                          277 Texarkana, TX                       65.49   24855.08
                                           95 Ft Smith, AR                       137.64   24992.72
                                          151 Little Rock, AR                    152.27      25145
                                          162 Memphis, TN                         157.3   25302.29
                                          192 Paducah, KY                        166.97   25469.26
                                           89 Evansville, IN                      94.86   25564.12
                                          140 Lafayette, IN                      175.16   25739.28
                                           96 Ft Wayne, IN                       130.36   25869.64
                                          139 Knoxville, TN                      366.84   26236.49
                                           10 Asheville, NC                       97.65   26334.13
                                           64 Columbia, SC                       152.46    26486.6
                                           52 Charleston, SC                      113.9   26600.49
                                          250 Savannah, GA                         93.9   26694.39
                                          127 Jacksonville, FL                   126.96   26821.35
                                          101 Gainesville, FL                     65.95    26887.3
                                           72 Daytona Beach, FL                   94.98   26982.28
                                          190 Orlando, FL                         52.58   27034.86
                                          275 Tampa, FL                           85.01   27119.87
                                          234 Saint Petersburg, FL                19.54   27139.41
                                          247 Sarasota, FL                        31.73   27171.14
                                          296 West Palm Beach, FL                176.46    27347.6
                                          164 Miami, FL                           65.75   27413.34
                                          136 Key West, FL                       138.36    27551.7
                                          274 Tallahassee, FL                    441.61   27993.31
                                          195 Pensacola, FL                      202.87   28196.18
                                          168 Mobile, AL                          60.12    28256.3
                                           28 Biloxi, MS                          61.74   28318.04
                                          112 Gulfport, MS                        14.47   28332.51
                                          180 New Orleans, LA                     73.62   28406.13
                                           20 Baton Rouge, LA                     82.09   28488.22
                                          176 Natchez, MS                         78.58    28566.8
                                          126 Jackson, MS                         98.43   28665.22
                                           56 Chattanooga, TN                    386.64   29051.86
                                          303 Wilmington, NC                     512.01   29563.88
                                          220 Richmond, VA                       232.37   29796.25
                                           41 Buffalo, NY                        381.27   30177.52
                                          182 Niagara Falls, ON                   20.54   30198.06
                                          227 Saint Catherines, ON                 8.92   30206.99
                                          223 Rochester, NY                      107.53   30314.52
                                          185 North Bay, ON                      260.14   30574.66
                                          269 Sudbury, ON                            93   30667.66
                                          279 Timmins, ON                        140.17   30807.83
                                          249 Sault Ste Marie, ON                260.02   31067.85
                                          278 Thunder Bay, ON                    357.29   31425.14
                                           75 Des Moines, IA                     553.68   31978.82
                                           84 El Paso, TX                       1119.89   33098.72
                                          144 Las Vegas, NV                      671.08    33769.8
                                          209 Prince Rupert, BC                 1638.53   35408.32
                                          131 Juneau, AK                         390.43   35798.75
                                          298 Whitehorse, YK                     172.32   35971.07
                                           70 Dawson, YT                         362.92   36333.99
                                           90 Fairbanks, AK                         596      36930
                                            8 Anchorage, AK                      292.11    37222.1
                                          183 Nome, AK                          1095.15   38317.26
                                          148 Lihue, HI                          2967.4   41284.65
                                          120 Honolulu, HI                        114.5   41399.15
                                          119 Hilo, HI                              176   41575.15
                                          309 Yellowknife, NT                   4111.93   45687.09
                                           59 Churchill, MB                     1431.71    47118.8
                                            5 Alert, NT                         2742.38   49861.18
                                          243 San Juan, PR                      4433.43   54294.61
                                          184 Norfolk, VA                       1451.64   55746.24
51 -> 288             1   56794.75         51 Champaign, IL
                                          288 Urbana, IL                           2.52       2.52
                                           73 Decatur, IL                         54.92      57.45
                                          262 Springfield, IL                     47.66     105.11
                                          196 Peoria, IL                          61.75     166.86
                                           32 Bloomington, IL                      43.6     210.46
                                          224 Rockford, IL                       123.66     334.12
                                          135 Kenosha, WI                         90.57     424.69
                                          165 Milwaukee, WI                       31.93     456.62
                                          214 Racine, WI                          23.24     479.86
                                           58 Chicago, IL                         61.23     541.09
                                          104 Gary, IN                            27.47     568.56
                                          259 South Bend, IN                      76.01     644.57
                                          132 Kalamazoo, MI                       62.16     706.73
                                           21 Battle Creek, MI                    28.23     734.96
                                          142 Lansing, MI                         51.65     786.61
                                          125 Jackson, MI                         35.28     821.89
                                            9 Ann Arbor, MI                       46.67     868.56
                                          280 Toledo, OH                          43.57     912.13
                                           76 Detroit, MI                         58.03     970.16
                                          304 Windsor, ON                          7.21     977.37
                                           94 Flint, MI                           71.67    1049.04
                                          226 Saginaw, MI                          33.5    1082.54
                                           22 Bay City, MI                        12.83    1095.36
                                          106 Grand Rapids, MI                   130.44     1225.8
                                           96 Ft Wayne, IN                          132     1357.8
                                          174 Muncie, IN                          67.15    1424.95
                                          123 Indianapolis, IN                    60.87    1485.83
                                          140 Lafayette, IN                       66.81    1552.63
                                          276 Terre Haute, IN                     75.45    1628.09
                                           89 Evansville, IN                     103.56    1731.64
                                          192 Paducah, KY                         94.86    1826.51
                                          175 Nashville, TN                      140.56    1967.07
                                           35 Bowling Green, KY                   61.65    2028.71
                                          154 Louisville, KY                       99.3    2128.02
                                          147 Lexington, KY                       90.44    2218.46
                                           60 Cincinnati, OH                      81.08    2299.54
                                          114 Hamilton, OH                        17.93    2317.47
                                           71 Dayton, OH                          35.63     2353.1
                                          265 Springfield, OH                     28.81    2381.91
                                           66 Columbus, OH                        56.03    2437.94
                                          312 Zanesville, OH                      68.11    2506.04
                                           47 Canton, OH                          73.78    2579.83
                                            2 Akron, OH                            21.8    2601.63
                                           61 Cleveland, OH                       31.35    2632.98
                                          310 Youngstown, OH                      77.36    2710.33
                                          267 Steubenville, OH                    50.45    2760.79
                                          297 Wheeling, WV                        21.97    2782.75
                                          201 Pittsburgh, PA                      56.46    2839.21
                                           86 Erie, PA                           116.83    2956.05
                                           37 Brantford, ON                       71.49    3027.54
                                          138 Kitchener, ON                       22.82    3050.35
                                          111 Guelph, ON                          10.29    3060.65
                                           42 Burlington, ONT                     29.68    3090.32
                                          115 Hamilton, ON                        19.51    3109.83
                                          227 Saint Catherines, ON                52.51    3162.34
                                           41 Buffalo, NY                         29.25    3191.58
                                          182 Niagara Falls, ON                   20.54    3212.12
                                          282 Toronto, ON                         42.01    3254.13
                                          197 Peterborough, ON                    82.62    3336.75
                                           24 Belleville, ON                      72.87    3409.61
                                          137 Kingston, ON                        49.28     3458.9
                                          191 Ottawa, ON                          85.39    3544.28
                                          172 Montreal, QC                       146.68    3690.97
                                           43 Burlington, VT                      97.19    3788.16
                                          171 Montpelier, VT                      46.45    3834.61
                                           38 Brattleboro, VT                     97.37    3931.97
                                          263 Springfield, MA                     51.84    3983.81
                                          117 Hartford, CT                        24.25    4008.06
                                          178 New Britain,CT                       9.62    4017.69
                                          163 Meriden, CT                          8.71     4026.4
                                          179 New Haven, CT                       17.96    4044.36
                                           39 Bridgeport, CT                      21.46    4065.82
                                          266 Stamford, CT                        24.55    4090.37
                                          299 White Plains, NY                    15.36    4105.73
                                          181 New York, NY                        27.75    4133.48
                                          128 Jersey City, NJ                      5.04    4138.52
                                          177 Newark, NJ                           6.57    4145.09
                                           83 Elizabeth, NJ                        5.61     4150.7
                                          194 Paterson, NJ                        17.67    4168.37
                                          283 Trenton, NJ                          62.4    4230.77
                                          198 Philadelphia, PA                    34.35    4265.12
                                          302 Wilmington, DE                      30.05    4295.18
                                          217 Reading, PA                         48.48    4343.66
                                          129 Johnstown, PA                        27.2    4370.86
                                          141 Lancaster, PA                       16.64     4387.5
                                          116 Harrisburg, PA                      43.19    4430.69
                                           18 Baltimore, MD                        70.5    4501.18
                                          294 Washington, DC                      40.06    4541.24
                                          220 Richmond, VA                        97.21    4638.45
                                          208 Portsmouth, VA                      94.39    4732.84
                                          184 Norfolk, VA                          1.19    4734.03
                                          215 Raleigh, NC                        178.76    4912.79
                                           80 Durham, NC                          23.61    4936.41
                                          109 Greensboro, NC                      61.97    4998.37
                                          306 Winston-Salem, NC                    31.3    5029.67
                                           54 Charlotte, NC                       73.13     5102.8
                                          260 Spartanburg, NC                     77.64    5180.45
                                          110 Greenville, SC                      32.62    5213.06
                                           10 Asheville, NC                       52.87    5265.93
                                          139 Knoxville, TN                       97.65    5363.58
                                           56 Chattanooga, TN                    114.91    5478.49
                                          100 Gadsden, AL                         86.02    5564.51
                                          122 Huntsville, AL                      63.64    5628.15
                                           30 Birmingham, AL                      84.91    5713.06
                                          170 Montgomery, AL                      86.96    5800.02
                                           65 Columbus, GA                         90.9    5890.93
                                          157 Macon, GA                           97.26    5988.18
                                           12 Atlanta, GA                         81.64    6069.82
                                           14 Augusta, GA                        167.83    6237.65
                                           64 Columbia, SC                        74.55    6312.21
                                           52 Charleston, SC                      113.9     6426.1
                                          250 Savannah, GA                         93.9       6520
                                          127 Jacksonville, FL                   126.96    6646.96
                                          101 Gainesville, FL                     65.95    6712.91
                                           72 Daytona Beach, FL                   94.98    6807.89
                                          190 Orlando, FL                         52.58    6860.48
                                          275 Tampa, FL                           85.01    6945.48
                                          234 Saint Petersburg, FL                19.54    6965.02
                                          247 Sarasota, FL                        31.73    6996.75
                                          296 West Palm Beach, FL                176.46    7173.21
                                          164 Miami, FL                           65.75    7238.96
                                          136 Key West, FL                       138.36    7377.32
                                          274 Tallahassee, FL                    441.61    7818.92
                                          195 Pensacola, FL                      202.87     8021.8
                                          168 Mobile, AL                          60.12    8081.91
                                           28 Biloxi, MS                          61.74    8143.65
                                          112 Gulfport, MS                        14.47    8158.12
                                          180 New Orleans, LA                     73.62    8231.74
                                           20 Baton Rouge, LA                     82.09    8313.83
                                          176 Natchez, MS                         78.58    8392.41
                                          126 Jackson, MS                         98.43    8490.84
                                          162 Memphis, TN                         197.2    8688.04
                                          151 Little Rock, AR                     157.3    8845.33
                                          277 Texarkana, TX                      151.96    8997.29
                                          160 Marshall, TX                        64.71       9062
                                          256 Shreveport, LA                      42.67    9104.67
                                           23 Beaumont, TX                       170.28    9274.96
                                          204 Port Arthur, TX                     17.62    9292.58
                                          103 Galveston, TX                       72.86    9365.44
                                          121 Houston, TX                         50.45    9415.89
                                           16 Austin, TX                         168.07    9583.96
                                          238 San Antonio, TX                     77.99    9661.95
                                           68 Corpus Christi, TX                 135.39    9797.35
                                          143 Laredo, TX                         147.28    9944.63
                                          292 Waco, TX                            323.5   10268.13
                                           97 Ft Worth, TX                        82.15   10350.28
                                           69 Dallas, TX                          36.19   10386.47
                                          188 Oklahoma City, OK                  191.95   10578.42
                                           85 Enid, OK                            68.83   10647.25
                                          300 Wichita, KS                         97.07   10744.32
                                          236 Salina, KS                          81.55   10825.87
                                          281 Topeka, KS                         134.35   10960.22
                                          133 Kansas City, KS                     72.73   11032.95
                                          134 Kansas City, MO                      3.52   11036.48
                                          231 Saint Joseph, MO                    49.79   11086.27
                                          189 Omaha, NE                          127.61   11213.88
                                          150 Lincoln, NE                         59.52    11273.4
                                          257 Sioux City, IA                     118.91    11392.3
                                          258 Sioux Falls, SD                     75.45   11467.76
                                          228 Saint Cloud, MN                    223.72   11691.48
                                          166 Minneapolis, MN                     73.94   11765.42
                                          233 Saint Paul, MN                      12.03   11777.45
                                          222 Rochester, MN                       76.94   11854.39
                                           81 Eau Claire, WI                       86.5   11940.89
                                          270 Superior, WI                       138.42    12079.3
                                           79 Duluth, MN                           4.32   12083.63
                                          278 Thunder Bay, ON                    221.38   12305.01
                                          108 Green Bay, WI                      281.05   12586.06
                                          253 Sheboygan, WI                       57.13   12643.19
                                          158 Madison, WI                         125.6   12768.78
                                           78 Dubuque, IA                         95.84   12864.62
                                           49 Cedar Rapids, IA                    75.74   12940.36
                                          124 Iowa City, IA                       25.25   12965.61
                                          295 Waterloo, IA                        80.35   13045.96
                                           75 Des Moines, IA                     107.02   13152.99
                                           63 Columbia, MO                       203.13   13356.12
                                          264 Springfield, MO                    137.23   13493.35
                                          130 Joplin, MO                          84.44   13577.79
                                           95 Ft Smith, AR                       117.62    13695.4
                                          287 Tulsa, OK                          122.27   13817.67
                                           77 Dodge City, KS                     299.19   14116.86
                                            7 Amarillo, TX                       215.16   14332.02
                                          156 Lubbock, TX                        113.61   14445.63
                                            1 Abilene, TX                        166.25   14611.88
                                           84 El Paso, TX                        469.27   15081.15
                                            4 Albuquerque, NM                    230.08   15311.23
                                          246 Santa Fe, NM                        64.52   15375.75
                                          102 Gallup, NM                         194.11   15569.86
                                           93 Flagstaff, AZ                      202.26   15772.12
                                          199 Phoenix, AZ                        124.38    15896.5
                                          286 Tucson, AZ                         116.06   16012.56
                                          311 Yuma, AZ                           257.86   16270.41
                                          240 San Diego, CA                      175.01   16445.43
                                          239 San Bernardino, CA                  96.69   16542.12
                                          193 Pasadena, CA                        59.12   16601.24
                                          153 Los Angeles, CA                      9.51   16610.75
                                          244 Santa Barbara, CA                  103.68   16714.43
                                           17 Bakersfield, CA                     80.84   16795.27
                                           99 Fresno, CA                         108.31   16903.58
                                          268 Stockton, CA                       134.15   17037.73
                                          225 Sacramento, CA                      45.35   17083.08
                                           26 Berkeley, CA                         72.8   17155.88
                                          186 Oakland, CA                          4.65   17160.53
                                          241 San Francisco, CA                   10.47      17171
                                          242 San Jose, CA                        47.11   17218.11
                                          245 Santa Cruz, CA                      26.93   17245.03
                                           48 Carson City, NV                    217.59   17462.63
                                          219 Reno, NV                            25.48   17488.11
                                           88 Eureka, CA                         313.15   17801.26
                                           87 Eugene, OR                         236.57   18037.82
                                          235 Salem, OR                           61.63   18099.46
                                          206 Portland, OR                        47.17   18146.63
                                          273 Tacoma, WA                         120.57    18267.2
                                          252 Seattle, WA                         25.62   18292.82
                                           25 Bellingham, WA                      80.42   18373.24
                                          290 Vancouver, BC                       56.66    18429.9
                                          291 Victoria, BC                        41.45   18471.35
                                          308 Yakima, WA                         246.37   18717.72
                                          293 Walla Walla, WA                    153.98    18871.7
                                          261 Spokane, WA                        127.07   18998.77
                                           33 Boise, ID                          291.99   19290.76
                                          203 Pocatello, ID                      264.67   19555.43
                                          187 Ogden, UT                          118.47    19673.9
                                          237 Salt Lake City, UT                  32.44   19706.34
                                          211 Provo, UT                           39.79   19746.13
                                          105 Grand Junction, CO                 229.45   19975.58
                                           74 Denver, CO                         250.76   20226.34
                                           62 Colorado Springs, CO                63.56    20289.9
                                          212 Pueblo, CO                          42.63   20332.53
                                           57 Cheyenne, WY                       199.91   20532.45
                                          216 Rapid City, SD                     230.96    20763.4
                                          200 Pierre, SD                         199.98   20963.38
                                           31 Bismarck, ND                       171.22    21134.6
                                          167 Minot, ND                          104.59   21239.19
                                           36 Brandon, MB                        148.55   21387.74
                                          305 Winnipeg, MB                       187.08   21574.82
                                           92 Fargo, ND                          211.94   21786.76
                                          218 Regina, SK                         597.09   22383.85
                                          173 Moose Jaw, SK                       62.04   22445.89
                                          248 Saskatoon, SK                      149.68   22595.57
                                          161 Medicine Hat, AB                   315.13    22910.7
                                          146 Lethbridge, AB                     146.13   23056.82
                                           45 Calgary, AB                        132.75   23189.57
                                           82 Edmonton, AB                       173.35   23362.92
                                          107 Great Falls, MT                    446.74   23809.67
                                          118 Helena, MT                           80.7   23890.36
                                           44 Butte, MT                           53.31   23943.68
                                           27 Billings, MT                       279.14   24222.81
                                          255 Sheridan, WY                       126.61   24349.42
                                          144 Las Vegas, NV                      821.24   25170.67
                                          209 Prince Rupert, BC                 1638.53   26809.19
                                          131 Juneau, AK                         390.43   27199.62
                                          298 Whitehorse, YK                     172.32   27371.94
                                           70 Dawson, YT                         362.92   27734.86
                                           90 Fairbanks, AK                         596   28330.87
                                            8 Anchorage, AK                      292.11   28622.97
                                          183 Nome, AK                          1095.15   29718.13
                                          148 Lihue, HI                          2967.4   32685.52
                                          120 Honolulu, HI                        114.5   32800.02
                                          119 Hilo, HI                              176   32976.02
                                          309 Yellowknife, NT                   4111.93   37087.96
                                           59 Churchill, MB                     1431.71   38519.67
                                          249 Sault Ste Marie, ON               1073.27   39592.94
                                          269 Sudbury, ON                        256.57   39849.51
                                          185 North Bay, ON                          93   39942.51
                                          279 Timmins, ON                        198.01   40140.52
                                          152 London, ON                         387.85   40528.37
                                          223 Rochester, NY                       249.8   40778.17
                                          272 Syracuse, NY                       101.71   40879.88
                                          289 Utica, NY                           63.31   40943.18
                                           29 Binghamtom, NY                      83.89   41027.07
                                          301 Wilkes-Barre, PA                    58.97   41086.05
                                            6 Allentown, PA                       51.68   41137.72
                                           13 Atlantic City, NJ                  113.26   41250.99
                                           50 Central Islip, NY                  129.74   41380.73
                                          202 Pittsfield, MA                      114.7   41495.43
                                          285 Troy, NY                            36.34   41531.77
                                            3 Albany, NY                           6.88   41538.65
                                          251 Schenectady, NY                     16.88   41555.54
                                          307 Worcester, MA                      152.51   41708.04
                                          210 Providence, RI                      40.53   41748.58
                                           91 Fall River, MA                      19.72   41768.29
                                           40 Brockton, MA                        28.03   41796.32
                                           34 Boston, MA                          19.21   41815.53
                                           46 Cambridge, MA                        3.36    41818.9
                                          155 Lowell, MA                          23.03   41841.93
                                          145 Lawrence, MA                        11.73   41853.65
                                          159 Manchester, NH                      28.36   41882.01
                                           67 Concord, NH                         15.76   41897.76
                                          207 Portsmouth, NH                      54.37   41952.14
                                          205 Portland, ME                        53.74   42005.88
                                           15 Augusta, ME                         55.61   42061.49
                                           19 Bangor, ME                          77.07   42138.56
                                           98 Fredericton, NB                    171.89   42310.45
                                          229 Saint John, NB                      58.53   42368.98
                                          169 Moncton, NB                         99.94   42468.93
                                           55 Charlottetown, PE                  108.58    42577.5
                                          113 Halifax, NS                        100.98   42678.49
                                          271 Syndey, NS                         254.97   42933.46
                                          230 Saint John's, NF                   514.07   43447.53
                                          213 Quebec City, QC                   1290.47   44737.99
                                          284 Trois-Rivieres, QC                 190.67   44928.66
                                          254 Sherbrooke, QC                      93.08   45021.74
                                          221 Roanoke, VA                        802.17   45823.91
                                           53 Charleston, WV                     138.61   45962.52
                                           11 Ashland, KY                         70.03   46032.55
                                          149 Lima, OH                           186.42   46218.96
                                          232 Saint Louis, MO                    445.62   46664.59
                                          303 Wilmington, NC                     899.59   47564.17
                                          243 San Juan, PR                      1361.81   48925.99
                                            5 Alert, NT                         4433.43   53359.42
                                           51 Champaign, IL                     3435.34   56794.75
                      2   56794.89         51 Champaign, IL
                                          288 Urbana, IL                           2.52       2.52
                                           73 Decatur, IL                         54.92      57.45
                                          262 Springfield, IL                     47.66     105.11
                                          196 Peoria, IL                          61.75     166.86
                                           32 Bloomington, IL                      43.6     210.46
                                          224 Rockford, IL                       123.66     334.12
                                          135 Kenosha, WI                         90.57     424.69
                                          165 Milwaukee, WI                       31.93     456.62
                                          214 Racine, WI                          23.24     479.86
                                           58 Chicago, IL                         61.23     541.09
                                          104 Gary, IN                            27.47     568.56
                                          259 South Bend, IN                      76.01     644.57
                                          132 Kalamazoo, MI                       62.16     706.73
                                           21 Battle Creek, MI                    28.23     734.96
                                          142 Lansing, MI                         51.65     786.61
                                          125 Jackson, MI                         35.28     821.89
                                            9 Ann Arbor, MI                       46.67     868.56
                                          280 Toledo, OH                          43.57     912.13
                                           76 Detroit, MI                         58.03     970.16
                                          304 Windsor, ON                          7.21     977.37
                                           94 Flint, MI                           71.67    1049.04
                                          226 Saginaw, MI                          33.5    1082.54
                                           22 Bay City, MI                        12.83    1095.36
                                          106 Grand Rapids, MI                   130.44     1225.8
                                           96 Ft Wayne, IN                          132     1357.8
                                          174 Muncie, IN                          67.15    1424.95
                                          123 Indianapolis, IN                    60.87    1485.83
                                          140 Lafayette, IN                       66.81    1552.63
                                          276 Terre Haute, IN                     75.45    1628.09
                                           89 Evansville, IN                     103.56    1731.64
                                          192 Paducah, KY                         94.86    1826.51
                                          175 Nashville, TN                      140.56    1967.07
                                           35 Bowling Green, KY                   61.65    2028.71
                                          154 Louisville, KY                       99.3    2128.02
                                          147 Lexington, KY                       90.44    2218.46
                                           60 Cincinnati, OH                      81.08    2299.54
                                          114 Hamilton, OH                        17.93    2317.47
                                           71 Dayton, OH                          35.63     2353.1
                                          265 Springfield, OH                     28.81    2381.91
                                           66 Columbus, OH                        56.03    2437.94
                                          312 Zanesville, OH                      68.11    2506.04
                                           47 Canton, OH                          73.78    2579.83
                                            2 Akron, OH                            21.8    2601.63
                                           61 Cleveland, OH                       31.35    2632.98
                                          310 Youngstown, OH                      77.36    2710.33
                                          267 Steubenville, OH                    50.45    2760.79
                                          297 Wheeling, WV                        21.97    2782.75
                                          201 Pittsburgh, PA                      56.46    2839.21
                                           86 Erie, PA                           116.83    2956.05
                                           37 Brantford, ON                       71.49    3027.54
                                          138 Kitchener, ON                       22.82    3050.35
                                          111 Guelph, ON                          10.29    3060.65
                                           42 Burlington, ONT                     29.68    3090.32
                                          115 Hamilton, ON                        19.51    3109.83
                                          227 Saint Catherines, ON                52.51    3162.34
                                          182 Niagara Falls, ON                    8.92    3171.26
                                           41 Buffalo, NY                         20.54     3191.8
                                          282 Toronto, ON                         62.46    3254.26
                                          197 Peterborough, ON                    82.62    3336.88
                                           24 Belleville, ON                      72.87    3409.75
                                          137 Kingston, ON                        49.28    3459.03
                                          191 Ottawa, ON                          85.39    3544.41
                                          172 Montreal, QC                       146.68     3691.1
                                           43 Burlington, VT                      97.19    3788.29
                                          171 Montpelier, VT                      46.45    3834.74
                                           38 Brattleboro, VT                     97.37    3932.11
                                          263 Springfield, MA                     51.84    3983.94
                                          117 Hartford, CT                        24.25     4008.2
                                          178 New Britain,CT                       9.62    4017.82
                                          163 Meriden, CT                          8.71    4026.53
                                          179 New Haven, CT                       17.96    4044.49
                                           39 Bridgeport, CT                      21.46    4065.95
                                          266 Stamford, CT                        24.55     4090.5
                                          299 White Plains, NY                    15.36    4105.86
                                          181 New York, NY                        27.75    4133.61
                                          128 Jersey City, NJ                      5.04    4138.65
                                          177 Newark, NJ                           6.57    4145.22
                                           83 Elizabeth, NJ                        5.61    4150.84
                                          194 Paterson, NJ                        17.67     4168.5
                                          283 Trenton, NJ                          62.4     4230.9
                                          198 Philadelphia, PA                    34.35    4265.26
                                          302 Wilmington, DE                      30.05    4295.31
                                          217 Reading, PA                         48.48    4343.79
                                          129 Johnstown, PA                        27.2    4370.99
                                          141 Lancaster, PA                       16.64    4387.63
                                          116 Harrisburg, PA                      43.19    4430.82
                                           18 Baltimore, MD                        70.5    4501.31
                                          294 Washington, DC                      40.06    4541.38
                                          220 Richmond, VA                        97.21    4638.58
                                          208 Portsmouth, VA                      94.39    4732.97
                                          184 Norfolk, VA                          1.19    4734.16
                                          215 Raleigh, NC                        178.76    4912.92
                                           80 Durham, NC                          23.61    4936.54
                                          109 Greensboro, NC                      61.97    4998.51
                                          306 Winston-Salem, NC                    31.3     5029.8
                                           54 Charlotte, NC                       73.13    5102.94
                                          260 Spartanburg, NC                     77.64    5180.58
                                          110 Greenville, SC                      32.62    5213.19
                                           10 Asheville, NC                       52.87    5266.06
                                          139 Knoxville, TN                       97.65    5363.71
                                           56 Chattanooga, TN                    114.91    5478.63
                                          100 Gadsden, AL                         86.02    5564.64
                                          122 Huntsville, AL                      63.64    5628.29
                                           30 Birmingham, AL                      84.91    5713.19
                                          170 Montgomery, AL                      86.96    5800.16
                                           65 Columbus, GA                         90.9    5891.06
                                          157 Macon, GA                           97.26    5988.32
                                           12 Atlanta, GA                         81.64    6069.95
                                           14 Augusta, GA                        167.83    6237.79
                                           64 Columbia, SC                        74.55    6312.34
                                           52 Charleston, SC                      113.9    6426.24
                                          250 Savannah, GA                         93.9    6520.14
                                          127 Jacksonville, FL                   126.96    6647.09
                                          101 Gainesville, FL                     65.95    6713.05
                                           72 Daytona Beach, FL                   94.98    6808.02
                                          190 Orlando, FL                         52.58    6860.61
                                          275 Tampa, FL                           85.01    6945.62
                                          234 Saint Petersburg, FL                19.54    6965.15
                                          247 Sarasota, FL                        31.73    6996.88
                                          296 West Palm Beach, FL                176.46    7173.34
                                          164 Miami, FL                           65.75    7239.09
                                          136 Key West, FL                       138.36    7377.45
                                          274 Tallahassee, FL                    441.61    7819.06
                                          195 Pensacola, FL                      202.87    8021.93
                                          168 Mobile, AL                          60.12    8082.04
                                           28 Biloxi, MS                          61.74    8143.79
                                          112 Gulfport, MS                        14.47    8158.25
                                          180 New Orleans, LA                     73.62    8231.87
                                           20 Baton Rouge, LA                     82.09    8313.96
                                          176 Natchez, MS                         78.58    8392.54
                                          126 Jackson, MS                         98.43    8490.97
                                          162 Memphis, TN                         197.2    8688.17
                                          151 Little Rock, AR                     157.3    8845.47
                                          277 Texarkana, TX                      151.96    8997.42
                                          160 Marshall, TX                        64.71    9062.13
                                          256 Shreveport, LA                      42.67    9104.81
                                           23 Beaumont, TX                       170.28    9275.09
                                          204 Port Arthur, TX                     17.62    9292.71
                                          103 Galveston, TX                       72.86    9365.57
                                          121 Houston, TX                         50.45    9416.02
                                           16 Austin, TX                         168.07     9584.1
                                          238 San Antonio, TX                     77.99    9662.09
                                           68 Corpus Christi, TX                 135.39    9797.48
                                          143 Laredo, TX                         147.28    9944.76
                                          292 Waco, TX                            323.5   10268.26
                                           97 Ft Worth, TX                        82.15   10350.41
                                           69 Dallas, TX                          36.19    10386.6
                                          188 Oklahoma City, OK                  191.95   10578.55
                                           85 Enid, OK                            68.83   10647.38
                                          300 Wichita, KS                         97.07   10744.46
                                          236 Salina, KS                          81.55      10826
                                          281 Topeka, KS                         134.35   10960.35
                                          133 Kansas City, KS                     72.73   11033.09
                                          134 Kansas City, MO                      3.52   11036.61
                                          231 Saint Joseph, MO                    49.79    11086.4
                                          189 Omaha, NE                          127.61   11214.01
                                          150 Lincoln, NE                         59.52   11273.53
                                          257 Sioux City, IA                     118.91   11392.44
                                          258 Sioux Falls, SD                     75.45   11467.89
                                          228 Saint Cloud, MN                    223.72   11691.61
                                          166 Minneapolis, MN                     73.94   11765.55
                                          233 Saint Paul, MN                      12.03   11777.58
                                          222 Rochester, MN                       76.94   11854.52
                                           81 Eau Claire, WI                       86.5   11941.02
                                          270 Superior, WI                       138.42   12079.44
                                           79 Duluth, MN                           4.32   12083.76
                                          278 Thunder Bay, ON                    221.38   12305.14
                                          108 Green Bay, WI                      281.05   12586.19
                                          253 Sheboygan, WI                       57.13   12643.32
                                          158 Madison, WI                         125.6   12768.91
                                           78 Dubuque, IA                         95.84   12864.75
                                           49 Cedar Rapids, IA                    75.74    12940.5
                                          124 Iowa City, IA                       25.25   12965.74
                                          295 Waterloo, IA                        80.35    13046.1
                                           75 Des Moines, IA                     107.02   13153.12
                                           63 Columbia, MO                       203.13   13356.25
                                          264 Springfield, MO                    137.23   13493.48
                                          130 Joplin, MO                          84.44   13577.92
                                           95 Ft Smith, AR                       117.62   13695.54
                                          287 Tulsa, OK                          122.27    13817.8
                                           77 Dodge City, KS                     299.19      14117
                                            7 Amarillo, TX                       215.16   14332.15
                                          156 Lubbock, TX                        113.61   14445.76
                                            1 Abilene, TX                        166.25   14612.02
                                           84 El Paso, TX                        469.27   15081.29
                                            4 Albuquerque, NM                    230.08   15311.37
                                          246 Santa Fe, NM                        64.52   15375.88
                                          102 Gallup, NM                         194.11   15569.99
                                           93 Flagstaff, AZ                      202.26   15772.25
                                          199 Phoenix, AZ                        124.38   15896.63
                                          286 Tucson, AZ                         116.06   16012.69
                                          311 Yuma, AZ                           257.86   16270.55
                                          240 San Diego, CA                      175.01   16445.56
                                          239 San Bernardino, CA                  96.69   16542.25
                                          193 Pasadena, CA                        59.12   16601.38
                                          153 Los Angeles, CA                      9.51   16610.89
                                          244 Santa Barbara, CA                  103.68   16714.56
                                           17 Bakersfield, CA                     80.84   16795.41
                                           99 Fresno, CA                         108.31   16903.71
                                          268 Stockton, CA                       134.15   17037.87
                                          225 Sacramento, CA                      45.35   17083.21
                                           26 Berkeley, CA                         72.8   17156.01
                                          186 Oakland, CA                          4.65   17160.66
                                          241 San Francisco, CA                   10.47   17171.13
                                          242 San Jose, CA                        47.11   17218.24
                                          245 Santa Cruz, CA                      26.93   17245.17
                                           48 Carson City, NV                    217.59   17462.76
                                          219 Reno, NV                            25.48   17488.24
                                           88 Eureka, CA                         313.15   17801.39
                                           87 Eugene, OR                         236.57   18037.96
                                          235 Salem, OR                           61.63   18099.59
                                          206 Portland, OR                        47.17   18146.76
                                          273 Tacoma, WA                         120.57   18267.33
                                          252 Seattle, WA                         25.62   18292.95
                                           25 Bellingham, WA                      80.42   18373.37
                                          290 Vancouver, BC                       56.66   18430.03
                                          291 Victoria, BC                        41.45   18471.48
                                          308 Yakima, WA                         246.37   18717.85
                                          293 Walla Walla, WA                    153.98   18871.83
                                          261 Spokane, WA                        127.07    18998.9
                                           33 Boise, ID                          291.99    19290.9
                                          203 Pocatello, ID                      264.67   19555.56
                                          187 Ogden, UT                          118.47   19674.03
                                          237 Salt Lake City, UT                  32.44   19706.47
                                          211 Provo, UT                           39.79   19746.26
                                          105 Grand Junction, CO                 229.45   19975.72
                                           74 Denver, CO                         250.76   20226.47
                                           62 Colorado Springs, CO                63.56   20290.03
                                          212 Pueblo, CO                          42.63   20332.67
                                           57 Cheyenne, WY                       199.91   20532.58
                                          216 Rapid City, SD                     230.96   20763.54
                                          200 Pierre, SD                         199.98   20963.52
                                           31 Bismarck, ND                       171.22   21134.74
                                          167 Minot, ND                          104.59   21239.32
                                           36 Brandon, MB                        148.55   21387.87
                                          305 Winnipeg, MB                       187.08   21574.95
                                           92 Fargo, ND                          211.94   21786.89
                                          218 Regina, SK                         597.09   22383.98
                                          173 Moose Jaw, SK                       62.04   22446.03
                                          248 Saskatoon, SK                      149.68    22595.7
                                          161 Medicine Hat, AB                   315.13   22910.83
                                          146 Lethbridge, AB                     146.13   23056.96
                                           45 Calgary, AB                        132.75    23189.7
                                           82 Edmonton, AB                       173.35   23363.06
                                          107 Great Falls, MT                    446.74    23809.8
                                          118 Helena, MT                           80.7    23890.5
                                           44 Butte, MT                           53.31   23943.81
                                           27 Billings, MT                       279.14   24222.95
                                          255 Sheridan, WY                       126.61   24349.56
                                          144 Las Vegas, NV                      821.24    25170.8
                                          209 Prince Rupert, BC                 1638.53   26809.33
                                          131 Juneau, AK                         390.43   27199.75
                                          298 Whitehorse, YK                     172.32   27372.07
                                           70 Dawson, YT                         362.92      27735
                                           90 Fairbanks, AK                         596      28331
                                            8 Anchorage, AK                      292.11   28623.11
                                          183 Nome, AK                          1095.15   29718.26
                                          148 Lihue, HI                          2967.4   32685.65
                                          120 Honolulu, HI                        114.5   32800.16
                                          119 Hilo, HI                              176   32976.16
                                          309 Yellowknife, NT                   4111.93   37088.09
                                           59 Churchill, MB                     1431.71    38519.8
                                          249 Sault Ste Marie, ON               1073.27   39593.07
                                          269 Sudbury, ON                        256.57   39849.65
                                          185 North Bay, ON                          93   39942.65
                                          279 Timmins, ON                        198.01   40140.66
                                          152 London, ON                         387.85   40528.51
                                          223 Rochester, NY                       249.8    40778.3
                                          272 Syracuse, NY                       101.71   40880.01
                                          289 Utica, NY                           63.31   40943.32
                                           29 Binghamtom, NY                      83.89   41027.21
                                          301 Wilkes-Barre, PA                    58.97   41086.18
                                            6 Allentown, PA                       51.68   41137.86
                                           13 Atlantic City, NJ                  113.26   41251.12
                                           50 Central Islip, NY                  129.74   41380.86
                                          202 Pittsfield, MA                      114.7   41495.56
                                          285 Troy, NY                            36.34    41531.9
                                            3 Albany, NY                           6.88   41538.78
                                          251 Schenectady, NY                     16.88   41555.67
                                          307 Worcester, MA                      152.51   41708.18
                                          210 Providence, RI                      40.53   41748.71
                                           91 Fall River, MA                      19.72   41768.43
                                           40 Brockton, MA                        28.03   41796.45
                                           34 Boston, MA                          19.21   41815.67
                                           46 Cambridge, MA                        3.36   41819.03
                                          155 Lowell, MA                          23.03   41842.06
                                          145 Lawrence, MA                        11.73   41853.79
                                          159 Manchester, NH                      28.36   41882.14
                                           67 Concord, NH                         15.76    41897.9
                                          207 Portsmouth, NH                      54.37   41952.27
                                          205 Portland, ME                        53.74   42006.01
                                           15 Augusta, ME                         55.61   42061.62
                                           19 Bangor, ME                          77.07    42138.7
                                           98 Fredericton, NB                    171.89   42310.58
                                          229 Saint John, NB                      58.53   42369.11
                                          169 Moncton, NB                         99.94   42469.06
                                           55 Charlottetown, PE                  108.58   42577.64
                                          113 Halifax, NS                        100.98   42678.62
                                          271 Syndey, NS                         254.97   42933.59
                                          230 Saint John's, NF                   514.07   43447.66
                                          213 Quebec City, QC                   1290.47   44738.13
                                          284 Trois-Rivieres, QC                 190.67    44928.8
                                          254 Sherbrooke, QC                      93.08   45021.87
                                          221 Roanoke, VA                        802.17   45824.05
                                           53 Charleston, WV                     138.61   45962.65
                                           11 Ashland, KY                         70.03   46032.68
                                          149 Lima, OH                           186.42    46219.1
                                          232 Saint Louis, MO                    445.62   46664.72
                                          303 Wilmington, NC                     899.59   47564.31
                                          243 San Juan, PR                      1361.81   48926.12
                                            5 Alert, NT                         4433.43   53359.55
                                           51 Champaign, IL                     3435.34   56794.89

1252 rows selected.

Elapsed: 00:01:25.25
Longest Routes
==============
ROOT_LEG       PATH_RNK   TOT_DIST    TOWN_ID NAME                             LEG_DIST   CUM_DIST
------------ ---------- ---------- ---------- ------------------------------ ---------- ----------
183 -> 230            1  649684.75        183 Nome, AK
                                          230 Saint John's, NF                  7870.89    7870.89
                                          148 Lihue, HI                         7576.95   15447.85
                                            5 Alert, NT                         7905.76   23353.61
                                          119 Hilo, HI                          7786.39   31139.99
                                          271 Syndey, NS                        6867.36   38007.35
                                          120 Honolulu, HI                      6973.04   44980.39
                                           55 Charlottetown, PE                 6769.69   51750.08
                                            8 Anchorage, AK                     6084.17   57834.25
                                          243 San Juan, PR                       6499.8   64334.05
                                           90 Fairbanks, AK                     6485.59   70819.64
                                          113 Halifax, NS                        5979.6   76799.24
                                           70 Dawson, YT                        5390.11   82189.35
                                          169 Moncton, NB                       5290.95    87480.3
                                          298 Whitehorse, YK                    4966.85   92447.16
                                          229 Saint John, NB                    4896.82   97343.98
                                          131 Juneau, AK                        4819.35  102163.34
                                           98 Fredericton, NB                   4768.78  106932.11
                                          209 Prince Rupert, BC                 4454.24  111386.35
                                           19 Bangor, ME                        4310.99  115697.34
                                           88 Eureka, CA                        3836.77  119534.11
                                           15 Augusta, ME                        3765.4  123299.51
                                          291 Victoria, BC                      3718.78  127018.29
                                          205 Portland, ME                      3689.93  130708.23
                                          290 Vancouver, BC                      3676.9  134385.13
                                          207 Portsmouth, NH                    3646.55  138031.68
                                           87 Eugene, OR                        3615.89  141647.57
                                           40 Brockton, MA                      3600.15  145247.72
                                          235 Salem, OR                         3599.44  148847.16
                                           34 Boston, MA                        3595.59  152442.75
                                           25 Bellingham, WA                    3580.78  156023.53
                                           91 Fall River, MA                    3580.15  159603.68
                                          206 Portland, OR                      3569.55  163173.24
                                           46 Cambridge, MA                     3569.83  166743.06
                                          273 Tacoma, WA                        3563.14   170306.2
                                          145 Lawrence, MA                      3557.08  173863.27
                                          241 San Francisco, CA                 3557.84  177421.11
                                          213 Quebec City, QC                      3607  181028.11
                                          186 Oakland, CA                       3596.53  184624.65
                                          155 Lowell, MA                        3536.42  188161.06
                                          252 Seattle, WA                       3541.57  191702.63
                                          210 Providence, RI                     3540.8  195243.43
                                           26 Berkeley, CA                      3524.68  198768.11
                                          254 Sherbrooke, QC                    3533.82  202301.93
                                          245 Santa Cruz, CA                    3527.03  205828.96
                                          159 Manchester, NH                    3519.15  209348.11
                                          242 San Jose, CA                      3506.93  212855.04
                                           67 Concord, NH                       3502.92  216357.96
                                          225 Sacramento, CA                    3466.46  219824.42
                                          307 Worcester, MA                     3442.81  223267.23
                                          268 Stockton, CA                      3432.24  226699.47
                                          284 Trois-Rivieres, QC                3408.48  230107.95
                                          244 Santa Barbara, CA                 3351.71  233459.66
                                          171 Montpelier, VT                     3326.1  236785.76
                                          308 Yakima, WA                        3315.62  240101.39
                                          263 Springfield, MA                   3325.25  243426.64
                                           99 Fresno, CA                        3280.93  246707.57
                                           38 Brattleboro, VT                   3289.35  249996.92
                                          219 Reno, NV                          3273.12  253270.05
                                          117 Hartford, CT                      3259.94  256529.98
                                           48 Carson City, NV                   3258.04  259788.02
                                          178 New Britain,CT                    3251.14  263039.16
                                           17 Bakersfield, CA                   3224.24   266263.4
                                           43 Burlington, VT                    3226.83  269490.23
                                          153 Los Angeles, CA                   3193.66  272683.89
                                          163 Meriden, CT                        3181.7  275865.59
                                          309 Yellowknife, NT                   3219.55  279085.14
                                          164 Miami, FL                         3467.82  282552.96
                                           82 Edmonton, AB                      2998.65  285551.61
                                          136 Key West, FL                      2971.34  288522.96
                                          261 Spokane, WA                       2934.85  291457.81
                                          179 New Haven, CT                     3105.67  294563.47
                                          193 Pasadena, CA                      3163.09  297726.57
                                          172 Montreal, QC                      3157.19  300883.76
                                          240 San Diego, CA                     3118.23  304001.99
                                          202 Pittsfield, MA                     3107.7  307109.68
                                          293 Walla Walla, WA                   3125.94  310235.63
                                           50 Central Islip, NY                 3140.18   313375.8
                                          239 San Bernardino, CA                3080.98  316456.79
                                           39 Bridgeport, CT                    3084.78  319541.56
                                           33 Boise, ID                         2975.73  322517.29
                                          266 Stamford, CT                      2952.96  325470.25
                                          311 Yuma, AZ                           2896.3  328366.55
                                          285 Troy, NY                          2911.41  331277.97
                                          144 Las Vegas, NV                      2899.2  334177.16
                                            3 Albany, NY                        2893.98  337071.14
                                           45 Calgary, AB                       2842.81  339913.95
                                          296 West Palm Beach, FL               2889.69  342803.64
                                          146 Lethbridge, AB                    2761.59  345565.23
                                          299 White Plains, NY                  2761.87   348327.1
                                           44 Butte, MT                         2700.79  351027.89
                                          181 New York, NY                      2687.05  353714.95
                                          199 Phoenix, AZ                       2677.74  356392.69
                                          251 Schenectady, NY                   2713.16  359105.85
                                          203 Pocatello, ID                     2660.51  361766.36
                                          128 Jersey City, NJ                    2655.1  364421.46
                                          118 Helena, MT                         2653.8  367075.27
                                          177 Newark, NJ                        2647.25  369722.51
                                           93 Flagstaff, AZ                     2617.66  372340.18
                                          194 Paterson, NJ                      2619.56  374959.74
                                          187 Ogden, UT                         2611.96   377571.7
                                           83 Elizabeth, NJ                     2609.47  380181.16
                                          107 Great Falls, MT                   2605.85  382787.01
                                           13 Atlantic City, NJ                  2609.3  385396.31
                                          161 Medicine Hat, AB                  2613.82  388010.13
                                          283 Trenton, NJ                        2576.5  390586.63
                                          237 Salt Lake City, UT                2566.97  393153.59
                                          289 Utica, NY                         2538.01   395691.6
                                          286 Tucson, AZ                        2578.23  398269.82
                                          191 Ottawa, ON                        2575.89  400845.71
                                          211 Provo, UT                          2487.2  403332.91
                                          198 Philadelphia, PA                  2521.63  405854.54
                                           27 Billings, MT                      2338.33  408192.87
                                          302 Wilmington, DE                    2314.81  410507.68
                                          248 Saskatoon, SK                     2317.41  412825.09
                                          247 Sarasota, FL                      2394.44  415219.54
                                           59 Churchill, MB                     2311.24  417530.77
                                          234 Saint Petersburg, FL              2279.52  419810.29
                                          173 Moose Jaw, SK                     2220.06  422030.35
                                          190 Orlando, FL                       2249.04  424279.39
                                          218 Regina, SK                        2208.47  426487.86
                                           72 Daytona Beach, FL                 2195.17  428683.03
                                          255 Sheridan, WY                      2090.58  430773.61
                                            6 Allentown, PA                     2193.28  432966.89
                                          102 Gallup, NM                        2324.19  435291.08
                                           29 Binghamtom, NY                    2312.96  437604.04
                                          105 Grand Junction, CO                2264.43  439868.47
                                          301 Wilkes-Barre, PA                  2262.27  442130.74
                                           84 El Paso, TX                       2213.93  444344.68
                                          137 Kingston, ON                      2237.67  446582.35
                                            4 Albuquerque, NM                    2170.5  448752.84
                                          272 Syracuse, NY                      2178.26   450931.1
                                          246 Santa Fe, NM                      2120.23  453051.33
                                          217 Reading, PA                       2098.29  455149.62
                                           74 Denver, CO                        2008.13  457157.75
                                          208 Portsmouth, VA                    1992.18  459149.93
                                           57 Cheyenne, WY                      1993.01  461142.94
                                          184 Norfolk, VA                       1993.78  463136.72
                                           62 Colorado Springs, CO              1976.45  465113.17
                                          129 Johnstown, PA                     1972.05  467085.22
                                          212 Pueblo, CO                        1959.85  469045.06
                                          141 Lancaster, PA                     1959.48  471004.54
                                          216 Rapid City, SD                    1881.23  472885.77
                                          303 Wilmington, NC                    1875.13   474760.9
                                          167 Minot, ND                         1881.45  476642.36
                                          275 Tampa, FL                         1912.76  478555.12
                                           36 Brandon, MB                       1940.02  480495.14
                                          101 Gainesville, FL                   1855.41  482350.55
                                           31 Bismarck, ND                      1741.25   484091.8
                                           18 Baltimore, MD                     1749.02  485840.82
                                          143 Laredo, TX                        1779.18  487620.01
                                           24 Belleville, ON                    1918.78  489538.79
                                          156 Lubbock, TX                       1847.76  491386.54
                                          116 Harrisburg, PA                    1786.27  493172.82
                                            7 Amarillo, TX                      1758.66  494931.47
                                          223 Rochester, NY                     1760.64  496692.12
                                           68 Corpus Christi, TX                1730.17  498422.29
                                          279 Timmins, ON                       1812.36  500234.65
                                          238 San Antonio, TX                   1774.49  502009.14
                                          185 North Bay, ON                     1763.41  503772.55
                                            1 Abilene, TX                       1701.18  505473.73
                                          197 Peterborough, ON                  1685.89  507159.62
                                           16 Austin, TX                         1650.4  508810.02
                                          269 Sudbury, ON                       1627.33  510437.35
                                          121 Houston, TX                       1539.52  511976.87
                                           41 Buffalo, NY                       1455.86  513432.73
                                           77 Dodge City, KS                    1503.01  514935.73
                                          294 Washington, DC                    1589.78  516525.51
                                          200 Pierre, SD                        1654.69   518180.2
                                           52 Charleston, SC                    1622.39  519802.59
                                          305 Winnipeg, MB                      1683.01  521485.61
                                          127 Jacksonville, FL                  1729.19   523214.8
                                           92 Fargo, ND                          1549.3   524764.1
                                          220 Richmond, VA                       1482.8  526246.89
                                          292 Waco, TX                          1422.07  527668.96
                                          282 Toronto, ON                       1483.47  529152.43
                                          103 Galveston, TX                     1453.39  530605.82
                                          182 Niagara Falls, ON                 1446.61  532052.43
                                           97 Ft Worth, TX                      1451.32  533503.75
                                          227 Saint Catherines, ON               1447.6  534951.35
                                           69 Dallas, TX                        1414.51  536365.85
                                           42 Burlington, ONT                   1383.45   537749.3
                                          204 Port Arthur, TX                   1349.79   539099.1
                                          111 Guelph, ON                        1334.48  540433.58
                                           23 Beaumont, TX                      1333.91  541767.49
                                          115 Hamilton, ON                      1332.75  543100.24
                                          188 Oklahoma City, OK                 1326.53  544426.77
                                          138 Kitchener, ON                     1306.17  545732.94
                                           85 Enid, OK                          1303.54  547036.48
                                          215 Raleigh, NC                       1330.04  548366.51
                                          258 Sioux Falls, SD                   1358.74  549725.26
                                          250 Savannah, GA                      1337.75  551063.01
                                          228 Saint Cloud, MN                   1296.84  552359.85
                                          274 Tallahassee, FL                   1248.21  553608.06
                                          278 Thunder Bay, ON                   1287.21  554895.27
                                          180 New Orleans, LA                   1273.63  556168.89
                                          249 Sault Ste Marie, ON               1205.19  557374.08
                                           20 Baton Rouge, LA                   1199.28  558573.36
                                           37 Brantford, ON                     1151.44   559724.8
                                          300 Wichita, KS                       1232.93  560957.73
                                           80 Durham, NC                         1279.4  562237.14
                                          236 Salina, KS                         1307.8  563544.94
                                          109 Greensboro, NC                    1245.96   564790.9
                                          257 Sioux City, IA                    1230.47  566021.37
                                           64 Columbia, SC                      1213.26  567234.63
                                          150 Lincoln, NE                       1177.83  568412.46
                                          221 Roanoke, VA                       1181.08  569593.54
                                          189 Omaha, NE                         1139.08  570732.62
                                          306 Winston-Salem, NC                 1141.42  571874.04
                                           79 Duluth, MN                        1103.04  572977.08
                                          195 Pensacola, FL                     1179.96  574157.04
                                          270 Superior, WI                      1175.77  575332.81
                                           14 Augusta, GA                       1152.38  576485.19
                                          166 Minneapolis, MN                    1113.9  577599.09
                                           54 Charlotte, NC                     1091.15  578690.24
                                          233 Saint Paul, MN                    1080.39  579770.63
                                          157 Macon, GA                         1061.49  580832.12
                                           81 Eau Claire, WI                     989.72  581821.84
                                           28 Biloxi, MS                        1012.28  582834.12
                                          152 London, ON                        1016.65  583850.76
                                          160 Marshall, TX                      1158.56  585009.32
                                           86 Erie, PA                          1188.43  586197.75
                                          287 Tulsa, OK                          1174.1  587371.86
                                          201 Pittsburgh, PA                    1144.29  588516.15
                                          256 Shreveport, LA                    1096.48  589612.63
                                          310 Youngstown, OH                    1081.83  590694.46
                                          277 Texarkana, TX                     1066.85  591761.31
                                          267 Steubenville, OH                  1043.65  592804.96
                                          281 Topeka, KS                        1043.45  593848.41
                                          297 Wheeling, WV                      1035.82  594884.23
                                           95 Ft Smith, AR                       998.79  595883.02
                                           47 Canton, OH                         974.26  596857.28
                                          130 Joplin, MO                         943.13  597800.41
                                            2 Akron, OH                          939.34  598739.75
                                          176 Natchez, MS                        948.25  599688.01
                                           22 Bay City, MI                       980.29   600668.3
                                          112 Gulfport, MS                       982.13  601650.43
                                          108 Green Bay, WI                      980.65  602631.08
                                          168 Mobile, AL                         955.25  603586.33
                                          222 Rochester, MN                      970.35  604556.68
                                          260 Spartanburg, NC                    960.77  605517.44
                                          231 Saint Joseph, MO                   952.41  606469.86
                                          110 Greenville, SC                     925.02  607394.87
                                           75 Des Moines, IA                     904.35  608299.23
                                           10 Asheville, NC                      869.08   609168.3
                                          133 Kansas City, KS                     868.8   610037.1
                                           61 Cleveland, OH                      908.59  610945.69
                                          134 Kansas City, MO                    905.45  611851.14
                                           53 Charleston, WV                     895.98  612747.12
                                          264 Springfield, MO                    809.82  613556.95
                                          312 Zanesville, OH                     802.13  614359.08
                                          151 Little Rock, AR                    795.57  615154.65
                                          226 Saginaw, MI                        831.32  615985.97
                                          126 Jackson, MS                         880.9  616866.87
                                           94 Flint, MI                          865.78  617732.65
                                          170 Montgomery, AL                     757.41  618490.06
                                          295 Waterloo, IA                       814.78  619304.84
                                           65 Columbus, GA                       859.51  620164.34
                                           49 Cedar Rapids, IA                   804.18  620968.53
                                           12 Atlanta, GA                        759.63  621728.16
                                           78 Dubuque, IA                        744.13  622472.29
                                           30 Birmingham, AL                     675.42   623147.7
                                          253 Sheboygan, WI                      709.66  623857.37
                                          100 Gadsden, AL                        683.03   624540.4
                                          158 Madison, WI                        668.43  625208.83
                                           56 Chattanooga, TN                    622.55  625831.37
                                          124 Iowa City, IA                      627.43   626458.8
                                          139 Knoxville, TN                      656.94  627115.74
                                           63 Columbia, MO                       616.95  627732.69
                                          304 Windsor, ON                         687.3  628419.98
                                          162 Memphis, TN                        694.56  629114.55
                                           76 Detroit, MI                        693.11  629807.66
                                          122 Huntsville, AL                     579.38  630387.04
                                          165 Milwaukee, WI                      581.29  630968.33
                                           11 Ashland, KY                        481.46  631449.79
                                          232 Saint Louis, MO                    522.45  631972.25
                                            9 Ann Arbor, MI                      513.15   632485.4
                                          192 Paducah, KY                        491.81   632977.2
                                          142 Lansing, MI                        480.06  633457.26
                                          175 Nashville, TN                      479.16  633936.42
                                          106 Grand Rapids, MI                   475.97  634412.39
                                           35 Bowling Green, KY                  416.17  634828.56
                                          224 Rockford, IL                       408.25  635236.82
                                           66 Columbus, OH                       450.37  635687.19
                                          262 Springfield, IL                    459.25  636146.44
                                          280 Toledo, OH                         439.91  636586.35
                                          196 Peoria, IL                         422.25  637008.59
                                          265 Springfield, OH                    402.89  637411.49
                                           32 Bloomington, IL                    360.32  637771.81
                                          147 Lexington, KY                      356.49  638128.31
                                          214 Racine, WI                         399.12  638527.43
                                          154 Louisville, KY                     339.14  638866.57
                                          135 Kenosha, WI                         331.4  639197.97
                                           60 Cincinnati, OH                     331.61  639529.58
                                           73 Decatur, IL                        314.29  639843.88
                                          125 Jackson, MI                        355.83   640199.7
                                           89 Evansville, IN                     366.87  640566.58
                                           21 Battle Creek, MI                   342.27  640908.84
                                           51 Champaign, IL                       260.8  641169.64
                                          149 Lima, OH                           289.17  641458.82
                                          288 Urbana, IL                         286.77  641745.59
                                           71 Dayton, OH                         278.52  642024.11
                                           58 Chicago, IL                        279.24  642303.35
                                          114 Hamilton, OH                       272.42  642575.77
                                          104 Gary, IN                           244.97  642820.74
                                          174 Muncie, IN                         166.43  642987.17
                                          276 Terre Haute, IN                    148.82  643135.98
                                          132 Kalamazoo, MI                      232.44  643368.42
                                          123 Indianapolis, IN                   178.76  643547.18
                                          259 South Bend, IN                     132.47  643679.65
                                          140 Lafayette, IN                       97.61  643777.26
                                           96 Ft Wayne, IN                       130.36  643907.62
                                          183 Nome, AK                          5777.13  649684.75
                      2  649684.62        183 Nome, AK
                                          230 Saint John's, NF                  7870.89    7870.89
                                          148 Lihue, HI                         7576.95   15447.85
                                            5 Alert, NT                         7905.76   23353.61
                                          119 Hilo, HI                          7786.39   31139.99
                                          271 Syndey, NS                        6867.36   38007.35
                                          120 Honolulu, HI                      6973.04   44980.39
                                           55 Charlottetown, PE                 6769.69   51750.08
                                            8 Anchorage, AK                     6084.17   57834.25
                                          243 San Juan, PR                       6499.8   64334.05
                                           90 Fairbanks, AK                     6485.59   70819.64
                                          113 Halifax, NS                        5979.6   76799.24
                                           70 Dawson, YT                        5390.11   82189.35
                                          169 Moncton, NB                       5290.95    87480.3
                                          298 Whitehorse, YK                    4966.85   92447.16
                                          229 Saint John, NB                    4896.82   97343.98
                                          131 Juneau, AK                        4819.35  102163.34
                                           98 Fredericton, NB                   4768.78  106932.11
                                          209 Prince Rupert, BC                 4454.24  111386.35
                                           19 Bangor, ME                        4310.99  115697.34
                                           88 Eureka, CA                        3836.77  119534.11
                                           15 Augusta, ME                        3765.4  123299.51
                                          291 Victoria, BC                      3718.78  127018.29
                                          205 Portland, ME                      3689.93  130708.23
                                          290 Vancouver, BC                      3676.9  134385.13
                                          207 Portsmouth, NH                    3646.55  138031.68
                                           87 Eugene, OR                        3615.89  141647.57
                                           40 Brockton, MA                      3600.15  145247.72
                                          235 Salem, OR                         3599.44  148847.16
                                           34 Boston, MA                        3595.59  152442.75
                                           25 Bellingham, WA                    3580.78  156023.53
                                           91 Fall River, MA                    3580.15  159603.68
                                          206 Portland, OR                      3569.55  163173.24
                                           46 Cambridge, MA                     3569.83  166743.06
                                          273 Tacoma, WA                        3563.14   170306.2
                                          145 Lawrence, MA                      3557.08  173863.27
                                          241 San Francisco, CA                 3557.84  177421.11
                                          213 Quebec City, QC                      3607  181028.11
                                          186 Oakland, CA                       3596.53  184624.65
                                          155 Lowell, MA                        3536.42  188161.06
                                          252 Seattle, WA                       3541.57  191702.63
                                          210 Providence, RI                     3540.8  195243.43
                                           26 Berkeley, CA                      3524.68  198768.11
                                          254 Sherbrooke, QC                    3533.82  202301.93
                                          245 Santa Cruz, CA                    3527.03  205828.96
                                          159 Manchester, NH                    3519.15  209348.11
                                          242 San Jose, CA                      3506.93  212855.04
                                           67 Concord, NH                       3502.92  216357.96
                                          225 Sacramento, CA                    3466.46  219824.42
                                          307 Worcester, MA                     3442.81  223267.23
                                          268 Stockton, CA                      3432.24  226699.47
                                          284 Trois-Rivieres, QC                3408.48  230107.95
                                          244 Santa Barbara, CA                 3351.71  233459.66
                                          171 Montpelier, VT                     3326.1  236785.76
                                          308 Yakima, WA                        3315.62  240101.39
                                          263 Springfield, MA                   3325.25  243426.64
                                           99 Fresno, CA                        3280.93  246707.57
                                           38 Brattleboro, VT                   3289.35  249996.92
                                          219 Reno, NV                          3273.12  253270.05
                                          117 Hartford, CT                      3259.94  256529.98
                                           48 Carson City, NV                   3258.04  259788.02
                                          178 New Britain,CT                    3251.14  263039.16
                                           17 Bakersfield, CA                   3224.24   266263.4
                                           43 Burlington, VT                    3226.83  269490.23
                                          153 Los Angeles, CA                   3193.66  272683.89
                                          163 Meriden, CT                        3181.7  275865.59
                                          309 Yellowknife, NT                   3219.55  279085.14
                                          164 Miami, FL                         3467.82  282552.96
                                           82 Edmonton, AB                      2998.65  285551.61
                                          136 Key West, FL                      2971.34  288522.96
                                          261 Spokane, WA                       2934.85  291457.81
                                          179 New Haven, CT                     3105.67  294563.47
                                          193 Pasadena, CA                      3163.09  297726.57
                                          172 Montreal, QC                      3157.19  300883.76
                                          240 San Diego, CA                     3118.23  304001.99
                                          202 Pittsfield, MA                     3107.7  307109.68
                                          293 Walla Walla, WA                   3125.94  310235.63
                                           50 Central Islip, NY                 3140.18   313375.8
                                          239 San Bernardino, CA                3080.98  316456.79
                                           39 Bridgeport, CT                    3084.78  319541.56
                                           33 Boise, ID                         2975.73  322517.29
                                          266 Stamford, CT                      2952.96  325470.25
                                          311 Yuma, AZ                           2896.3  328366.55
                                          285 Troy, NY                          2911.41  331277.97
                                          144 Las Vegas, NV                      2899.2  334177.16
                                            3 Albany, NY                        2893.98  337071.14
                                           45 Calgary, AB                       2842.81  339913.95
                                          296 West Palm Beach, FL               2889.69  342803.64
                                          146 Lethbridge, AB                    2761.59  345565.23
                                          299 White Plains, NY                  2761.87   348327.1
                                           44 Butte, MT                         2700.79  351027.89
                                          181 New York, NY                      2687.05  353714.95
                                          199 Phoenix, AZ                       2677.74  356392.69
                                          251 Schenectady, NY                   2713.16  359105.85
                                          203 Pocatello, ID                     2660.51  361766.36
                                          128 Jersey City, NJ                    2655.1  364421.46
                                          118 Helena, MT                         2653.8  367075.27
                                          177 Newark, NJ                        2647.25  369722.51
                                           93 Flagstaff, AZ                     2617.66  372340.18
                                          194 Paterson, NJ                      2619.56  374959.74
                                          187 Ogden, UT                         2611.96   377571.7
                                           83 Elizabeth, NJ                     2609.47  380181.16
                                          107 Great Falls, MT                   2605.85  382787.01
                                           13 Atlantic City, NJ                  2609.3  385396.31
                                          161 Medicine Hat, AB                  2613.82  388010.13
                                          283 Trenton, NJ                        2576.5  390586.63
                                          237 Salt Lake City, UT                2566.97  393153.59
                                          289 Utica, NY                         2538.01   395691.6
                                          286 Tucson, AZ                        2578.23  398269.82
                                          191 Ottawa, ON                        2575.89  400845.71
                                          211 Provo, UT                          2487.2  403332.91
                                          198 Philadelphia, PA                  2521.63  405854.54
                                           27 Billings, MT                      2338.33  408192.87
                                          302 Wilmington, DE                    2314.81  410507.68
                                          248 Saskatoon, SK                     2317.41  412825.09
                                          247 Sarasota, FL                      2394.44  415219.54
                                           59 Churchill, MB                     2311.24  417530.77
                                          234 Saint Petersburg, FL              2279.52  419810.29
                                          173 Moose Jaw, SK                     2220.06  422030.35
                                          190 Orlando, FL                       2249.04  424279.39
                                          218 Regina, SK                        2208.47  426487.86
                                           72 Daytona Beach, FL                 2195.17  428683.03
                                          255 Sheridan, WY                      2090.58  430773.61
                                            6 Allentown, PA                     2193.28  432966.89
                                          102 Gallup, NM                        2324.19  435291.08
                                           29 Binghamtom, NY                    2312.96  437604.04
                                          105 Grand Junction, CO                2264.43  439868.47
                                          301 Wilkes-Barre, PA                  2262.27  442130.74
                                           84 El Paso, TX                       2213.93  444344.68
                                          137 Kingston, ON                      2237.67  446582.35
                                            4 Albuquerque, NM                    2170.5  448752.84
                                          272 Syracuse, NY                      2178.26   450931.1
                                          246 Santa Fe, NM                      2120.23  453051.33
                                          217 Reading, PA                       2098.29  455149.62
                                           74 Denver, CO                        2008.13  457157.75
                                          208 Portsmouth, VA                    1992.18  459149.93
                                           57 Cheyenne, WY                      1993.01  461142.94
                                          184 Norfolk, VA                       1993.78  463136.72
                                           62 Colorado Springs, CO              1976.45  465113.17
                                          129 Johnstown, PA                     1972.05  467085.22
                                          212 Pueblo, CO                        1959.85  469045.06
                                          141 Lancaster, PA                     1959.48  471004.54
                                          216 Rapid City, SD                    1881.23  472885.77
                                          303 Wilmington, NC                    1875.13   474760.9
                                          167 Minot, ND                         1881.45  476642.36
                                          275 Tampa, FL                         1912.76  478555.12
                                           36 Brandon, MB                       1940.02  480495.14
                                          101 Gainesville, FL                   1855.41  482350.55
                                           31 Bismarck, ND                      1741.25   484091.8
                                           18 Baltimore, MD                     1749.02  485840.82
                                          143 Laredo, TX                        1779.18  487620.01
                                           24 Belleville, ON                    1918.78  489538.79
                                          156 Lubbock, TX                       1847.76  491386.54
                                          116 Harrisburg, PA                    1786.27  493172.82
                                            7 Amarillo, TX                      1758.66  494931.47
                                          223 Rochester, NY                     1760.64  496692.12
                                           68 Corpus Christi, TX                1730.17  498422.29
                                          279 Timmins, ON                       1812.36  500234.65
                                          238 San Antonio, TX                   1774.49  502009.14
                                          185 North Bay, ON                     1763.41  503772.55
                                            1 Abilene, TX                       1701.18  505473.73
                                          197 Peterborough, ON                  1685.89  507159.62
                                           16 Austin, TX                         1650.4  508810.02
                                          269 Sudbury, ON                       1627.33  510437.35
                                          121 Houston, TX                       1539.52  511976.87
                                           41 Buffalo, NY                       1455.86  513432.73
                                           77 Dodge City, KS                    1503.01  514935.73
                                          294 Washington, DC                    1589.78  516525.51
                                          200 Pierre, SD                        1654.69   518180.2
                                           52 Charleston, SC                    1622.39  519802.59
                                          305 Winnipeg, MB                      1683.01  521485.61
                                          127 Jacksonville, FL                  1729.19   523214.8
                                           92 Fargo, ND                          1549.3   524764.1
                                          220 Richmond, VA                       1482.8  526246.89
                                          292 Waco, TX                          1422.07  527668.96
                                          282 Toronto, ON                       1483.47  529152.43
                                          103 Galveston, TX                     1453.39  530605.82
                                          182 Niagara Falls, ON                 1446.61  532052.43
                                           97 Ft Worth, TX                      1451.32  533503.75
                                          227 Saint Catherines, ON               1447.6  534951.35
                                           69 Dallas, TX                        1414.51  536365.85
                                           42 Burlington, ONT                   1383.45   537749.3
                                           23 Beaumont, TX                      1349.56  539098.86
                                          111 Guelph, ON                        1333.91  540432.77
                                          204 Port Arthur, TX                   1334.48  541767.25
                                          115 Hamilton, ON                      1332.86  543100.11
                                          188 Oklahoma City, OK                 1326.53  544426.64
                                          138 Kitchener, ON                     1306.17  545732.81
                                           85 Enid, OK                          1303.54  547036.35
                                          215 Raleigh, NC                       1330.04  548366.39
                                          258 Sioux Falls, SD                   1358.74  549725.13
                                          250 Savannah, GA                      1337.75  551062.88
                                          228 Saint Cloud, MN                   1296.84  552359.72
                                          274 Tallahassee, FL                   1248.21  553607.93
                                          278 Thunder Bay, ON                   1287.21  554895.14
                                          180 New Orleans, LA                   1273.63  556168.77
                                          249 Sault Ste Marie, ON               1205.19  557373.95
                                           20 Baton Rouge, LA                   1199.28  558573.23
                                           37 Brantford, ON                     1151.44  559724.67
                                          300 Wichita, KS                       1232.93   560957.6
                                           80 Durham, NC                         1279.4  562237.01
                                          236 Salina, KS                         1307.8  563544.81
                                          109 Greensboro, NC                    1245.96  564790.77
                                          257 Sioux City, IA                    1230.47  566021.24
                                           64 Columbia, SC                      1213.26   567234.5
                                          150 Lincoln, NE                       1177.83  568412.33
                                          221 Roanoke, VA                       1181.08  569593.41
                                          189 Omaha, NE                         1139.08  570732.49
                                          306 Winston-Salem, NC                 1141.42  571873.91
                                           79 Duluth, MN                        1103.04  572976.95
                                          195 Pensacola, FL                     1179.96  574156.91
                                          270 Superior, WI                      1175.77  575332.68
                                           14 Augusta, GA                       1152.38  576485.06
                                          166 Minneapolis, MN                    1113.9  577598.96
                                           54 Charlotte, NC                     1091.15  578690.11
                                          233 Saint Paul, MN                    1080.39   579770.5
                                          157 Macon, GA                         1061.49  580831.99
                                           81 Eau Claire, WI                     989.72  581821.71
                                           28 Biloxi, MS                        1012.28  582833.99
                                          152 London, ON                        1016.65  583850.64
                                          160 Marshall, TX                      1158.56  585009.19
                                           86 Erie, PA                          1188.43  586197.63
                                          287 Tulsa, OK                          1174.1  587371.73
                                          201 Pittsburgh, PA                    1144.29  588516.02
                                          256 Shreveport, LA                    1096.48   589612.5
                                          310 Youngstown, OH                    1081.83  590694.33
                                          277 Texarkana, TX                     1066.85  591761.18
                                          267 Steubenville, OH                  1043.65  592804.83
                                          281 Topeka, KS                        1043.45  593848.28
                                          297 Wheeling, WV                      1035.82   594884.1
                                           95 Ft Smith, AR                       998.79  595882.89
                                           47 Canton, OH                         974.26  596857.16
                                          130 Joplin, MO                         943.13  597800.28
                                            2 Akron, OH                          939.34  598739.63
                                          176 Natchez, MS                        948.25  599687.88
                                           22 Bay City, MI                       980.29  600668.17
                                          112 Gulfport, MS                       982.13   601650.3
                                          108 Green Bay, WI                      980.65  602630.95
                                          168 Mobile, AL                         955.25   603586.2
                                          222 Rochester, MN                      970.35  604556.55
                                          260 Spartanburg, NC                    960.77  605517.32
                                          231 Saint Joseph, MO                   952.41  606469.73
                                          110 Greenville, SC                     925.02  607394.74
                                           75 Des Moines, IA                     904.35   608299.1
                                           10 Asheville, NC                      869.08  609168.17
                                          133 Kansas City, KS                     868.8  610036.97
                                           61 Cleveland, OH                      908.59  610945.56
                                          134 Kansas City, MO                    905.45  611851.01
                                           53 Charleston, WV                     895.98  612746.99
                                          264 Springfield, MO                    809.82  613556.82
                                          312 Zanesville, OH                     802.13  614358.95
                                          151 Little Rock, AR                    795.57  615154.52
                                          226 Saginaw, MI                        831.32  615985.85
                                          126 Jackson, MS                         880.9  616866.74
                                           94 Flint, MI                          865.78  617732.52
                                          170 Montgomery, AL                     757.41  618489.93
                                          295 Waterloo, IA                       814.78  619304.71
                                           65 Columbus, GA                       859.51  620164.22
                                           49 Cedar Rapids, IA                   804.18   620968.4
                                           12 Atlanta, GA                        759.63  621728.03
                                           78 Dubuque, IA                        744.13  622472.16
                                           30 Birmingham, AL                     675.42  623147.57
                                          253 Sheboygan, WI                      709.66  623857.24
                                          100 Gadsden, AL                        683.03  624540.27
                                          158 Madison, WI                        668.43   625208.7
                                           56 Chattanooga, TN                    622.55  625831.25
                                          124 Iowa City, IA                      627.43  626458.68
                                          139 Knoxville, TN                      656.94  627115.61
                                           63 Columbia, MO                       616.95  627732.56
                                          304 Windsor, ON                         687.3  628419.86
                                          162 Memphis, TN                        694.56  629114.42
                                           76 Detroit, MI                        693.11  629807.53
                                          122 Huntsville, AL                     579.38  630386.91
                                          165 Milwaukee, WI                      581.29   630968.2
                                           11 Ashland, KY                        481.46  631449.67
                                          232 Saint Louis, MO                    522.45  631972.12
                                            9 Ann Arbor, MI                      513.15  632485.27
                                          192 Paducah, KY                        491.81  632977.08
                                          142 Lansing, MI                        480.06  633457.13
                                          175 Nashville, TN                      479.16  633936.29
                                          106 Grand Rapids, MI                   475.97  634412.26
                                           35 Bowling Green, KY                  416.17  634828.44
                                          224 Rockford, IL                       408.25  635236.69
                                           66 Columbus, OH                       450.37  635687.06
                                          262 Springfield, IL                    459.25  636146.31
                                          280 Toledo, OH                         439.91  636586.22
                                          196 Peoria, IL                         422.25  637008.47
                                          265 Springfield, OH                    402.89  637411.36
                                           32 Bloomington, IL                    360.32  637771.68
                                          147 Lexington, KY                      356.49  638128.18
                                          214 Racine, WI                         399.12   638527.3
                                          154 Louisville, KY                     339.14  638866.44
                                          135 Kenosha, WI                         331.4  639197.84
                                           60 Cincinnati, OH                     331.61  639529.45
                                           73 Decatur, IL                        314.29  639843.75
                                          125 Jackson, MI                        355.83  640199.57
                                           89 Evansville, IN                     366.87  640566.45
                                           21 Battle Creek, MI                   342.27  640908.71
                                           51 Champaign, IL                       260.8  641169.51
                                          149 Lima, OH                           289.17  641458.69
                                          288 Urbana, IL                         286.77  641745.46
                                           71 Dayton, OH                         278.52  642023.98
                                           58 Chicago, IL                        279.24  642303.22
                                          114 Hamilton, OH                       272.42  642575.65
                                          104 Gary, IN                           244.97  642820.61
                                          174 Muncie, IN                         166.43  642987.04
                                          276 Terre Haute, IN                    148.82  643135.86
                                          132 Kalamazoo, MI                      232.44  643368.29
                                          123 Indianapolis, IN                   178.76  643547.05
                                          259 South Bend, IN                     132.47  643679.52
                                          140 Lafayette, IN                       97.61  643777.13
                                           96 Ft Wayne, IN                       130.36  643907.49
                                          183 Nome, AK                          5777.13  649684.62
5 -> 148              1  650614.77          5 Alert, NT
                                          148 Lihue, HI                         7905.76    7905.76
                                          230 Saint John's, NF                  7576.95   15482.71
                                          183 Nome, AK                          7870.89   23353.61
                                          271 Syndey, NS                        7389.33   30742.93
                                          120 Honolulu, HI                      6973.04   37715.97
                                           55 Charlottetown, PE                 6769.69   44485.66
                                          119 Hilo, HI                          6665.33   51150.99
                                          113 Halifax, NS                       6613.34   57764.33
                                            8 Anchorage, AK                     6075.13   63839.46
                                          243 San Juan, PR                       6499.8   70339.26
                                           90 Fairbanks, AK                     6485.59   76824.85
                                          169 Moncton, NB                        5881.4   82706.26
                                           70 Dawson, YT                        5290.95   87997.21
                                          229 Saint John, NB                    5223.21   93220.42
                                          298 Whitehorse, YK                    4896.82   98117.25
                                           98 Fredericton, NB                   4845.34  102962.58
                                          131 Juneau, AK                        4768.78  107731.36
                                           19 Bangor, ME                        4630.48  112361.84
                                          209 Prince Rupert, BC                 4310.99  116672.83
                                           15 Augusta, ME                       4247.95  120920.78
                                           88 Eureka, CA                         3765.4  124686.18
                                          205 Portland, ME                      3729.96  128416.14
                                          291 Victoria, BC                      3689.93  132106.07
                                          207 Portsmouth, NH                     3659.1  135765.18
                                          290 Vancouver, BC                     3646.55  139411.72
                                           40 Brockton, MA                      3637.58  143049.31
                                          235 Salem, OR                         3599.44  146648.74
                                           34 Boston, MA                        3595.59  150244.33
                                           87 Eugene, OR                        3596.62  153840.95
                                           46 Cambridge, MA                     3593.43  157434.38
                                           25 Bellingham, WA                    3577.51  161011.89
                                           91 Fall River, MA                    3580.15  164592.04
                                          206 Portland, OR                      3569.55  168161.59
                                          145 Lawrence, MA                      3564.53  171726.12
                                          241 San Francisco, CA                 3557.84  175283.96
                                          213 Quebec City, QC                      3607  178890.96
                                          186 Oakland, CA                       3596.53  182487.49
                                          155 Lowell, MA                        3536.42  186023.91
                                          273 Tacoma, WA                           3547  189570.91
                                          210 Providence, RI                    3545.83  193116.74
                                          252 Seattle, WA                        3540.8  196657.53
                                          159 Manchester, NH                    3529.69  200187.22
                                           26 Berkeley, CA                      3528.99  203716.21
                                          254 Sherbrooke, QC                    3533.82  207250.03
                                          245 Santa Cruz, CA                    3527.03  210777.06
                                           67 Concord, NH                       3515.24   214292.3
                                          242 San Jose, CA                      3502.92  217795.22
                                          307 Worcester, MA                     3477.76  221272.98
                                          225 Sacramento, CA                    3442.81  224715.79
                                          284 Trois-Rivieres, QC                 3415.3  228131.09
                                          268 Stockton, CA                      3408.48  231539.57
                                          171 Montpelier, VT                    3393.96  234933.53
                                          244 Santa Barbara, CA                  3326.1  238259.63
                                           38 Brattleboro, VT                   3308.76  241568.39
                                          308 Yakima, WA                           3323   244891.4
                                          263 Springfield, MA                   3325.25  248216.65
                                           99 Fresno, CA                        3280.93  251497.58
                                          117 Hartford, CT                      3271.83  254769.41
                                          219 Reno, NV                          3259.94  258029.35
                                          178 New Britain,CT                     3253.1  261282.44
                                           48 Carson City, NV                   3251.14  264533.58
                                          163 Meriden, CT                        3248.8  267782.39
                                           17 Bakersfield, CA                   3221.22  271003.61
                                           43 Burlington, VT                    3226.83  274230.43
                                          153 Los Angeles, CA                   3193.66   277424.1
                                          179 New Haven, CT                      3170.9  280594.99
                                          309 Yellowknife, NT                   3219.25  283814.25
                                          164 Miami, FL                         3467.82  287282.06
                                           82 Edmonton, AB                      2998.65  290280.72
                                          136 Key West, FL                      2971.34  293252.06
                                          261 Spokane, WA                       2934.85  296186.91
                                           50 Central Islip, NY                 3092.23  299279.15
                                          293 Walla Walla, WA                   3140.18  302419.32
                                           39 Bridgeport, CT                    3137.06  305556.38
                                          193 Pasadena, CA                      3142.69  308699.07
                                          172 Montreal, QC                      3157.19  311856.26
                                          240 San Diego, CA                     3118.23  314974.49
                                          202 Pittsfield, MA                     3107.7  318082.19
                                          239 San Bernardino, CA                3097.28  321179.47
                                          285 Troy, NY                          3070.66  324250.12
                                           33 Boise, ID                         2937.92  327188.04
                                          266 Stamford, CT                      2952.96     330141
                                          311 Yuma, AZ                           2896.3   333037.3
                                            3 Albany, NY                        2905.84  335943.14
                                          144 Las Vegas, NV                     2893.98  338837.12
                                          251 Schenectady, NY                   2883.23  341720.35
                                           45 Calgary, AB                       2828.13  344548.48
                                          296 West Palm Beach, FL               2889.69  347438.17
                                          146 Lethbridge, AB                    2761.59  350199.76
                                          299 White Plains, NY                  2761.87  352961.63
                                           44 Butte, MT                         2700.79  355662.42
                                          181 New York, NY                      2687.05  358349.48
                                          199 Phoenix, AZ                       2677.74  361027.22
                                          128 Jersey City, NJ                   2673.06  363700.28
                                          203 Pocatello, ID                      2655.1  366355.39
                                          177 Newark, NJ                        2648.53  369003.92
                                          118 Helena, MT                        2647.25  371651.17
                                           13 Atlantic City, NJ                 2646.38  374297.55
                                          161 Medicine Hat, AB                  2613.82  376911.37
                                           83 Elizabeth, NJ                     2604.16  379515.53
                                           93 Flagstaff, AZ                     2614.32  382129.85
                                          194 Paterson, NJ                      2619.56  384749.41
                                          187 Ogden, UT                         2611.96  387361.37
                                          283 Trenton, NJ                       2573.35  389934.72
                                          107 Great Falls, MT                   2575.55  392510.27
                                          198 Philadelphia, PA                  2550.72  395060.99
                                          237 Salt Lake City, UT                2538.22  397599.21
                                          289 Utica, NY                         2538.01  400137.22
                                          286 Tucson, AZ                        2578.23  402715.44
                                          191 Ottawa, ON                        2575.89  405291.33
                                          211 Provo, UT                          2487.2  407778.53
                                            6 Allentown, PA                     2499.13  410277.67
                                          102 Gallup, NM                        2324.19  412601.86
                                           29 Binghamtom, NY                    2312.96  414914.82
                                           27 Billings, MT                       2265.6  417180.42
                                          302 Wilmington, DE                    2314.81  419495.23
                                          248 Saskatoon, SK                     2317.41  421812.65
                                          247 Sarasota, FL                      2394.44  424207.09
                                           59 Churchill, MB                     2311.24  426518.32
                                          234 Saint Petersburg, FL              2279.52  428797.84
                                          173 Moose Jaw, SK                     2220.06   431017.9
                                          190 Orlando, FL                       2249.04  433266.94
                                          218 Regina, SK                        2208.47  435475.41
                                           72 Daytona Beach, FL                 2195.17  437670.58
                                          255 Sheridan, WY                      2090.58  439761.16
                                          184 Norfolk, VA                       2189.22  441950.37
                                          105 Grand Junction, CO                2234.59  444184.96
                                          301 Wilkes-Barre, PA                  2262.27  446447.23
                                           84 El Paso, TX                       2213.93  448661.17
                                          137 Kingston, ON                      2237.67  450898.84
                                            4 Albuquerque, NM                    2170.5  453069.33
                                          272 Syracuse, NY                      2178.26  455247.59
                                          246 Santa Fe, NM                      2120.23  457367.82
                                          217 Reading, PA                       2098.29  459466.11
                                           74 Denver, CO                        2008.13  461474.24
                                          208 Portsmouth, VA                    1992.18  463466.42
                                           57 Cheyenne, WY                      1993.01  465459.43
                                          141 Lancaster, PA                     1971.66  467431.09
                                           62 Colorado Springs, CO              1972.03  469403.12
                                          129 Johnstown, PA                     1972.05  471375.16
                                          212 Pueblo, CO                        1959.85  473335.01
                                           18 Baltimore, MD                     1935.73  475270.74
                                          216 Rapid City, SD                    1868.74  477139.48
                                          303 Wilmington, NC                    1875.13  479014.61
                                          167 Minot, ND                         1881.45  480896.06
                                          275 Tampa, FL                         1912.76  482808.82
                                           36 Brandon, MB                       1940.02  484748.84
                                          101 Gainesville, FL                   1855.41  486604.25
                                           31 Bismarck, ND                      1741.25  488345.51
                                          127 Jacksonville, FL                  1744.35  490089.86
                                          305 Winnipeg, MB                      1729.19  491819.04
                                           52 Charleston, SC                    1683.01  493502.06
                                          200 Pierre, SD                        1622.39  495124.45
                                          294 Washington, DC                    1654.69  496779.14
                                          156 Lubbock, TX                       1753.74  498532.87
                                           24 Belleville, ON                    1847.76  500380.63
                                          143 Laredo, TX                        1918.78  502299.41
                                          279 Timmins, ON                       1920.31  504219.72
                                           68 Corpus Christi, TX                1812.36  506032.08
                                          185 North Bay, ON                      1786.7  507818.78
                                          238 San Antonio, TX                   1763.41  509582.19
                                          223 Rochester, NY                     1726.57  511308.76
                                            7 Amarillo, TX                      1760.64   513069.4
                                          116 Harrisburg, PA                    1758.66  514828.06
                                            1 Abilene, TX                       1668.54   516496.6
                                          197 Peterborough, ON                  1685.89  518182.49
                                           16 Austin, TX                         1650.4  519832.89
                                          269 Sudbury, ON                       1627.33  521460.22
                                          121 Houston, TX                       1539.52  522999.73
                                           41 Buffalo, NY                       1455.86   524455.6
                                           77 Dodge City, KS                    1503.01   525958.6
                                          220 Richmond, VA                      1558.59  527517.19
                                           92 Fargo, ND                          1482.8  528999.99
                                          250 Savannah, GA                      1489.99  530489.98
                                          258 Sioux Falls, SD                   1337.75  531827.74
                                          215 Raleigh, NC                       1358.74  533186.48
                                           85 Enid, OK                          1330.04  534516.52
                                          182 Niagara Falls, ON                 1380.26  535896.78
                                          292 Waco, TX                          1483.03  537379.81
                                          282 Toronto, ON                       1483.47  538863.29
                                           97 Ft Worth, TX                       1449.6  540312.89
                                          227 Saint Catherines, ON               1447.6  541760.49
                                          103 Galveston, TX                     1444.61  543205.09
                                           42 Burlington, ONT                   1421.73  544626.82
                                           69 Dallas, TX                        1383.45  546010.27
                                          115 Hamilton, ON                      1368.85  547379.12
                                           23 Beaumont, TX                      1332.75  548711.87
                                          111 Guelph, ON                        1333.91  550045.78
                                          204 Port Arthur, TX                   1334.48  551380.26
                                          138 Kitchener, ON                     1324.27  552704.53
                                          188 Oklahoma City, OK                 1306.17   554010.7
                                           37 Brantford, ON                     1299.42  555310.11
                                          300 Wichita, KS                       1232.93  556543.05
                                           80 Durham, NC                         1279.4  557822.45
                                          236 Salina, KS                         1307.8  559130.25
                                          109 Greensboro, NC                    1245.96  560376.22
                                          257 Sioux City, IA                    1230.47  561606.68
                                           64 Columbia, SC                      1213.26  562819.94
                                          228 Saint Cloud, MN                   1208.61  564028.55
                                          274 Tallahassee, FL                   1248.21  565276.76
                                          278 Thunder Bay, ON                   1287.21  566563.97
                                          180 New Orleans, LA                   1273.63   567837.6
                                          249 Sault Ste Marie, ON               1205.19  569042.78
                                           20 Baton Rouge, LA                   1199.28  570242.06
                                           79 Duluth, MN                        1130.44  571372.51
                                          195 Pensacola, FL                     1179.96  572552.47
                                          270 Superior, WI                      1175.77  573728.24
                                           14 Augusta, GA                       1152.38  574880.62
                                          150 Lincoln, NE                       1134.43  576015.05
                                          221 Roanoke, VA                       1181.08  577196.13
                                          189 Omaha, NE                         1139.08  578335.21
                                          306 Winston-Salem, NC                 1141.42  579476.63
                                          166 Minneapolis, MN                   1088.91  580565.53
                                           54 Charlotte, NC                     1091.15  581656.69
                                          233 Saint Paul, MN                    1080.39  582737.08
                                          157 Macon, GA                         1061.49  583798.57
                                           81 Eau Claire, WI                     989.72  584788.28
                                           28 Biloxi, MS                        1012.28  585800.56
                                          152 London, ON                        1016.65  586817.21
                                          160 Marshall, TX                      1158.56  587975.77
                                           86 Erie, PA                          1188.43   589164.2
                                          287 Tulsa, OK                          1174.1   590338.3
                                          201 Pittsburgh, PA                    1144.29  591482.59
                                          256 Shreveport, LA                    1096.48  592579.08
                                          310 Youngstown, OH                    1081.83   593660.9
                                          277 Texarkana, TX                     1066.85  594727.75
                                          267 Steubenville, OH                  1043.65  595771.41
                                          281 Topeka, KS                        1043.45  596814.86
                                          297 Wheeling, WV                      1035.82  597850.68
                                           95 Ft Smith, AR                       998.79  598849.47
                                           61 Cleveland, OH                      974.07  599823.54
                                          176 Natchez, MS                        959.96  600783.49
                                           22 Bay City, MI                       980.29  601763.78
                                          112 Gulfport, MS                       982.13  602745.92
                                          108 Green Bay, WI                      980.65  603726.56
                                          168 Mobile, AL                         955.25  604681.82
                                          222 Rochester, MN                      970.35  605652.16
                                          260 Spartanburg, NC                    960.77  606612.93
                                          231 Saint Joseph, MO                   952.41  607565.34
                                           47 Canton, OH                         933.28  608498.62
                                          130 Joplin, MO                         943.13  609441.75
                                            2 Akron, OH                          939.34  610381.09
                                          133 Kansas City, KS                    915.85  611296.95
                                           53 Charleston, WV                     899.41  612196.36
                                          134 Kansas City, MO                    895.98  613092.34
                                          110 Greenville, SC                     891.55  613983.89
                                           75 Des Moines, IA                     904.35  614888.24
                                           10 Asheville, NC                      869.08  615757.32
                                          295 Waterloo, IA                       827.18   616584.5
                                           65 Columbus, GA                       859.51  617444.01
                                          253 Sheboygan, WI                      802.52  618246.52
                                          126 Jackson, MS                         809.5  619056.02
                                          226 Saginaw, MI                         880.9  619936.92
                                          151 Little Rock, AR                    831.32  620768.24
                                          304 Windsor, ON                        828.42  621596.66
                                          264 Springfield, MO                    795.38  622392.04
                                          312 Zanesville, OH                     802.13  623194.17
                                           63 Columbia, MO                       716.36  623910.53
                                           76 Detroit, MI                        682.93  624593.46
                                          170 Montgomery, AL                      724.3  625317.77
                                          158 Madison, WI                        770.17  626087.93
                                           12 Atlanta, GA                        731.47  626819.41
                                           49 Cedar Rapids, IA                   759.63  627579.04
                                          100 Gadsden, AL                        675.88  628254.92
                                           78 Dubuque, IA                        668.88   628923.8
                                           30 Birmingham, AL                     675.42  629599.22
                                           94 Flint, MI                          690.27  630289.49
                                          162 Memphis, TN                        698.85  630988.33
                                          142 Lansing, MI                           647  631635.33
                                          122 Huntsville, AL                     570.44  632205.78
                                          124 Iowa City, IA                      588.25  632794.02
                                          139 Knoxville, TN                      656.94  633450.96
                                          224 Rockford, IL                       563.81  634014.76
                                           56 Chattanooga, TN                    563.58  634578.34
                                          165 Milwaukee, WI                      580.71  635159.05
                                           11 Ashland, KY                        481.46  635640.51
                                          232 Saint Louis, MO                    522.45  636162.96
                                            9 Ann Arbor, MI                      513.15  636676.12
                                          192 Paducah, KY                        491.81  637167.92
                                          125 Jackson, MI                        459.78   637627.7
                                          175 Nashville, TN                      451.22  638078.92
                                          106 Grand Rapids, MI                   475.97  638554.89
                                           35 Bowling Green, KY                  416.17  638971.07
                                          214 Racine, WI                         406.98  639378.05
                                          147 Lexington, KY                      399.12  639777.17
                                          196 Peoria, IL                         399.56  640176.73
                                           66 Columbus, OH                       458.14  640634.87
                                          262 Springfield, IL                    459.25  641094.13
                                          280 Toledo, OH                         439.91  641534.03
                                           73 Decatur, IL                        393.78  641927.82
                                          265 Springfield, OH                    355.61  642283.42
                                           32 Bloomington, IL                    360.32  642643.75
                                          149 Lima, OH                           338.23  642981.98
                                           89 Evansville, IN                     305.64  643287.62
                                           21 Battle Creek, MI                   342.27  643629.89
                                          154 Louisville, KY                     283.85  643913.74
                                          135 Kenosha, WI                         331.4  644245.14
                                           60 Cincinnati, OH                     331.61  644576.75
                                           58 Chicago, IL                         288.4  644865.14
                                           71 Dayton, OH                         279.24  645144.39
                                           51 Champaign, IL                      281.04  645425.42
                                          114 Hamilton, OH                       259.18   645684.6
                                          288 Urbana, IL                         256.66  645941.26
                                          132 Kalamazoo, MI                      235.55  646176.81
                                          276 Terre Haute, IN                    232.44  646409.25
                                           96 Ft Wayne, IN                        195.3  646604.55
                                          104 Gary, IN                           156.52  646761.07
                                          174 Muncie, IN                         166.43   646927.5
                                          259 South Bend, IN                     118.99  647046.49
                                          123 Indianapolis, IN                   132.47  647178.96
                                          140 Lafayette, IN                       66.81  647245.77
                                            5 Alert, NT                         3369.01  650614.77
                      2  650613.92          5 Alert, NT
                                          148 Lihue, HI                         7905.76    7905.76
                                          230 Saint John's, NF                  7576.95   15482.71
                                          183 Nome, AK                          7870.89   23353.61
                                          271 Syndey, NS                        7389.33   30742.93
                                          120 Honolulu, HI                      6973.04   37715.97
                                           55 Charlottetown, PE                 6769.69   44485.66
                                          119 Hilo, HI                          6665.33   51150.99
                                          113 Halifax, NS                       6613.34   57764.33
                                            8 Anchorage, AK                     6075.13   63839.46
                                          243 San Juan, PR                       6499.8   70339.26
                                           90 Fairbanks, AK                     6485.59   76824.85
                                          169 Moncton, NB                        5881.4   82706.26
                                           70 Dawson, YT                        5290.95   87997.21
                                          229 Saint John, NB                    5223.21   93220.42
                                          298 Whitehorse, YK                    4896.82   98117.25
                                           98 Fredericton, NB                   4845.34  102962.58
                                          131 Juneau, AK                        4768.78  107731.36
                                           19 Bangor, ME                        4630.48  112361.84
                                          209 Prince Rupert, BC                 4310.99  116672.83
                                           15 Augusta, ME                       4247.95  120920.78
                                           88 Eureka, CA                         3765.4  124686.18
                                          205 Portland, ME                      3729.96  128416.14
                                          291 Victoria, BC                      3689.93  132106.07
                                          207 Portsmouth, NH                     3659.1  135765.18
                                          290 Vancouver, BC                     3646.55  139411.72
                                           40 Brockton, MA                      3637.58  143049.31
                                          235 Salem, OR                         3599.44  146648.74
                                           34 Boston, MA                        3595.59  150244.33
                                           87 Eugene, OR                        3596.62  153840.95
                                           46 Cambridge, MA                     3593.43  157434.38
                                           25 Bellingham, WA                    3577.51  161011.89
                                           91 Fall River, MA                    3580.15  164592.04
                                          206 Portland, OR                      3569.55  168161.59
                                          145 Lawrence, MA                      3564.53  171726.12
                                          241 San Francisco, CA                 3557.84  175283.96
                                          213 Quebec City, QC                      3607  178890.96
                                          186 Oakland, CA                       3596.53  182487.49
                                          155 Lowell, MA                        3536.42  186023.91
                                          273 Tacoma, WA                           3547  189570.91
                                          210 Providence, RI                    3545.83  193116.74
                                          252 Seattle, WA                        3540.8  196657.53
                                          159 Manchester, NH                    3529.69  200187.22
                                           26 Berkeley, CA                      3528.99  203716.21
                                          254 Sherbrooke, QC                    3533.82  207250.03
                                          245 Santa Cruz, CA                    3527.03  210777.06
                                           67 Concord, NH                       3515.24   214292.3
                                          242 San Jose, CA                      3502.92  217795.22
                                          307 Worcester, MA                     3477.76  221272.98
                                          225 Sacramento, CA                    3442.81  224715.79
                                          284 Trois-Rivieres, QC                 3415.3  228131.09
                                          268 Stockton, CA                      3408.48  231539.57
                                          171 Montpelier, VT                    3393.96  234933.53
                                          244 Santa Barbara, CA                  3326.1  238259.63
                                           38 Brattleboro, VT                   3308.76  241568.39
                                          308 Yakima, WA                           3323   244891.4
                                          263 Springfield, MA                   3325.25  248216.65
                                           99 Fresno, CA                        3280.93  251497.58
                                          117 Hartford, CT                      3271.83  254769.41
                                          219 Reno, NV                          3259.94  258029.35
                                          178 New Britain,CT                     3253.1  261282.44
                                           48 Carson City, NV                   3251.14  264533.58
                                          163 Meriden, CT                        3248.8  267782.39
                                           17 Bakersfield, CA                   3221.22  271003.61
                                           43 Burlington, VT                    3226.83  274230.43
                                          153 Los Angeles, CA                   3193.66   277424.1
                                          179 New Haven, CT                      3170.9  280594.99
                                          309 Yellowknife, NT                   3219.25  283814.25
                                          164 Miami, FL                         3467.82  287282.06
                                           82 Edmonton, AB                      2998.65  290280.72
                                          136 Key West, FL                      2971.34  293252.06
                                          261 Spokane, WA                       2934.85  296186.91
                                           50 Central Islip, NY                 3092.23  299279.15
                                          293 Walla Walla, WA                   3140.18  302419.32
                                           39 Bridgeport, CT                    3137.06  305556.38
                                          193 Pasadena, CA                      3142.69  308699.07
                                          172 Montreal, QC                      3157.19  311856.26
                                          240 San Diego, CA                     3118.23  314974.49
                                          202 Pittsfield, MA                     3107.7  318082.19
                                          239 San Bernardino, CA                3097.28  321179.47
                                          285 Troy, NY                          3070.66  324250.12
                                           33 Boise, ID                         2937.92  327188.04
                                          266 Stamford, CT                      2952.96     330141
                                          311 Yuma, AZ                           2896.3   333037.3
                                            3 Albany, NY                        2905.84  335943.14
                                          144 Las Vegas, NV                     2893.98  338837.12
                                          251 Schenectady, NY                   2883.23  341720.35
                                           45 Calgary, AB                       2828.13  344548.48
                                          296 West Palm Beach, FL               2889.69  347438.17
                                          146 Lethbridge, AB                    2761.59  350199.76
                                          299 White Plains, NY                  2761.87  352961.63
                                           44 Butte, MT                         2700.79  355662.42
                                          181 New York, NY                      2687.05  358349.48
                                          199 Phoenix, AZ                       2677.74  361027.22
                                          128 Jersey City, NJ                   2673.06  363700.28
                                          203 Pocatello, ID                      2655.1  366355.39
                                          177 Newark, NJ                        2648.53  369003.92
                                          118 Helena, MT                        2647.25  371651.17
                                           13 Atlantic City, NJ                 2646.38  374297.55
                                          161 Medicine Hat, AB                  2613.82  376911.37
                                           83 Elizabeth, NJ                     2604.16  379515.53
                                           93 Flagstaff, AZ                     2614.32  382129.85
                                          194 Paterson, NJ                      2619.56  384749.41
                                          187 Ogden, UT                         2611.96  387361.37
                                          283 Trenton, NJ                       2573.35  389934.72
                                          107 Great Falls, MT                   2575.55  392510.27
                                          198 Philadelphia, PA                  2550.72  395060.99
                                          237 Salt Lake City, UT                2538.22  397599.21
                                          289 Utica, NY                         2538.01  400137.22
                                          286 Tucson, AZ                        2578.23  402715.44
                                          191 Ottawa, ON                        2575.89  405291.33
                                          211 Provo, UT                          2487.2  407778.53
                                            6 Allentown, PA                     2499.13  410277.67
                                          102 Gallup, NM                        2324.19  412601.86
                                           29 Binghamtom, NY                    2312.96  414914.82
                                           27 Billings, MT                       2265.6  417180.42
                                          302 Wilmington, DE                    2314.81  419495.23
                                          248 Saskatoon, SK                     2317.41  421812.65
                                          247 Sarasota, FL                      2394.44  424207.09
                                           59 Churchill, MB                     2311.24  426518.32
                                          234 Saint Petersburg, FL              2279.52  428797.84
                                          173 Moose Jaw, SK                     2220.06   431017.9
                                          190 Orlando, FL                       2249.04  433266.94
                                          218 Regina, SK                        2208.47  435475.41
                                           72 Daytona Beach, FL                 2195.17  437670.58
                                          255 Sheridan, WY                      2090.58  439761.16
                                          184 Norfolk, VA                       2189.22  441950.37
                                          105 Grand Junction, CO                2234.59  444184.96
                                          301 Wilkes-Barre, PA                  2262.27  446447.23
                                           84 El Paso, TX                       2213.93  448661.17
                                          137 Kingston, ON                      2237.67  450898.84
                                            4 Albuquerque, NM                    2170.5  453069.33
                                          272 Syracuse, NY                      2178.26  455247.59
                                          246 Santa Fe, NM                      2120.23  457367.82
                                          217 Reading, PA                       2098.29  459466.11
                                           74 Denver, CO                        2008.13  461474.24
                                          208 Portsmouth, VA                    1992.18  463466.42
                                           57 Cheyenne, WY                      1993.01  465459.43
                                          141 Lancaster, PA                     1971.66  467431.09
                                           62 Colorado Springs, CO              1972.03  469403.12
                                          129 Johnstown, PA                     1972.05  471375.16
                                          212 Pueblo, CO                        1959.85  473335.01
                                           18 Baltimore, MD                     1935.73  475270.74
                                          216 Rapid City, SD                    1868.74  477139.48
                                          303 Wilmington, NC                    1875.13  479014.61
                                          167 Minot, ND                         1881.45  480896.06
                                          275 Tampa, FL                         1912.76  482808.82
                                           36 Brandon, MB                       1940.02  484748.84
                                          101 Gainesville, FL                   1855.41  486604.25
                                           31 Bismarck, ND                      1741.25  488345.51
                                          127 Jacksonville, FL                  1744.35  490089.86
                                          305 Winnipeg, MB                      1729.19  491819.04
                                           52 Charleston, SC                    1683.01  493502.06
                                          200 Pierre, SD                        1622.39  495124.45
                                          294 Washington, DC                    1654.69  496779.14
                                          156 Lubbock, TX                       1753.74  498532.87
                                           24 Belleville, ON                    1847.76  500380.63
                                          143 Laredo, TX                        1918.78  502299.41
                                          279 Timmins, ON                       1920.31  504219.72
                                           68 Corpus Christi, TX                1812.36  506032.08
                                          185 North Bay, ON                      1786.7  507818.78
                                          238 San Antonio, TX                   1763.41  509582.19
                                          223 Rochester, NY                     1726.57  511308.76
                                            7 Amarillo, TX                      1760.64   513069.4
                                          116 Harrisburg, PA                    1758.66  514828.06
                                            1 Abilene, TX                       1668.54   516496.6
                                          197 Peterborough, ON                  1685.89  518182.49
                                           16 Austin, TX                         1650.4  519832.89
                                          269 Sudbury, ON                       1627.33  521460.22
                                          121 Houston, TX                       1539.52  522999.73
                                           41 Buffalo, NY                       1455.86   524455.6
                                           77 Dodge City, KS                    1503.01   525958.6
                                          220 Richmond, VA                      1558.59  527517.19
                                           92 Fargo, ND                          1482.8  528999.99
                                          250 Savannah, GA                      1489.99  530489.98
                                          258 Sioux Falls, SD                   1337.75  531827.74
                                          215 Raleigh, NC                       1358.74  533186.48
                                           85 Enid, OK                          1330.04  534516.52
                                          182 Niagara Falls, ON                 1380.26  535896.78
                                          292 Waco, TX                          1483.03  537379.81
                                          282 Toronto, ON                       1483.47  538863.29
                                           97 Ft Worth, TX                       1449.6  540312.89
                                          227 Saint Catherines, ON               1447.6  541760.49
                                          103 Galveston, TX                     1444.61  543205.09
                                           42 Burlington, ONT                   1421.73  544626.82
                                           69 Dallas, TX                        1383.45  546010.27
                                          115 Hamilton, ON                      1368.85  547379.12
                                           23 Beaumont, TX                      1332.75  548711.87
                                          111 Guelph, ON                        1333.91  550045.78
                                          204 Port Arthur, TX                   1334.48  551380.26
                                          138 Kitchener, ON                     1324.27  552704.53
                                          188 Oklahoma City, OK                 1306.17   554010.7
                                           37 Brantford, ON                     1299.42  555310.11
                                          300 Wichita, KS                       1232.93  556543.05
                                           80 Durham, NC                         1279.4  557822.45
                                          236 Salina, KS                         1307.8  559130.25
                                          109 Greensboro, NC                    1245.96  560376.22
                                          257 Sioux City, IA                    1230.47  561606.68
                                           64 Columbia, SC                      1213.26  562819.94
                                          228 Saint Cloud, MN                   1208.61  564028.55
                                          274 Tallahassee, FL                   1248.21  565276.76
                                          278 Thunder Bay, ON                   1287.21  566563.97
                                          180 New Orleans, LA                   1273.63   567837.6
                                          249 Sault Ste Marie, ON               1205.19  569042.78
                                           20 Baton Rouge, LA                   1199.28  570242.06
                                           79 Duluth, MN                        1130.44  571372.51
                                          195 Pensacola, FL                     1179.96  572552.47
                                          270 Superior, WI                      1175.77  573728.24
                                           14 Augusta, GA                       1152.38  574880.62
                                          150 Lincoln, NE                       1134.43  576015.05
                                          221 Roanoke, VA                       1181.08  577196.13
                                          189 Omaha, NE                         1139.08  578335.21
                                          306 Winston-Salem, NC                 1141.42  579476.63
                                          166 Minneapolis, MN                   1088.91  580565.53
                                           54 Charlotte, NC                     1091.15  581656.69
                                          233 Saint Paul, MN                    1080.39  582737.08
                                          157 Macon, GA                         1061.49  583798.57
                                           81 Eau Claire, WI                     989.72  584788.28
                                           28 Biloxi, MS                        1012.28  585800.56
                                          152 London, ON                        1016.65  586817.21
                                          160 Marshall, TX                      1158.56  587975.77
                                           86 Erie, PA                          1188.43   589164.2
                                          287 Tulsa, OK                          1174.1   590338.3
                                          201 Pittsburgh, PA                    1144.29  591482.59
                                          256 Shreveport, LA                    1096.48  592579.08
                                          310 Youngstown, OH                    1081.83   593660.9
                                          277 Texarkana, TX                     1066.85  594727.75
                                          267 Steubenville, OH                  1043.65  595771.41
                                          281 Topeka, KS                        1043.45  596814.86
                                          297 Wheeling, WV                      1035.82  597850.68
                                           95 Ft Smith, AR                       998.79  598849.47
                                           61 Cleveland, OH                      974.07  599823.54
                                          176 Natchez, MS                        959.96  600783.49
                                           22 Bay City, MI                       980.29  601763.78
                                          112 Gulfport, MS                       982.13  602745.92
                                          108 Green Bay, WI                      980.65  603726.56
                                          168 Mobile, AL                         955.25  604681.82
                                          222 Rochester, MN                      970.35  605652.16
                                          260 Spartanburg, NC                    960.77  606612.93
                                          231 Saint Joseph, MO                   952.41  607565.34
                                           47 Canton, OH                         933.28  608498.62
                                          130 Joplin, MO                         943.13  609441.75
                                            2 Akron, OH                          939.34  610381.09
                                          133 Kansas City, KS                    915.85  611296.95
                                           53 Charleston, WV                     899.41  612196.36
                                          134 Kansas City, MO                    895.98  613092.34
                                          110 Greenville, SC                     891.55  613983.89
                                           75 Des Moines, IA                     904.35  614888.24
                                           10 Asheville, NC                      869.08  615757.32
                                          295 Waterloo, IA                       827.18   616584.5
                                           65 Columbus, GA                       859.51  617444.01
                                          253 Sheboygan, WI                      802.52  618246.52
                                          126 Jackson, MS                         809.5  619056.02
                                          226 Saginaw, MI                         880.9  619936.92
                                          151 Little Rock, AR                    831.32  620768.24
                                          304 Windsor, ON                        828.42  621596.66
                                          264 Springfield, MO                    795.38  622392.04
                                          312 Zanesville, OH                     802.13  623194.17
                                           63 Columbia, MO                       716.36  623910.53
                                           76 Detroit, MI                        682.93  624593.46
                                          170 Montgomery, AL                      724.3  625317.77
                                          158 Madison, WI                        770.17  626087.93
                                           12 Atlanta, GA                        731.47  626819.41
                                           49 Cedar Rapids, IA                   759.63  627579.04
                                          100 Gadsden, AL                        675.88  628254.92
                                           78 Dubuque, IA                        668.88   628923.8
                                           30 Birmingham, AL                     675.42  629599.22
                                           94 Flint, MI                          690.27  630289.49
                                          162 Memphis, TN                        698.85  630988.33
                                          142 Lansing, MI                           647  631635.33
                                          122 Huntsville, AL                     570.44  632205.78
                                          124 Iowa City, IA                      588.25  632794.02
                                          139 Knoxville, TN                      656.94  633450.96
                                          224 Rockford, IL                       563.81  634014.76
                                           56 Chattanooga, TN                    563.58  634578.34
                                          165 Milwaukee, WI                      580.71  635159.05
                                           11 Ashland, KY                        481.46  635640.51
                                          232 Saint Louis, MO                    522.45  636162.96
                                            9 Ann Arbor, MI                      513.15  636676.12
                                          192 Paducah, KY                        491.81  637167.92
                                          125 Jackson, MI                        459.78   637627.7
                                          175 Nashville, TN                      451.22  638078.92
                                          106 Grand Rapids, MI                   475.97  638554.89
                                           35 Bowling Green, KY                  416.17  638971.07
                                          214 Racine, WI                         406.98  639378.05
                                          147 Lexington, KY                      399.12  639777.17
                                          196 Peoria, IL                         399.56  640176.73
                                           66 Columbus, OH                       458.14  640634.87
                                          262 Springfield, IL                    459.25  641094.13
                                          280 Toledo, OH                         439.91  641534.03
                                           73 Decatur, IL                        393.78  641927.82
                                          265 Springfield, OH                    355.61  642283.42
                                           32 Bloomington, IL                    360.32  642643.75
                                          149 Lima, OH                           338.23  642981.98
                                           89 Evansville, IN                     305.64  643287.62
                                           21 Battle Creek, MI                   342.27  643629.89
                                          154 Louisville, KY                     283.85  643913.74
                                          135 Kenosha, WI                         331.4  644245.14
                                           60 Cincinnati, OH                     331.61  644576.75
                                           58 Chicago, IL                         288.4  644865.14
                                           71 Dayton, OH                         279.24  645144.39
                                          288 Urbana, IL                         278.52  645422.91
                                          114 Hamilton, OH                       256.66  645679.57
                                           51 Champaign, IL                      259.18  645938.75
                                          132 Kalamazoo, MI                      237.21  646175.96
                                          276 Terre Haute, IN                    232.44   646408.4
                                           96 Ft Wayne, IN                        195.3   646603.7
                                          104 Gary, IN                           156.52  646760.22
                                          174 Muncie, IN                         166.43  646926.65
                                          259 South Bend, IN                     118.99  647045.64
                                          123 Indianapolis, IN                   132.47  647178.11
                                          140 Lafayette, IN                       66.81  647244.92
                                            5 Alert, NT                         3369.01  650613.92

1252 rows selected.

Elapsed: 00:01:24.28

Summary of Results

Here we list the best solutions found for each root leg, i.e. those with PATH_RNK = 1. We do not know what the optima are.

Shortest Routes
===============
ROOT_LEG       TOT_DIST
------------ ----------
184 -> 208     55744.86
51 -> 288      56794.75

Longest Routes
==============
ROOT_LEG       TOT_DIST
------------ ----------
183 -> 230    649684.75
5 -> 148      650614.77

Execution Plan for Shortest Routes, USCA312

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                                             | Name        | Starts | E-Rows | A-Rows |   A-Time   | Buffers | Reads  | Writes |  OMem |  1Mem | Used-Mem |
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                                      |             |      1 |        |   1252 |00:01:24.88 |      10M|    113K|  10654 |       |       |          |
|   1 |  WINDOW SORT                                          |             |      1 |     10 |   1252 |00:01:24.88 |      10M|    113K|  10654 |   267K|   267K|  237K (0)|
|   2 |   NESTED LOOPS OUTER                                  |             |      1 |     10 |   1252 |00:01:24.88 |      10M|    113K|  10654 |       |       |          |
|   3 |    MERGE JOIN                                         |             |      1 |     10 |   1252 |00:01:24.87 |      10M|    113K|  10654 |       |       |          |
|   4 |     TABLE ACCESS BY INDEX ROWID                       | TOWNS       |      1 |      5 |    312 |00:00:00.01 |     205 |      0 |      0 |       |       |          |
|   5 |      INDEX FULL SCAN                                  | SYS_C008004 |      1 |      5 |    312 |00:00:00.01 |       1 |      0 |      0 |       |       |          |
|*  6 |     SORT JOIN                                         |             |    312 |     10 |   1252 |00:01:24.87 |      10M|    113K|  10654 |   133K|   133K|  118K (0)|
|   7 |      VIEW                                             |             |      1 |     10 |   1252 |00:01:24.86 |      10M|    113K|  10654 |       |       |          |
|   8 |       WINDOW SORT                                     |             |      1 |     10 |   1252 |00:01:24.86 |      10M|    113K|  10654 |  1895K|   658K| 1684K (0)|
|   9 |        MERGE JOIN CARTESIAN                           |             |      1 |     10 |   1252 |00:01:24.85 |      10M|    113K|  10654 |       |       |          |
|  10 |         VIEW                                          |             |      1 |      1 |    313 |00:00:00.01 |       1 |      0 |      0 |       |       |          |
|  11 |          CONNECT BY WITHOUT FILTERING                 |             |      1 |        |    313 |00:00:00.01 |       1 |      0 |      0 |       |       |          |
|  12 |           VIEW                                        |             |      1 |      1 |      1 |00:00:00.01 |       1 |      0 |      0 |       |       |          |
|  13 |            SORT AGGREGATE                             |             |      1 |      1 |      1 |00:00:00.01 |       1 |      0 |      0 |       |       |          |
|  14 |             INDEX FULL SCAN                           | SYS_C008004 |      1 |      5 |    312 |00:00:00.01 |       1 |      0 |      0 |       |       |          |
|  15 |         BUFFER SORT                                   |             |    313 |     10 |   1252 |00:01:24.85 |      10M|    113K|  10654 |  9216 |  9216 | 8192  (0)|
|* 16 |          VIEW                                         |             |      1 |     10 |      4 |00:01:24.85 |      10M|    113K|  10654 |       |       |          |
|* 17 |           WINDOW SORT PUSHED RANK                     |             |      1 |     10 |      4 |00:01:24.85 |      10M|    113K|  10654 |  9216 |  9216 | 8192  (0)|
|  18 |            NESTED LOOPS                               |             |      1 |        |      4 |00:00:34.80 |      10M|    113K|  10654 |       |       |          |
|  19 |             NESTED LOOPS                              |             |      1 |     10 |      4 |00:00:34.80 |      10M|    113K|  10654 |       |       |          |
|* 20 |              VIEW                                     |             |      1 |     12 |      4 |00:00:34.80 |      10M|    113K|  10654 |       |       |          |
|  21 |               UNION ALL (RECURSIVE WITH) BREADTH FIRST|             |      1 |        |    192K|00:00:04.53 |      10M|    113K|  10654 |       |       |          |
|* 22 |                VIEW                                   |             |      1 |     10 |      2 |00:00:00.10 |     693 |      1 |      0 |       |       |          |
|* 23 |                 WINDOW SORT PUSHED RANK               |             |      1 |     10 |      3 |00:00:00.10 |     693 |      1 |      0 |  2048 |  2048 | 2048  (0)|
|  24 |                  WINDOW BUFFER                        |             |      1 |     10 |  48516 |00:00:00.08 |     693 |      1 |      0 |  3100K|   779K| 2755K (0)|
|  25 |                   TABLE ACCESS BY INDEX ROWID         | DISTANCES   |      1 |     10 |  48516 |00:00:00.04 |     693 |      1 |      0 |       |       |          |
|* 26 |                    INDEX FULL SCAN                    | DISTANCE_PK |      1 |     10 |  48516 |00:00:00.02 |     212 |      0 |      0 |       |       |          |
|  27 |                WINDOW SORT                            |             |    311 |      2 |    192K|00:00:04.40 |    5664 |      1 |      0 |   619K|   472K|  550K (0)|
|  28 |                 NESTED LOOPS                          |             |    311 |        |    192K|00:00:05.39 |    5664 |      1 |      0 |       |       |          |
|  29 |                  NESTED LOOPS                         |             |    311 |      2 |    192K|00:00:05.08 |    2392 |      0 |      0 |       |       |          |
|  30 |                   RECURSIVE WITH PUMP                 |             |    311 |        |   1242 |00:00:00.01 |       0 |      0 |      0 |       |       |          |
|* 31 |                   INDEX RANGE SCAN                    | DISTANCE_PK |   1242 |      1 |    192K|00:00:06.49 |    2392 |      0 |      0 |       |       |          |
|  32 |                  TABLE ACCESS BY INDEX ROWID          | DISTANCES   |    192K|      1 |    192K|00:00:00.15 |    3272 |      1 |      0 |       |       |          |
|* 33 |              INDEX UNIQUE SCAN                        | DISTANCE_PK |      4 |      1 |      4 |00:00:00.01 |       6 |      0 |      0 |       |       |          |
|  34 |             TABLE ACCESS BY INDEX ROWID               | DISTANCES   |      4 |      1 |      4 |00:00:00.01 |       4 |      0 |      0 |       |       |          |
|  35 |    TABLE ACCESS BY INDEX ROWID                        | DISTANCES   |   1252 |      1 |   1248 |00:00:00.01 |    2498 |      0 |      0 |       |       |          |
|* 36 |     INDEX UNIQUE SCAN                                 | DISTANCE_PK |   1252 |      1 |   1248 |00:00:00.01 |    1250 |      0 |      0 |       |       |          |
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   6 - access("TWN"."ID"="TOP"."TOWN_ID")
       filter("TWN"."ID"="TOP"."TOWN_ID")
  16 - filter("CIRCUITS"."PATH_RNK"<=:KEEP_NUM)
  17 - filter(ROW_NUMBER() OVER ( PARTITION BY "R"."ROOT_LEG" ORDER BY :SIGN*("R"."TOT_PRICE"+"D"."DST"))<=:KEEP_NUM)
  20 - filter(("R"."LEV"="R"."N_TOWNS" AND "R"."PATH_RNK"<=:KEEP_NUM))
  22 - filter("D"."RNK_BY_DST"<=:KEEP_NUM_ROOT)
  23 - filter(ROW_NUMBER() OVER ( ORDER BY :SIGN*"DST")<=:KEEP_NUM_ROOT) 26 - filter("B">"A")
  31 - access("D"."A"="R"."NXT_ID")
       filter("R"."PATH" NOT LIKE '%|'||LPAD(TO_CHAR("D"."B"),3,'0')||'%')
  33 - access("D"."A"="R"."NXT_ID" AND "D"."B"="R"."ROOT")
  36 - access("DST"."A"="TOP"."TOWN_ID_PRIOR" AND "DST"."B"="TOP"."TOWN_ID")

Notes

  • In the closed version of TSP that we have considered here, the starting point does not essentially affect the set of possible solutions; however, it may affect the solutions actually obtained by an approximate algorithm; partitioning by a set of root legs is designed to improve the quality of solutions obtained
  • I found that the query uses increasing amounts of temp tablespace as the keep values are increased for the larger problem; in my previous article, on a knapsack problem, I included a PL/SQL solution that had the flexibility to discard all but the best solutions as it went, thus keeping space usage to a minimum; it also had the flexibility of the conventional 'branch and bound' algorithms to retain the best solution values globally and close off paths that could not beat them. This is difficult to do in SQL, but against that, the SQL is much simpler

Conclusions

Following my earlier two articles on related subjects, we have again seen that the recursive capabilities of Oracle's SQL from v11.2 can provide surprisingly simple approximate solutions to 'hard' combinatorial problems in reasonable execution times.

20 February 2016: Added attachment with the input data files, DDL and raw results:

TSP Files: input data files, DDL and raw results

The new (November 2017) GitHub project also includes scripts and will be easier to install: Brendan's repo for interesting SQL