How to speed up counting and filtering on table with a lot of columns and filter conditions?

Question

I have TABLE_A in my database that has a lot of columns.

Let's say there are 100 columns: COLUMN_1, COLUMN_2, COLUMN_3, .. COLUMN_100

There are so many columns not because of denormalized design, but because each row represent Entity with a lot of properties (in this example - with 99 properties, first column is just an id)

My Application should do the following tasks:

• Receive a set of filter conditions from the user
• Execute a query in the database that filters the data on given conditions and then should count the result rows

There are no limits on the number of filter conditions:

• there may be no filter conditions
• there may be filter conditions on every column of the table
• there may be filter conditions on some columns of the table (for example on 50 columns out of all)

So below is an example query that my application executes:

SELECT 
    COUNT(*)
FROM 
    TABLE_A 
WHERE 
    COLUMN_1 = 'test'
    AND COLUMN_2 != 'q'
    AND COLUMN_45 > 5
    AND COLUMN_45 < 511
    AND COLUMN_92 LIKE '%ddd%'
    AND COLUMN_98 > 1000

TABLE_A doesn't have any indexes - each column can be used for filtering and there are no sets of queries that are run much more frequently than the rest.

I also don't use any kind of cache on any level: insert and update operations happen not very often but more often than at least 2 query with the same filter conditions occur.

So in case of every query the sequential search is executed. It was not a problem earlier, but now the run-times of the query became unacceptable (number of rows in the table increased a lot).

So..

Is there any solution on how to speed up the execution of the task?

Any suggestions would be appreciated - I can change anything except one thing - I should use SQL. Currently I use PostgreSQL, but I would change DBMS if it will help.

Answer 1

I feel your pain, nik. We have a similar use case here, and have been struggling through as best we can with a metric ton of indexes.

I know you said you need to stick with SQL, but I really think you might want to consider a column store (https://en.wikipedia.org/wiki/Column-oriented_DBMS), perhaps one SQL-like enough for you to still find workable.

MariaDB seems to be embracing this now too: https://mariadb.com/resources/blog/why-columnstore-important

Answer 2

there are no sets of queries that are run much more frequently than the rest.

That removes the quick solution of "index the most commonly touched columns, and let the rest still scan" so the only other quick solution is an index on each of the columns. This means at least part of almost all the queries is indexed, only those with no filter or all non-sargable filters will still need to perform a full scan. The query planner will hopefully pick the most selective index option each time reducing the number of rows than need everything else to be checked. But of course this will use a lot of space and may increase your RAM needs as the indexes become part of the common working set that you'd like to keep in active memory as much as possible.

As Kevin suggests, a database that offers column oriented storage is likely to help here. MS SQL Server offers such table types in later versions though if your DB is larger than 10Gb or you need to use more than 2Gb of RAM to be efficient (the limits of the free "express" edition) that could be expensive.

Other than that, this may be a circumstance where the EAV pattern isn't a completely terrible idea, but it probably still is. In this model your wide table becomes something like id:int, property_name:string, int_value:int, str_value:string with indexes on the two value columns, though note that unless a lot of your columns are generally sparse (are often NULL) these two value indexes are not going to be much smaller than the 99 indexes covering your wide table's column set. Your queries will need to change drastically, unless you replicate the original table as view and hope to [preferred deity] that the database's query planner can do something smart with that.