[Bug 12071] New: MSI SQL joins on tables with many rows are extremely slow

http://bugs.winehq.org/show_bug.cgi?id=12071

Summary: MSI SQL joins on tables with many rows are extremely
                    slow
           Product: Wine
           Version: 0.9.57.
          Platform: PC
        OS/Version: Linux
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: msi
        AssignedTo: [e-mail]
        ReportedBy: [e-mail]
                CC: [e-mail]

With the current implementation of MSI SQL joins, we perform a Cartesian
product on the tables joined together.  In the case where there is no WHERE
clause, this is the correct output, but if there is a WHERE clause, we still
perform the Cartesian product and then filter on the WHERE clause.  Though it's
uncommon, there are a few installers (Visual Studio, Nero Express 7) that join
tables with thousands of rows.  For example, say we have tables A, B, and C
s.t.

colA   colB   colC
-----   -----   -----
1       1       1
2       2       2
...     ...     ...
1000   1000    1000

and we have the query

SELECT * FROM A, B, C WHERE `colA`=1 AND `colB`=1 AND `colC`=1

then the current implementation will create a new table with those columns
containing 1000*1000*1000=1 billion rows.  Then we check each of the 1 billion
rows for any matches.  There are several algorithms for optimizing joins:

http://en.wikipedia.org/wiki/Join_(SQL)#Join_algorithms

The solution I'll be working on is the merge join.  This solution parses the
WHERE clause,  starting with the two tables that the columns of the clause
belong to (colA -> A, colB -> B, etc) and joins those together, making sure to
eliminate rows based on the WHERE clause.  Then the next table in the clause is
merged into the previously created table, eliminating rows.  This continues
until there are no tables left.  One optimization of this solution is to start
with parts of the WHERE clause that compare against literals.  For example, the
query:

SELECT * FROM A, B, C WHERE `colA` = `colB` AND `colB` = 1 AND `colC` = 1

We'd start with "`colB` = 1" since the comparison is against a literal.  We
perform 1000 comparisons on the rows of table B (count = 1000).  The resulting
table is:

colB
----
1

then we do the same for table C (count = 1000), and the merged table is:

colB   colC
----   ----
1      1

next we merge this table with table A:

colA   colB   colC
----   ----   ----
1      1      1
2      1      1
...    ...    ...
1000   1      1

and we search through this table for the condition `colA` = `colB` (count =
1000).  So we've reduced billions of comparisons to 3000.

Unfortunately, the way our SQL engine is implemented, this will not be an easy
task.

[Bug 12071] MSI SQL joins on tables with many rows are extremely slow

http://bugs.winehq.org/show_bug.cgi?id=12071

--- Comment #1 from Austin English   2008-10-23 15:37:37 ---
Do your recent database patches help this at all James?

[Bug 12071] MSI SQL joins on tables with many rows are extremely slow

http://bugs.winehq.org/show_bug.cgi?id=12071

--- Comment #2 from James Hawkins   2008-10-23 15:38:54 ---
Nope.  I'll mark it fixed when it's fixed.

[Bug 12071] MSI SQL joins on tables with many rows are extremely slow

http://bugs.winehq.org/show_bug.cgi?id=12071

Austin English  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |[e-mail]

[Bug 12071] MSI SQL joins on tables with many rows are extremely slow

http://bugs.winehq.org/show_bug.cgi?id=12071

--- Comment #3 from Austin English   2009-10-29 15:25:23 ---
Is this still an issue in current (1.1.32 or newer) wine?

[Bug 12071] MSI SQL joins on tables with many rows are extremely slow

http://bugs.winehq.org/show_bug.cgi?id=12071

James Hawkins  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|[e-mail]           |[e-mail]

--- Comment #4 from James Hawkins   2009-10-29 15:27:18 ---
See comment #2.  I'm not working on it anymore, but it would be very obvious if
the fix for this went in.

[Bug 12071] MSI SQL joins on tables with many rows are extremely slow

