When generating combinations using a CTE, is there a way to use an index to group the elements of each combination?

Question

I have a project that involves combining a variety of things into their possible combinations. This includes permutations, combinations, with and without repetition, and some more exotic ways of arriving at sets of elements combined in different ways. So far I have succeeded at generating such combinations using the following method:

1. Recursively add elements to combinations using a CTE.
2. Track the path through which each element was added using a string.
3. Constitute the set of elements that belong together using that path string.

This method reliably produces correct results for all of the above. However, I have found step (3) is resilient to using indexes because it uses LIKE. Some of the combinations number in the millions and without indexing step (3) can take hours to complete.

Other considerations for this question

I'm currently using SQLite (as opposed to a database server) because I am familiar with it and this project has no need for client/server separation, but does benefit from portability of an in-process database. I am also familiar with Microsoft SQL Server, but would like to avoid server installation as a prerequisite for this project.

I'm aware of the full-text search capabilities of the FTSx SQLite extensions, and I suppose a full-text search table might overcome the inability for LIKE to use an index. I'm not sure how well that would work for this purpose, though, and I'm avoiding that avenue until I can determine that a simpler native approach is not available.

Example Query

Consider the table of values

| grp | value |
| --- | ----  |
| a   | 1     |
| a   | 2     |
| b   | 9     |
| b   | 3     |
| b   | 2     |

which results in the following table of all possible combinations partitioned by grp, with repetition:

| grp | path  | value |
| --- | ----  | ----- |
| a   | 1.1   |     1 |
| a   | 1.1   |     1 |
| a   | 2.1   |     2 |
| a   | 2.1   |     1 |
| a   | 2.2   |     2 |
| a   | 2.2   |     2 |
| b   | 2.2.2 |     2 |
| b   | 2.2.2 |     2 |
| b   | 2.2.2 |     2 |
| b   | 3.2.2 |     3 |
| b   | 3.2.2 |     2 |
| b   | 3.2.2 |     2 |
| b   | 3.3.2 |     3 |
| b   | 3.3.2 |     3 |
| b   | 3.3.2 |     2 |
| b   | 3.3.3 |     3 |
| b   | 3.3.3 |     3 |
| b   | 3.3.3 |     3 |
| b   | 9.2.2 |     9 |
| b   | 9.2.2 |     2 |
| b   | 9.2.2 |     2 |
| b   | 9.3.2 |     9 |
| b   | 9.3.2 |     3 |
| b   | 9.3.2 |     2 |
| b   | 9.3.3 |     9 |
| b   | 9.3.3 |     3 |
| b   | 9.3.3 |     3 |
| b   | 9.9.2 |     9 |
| b   | 9.9.2 |     9 |
| b   | 9.9.2 |     2 |
| b   | 9.9.3 |     9 |
| b   | 9.9.3 |     9 |
| b   | 9.9.3 |     3 |
| b   | 9.9.9 |     9 |
| b   | 9.9.9 |     9 |
| b   | 9.9.9 |     9 |

Here is a SQL Fiddle demonstrating this work being performed by the following query:

WITH
elements
    (grp,value) AS ( VALUES
    ('a',1    ),
    ('a',2    ),
    ('b',9    ),
    ('b',3    ),
    ('b',2    )
),
base AS
(
    SELECT
        grp  ,
        value,
        COUNT(*) OVER (
            PARTITION BY grp) AS grp_count
    FROM
        elements
),
combinations AS
(
    SELECT
                       grp            ,
                       value          ,
        grp_count   AS partition_index,
        value || '' AS path
    FROM
        base

    UNION

    SELECT
                          prior.grp            ,
                        current.value          ,
        partition_index - 1  AS partition_index,
        path          ||
        '.'           ||
        current.value        AS path
    FROM
        combinations AS prior
    JOIN
        base AS current
        ON
        prior.grp IS current.grp
    WHERE
        partition_index >  1             AND
        prior.value     >= current.value
),
combination_sets AS
(
    SELECT
        grp,
        path
    FROM
        combinations
    WHERE
        partition_index IS 1
)
SELECT
    combination_sets.grp,
    combination_sets.path,
    value
FROM
    combination_sets
JOIN
    combinations
    ON
    combination_sets.grp  IS   combinations.grp           AND
    combination_sets.path LIKE (combinations.path || '%')
ORDER BY
    combination_sets.grp,
    combination_sets.path

Query plan

The query plan for the above is

