I have quite a large table (20 million rows) that has a columnstore index.
When I try to delete portion of data from it, the delete is slow and takes several minutes.
What would be an option to speed up the delete in columnstore table? Would adding regular indexes help speed up the delete? I know in columnstore table columnstore indexes are already physically stored in columns so I am not sure adding more indexes would help.
First, 20 million records is nothing. You don't need columnstore for that few data; ordinary indices would do just fine.
Second, columnar storage, in MS SQL Server anyway, is meant to be read-only. This is by design. You might get some improvement with deletion by partitioning your data and deleting it one section at a time, but partitioning 20M records is a sure overkill.
Worse yet, deletion creates fragmentation within columnstore groups because, unlike rowstore, free space isn't reclaimed by the database engine until you run rebuild / reorganize for that index (which one to choose depends on the SQL Server version; check ALTER INDEX for details).
In short, it makes sense to consider columnstore only when the rowstore storage doesn't cut it anymore, and this is clearly not your case (not yet, at least).