http://bugs.winehq.org/show_bug.cgi?id=12071

Austin English  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
             Blocks|                            |14168

[Bug 12071] MSI SQL joins on tables with many rows are extremely slow

http://bugs.winehq.org/show_bug.cgi?id=12071

Austin English  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |Installer

[Bug 12071] MSI SQL joins on tables with many rows are extremely slow

http://bugs.winehq.org/show_bug.cgi?id=12071

A Wine user  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |[e-mail]

[Bug 12071] MSI SQL joins on tables with many rows are extremely slow ("Nero 7 essentials" installer)

http://bugs.winehq.org/show_bug.cgi?id=12071

Anastasius Focht  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |[e-mail]
            Summary|MSI SQL joins on tables     |MSI SQL joins on tables
                   |with many rows are          |with many rows are
                   |extremely slow              |extremely slow ("Nero 7
                   |                            |essentials" installer)

--- Comment #5 from Anastasius Focht  2011-06-27 14:16:09 CDT ---
Hello,

updating bug status, still present.
"Nero 7 essentials" installer pegs the cpu ~45 mins on table joins _0o_

(winedbg bt while running)

--- snip ---
Backtracing for thread 0023 in process 001d (C:\windows\system32\msiexec.exe):
Backtrace:
=>0 0x7a7b7041 JOIN_fetch_int+0x63(view=0x1f4aa8, row=0x60083c45, col=0x9,
val=0x7fe48c) [/opt/projects/wine/wine-git/dlls/msi/join.c:73] in msi
(0x007fe474)
  1 0x7a7f3a11 STRING_evaluate+0x60(wv=0x1b5a00, row=0x60083c45, expr=0x1bea40,
record=(nil)) [/opt/projects/wine/wine-git/dlls/msi/where.c:276] in msi
(0x007fe4a4)
  2 0x7a7f3b10 STRCMP_Evaluate+0x4e(wv=0x1b5a00, row=0x60083c45, cond=0x1b5780,
val=0x7fe558, record=(nil)) [/opt/projects/wine/wine-git/dlls/msi/where.c:301]
in msi (0x007fe4d4)
  3 0x7a7f3df1 WHERE_evaluate+0x231(wv=0x1b5a00, row=0x60083c45, cond=0x1b5780,
val=0x7fe558, record=(nil)) [/opt/projects/wine/wine-git/dlls/msi/where.c:365]
in msi (0x007fe524)
  4 0x7a7f3ced WHERE_evaluate+0x12d(wv=0x1b5a00, row=0x60083c45, cond=0x1b58d8,
val=0x7fe5a8, record=(nil)) [/opt/projects/wine/wine-git/dlls/msi/where.c:348]
in msi (0x007fe574)
  5 0x7a7f3ced WHERE_evaluate+0x12d(wv=0x1b5a00, row=0x60083c45, cond=0x1b59e8,
val=0x7fe5fc, record=(nil)) [/opt/projects/wine/wine-git/dlls/msi/where.c:348]
in msi (0x007fe5c4)
  6 0x7a7f3fe5 WHERE_execute+0x16c(view=0x1b5a00, record=(nil))
[/opt/projects/wine/wine-git/dlls/msi/where.c:458] in msi (0x007fe624)
  7 0x7a7dd8d2 SELECT_execute+0x9d(view=0x1b5a40, record=(nil))
[/opt/projects/wine/wine-git/dlls/msi/select.c:181] in msi (0x007fe664)
  8 0x7a7c73b3 MSI_ViewExecute+0xb4(query=0x1f4640, rec=(nil))
[/opt/projects/wine/wine-git/dlls/msi/msiquery.c:462] in msi (0x007fe6a4)
  9 0x7a7c7494 MsiViewExecute+0xda(hView=0xb, hRec=0)
[/opt/projects/wine/wine-git/dlls/msi/msiquery.c:488] in msi (0x007fe6f4)
  10 0x1006b26f in msi4d5d.tmp (+0x6b26e) (0x007fe788)
  11 0x00000100 (0x100e9ce8)
  12 0x49534d43 (0x1006a900)
--- snip ---

$ wine --version
wine-1.3.23

Regards

[Bug 12071] MSI SQL joins on tables with many rows are extremely slow ("Nero 7 essentials", "NI Multisim 11.x" installer)

http://bugs.winehq.org/show_bug.cgi?id=12071

Anastasius Focht  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|MSI SQL joins on tables     |MSI SQL joins on tables
                   |with many rows are          |with many rows are
                   |extremely slow ("Nero 7     |extremely slow ("Nero 7
                   |essentials" installer)      |essentials", "NI Multisim
                   |                            |11.x" installer)

--- Comment #6 from Anastasius Focht  2011-07-24 13:38:48 CDT ---
Hello,

adding another app, "NI Multisim 11.x" to list.
The installer pegs the cpu awfully long on table joins.

(winedbg bt of relevant threads while running)

--- snip ---
...
Backtracing for thread 008c in process 0024
(Z:\home\focht\Downloads\11.0.1\setup.exe):
Backtrace:
=>0 0x2fefbe64 JOIN_fetch_int+0x90(view=0x24896a8, row=0x7f462ac, col=0xe,
val=0x176e068) [/opt/projects/wine/wine-git/dlls/msi/join.c:73] in msi
(0x0176e050)
  1 0x2ff385c4 STRING_evaluate+0x60(wv=0x2489b48, row=0x7f462ac,
expr=0x2489af0, record=(nil))
[/opt/projects/wine/wine-git/dlls/msi/where.c:276] in msi (0x0176e080)
  2 0x2ff386c4 STRCMP_Evaluate+0x4e(wv=0x2489b48, row=0x7f462ac,
cond=0x2489b10, val=0x176e130, record=(nil))
[/opt/projects/wine/wine-git/dlls/msi/where.c:301] in msi (0x0176e0b0)
  3 0x2ff389a5 WHERE_evaluate+0x231(wv=0x2489b48, row=0x7f462ac,
cond=0x2489b10, val=0x176e130, record=(nil))
[/opt/projects/wine/wine-git/dlls/msi/where.c:365] in msi (0x0176e100)
  4 0x2ff388dc WHERE_evaluate+0x168(wv=0x2489b48, row=0x7f462ac,
cond=0x2489b30, val=0x176e188, record=(nil))
[/opt/projects/wine/wine-git/dlls/msi/where.c:351] in msi (0x0176e150)
  5 0x2ff38b98 WHERE_execute+0x16a(view=0x2489b48, record=(nil))
[/opt/projects/wine/wine-git/dlls/msi/where.c:458] in msi (0x0176e1b0)
  6 0x2ff226d2 SELECT_execute+0x9d(view=0x2489b88, record=(nil))
[/opt/projects/wine/wine-git/dlls/msi/select.c:181] in msi (0x0176e1f0)
  7 0x2ff0c3e1 MSI_ViewExecute+0xb4(query=0x27b86c8, rec=(nil))
[/opt/projects/wine/wine-git/dlls/msi/msiquery.c:462] in msi (0x0176e230)
  8 0x2ff0c4c2 MsiViewExecute+0xda(hView=0x6, hRec=0)
[/opt/projects/wine/wine-git/dlls/msi/msiquery.c:488] in msi (0x0176e280)

Backtracing for thread 003e in process 0024
(Z:\home\focht\Downloads\11.0.1\setup.exe):
Backtrace:
=>0 0x68000830 GLIBC_2+0x830() in ld-linux.so.2 (0x0186dd50)
  1 0x68359b8e NTDLL_wait_for_multiple_objects+0x1e5(count=0x1,
handles=0x186dff8, flags=0x4, timeout=(nil), signal_object=0x0(nil))
[/opt/projects/wine/wine-git/dlls/ntdll/sync.c:1124] in ntdll (0x0186df70)
  2 0x68359c72 NtWaitForMultipleObjects+0x67(count=0x1, handles=0x186dff8,
wait_all=0, alertable=0, timeout=(nil))
[/opt/projects/wine/wine-git/dlls/ntdll/sync.c:1162] in ntdll (0x0186dfc0)
  3 0x7b86f03a WaitForMultipleObjectsEx+0x137(count=0x1, handles=0x186e148,
wait_all=0, timeout=0xffffffff, alertable=0)
[/opt/projects/wine/wine-git/dlls/kernel32/sync.c:188] in kernel32 (0x0186e110)
  4 0x7b86ee6f WaitForSingleObject+0x3b(handle=0x828, timeout=0xffffffff)
[/opt/projects/wine/wine-git/dlls/kernel32/sync.c:128] in kernel32 (0x0186e140)
  5 0x2feec60a msi_dialog_check_messages+0x45(handle=0x828)
[/opt/projects/wine/wine-git/dlls/msi/dialog.c:3802] in msi (0x0186e180)
  6 0x2fed9a44 wait_thread_handle+0x94(info=0x2489140)
[/opt/projects/wine/wine-git/dlls/msi/custom.c:414] in msi (0x0186e1d0)
  7 0x2fedaa29 HANDLE_CustomType1+0xe3(package=0x235e218,
source="NIMetaUtilsCA.91D5760B_F9E8_4332_BFB1_38A4CB799A3E",
target="SaveDirsToReg", type=0x1,
action="NIPathsSavePaths2.91D5760B_F9E8_4332_BFB1_38A4CB799A3E")
[/opt/projects/wine/wine-git/dlls/msi/custom.c:766] in msi (0x0186e220)
  8 0x2fedc496 ACTION_CustomAction+0x575(package=0x235e218,
action="NIPathsSavePaths2.91D5760B_F9E8_4332_BFB1_38A4CB799A3E",
script=0xffffffff, execute=0x1)
[/opt/projects/wine/wine-git/dlls/msi/custom.c:1295] in msi (0x0186e2d0)
  9 0x2feb57e4 ACTION_HandleCustomAction+0x2c(package=0x235e218,
action="NIPathsSavePaths2.91D5760B_F9E8_4332_BFB1_38A4CB799A3E", rc=0x186e330,
script=0xffffffff, force=0x1)
[/opt/projects/wine/wine-git/dlls/msi/action.c:659] in msi (0x0186e300)
  10 0x2fec7135 ACTION_PerformAction+0xba(package=0x235e218,
action="NIPathsSavePaths2.91D5760B_F9E8_4332_BFB1_38A4CB799A3E",
script=0xffffffff) [/opt/projects/wine/wine-git/dlls/msi/action.c:7294] in msi
(0x0186e350)
  11 0x2feb53bc ITERATE_Actions+0x15c(row=0x27f9b70, param=0x235e218)
[/opt/projects/wine/wine-git/dlls/msi/action.c:533] in msi (0x0186e3b0)
  12 0x2ff0b90e MSI_IterateRecords+0x88(view=0x2784250, count=0x0(nil),
func=0x2feb525f, param=0x235e218)
[/opt/projects/wine/wine-git/dlls/msi/msiquery.c:193] in msi (0x0186e3e0)
  13 0x2feb56e2 ACTION_ProcessExecSequence+0x19d(package=0x235e218, UIran=0)
[/opt/projects/wine/wine-git/dlls/msi/action.c:618] in msi (0x0186e420)
  14 0x2fec7965 MSI_InstallPackage+0x490(package=0x235e218,
szPackagePath="Z:\home\focht\Downloads\11.0.1\Parts\NITraceEngine\NITraceEngine.msi",
szCommandLine="ADDLOCAL="TraceEngine.LV.TRCENG.90"    
AAAAAA.WP.CORE201="C:\Program Files\National Instruments\Shared\Pipeline\Bin"
AAAAAA.WP.X64201="C:\NIDummy\Pipeline\Bin" ALLUSERSPROFILE.EWB.CORE.110="C:"
ALLUSERSPROFILE.EWB.PRO.110="C:" ALLUSERSPROFILE.EWB.PRO_LIC.110="C:"
BIN2.USI.USI64.170="C:\NIDummy\USI\Bin" CDS110DIR="C:\Program Files\National
Instruments\Circuit Design Suite 11.0" FIREFOXDIR="C:\Program Files\Mozilla
Firefox" FIREFOXPLUGINSDIR="C:\Program Files\Mozilla Firefox\Plugins"
GAC="C:" IEDIR="C:\Program Files\Internet Explorer" IEPLUGINSDIR="C:\Program
Files\Internet Explorer" INSTALLDIR.EWB.PRO_LIC.110="C:\Program Files\National
Instruments\Shared\License Manager\Licenses"
INSTALLDIR.HELPASST101="C:\Program Files\National Instruments\Shared\HelpAsst"
INSTALLDIR.HELPASST64101="C:\NIDummy\HelpAsst"
INSTALLDIR1.USI.USI64.170="C:\NIDummy\USI" IVIFOUNDATIONDIR="C:\Program
Files\IVI Foundation" LICENSES.EWB.PRO_LIC.110="C:\Program Files\National
Instruments\Shared\License Manager\Licenses"")
[/opt/projects/wine/wine-git/dlls/msi/action.c:7485] in msi (0x0186e480)
  15 0x2ff007ab
MsiInstallProductW+0xd5(szPackagePath="Z:\home\focht\Downloads\11.0.1\Parts\NITraceEngine\NITraceEngine.msi",
szCommandLine="ADDLOCAL="TraceEngine.LV.TRCENG.90"    
AAAAAA.WP.CORE201="C:\Program Files\National Instruments\Shared\Pipeline\Bin"
AAAAAA.WP.X64201="C:\NIDummy\Pipeline\Bin" ALLUSERSPROFILE.EWB.CORE.110="C:"
ALLUSERSPROFILE.EWB.PRO.110="C:" ALLUSERSPROFILE.EWB.PRO_LIC.110="C:"
BIN2.USI.USI64.170="C:\NIDummy\USI\Bin" CDS110DIR="C:\Program Files\National
Instruments\Circuit Design Suite 11.0" FIREFOXDIR="C:\Program Files\Mozilla
Firefox" FIREFOXPLUGINSDIR="C:\Program Files\Mozilla Firefox\Plugins"
GAC="C:" IEDIR="C:\Program Files\Internet Explorer" IEPLUGINSDIR="C:\Program
Files\Internet Explorer" INSTALLDIR.EWB.PRO_LIC.110="C:\Program Files\National
Instruments\Shared\License Manager\Licenses"
INSTALLDIR.HELPASST101="C:\Program Files\National Instruments\Shared\HelpAsst"
INSTALLDIR.HELPASST64101="C:\NIDummy\HelpAsst"
INSTALLDIR1.USI.USI64.170="C:\NIDummy\USI" IVIFOUNDATIONDIR="C:\Program
Files\IVI Foundation" LICENSES.EWB.PRO_LIC.110="C:\Program Files\National
Instruments\Shared\License Manager\Licenses"")
[/opt/projects/wine/wine-git/dlls/msi/msi.c:247] in msi (0x0186e4c0)
  16 0x004cb30e in setup (+0xcb30d) (0x00868830)
...
--- snip ---

Regards

[Bug 12071] MSI SQL joins on tables with many rows are extremely slow ("Nero 7 essentials", "NI Multisim 11.x" installer)

http://bugs.winehq.org/show_bug.cgi?id=12071

Anastasius Focht  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |download
                URL|                            |ftp://ftp.ni.com/evaluation
                   |                            |/EWB/NI_Circuit_Design_Suit
                   |                            |e_11_0_1.exe

--- Comment #7 from Anastasius Focht  2011-07-24 13:49:24 CDT ---
Hello,

adding download link to one of the apps for reproducing...

(needs 'winetricks -q dotnet20' prerequisite on clean WINEPREFIX)

$ sha1sum NI_Circuit_Design_Suite_11_0_1.exe 
93d1f2308f3c5f6d00401ee6fb139ea8cd287aa1  NI_Circuit_Design_Suite_11_0_1.exe

$ wine --version
wine-1.3.25-1-gdf65f3e

Regards

[Bug 12071] MSI SQL joins on tables with many rows are extremely slow ("Nero 7 essentials", "NI Multisim 11.x" installer)

http://bugs.winehq.org/show_bug.cgi?id=12071

jhgf  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |[e-mail]
         Resolution|                            |FIXED

--- Comment #8 from jhgf  2011-10-20 15:01:28 CDT ---
should be fixed by
http://source.winehq.org/git/wine.git/commit/4383aafadd296b11aecb7f53bee4c90...

[Bug 12071] MSI SQL joins on tables with many rows are extremely slow ("Nero 7 essentials", "NI Multisim 11.x" installer)

http://bugs.winehq.org/show_bug.cgi?id=12071

Anastasius Focht  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
      Fixed by SHA1|                            |4383aafadd296b11aecb7f53bee
                   |                            |4c90041c3e00c

--- Comment #9 from Anastasius Focht  2011-10-20 16:13:54 CDT ---
Hello Bernhard,

I couldn't test all mentioned apps here but the VS.NET 2005 Prof and some SDK
installers which suffered early from this problem (bug 14168) are faster now.
The "CostInitialize" action sped up significantly.
Thanks for the work!

Regards

[Bug 12071] MSI SQL joins on tables with many rows are extremely slow ("Nero 7 essentials", "NI Multisim 11.x" installer)

http://bugs.winehq.org/show_bug.cgi?id=12071

Alexandre Julliard  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |CLOSED

--- Comment #10 from Alexandre Julliard  2011-10-21 13:50:53 CDT ---
Closing bugs fixed in 1.3.31.

[Bug 12071] MSI SQL joins on tables with many rows are extremely slow ("Nero 7 essentials", "NI Multisim 11.x" installer)

http://bugs.winehq.org/show_bug.cgi?id=12071

Anastasius Focht  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |[e-mail]

--- Comment #11 from Anastasius Focht  2012-01-29 09:24:23 CST ---
*** Bug 27010 has been marked as a duplicate of this bug. ***

[Bug 12071] MSI SQL joins on tables with many rows are extremely slow ("Nero 7 essentials", "NI Multisim 11.x" installer)

[WineHQ Bugzilla]

https://bugs.winehq.org/show_bug.cgi?id=12071

Anastasius Focht  changed:

What    |Removed                     |Added
----------------------------------------------------------------------------
                URL|ftp://ftp.ni.com/evaluation |https://web.archive.org/web
                   |/EWB/NI_Circuit_Design_Suit |/20180929034647/http://down
                   |e_11_0_1.exe                |load.ni.com/evaluation/labv
                   |                            |iew/ekit/other/downloader/N
                   |                            |I_Circuit_Design_Suite_11_0
                   |                            |_2.exe

--- Comment #12 from Anastasius Focht  ---
Hello folks,

adding stable download link via Internet Archive for documentation:

https://web.archive.org/web/20180929034647/http://download.ni.com/evaluation...

$ sha1sum NI_Circuit_Design_Suite_11_0_2.exe 
8e4cb626199028d2334e19fc8bde0b7551ecfefe  NI_Circuit_Design_Suite_11_0_2.exe

$ du -sh NI_Circuit_Design_Suite_11_0_2.exe 
454M    NI_Circuit_Design_Suite_11_0_2.exe

Regards