QUERY PLAN
|--MATERIALIZE 8
| |--SETUP
| | |--CO-ROUTINE 6
| | | |--CO-ROUTINE 11
| | | | |--CO-ROUTINE 5
| | | | | `--SCAN 5 CONSTANT ROWS
| | | | |--SCAN SUBQUERY 5
| | | | `--USE TEMP B-TREE FOR ORDER BY
| | | `--SCAN SUBQUERY 11
| | `--SCAN SUBQUERY 6
| `--RECURSIVE STEP
| |--MATERIALIZE 6
| | |--CO-ROUTINE 12
| | | |--CO-ROUTINE 5
| | | | `--SCAN 5 CONSTANT ROWS
| | | |--SCAN SUBQUERY 5
| | | `--USE TEMP B-TREE FOR ORDER BY
| | `--SCAN SUBQUERY 12
| |--SCAN SUBQUERY 6 AS current
| `--SCAN TABLE combinations AS prior
|--MATERIALIZE 8
| |--SETUP
| | |--CO-ROUTINE 6
| | | |--CO-ROUTINE 13
| | | | |--CO-ROUTINE 5
| | | | | `--SCAN 5 CONSTANT ROWS
| | | | |--SCAN SUBQUERY 5
| | | | `--USE TEMP B-TREE FOR ORDER BY
| | | `--SCAN SUBQUERY 13
| | `--SCAN SUBQUERY 6
| `--RECURSIVE STEP
| |--MATERIALIZE 6
| | |--CO-ROUTINE 14
| | | |--CO-ROUTINE 5
| | | | `--SCAN 5 CONSTANT ROWS
| | | |--SCAN SUBQUERY 5
| | | `--USE TEMP B-TREE FOR ORDER BY
| | `--SCAN SUBQUERY 14
| |--SCAN SUBQUERY 6 AS current
| `--SCAN TABLE combinations AS prior
|--SCAN SUBQUERY 8
|--SEARCH SUBQUERY 8 USING AUTOMATIC COVERING INDEX (grp=?)
`--USE TEMP B-TREE FOR ORDER BY

with the line

|--SEARCH SUBQUERY 8 USING AUTOMATIC COVERING INDEX (grp=?)

indicating, as I understand it, that the line combination_sets.path LIKE (combinations.path || '%') does not use an index. As much would be expected from the LIKE Optimization documentation which specifies that, in order for LIKE to use an index, the following criteria, among others, must be met:

1. The right-hand side of the LIKE or GLOB must be either a string literal or a parameter bound to a string literal that does not begin with a wildcard character.

The right-hand side is not, and can't easily be, such a string literal. So I cannot expect the LIKE Optimization to happen here.

Attempting string comparison operators

This answer on the topic of LIKE and indexes suggests that if a LIKE query can be correctly recast to use inequality operators instead, then indexing will be used.

The method used in the above example query affords substantial freedom for contriving the path string (or strings, for that matter). I have experimented with a variety of ways of formatting such strings looking for a way to use string comparison to group the combinations instead of using LIKE. The closest I achieved was using : and . as delimiters for upper and lower bounds a la

| path  | lower_bound | upper_bound |
| 1.2.3 | 1.2.3.      | 1:2:3:      |

However, that still resulted in cases that were incorrect.

Some other method?

I suppose there might be other methods for reconstituting sets of combinations generated with a recursive CTE. I don't know what that would look like, though.

Is this possible?

This all leads me to the following questions: When generating combinations using a CTE,

1. can a path string be used with an index?
2. is there any way to use an index to group the elements of each combination?

Answer 1

I am not sure what are you trying to do. If you generate a "path" like this through CTE, what is the point of searching through it??? If you generate such path from a real data in a real table - then most likely, you can store the path in the same (or additional) table with a proper index.

In both scenario the questions you are asking are purely academical and have a semi-strange answer:

1. can a path string be used with an index?

Yes, it can. Just store it in the field, add index on that field. It would be used, and you already described how.

2. is there any way to use an index to group the elements of each combination?

That depends on how you define the group. Do you use a substring() to extract part of the path? Or... what???

It could be beneficial to your real business task to consider creating "path" as a bunch of columns. Something like

create table t (
   data,
   top_level,
   second_level,
   ... etc
   tenth_level
);

You, of course, would have to limit how deep the path can be, but it would be very easy to work with.

Another point you should look at, is version of your sqlite engine. The one used by sqlfiddle is kind of old. The more modern (3.37) gives a completely different plan:

QUERY PLAN
|--MATERIALIZE combinations
|  |--SETUP
|  |  |--MATERIALIZE base
|  |  |  |--CO-ROUTINE SUBQUERY 11
|  |  |  |  |--MATERIALIZE elements
|  |  |  |  |  `--SCAN 5 CONSTANT ROWS
|  |  |  |  |--SCAN elements
|  |  |  |  `--USE TEMP B-TREE FOR ORDER BY
|  |  |  `--SCAN SUBQUERY 11
|  |  `--SCAN base
|  `--RECURSIVE STEP
|     |--SCAN prior
|     `--SEARCH current USING AUTOMATIC COVERING INDEX (grp=?)
|--SCAN combinations
|--SEARCH combinations USING AUTOMATIC PARTIAL COVERING INDEX (partition_index=? AND grp=?)
`--USE TEMP B-TREE FOR ORDER BY

As you can see, it does an automatic materialization of CTEs and even create indexes for it.